Coherent space
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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".
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". The elements of the sets in \mathcal A are tokens. The set of tokens is |\mathcal A| = \bigcup \mathcal A = \{\alpha \mid \{\alpha\} \in \mathcal A\}.
We say that each a \in A is a coherent set of tokens. If a set X is given in advance, and the elements of \mathcal A are presented as subsets of X , then one also requires \{\alpha\} \in \mathcal A for every \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 \sim on |\mathcal A| , called coherence modulo \mathcal A , by setting \alpha \sim \beta \quad \text{if and only if} \quad \{\alpha,\beta\} \in \mathcal A.
The elements of \mathcal A are then precisely the subsets of |\mathcal A| whose elements are pairwise related by \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, \mathcal A_{\max} , then perform a down-closure: \mathcal A = \{a : \exists a' \in \mathcal A_{\max}, a' \supset a\} The only condition on \mathcal A_{\max} is that any two a, a'\in \mathcal A_{\max} , if they are distinct, then neither contains the other.
Conversely, given an undirected graph (|\mathcal A|,E) where each vertex has a self-edge, one obtains a coherence space by taking \mathcal A to be the family of all cliques of the graph: \mathcal A = \{a \subseteq |\mathcal A| \mid \forall \alpha,\beta \in a, \{\alpha,\beta\} \in E\}. That is, the elements of \mathcal A are the sets of vertices whose elements are pairwise adjacent. For a family \mathcal A \subseteq \mathcal P(|\mathcal A|) , its dual is the family \mathcal A^\perp = \{a \subseteq |\mathcal A| \mid \forall b \in \mathcal A,\ a \perp b\}.
A coherence space is a family \mathcal A \subseteq \mathcal P(|\mathcal A|) satisfying \mathcal A = (\mathcal A^\perp)^\perp. That is, it is a family that is biorthogonally closed under polarity. A stable function is defined as a function mapping cliques to cliques: f : \mathcal A \to \mathcal B such that it is continuous: If \{a_i\}_i \subset \mathcal A is a directed family, then f(\cup_i a_i) = \cup_i f(a_i) . stable: If a, a' \in \mathcal A such that a \cup a' \in \mathcal A , then f(a \cap a') = f(a) \cap f(a') .
By stability, if a \subset a' \in \mathcal A then f(a) \subset f(a') , so f is monotonic. By stability, f(a) = \cup_{a' \subset a, a'\text{ is finite}} f(a') . So it shows that f is determined by its value on finite coherent sets. For continuity, considering the special case where \{a_i\}_i \subset \mathcal A is the empty set, we have f(\emptyset) = \emptyset .
Given a stable function, its trace Tr(f) \subset \mathcal A \times |\mathcal B| is defined as Tr(f) := \{(a, \beta) | a \in \mathcal A, \beta \in f(a) , (\forall a' \subsetneq a, \beta\not\in f(a'))\} That is, each (a, \beta) \in Tr(f) is such that a is a minimal coherent set needed to produce token \beta . By stability, any (a, \beta) \in Tr(f) must have a finite a .
Conversely, each stable function is determined by its trace: f(a) = \{\beta : (a', \beta) \in Tr(f), a' \subset a\} Given two coherent spaces \mathcal A, \mathcal B , there is a coherent space \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: |\mathcal A\& \mathcal B| = |\mathcal A| + |\mathcal B| and the edges of \mathcal A\& \mathcal B is the union of the edges in \mathcal A , the edges in \mathcal B , and \{\{\alpha, \beta\}: \alpha \in \mathcal A, \beta \in \mathcal B\} . More generally, given a family of coherent spaces, \{\mathcal A_i\}_{i\in I} , we can define \&_{i \in I} \mathcal A_i similarly. Given two coherent spaces \mathcal A, \mathcal B , there is a coherent space \mathcal A \sqcup \mathcal B .
The set of tokens is still |\mathcal A\sqcup \mathcal B| = |\mathcal A| + |\mathcal B| and the edges of \mathcal A\sqcup \mathcal B is the union of the edges in \mathcal A , the edges in \mathcal B . This is the coproduct. This can be defined in general for a family of coherent spaces, \{\mathcal A_i\}_{i\in I} . Now, define \mathcal X, \mathcal Y to be the discrete/minimal coherent spaces.
Then f : \mathcal X \to \mathcal Y is a stable function iff there is a partial function f': X \to Y , such that f(\{x\}) = \begin{cases} \{f'(x)\} &\text{ if }f'(x) \text{ is defined,}\\ \emptyset &\text{ else} \end{cases} and f' can be identified with its set of traits, which is a coherent set in \&_{x\in X}\mathcal Y_x . Thus, \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 \Rightarrow: \mathbf{Coh}^2 \to \mathbf{Coh} , contravariant in the first argument and covariant in the second argument, such that \mathrm{Hom}_{\mathbf{Coh}}(\mathcal A , \mathcal B) \simeq \mathcal A \Rightarrow \mathcal B That is, given any two coherent spaces \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 |\mathcal A \Rightarrow \mathcal B| is \mathcal A_{\text{fin}} \times |\mathcal B| , where \mathcal A_{\text{fin}} is the set of nonempty finite coherent sets in \mathcal A . Two tokens (a, \beta), (a', \beta') are coherent iff If a \cup a' \in \mathcal A , then \{\beta, \beta'\}\in \mathcal B . If a \cup a' \in \mathcal A and a \neq a' , then \beta \neq \beta' . Note that, if a \cup a'\not\in \mathcal A , then (a, \beta), (a', \beta') for any \beta, \beta' \in |\mathcal B| .
That is, we only demand coherence in \mathcal B given coherence in \mathcal A . If there is no coherence in \mathcal A , then we make no demands on coherence in \mathcal B . Coherence spaces can act as an interpretation for types in type theory where points of a type \mathcal A are points of the coherence space \mathcal A . This allows for some structure to be discussed on types. For instance, each term a of a type \mathcal A can be given a set of finite approximations I which is in fact, a directed set with the subset relation.
With a being a coherent subset of the token space |\mathcal A| (i.e. an element of \mathcal A ), any element of I is a finite subset of a and therefore also coherent, and we have a = \bigcup a_i, a_i \in I. It is continuous (categorically, preserves filtered colimits): F(\bigcup_{i\in I}^{\uparrow}a_i)= \bigcup_{i\in I}^\uparrow F(a_i) where \bigcup_{i\in I}^\uparrow is the directed union over I , the set of finite approximants of a . It is stable: 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: 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 \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: | \mathcal A \ \&\ \mathcal B| = |\mathcal A| + |\mathcal B| = (\{1\} \times |\mathcal A|) \cup (\{2\} \times |\mathcal B|) (i.e. the set of tokens of \mathcal A \ \&\ \mathcal B is the coproduct (or disjoint union) of the token sets of \mathcal A and \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.
(1, \alpha) \sim_{\mathcal A\ \&\ \mathcal B} (1, \alpha') \iff \alpha \sim_{\mathcal A} \alpha' (2, \beta) \sim_{\mathcal A\ \&\ \mathcal B} (2, \beta') \iff \beta \sim_{\mathcal B} \beta' (1, \alpha) \sim_{\mathcal A\ \&\ \mathcal B} (2, \beta), \forall \alpha \in |\mathcal A|, \beta \in |\mathcal B|
References
. .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1361256878 under CC BY-SA 4.0; modifications have been made.