↑ arvau

Wikipedia / 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".

Definitions

There are several equivalent definitions of a coherent space.

As a family of subsets

The original definition by Jean-Yves Girard is a family of sets, satisfying the following closure conditions:

  • Down-closure.

  • Binary completeness.

are tokens is a coherent set of tokens. This intuitively states that any token is coherent at least to itself.

Given such a family, one obtains a reflexive, symmetric, called coherence modulo.

As a family of maximally coherent subsets

The coherent sets are partially ordered under inclusion. By binary completeness and Zorn's lemma, if they are distinct, then neither contains the other.

As an undirected graph

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

, its associated graph, called the web. Note that we require each vertex to have a self-edge purely as a convenient convention.

to be the family of all cliques are the sets of vertices whose elements are pairwise adjacent.

As a biorthogonally closed family

be a set are said to be orthogonal, (or polar is either empty or a singleton.

, its dualThat is, it is a family that is biorthogonally closed under polarity.

Stable functions

The coherent spaces make up a category is a stable function.

Definition

such that it is

is monotonic.

is determined by its value on finite coherent sets.

is the empty set.

Trace

.

Linearity

is linear 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.

Examples

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.

Categorical constructions

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

is still a coherent space. This is a dual object construction in category theory.

.

(pronounced "A and B"). It is defined as a graph. The set of tokens is the disjoint union similarly.

. This is the coproduct.

Coherent space of stable functions

is the coherent space that we constructed.

This can be intuitively understood as follows: a partial function. A maximally coherent set is the set of traits of a total function. As we enumerate is computed by a Turing machine 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.

is a coherent space.

, the hom-set between them is structured as a coherent space as well. This makes the category enriched over itself.

are coherent iff

  • .

  • .

.

Coherence spaces as types

Coherence spaces can act as an interpretation for types in type theory which is in fact, a directed set

Stable functions

Functions are seen as stable is a stable function when

  1. It is monotone with respect to the subset order (respects approximation, categorically, is a functor over the poset

  2. It is continuous (categorically, preserves filtered colimits is the directed union.

  3. It is stable Categorically, this means that it preserves the pullback:

Product space

which would mean that in addition to stability in each argument alone, the pullback 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:

Tokens from differents sets are always coherent and tokens from the same set are coherent exactly when they are coherent in that set.

References

  • .

  • .