Coherent semantics

Revision as of 13:52, 22 February 2009

Coherent semantics was invented by Girard in the paper The system F, 15 years later^[1]with the objective of building a denotationnal interpretation of second order intuitionnistic logic (aka polymorphic lambda-calculus).

Coherent semantics is based on the notion of stable functions that was initially proposed by Gérard Berry. Stability is a condition on Scott continuous functions that expresses the determinism of the relation between the output and the input: the typical Scott continuous but non stable function is the parallel or because when the two inputs are both set to true, only one of them is the reason why the result is true but there is no way to determine which one.

A further achievement of coherent semantics was that it allowed to endow the set of stable functions from $X$ to $Y$ with a structure of domain, thus closing the category of coherent spaces and stable functions. However the most interesting point was the discovery of a special class of stable functions, linear functions, which was the first step leading to Linear Logic.

The cartesian closed structure of coherent semantics

There are three equivalent definitions of coherent spaces: the first one, coherent spaces as domains, is interesting from a historical point of view as it emphazises the fact that coherent spaces are particular cases of Scott domains. The second one, coherent spaces as graphs, is the most commonly used and will be our "official" definition in the sequel. The last one, cliqued spaces a particular example of a more general scheme that one could call "linear logical relations" in reference to logical relations; this scheme is underlying lots of constructions in linear logic such as phase semantics or the proof of strong normalisation for proof-nets.

Coherent spaces

As domains

Definition (Coherent space)

A coherent space $X$ is a family of subsets of a given set $\web X$ (the web of $X$ ), which satisfies:

subset closure: if $x\subset y\in X$ then $x\in X$ ,
singletons: $\{a\}\in X$ for $a\in\web X$ .
binary compatibility: if $A$ is a family of pairwise compatible elements of $X$ , that is if $x\cup y\in X$ for any $x,y\in A$ , then $\bigcup A\in X$ .

A coherent space is thus ordered by inclusion; one easily checks that it is a domain. In particular finite elements of $X$ correspond to compact elements.

As graphs

Definition (Coherent space)

A coherent space $X$ is a family of subsets of a given set $\web X$ (the web of $X$ ) which satisfies that there is a reflexive and symetric relation $\coh_X$ on $\web X$ (the coherence relation) such that $x\in X$ iff $\forall a,b\in x,\, a\coh_X b$ , for any $x\subset\web X$ . In other terms $X$ is the set of complete subgraphs of the simple unoriented graph of the $\coh_X$ relation. For this reason, the elements of $X$ are called cliques.

The strict coherence relation $\scoh_X$ on $X$ is defined by: $a\scoh_X b$ iff $a\neq b$ and $a\coh_X b$ .

A coherent space in the domain sense is seen to be a coherent space in the graph sense by setting $a\coh_X b$ iff $\{a,b\}\in X$ ; conversely one easily checks that cliques in the graph sense are subset closed and satisfy the binary compatibility condition.

A coherent space is completely determined by its web and its coherence relation, or equivalently by its web and its strict coherence.

Cliqued space

Definition (Duality)

Let $x$ and $y$ be two sets. We will say that they are dual, written $x\bot y$ if their intersection contains at most one element: $\mathrm{Card}(x\cap y)\leq 1$ .

Let $T$ be a set and $X$ be a family of subsets of $T$ . We define the dual of $X$ to be the collection of subsets of $T$ that are dual to all elements of $X$ : $X^\bot = \{y\subset T$ s.t. for any $x\in X,\, y\perp x\}$

Given a such a collection $X$ of subsets of $T$ one sees that we have $X\subset (X^\bot)^\bot$ . The reverse inclusion is not true in general, however it holds in the case where $X=Y^\bot$ for some collection $Y$ of subsets of $T$ . In other terms we always have $((X^\bot)^\bot)^\bot = X^\bot$ .

From now on we will denote $X^{\bot\bot} = (X^\bot)^\bot$ .

Definition (Cliqued space)

A cliqued space $X$ is a family of subsets of a given set $\web X$ such that $X^{\bot\bot} = X$ .

Let $X$ be a cliqued space and define a relation on $\web X$ by setting $a\coh_X b$ iff there is $x\in X$ such that $a, b\in x$ . This relation is obviously symetric; it is also reflexive because all singletons belong to $X$ : if $a\in \web X$ then ${a}$ is dual to any element of $X^\bot$ (actually ${a}$ is dual to any subset of $\web X$ ), thus ${a}$ is in $X^{\bot\bot}$ , thus in $X$ .

Let $a\coh_X b$ . Then $\{a,b\}\in X$ ; indeed there is an $x\in X$ such that $a, b\in x$ . This $x$ is dual to any $y\in X^\bot$ , that is meets any $y\in X^\bot$ in a most one point. Since $\{a,b\}\subset x$ this is also true of ${a, b}$ , so that ${a, b}$ is in $X^{\bot\bot}$ thus in $X$ . Now let $x$ be a clique for $\coh_X$ and $y$ be an element of $X^\bot$ . Suppose $a, b\in x\cap y$ , then since $a$ and $b$ are coherent (by hypothesis on $x$ ) we have $\{a,b\}\in X$ and since $y\in X^\bot$ we must have that ${a, b}$ and $y$ meet in at most one point. Thus $a = b$ and we have shown that $x$ and $y$ are dual. Since $y$ was arbitrary this means that $x$ is in $X^{\bot\bot}$ , thus in $X$ . Finally we get that any clique of $X$ is in $X$ . Conversely any $x\in X$ is obviously a clique so eventually we get that $X$ is a coherent space in the graph sense.

Conversely given a coherent space $X$ in the graph sense, one can check that it is a cliqued space. Call anticlique a set $y\subset \web X$ of pairwise incoherent points: for all $a, b$ in $y$ , if $a\coh_X b$ then $a = b$ . Any anticlique intersects any clique in at most one point: let $x$ be a clique and $y$ be an anticlique, then if $a,b\in x\cap y$ , since $a, b\in x$ we have $a\coh_X b$ and since $y$ is an anticlique we have $a = b$ .

Thus the collection of anticliques of $X$ is the dual $X^\bot$ of $X$ . Note that the incoherence relation defined above is reflexive and symetric, so that $X^\bot$ is a coherent space in the graph sense. Thus we can do for $X^\bot$ exactly what we've just done for $X$ and consider the anti-anticliques, that is the anticliques for the incoherent relation which are the cliques for the in-incoherent relation. It is not difficult to see that this in-incoherence relation is just the coherence relation we started with; we thus obtain that $X^{\bot\bot} = X$ , so that $X$ is a cliqued space.

Stable functions

Definition (Stable function)

Let $X$ and $Y$ be two coherent spaces. A function $F:X\mapsto Y$ is stable if it satisfies:

it is non decreasing: for any $x,y\in X$ if $x\subset y$ then $F(x)\subset F(y)$ ;
it is continuous (in the Scott sense): if $A$ is a directed family of cliques of $X$ , that is if for any $x,y\in A$ there is a $z\in A$ such that $x\cup y\subset z$ , then $\bigcup_{x\in A}F(x) = F(\bigcup A)$ ;
it satisfies the stability condition: if $x,y\in X$ are compatible, that is if $x\cup y\in X$ , then $F(x\cap y) = F(x)\cap F(y)$ .

This definition is admitedly not very tractable. An equivalent and most useful caracterisation of stable functions is given by the following theorem.

Theorem

Let $F:X\mapsto Y$ be a non-decreasing function from the coherent space $X$ to the coherent space $Y$ . The function $F$ is stable iff it satisfies: for any $x\in X$ , $b\in\web Y$ , if $b\in F(x)$ then there is a finite clique $x_0\subset x$ such that:

$b\in F(x_0)$ ,
for any $y\subset x$ if $b\in F(y)$ then $x_0\subset y$ ( $x 0$ is the minimum sub-clique of $x$ such that $b\in F(x_0)$ ).

Note that the stability condition doesn't depend on the coherent space structure and can be expressed more generally for continuous functions on domains. However, as mentionned in the introduction, the restriction to coherent spaces allows to endow the set of stable functions from $X$ to $Y$ with a structure of coherent space.

Definition (The space of stable functions)

Let $X$ and $Y$ be coherent spaces. The function space $X\rightarrow Y$ is defined by:

$\web{X\rightarrow Y} = \mathcal{C}_{\mathrm{fin}}(X)\times \web Y$ ,
$(x_0, a)\coh_{X\rightarrow Y}(y_0, b)$ iff $\begin{cases}\text{if } x_0\cup y_0\in X\text{ then } a\coh_Y b,\\ \text{if } x_0\cup y_0\in X\text{ and } a = b\text{ then } x_0 = y_0\end{cases}$ .

One could equivalently define the strict coherence relation on $X\rightarrow Y$ by: $(x_0,a)\scoh_{X\rightarrow Y}(y_0, b)$ iff $x_0\cup y_0\in X$ and $x_0\neq y_0$ entails that $a\scoh_Y b$ .

Definition (Trace of a stable function)

Let $F:X\mapsto Y$ be a function. The trace of $F$ is the set:

$Tr(F) = {(x 0, b), x 0$ minimal such that $b\in F(x_0)\}$ .

Theorem

$F$ is stable iff $Tr(F)$ is a clique of the function space $X\rightarrow Y$

In particular the continuity of $F$ entails that if $x 0$ is minimal such that $b\in F(x_0)$ , then $x 0$ is finite.

Definition (The evaluation function)

Let $f$ be a clique in $X\rightarrow Y$ . We define a function $\mathrm{Fun}\,f:X\mapsto Y$ by: $\mathrm{Fun}\,f(x) = \{b\in Y,$ there is $x_0\subset x$ such that $(x_0, b)\in f\}$ .

Theorem (Closure)

If $f$ is a clique of the function space $X\rightarrow Y$ then we have $\mathrm{Tr}(\mathrm{Fun}\,f) = f$ . Conversely if $F:X\mapsto Y$ is a stable function then we have $F = \mathrm{Fun}\,\mathrm{Tr}(F)$ .

Cartesian product

Definition (Cartesian product)

Let $X 1$ and $X 2$ be two coherent spaces. Their cartesian products $X_1\with X_2$ is the coherent space defined by:

the web is the disjoint union of the webs: $\web{X_1\with X_2} = \{1\}\times\web{X_1}\cup \{2\}\times\web{X_2}$ ;
the coherence relation is the serie composition of the relations on $X 1$ and $X 2$ : $(i, a)\coh_{X_1\with X_2}(j, b)$ iff $i\neq j$ or $i = j$ and $a\coh_{X_i} b$ .

This definition is just the way to put a coherent space structure on the cartesian product. Indeed one easily shows the

Theorem

Given cliques $x 1$ and $x 2$ in $X 1$ and $X 2$ , we define the subset $\langle x_1, x_2\rangle$ of $\web{X_1\with X_2}$ by: $\langle x_1, x_2\rangle = \{1\}\times x_1\cup \{2\}\times x_2$ . Then $\langle x_1, x_2\rangle$ is a clique in $X_1\with X_2$ .

Conversely, given a clique $x\in X_1\with X_2$ , for $i = 1,2$ we define $\pi_i(x) = \{a\in X_i, (i, a)\in x\}$ . Then $π i (x)$ is a clique in $X i$ and the function $\pi_i:X_1\with X_2\mapsto X_i$ is stable.

Furthemore these two operations are inverse of each other: $\pi_i(\langle x_1, x_2\rangle) = x_i$ and $\langle\pi_1(x), \pi_2(x)\rangle = x$ . In particular any clique in $X_1\with X_2$ is of the form $\langle x_1, x_2\rangle$ .

Altogether the results above (and a few other more that we shall leave to the reader) allow to get:

Theorem

The category of coherent spaces and stable functions is cartesian closed.

In particular this means that if we define $\mathrm{Eval}:(X\rightarrow Y)\with X\mapsto Y$ by: $\mathrm{Eval}(\langle f, x\rangle) = \mathrm{Fun}\,f(x)$ then $Eval$ is stable.

Linear functions

Definition (Linear function)

A function $F:X\mapsto Y$ is linear if it is stable and furthemore satisfies: for any family $A$ of pairwise compatible cliques of $X$ , that is such that for any $x, y\in A$ , $x\cup y\in X$ , we have $\bigcup_{x\in A}F(x) = F(\bigcup A)$ .

In particular if we take $A$ to be the empty family, then we have $F(\emptyset) = \emptyset$ .

The condition for linearity is quite similar to the condition for Scott continuity, except that we dropped the constraint that $A$ is directed. Linearity is therefore much stronger than stability: most stable functions are not linear.

As with stable function we have an equivalent and much more tractable caracterisation of linear function:

Theorem

Let $F:X\mapsto Y$ be a continuous function. Then $F$ is linear iff it satisfies: for any clique $x\in X$ and any $b\in F(x)$ there is a unique $a\in x$ such that $b\in F(\{a\})$ .

Just as the caracterisation theorem for stable functions allowed us to build the coherent space of stable functions, this theorem will help us to endow the set of linear maps with a structure of coherent space.

Definition (The linear functions space)

Let $X$ and $Y$ be coherent spaces. The linear function space $X\limp Y$ is defined by:

$\web{X\limp Y} = \web X\times \web Y$ ,
$(a,b)\coh_{X\limp Y}(a', b')$ iff $\begin{cases}\text{if }a\coh_X a'\text{ then } b\coh_Y b'\\ \text{if }a\coh_X a' \text{ and }b=b'\text{ then }a=a'\end{cases}$

Equivalently one could define the strict coherence to be: $(a,b)\scoh_{X\limp Y}(a',b')$ iff $a\scoh_X a'$ entails $b\scoh_Y b'$ .

Definition (Linear trace)

Let $F:X\mapsto Y$ be a function. The linear trace of $F$ denoted as $LinTr(F)$ is the set: $\mathrm{LinTr}(F) = \{(a, b)\in\web X\times\web Y$ such that $b\in F(\{a\})\}$ .

Theorem

If $F$ is linear then $LinTr(F)$ is a clique of $X\limp Y$ .

Definition (Evaluation of linear function)

Let $f$ be a clique of $X\limp Y$ . We define the function $\mathrm{LinFun}\,f:X\mapsto Y$ by: $\mathrm{LinFun}\,f(x) = \{b\in\web Y$ such that there is an $a\in x$ satisfying $(a,b)\in f\}$ .

Theorem (Linear closure)

Let $f$ be a clique in $X\limp Y$ . Then we have $\mathrm{LinTr}(\mathrm{LinFun}\, f) = f$ . Conversely if $F:X\mapsto Y$ is linear then we have $F = \mathrm{LinFun}\,\mathrm{LinTr}(F)$ .

It remains to define a tensor product and we will get that the category of coherent spaces with linear functions is monoidal symetric (it is actually *-autonomous).

References

↑ Girard, Jean-Yves. The System F of Variable Types, Fifteen Years Later. Theoretical Computer Science. Volume 45, Issue 2, pp. 159-192, doi:10.1016/0304-3975(86)90044-7, 1986.

[0] Girard, Jean-Yves. The System F of Variable Types, Fifteen Years Later. Theoretical Computer Science. Volume 45, Issue 2, pp. 159-192, doi:10.1016/0304-3975(86)90044-7, 1986.

[1]

@@ Line 34: / Line 34: @@
 A coherent space is completely determined by its web and its coherence relation, or equivalently by its web and its strict coherence.
-==== CLiqued space ====
+==== Cliqued space ====
 {{Definition|title=Duality|
@@ Line 57: / Line 57: @@
 Conversely given a coherent space <math>X</math> in the graph sense, one can check that it is a cliqued space. Call ''anticlique'' a set <math>y\subset \web X</math> of pairwise incoherent points: for all <math>a, b</math> in <math>y</math>, if <math>a\coh_X b</math> then <math>a=b</math>. Any anticlique intersects any clique in at most one point: let <math>x</math> be a clique and <math>y</math> be an anticlique, then if <math>a,b\in x\cap y</math>, since <math>a, b\in x</math> we have <math>a\coh_X b</math> and since <math>y</math> is an anticlique we have <math>a = b</math>.
-Thus the collection of anticliques of <math>X</math> is the dual <math>X^\bot</math> of <math>X</math>. Note that the incoherence relation defined above is reflexive an symetric, so that <math>X^\bot</math> is a coherent space in the graph sense. Thus we can do for <math>X^\bot</math> exactly what we've just done for <math>X</math> and consider the anti-anticliques, that is the anticliques for the incoherent relation which are the cliques for the in-incoherent relation. It is not difficult to see that this  in-incoherence relation is just the coherence relation we started with; we thus obtain that <math>X^{\bot\bot} = X</math>, so that <math>X</math> is a cliqued space.
+Thus the collection of anticliques of <math>X</math> is the dual <math>X^\bot</math> of <math>X</math>. Note that the incoherence relation defined above is reflexive and symetric, so that <math>X^\bot</math> is a coherent space in the graph sense. Thus we can do for <math>X^\bot</math> exactly what we've just done for <math>X</math> and consider the anti-anticliques, that is the anticliques for the incoherent relation which are the cliques for the in-incoherent relation. It is not difficult to see that this  in-incoherence relation is just the coherence relation we started with; we thus obtain that <math>X^{\bot\bot} = X</math>, so that <math>X</math> is a cliqued space.
 === Stable functions ===

Coherent semantics

Revision as of 13:52, 22 February 2009

Contents

The cartesian closed structure of coherent semantics

Coherent spaces

As domains

As graphs

Cliqued space

Stable functions

Cartesian product

Linear functions

References

Views

Personal tools

Navigation

Search

Tools