Coherent space

In proof theory, a coherent space (also coherence space) is a concept introduced in the semantic study of linear logic.

In Proofs and Types, coherent spaces are called coherence spaces. A footnote explains that although in the French original they were "espaces cohérents", the translation used "coherence space", because spectral spaces are sometimes called "coherent spaces".

There are several equivalent definitions of a coherent space.

The original definition by Jean-Yves Girard is a family of sets ${\displaystyle {\mathcal {A}}}$, satisfying the following closure conditions:

• Down-closure: if ${\displaystyle a\in {\mathcal {A}}}$ and ${\displaystyle a'\subseteq a}$, then ${\displaystyle a'\in {\mathcal {A}}}$.
• Binary completeness: for every ${\displaystyle M\subseteq {\mathcal {A}}}$, if ${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}}$ for all ${\displaystyle a_{1},a_{2}\in M}$, then ${\displaystyle \bigcup M\in {\mathcal {A}}}$.

The elements of the sets in ${\displaystyle {\mathcal {A}}}$ are tokens. The set of tokens is$${\displaystyle |{\mathcal {A}}|=\bigcup {\mathcal {A}}=\{\alpha \mid \{\alpha \}\in {\mathcal {A}}\}.}$$We say that each ${\displaystyle a\in A}$ is a coherent set of tokens. If a set ${\displaystyle X}$ is given in advance, and the elements of ${\displaystyle {\mathcal {A}}}$ are presented as subsets of ${\displaystyle X}$, then one also requires ${\displaystyle \{\alpha \}\in {\mathcal {A}}}$ for every ${\displaystyle \alpha \in X}$. This intuitively states that any token is coherent at least to itself.

Given such a family, one obtains a reflexive, symmetric relation ${\displaystyle \sim }$ on ${\displaystyle |{\mathcal {A}}|}$, called coherence modulo ${\displaystyle {\mathcal {A}}}$, by setting$${\displaystyle \alpha \sim \beta \quad {\text{if and only if}}\quad \{\alpha ,\beta \}\in {\mathcal {A}}.}$$The elements of ${\displaystyle {\mathcal {A}}}$ are then precisely the subsets of ${\displaystyle |{\mathcal {A}}|}$ whose elements are pairwise related by ${\displaystyle \sim }$.

The coherent sets are partially ordered under inclusion. By binary completeness and Zorn's lemma, any coherent set is contained in a maximally coherent set. Consequently, it is only necessary to specify the maximally coherent sets, ${\displaystyle {\mathcal {A}}_{\max }}$, then perform a down-closure:$${\displaystyle {\mathcal {A}}=\{a:\exists a'\in {\mathcal {A}}_{\max },a'\supset a\}}$$The only condition on ${\displaystyle {\mathcal {A}}_{\max }}$ is that any two ${\displaystyle a,a'\in {\mathcal {A}}_{\max }}$, if they are distinct, then neither contains the other.

Coherence spaces are in bijection with undirected graphs whose vertices are tokens.

Given a coherence space ${\displaystyle {\mathcal {A}}}$, its associated graph, called the web of ${\displaystyle {\mathcal {A}}}$, has vertex set ${\displaystyle |{\mathcal {A}}|}$. Its edges are the unordered pairs ${\displaystyle \{\alpha ,\beta \}}$ such that ${\displaystyle \alpha \sim \beta }$. Note that we require each vertex to have a self-edge purely as a convenient convention.

Conversely, given an undirected graph ${\displaystyle (|{\mathcal {A}}|,E)}$ where each vertex has a self-edge, one obtains a coherence space by taking ${\displaystyle {\mathcal {A}}}$ to be the family of all cliques of the graph:$${\displaystyle {\mathcal {A}}=\{a\subseteq |{\mathcal {A}}|\mid \forall \alpha ,\beta \in a,\{\alpha ,\beta \}\in E\}.}$$That is, the elements of ${\displaystyle {\mathcal {A}}}$ are the sets of vertices whose elements are pairwise adjacent.

Let ${\displaystyle |{\mathcal {A}}|}$ be a set of tokens. Two subsets ${\displaystyle a,b\subseteq |{\mathcal {A}}|}$ are said to be orthogonal, (or polar), if ${\displaystyle a\cap b}$ is either empty or a singleton. We write this as ${\displaystyle a\perp b}$.

For a family ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {P}}(|{\mathcal {A}}|)}$, its dual is the family$${\displaystyle {\mathcal {A}}^{\perp }=\{a\subseteq |{\mathcal {A}}|\mid \forall b\in {\mathcal {A}},\ a\perp b\}.}$$A coherence space is a family ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {P}}(|{\mathcal {A}}|)}$ satisfying$${\displaystyle {\mathcal {A}}=({\mathcal {A}}^{\perp })^{\perp }.}$$That is, it is a family that is biorthogonally closed under polarity.

The coherent spaces make up a category ${\displaystyle \mathbf {Coh} }$. Each object is a coherent space, and each morphism ${\displaystyle f:{\mathcal {A}}\to {\mathcal {B}}}$ is a stable function.

A stable function is defined as a function mapping cliques to cliques:$${\displaystyle f:{\mathcal {A}}\to {\mathcal {B}}}$$such that it is

• continuous: If ${\displaystyle \{a_{i}\}_{i}\subset {\mathcal {A}}}$ is a directed family, then ${\displaystyle f(\cup _{i}a_{i})=\cup _{i}f(a_{i})}$.
• stable: If ${\displaystyle a,a'\in {\mathcal {A}}}$ such that ${\displaystyle a\cup a'\in {\mathcal {A}}}$, then ${\displaystyle f(a\cap a')=f(a)\cap f(a')}$.

By stability, if ${\displaystyle a\subset a'\in {\mathcal {A}}}$ then ${\displaystyle f(a)\subset f(a')}$, so ${\displaystyle f}$ is monotonic.

By stability, ${\displaystyle f(a)=\cup _{a'\subset a,a'{\text{ is finite}}}f(a')}$. So it shows that ${\displaystyle f}$ is determined by its value on finite coherent sets.

For continuity, considering the special case where ${\displaystyle \{a_{i}\}_{i}\subset {\mathcal {A}}}$ is the empty set, we have ${\displaystyle f(\emptyset )=\emptyset }$.

Given a stable function, its trace ${\displaystyle Tr(f)\subset {\mathcal {A}}\times |{\mathcal {B}}|}$ is defined as$${\displaystyle Tr(f):=\{(a,\beta )|a\in {\mathcal {A}},\beta \in f(a),(\forall a'\subsetneq a,\beta \not \in f(a'))\}}$$That is, each ${\displaystyle (a,\beta )\in Tr(f)}$ is such that ${\displaystyle a}$ is a minimal coherent set needed to produce token ${\displaystyle \beta }$. By stability, any ${\displaystyle (a,\beta )\in Tr(f)}$ must have a finite ${\displaystyle a}$.

Conversely, each stable function is determined by its trace:$${\displaystyle f(a)=\{\beta :(a',\beta )\in Tr(f),a'\subset a\}}$$

A stable function ${\displaystyle f}$ is linear iff any ${\displaystyle (a,\beta )\in Tr(f)}$, ${\displaystyle a}$ has just one element. This was the original motivation for linear logic.

Linear stable functions are particularly simple and can be thought of as a clique-valued function ${\displaystyle f:|{\mathcal {A}}|\to {\mathcal {B}}}$ such that given a clique ${\displaystyle a\in {\mathcal {A}}}$, ${\displaystyle \cup _{\alpha \in a}f(\alpha )}$ is still a clique in ${\displaystyle {\mathcal {B}}}$.

The intuition of a coherent space is that each token is a trait that an object might possess, and a coherent set of tokens is a set of traits that is possessed by some object simultaneously. There is no object that can possess an incoherent set of tokens as its traits. One explores an object by observing more and more of its traits. The set of observed traits grows, but will always remain coherent.

Any coherent space can be specified by its maximally coherent sets. Any union of two distinct maximally coherent sets is incoherent.

Given a coherent space ${\displaystyle {\mathcal {A}}}$, its polar ${\displaystyle {\mathcal {A}}^{\perp }}$ is still a coherent space. This is a dual object construction in category theory.

Given any set ${\displaystyle X}$, we have the discrete/minimal coherent space ${\displaystyle \{\{\alpha \}:\alpha \in X\}}$, and the indiscrete/maximal coherent space ${\displaystyle {\mathcal {P}}(X)}$.

Given two coherent spaces ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, there is a coherent space ${\displaystyle {\mathcal {A}}\&{\mathcal {B}}}$ (pronounced "A and B"). It is defined as a graph. The set of tokens is the disjoint union of the two sets of tokens:$${\displaystyle |{\mathcal {A}}\&{\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|}$$and the edges of ${\displaystyle {\mathcal {A}}\&{\mathcal {B}}}$ is the union of the edges in ${\displaystyle {\mathcal {A}}}$, the edges in ${\displaystyle {\mathcal {B}}}$, and ${\displaystyle \{\{\alpha ,\beta \}:\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}\}}$. More generally, given a family of coherent spaces, ${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$, we can define ${\displaystyle \&_{i\in I}{\mathcal {A}}_{i}}$ similarly.

Given two coherent spaces ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, there is a coherent space ${\displaystyle {\mathcal {A}}\sqcup {\mathcal {B}}}$. The set of tokens is still$${\displaystyle |{\mathcal {A}}\sqcup {\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|}$$ and the edges of ${\displaystyle {\mathcal {A}}\sqcup {\mathcal {B}}}$ is the union of the edges in ${\displaystyle {\mathcal {A}}}$, the edges in ${\displaystyle {\mathcal {B}}}$. This is the coproduct. This can be defined in general for a family of coherent spaces, ${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$.

Given two sets ${\displaystyle X,Y}$, the set of partial functions of type ${\displaystyle X\to Y}$ can be modelled by a coherent space. The token set is ${\displaystyle X\times Y}$, and the edges are ${\displaystyle \{(x,y),(x',y')\}}$ for all ${\displaystyle x\neq x'}$. Equivalently, for each ${\displaystyle x\in X}$, define ${\displaystyle {\mathcal {Y}}_{x}}$ to be the discrete/minimal coherent space of ${\displaystyle Y}$. Then ${\displaystyle \&_{x\in X}{\mathcal {Y}}_{x}}$ is the coherent space that we constructed.

This can be intuitively understood as follows: a partial function ${\displaystyle f:X\to Y}$ has the set of traits ${\displaystyle \{(x,f(x)):x\in X\land f(x){\text{ is defined}}\}}$. A maximally coherent set is the set of traits of a total function. As we enumerate the values of a partial function, we enumerate the set of traits, which is coherent at every step. This is useful when ${\displaystyle f}$ is computed by a Turing machine that might fail to halt on some entries. If ${\displaystyle f(x)}$ does not halt, then we simply never observe the trait during trait-enumeration. The set of observed traits will remain coherent at all steps of our enumeration.

Now, define ${\displaystyle {\mathcal {X}},{\mathcal {Y}}}$ to be the discrete/minimal coherent spaces. Then ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$ is a stable function iff there is a partial function ${\displaystyle f':X\to Y}$, such that$${\displaystyle f(\{x\})={\begin{cases}\{f'(x)\}&{\text{ if }}f'(x){\text{ is defined,}}\\\emptyset &{\text{ else}}\end{cases}}}$$and ${\displaystyle f'}$ can be identified with its set of traits, which is a coherent set in ${\displaystyle \&_{x\in X}{\mathcal {Y}}_{x}}$. Thus, ${\displaystyle \mathrm {Hom} _{\mathbf {Coh} }({\mathcal {X}},{\mathcal {Y}})\simeq \&_{x\in X}{\mathcal {Y}}_{x}}$ is a coherent space.

In general, we have a functor ${\displaystyle \Rightarrow :\mathbf {Coh} ^{2}\to \mathbf {Coh} }$, contravariant in the first argument and covariant in the second argument, such that$${\displaystyle \mathrm {Hom} _{\mathbf {Coh} }({\mathcal {A}},{\mathcal {B}})\simeq {\mathcal {A}}\Rightarrow {\mathcal {B}}}$$That is, given any two coherent spaces ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, the hom-set between them is structured as a coherent space as well. This makes the category enriched over itself.

The token set ${\displaystyle |{\mathcal {A}}\Rightarrow {\mathcal {B}}|}$ is ${\displaystyle {\mathcal {A}}_{\text{fin}}\times |{\mathcal {B}}|}$, where ${\displaystyle {\mathcal {A}}_{\text{fin}}}$ is the set of nonempty finite coherent sets in ${\displaystyle {\mathcal {A}}}$. Two tokens ${\displaystyle (a,\beta ),(a',\beta ')}$ are coherent iff

• If ${\displaystyle a\cup a'\in {\mathcal {A}}}$, then ${\displaystyle \{\beta ,\beta '\}\in {\mathcal {B}}}$.
• If ${\displaystyle a\cup a'\in {\mathcal {A}}}$ and ${\displaystyle a\neq a'}$, then ${\displaystyle \beta \neq \beta '}$.

Note that, if ${\displaystyle a\cup a'\not \in {\mathcal {A}}}$, then ${\displaystyle (a,\beta ),(a',\beta ')}$ for any ${\displaystyle \beta ,\beta '\in |{\mathcal {B}}|}$. That is, we only demand coherence in ${\displaystyle {\mathcal {B}}}$ given coherence in ${\displaystyle {\mathcal {A}}}$. If there is no coherence in ${\displaystyle {\mathcal {A}}}$, then we make no demands on coherence in ${\displaystyle {\mathcal {B}}}$.

Coherence spaces can act as an interpretation for types in type theory where points of a type ${\displaystyle {\mathcal {A}}}$ are points of the coherence space ${\displaystyle {\mathcal {A}}}$. This allows for some structure to be discussed on types. For instance, each term ${\displaystyle a}$ of a type ${\displaystyle {\mathcal {A}}}$ can be given a set of finite approximations ${\displaystyle I}$ which is in fact, a directed set with the subset relation. With ${\displaystyle a}$ being a coherent subset of the token space ${\displaystyle |{\mathcal {A}}|}$ (i.e. an element of ${\displaystyle {\mathcal {A}}}$), any element of ${\displaystyle I}$ is a finite subset of ${\displaystyle a}$ and therefore also coherent, and we have ${\displaystyle a=\bigcup a_{i},a_{i}\in I.}$

Functions between types ${\displaystyle {\mathcal {A}}\to {\mathcal {B}}}$ are seen as stable functions between coherence spaces. A stable function is defined to be one which respects approximants and satisfies a certain stability axiom. Formally, ${\displaystyle F:{\mathcal {A}}\to {\mathcal {B}}}$ is a stable function when

1. It is monotone with respect to the subset order (respects approximation, categorically, is a functor over the poset ${\displaystyle {\mathcal {A}}}$): ${\displaystyle a'\subset a\in {\mathcal {A}}\implies F(a')\subset F(a).}$
2. It is continuous (categorically, preserves filtered colimits): ${\textstyle F(\bigcup _{i\in I}^{\uparrow }a_{i})=\bigcup _{i\in I}^{\uparrow }F(a_{i})}$ where ${\textstyle \bigcup _{i\in I}^{\uparrow }}$ is the directed union over ${\displaystyle I}$, the set of finite approximants of ${\displaystyle a}$.
3. It is stable: ${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}\implies F(a_{1}\cap a_{2})=F(a_{1})\cap F(a_{2}).}$ Categorically, this means that it preserves the pullback:

   

In order to be considered stable, functions of two arguments must satisfy the criterion 3 above in this form: $${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}\land b_{1}\cup b_{2}\in {\mathcal {B}}\implies F(a_{1}\cap a_{2},b_{1}\cap b_{2})=F(a_{1},b_{1})\cap F(a_{2},b_{2})}$$which would mean that in addition to stability in each argument alone, the pullback

is preserved with stable functions of two arguments. This leads to the definition of a product space ${\displaystyle {\mathcal {A}}\ \&\ {\mathcal {B}}}$ which makes a bijection between stable binary functions (functions of two arguments) and stable unary functions (one argument) over the product space. The product coherence space is a product in the categorical sense i.e. it satisfies the universal property for products. It is defined by the equations:

• ${\displaystyle |{\mathcal {A}}\ \&\ {\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|=(\{1\}\times |{\mathcal {A}}|)\cup (\{2\}\times |{\mathcal {B}}|)}$ (i.e. the set of tokens of ${\displaystyle {\mathcal {A}}\ \&\ {\mathcal {B}}}$ is the coproduct (or disjoint union) of the token sets of ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$.
• Tokens from differents sets are always coherent and tokens from the same set are coherent exactly when they are coherent in that set.
  • ${\displaystyle (1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(1,\alpha ')\iff \alpha \sim _{\mathcal {A}}\alpha '}$
  • ${\displaystyle (2,\beta )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(2,\beta ')\iff \beta \sim _{\mathcal {B}}\beta '}$
  • ${\displaystyle (1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(2,\beta ),\forall \alpha \in |{\mathcal {A}}|,\beta \in |{\mathcal {B}}|}$

• Girard, J.-Y.; Lafont, Y.; Taylor, P. (1989), Proofs and types (PDF), Cambridge University Press.
• Girard, J.-Y. (2004), "Between logic and quantic: a tract", in Ehrhard; Girard; Ruet; et al. (eds.), Linear logic in computer science (PDF), Cambridge University Press.
• Girard, Jean-Yves (1986-01-01). "The system F of variable types, fifteen years later". Theoretical Computer Science. 45: 159–192. doi:10.1016/0304-3975(86)90044-7. ISSN 0304-3975.