Jump to content

Coherent space

From Wikipedia, the free encyclopedia

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

Let a set C be given. Two subsets S,TC are said to be orthogonal, written ST, if ST is ∅ or a singleton. The dual of a family F ⊆ ℘(C) is the family F of all subsets SC orthogonal to every member of F, i.e., such that ST for all TF. A coherent space F over C is a family of C-subsets for which F = (F ) .

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 coherence space translation was used because spectral spaces are sometimes called coherent spaces.

Definitions

[edit]

As defined by Jean-Yves Girard, a coherence space is a collection of sets satisfying down-closure and binary completeness in the following sense:

  • Down-closure: all subsets of a set in remain in :
  • Binary completeness: for any subset of , if the pairwise union of any of its elements is in , then so is the union of all the elements of :

The elements of the sets in are known as tokens, and they are the elements of the set .

Coherence spaces correspond one-to-one with (undirected) graphs (in the sense of a bijection from the set of coherence spaces to that of undirected graphs). The graph corresponding to is called the web of and is the graph induced a reflexive, symmetric relation over the token space of known as coherence modulo defined as:In the web of , nodes are tokens from and an edge is shared between nodes and when (i.e. .) This graph is unique for each coherence space, and in particular, elements of are exactly the cliques of the web of i.e. the sets of nodes whose elements are pairwise adjacent (share an edge.)

Coherence spaces as types

[edit]

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

Stable functions

[edit]

Functions between types 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, 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): where is the directed union over , the set of finite approximants of .
  3. It is stable: Categorically, this means that it preserves the pullback:
    Commutative diagram of the pullback preserved by stable functions

Product space

[edit]

In order to be considered stable, functions of two arguments must satisfy the criterion 3 above in this form: 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 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:

  • (i.e. the set of tokens of is the coproduct (or disjoint union) of the token sets of and .
  • Tokens from differents sets are always coherent and tokens from the same set are coherent exactly when they are coherent in that set.

References

[edit]
  • 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.