Coherent semantics

Revision as of 18:51, 7 February 2009

Coherent semantics was invented by Girard in the paper The system F, 15 years later. It is a refinement of the former qualitative domains that allows for building an interpretation of system F terms, that is for second order quantifiers.

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.

Although coherent semantics allowed to solve for the first time the old standing problem of building a denotationnal semantics for polymorphism, one of its main interest is that it also lead Girard to discover the notion of linear function, which rapidly gave rise to linear logic. It is one of the originality of linear logic that its syntax was derived from its semantics.

Preliminary definitions and notations

There are two equivalent definitions of coherence spaces: the first one, coherent spaces as graphs, is the most commonly used and will be our "official" definition in the sequel. The second one, coherent spaces as domains, is however interesting from a historical point of view.

Coherent spaces

As graphs

Definition (Coherent space)

A coherent space $X$ is a set of points denoted $\web X$ and called the web of $X$ together with a reflexive and symetric relation $\coh_X$ on $\web X$ called the coherence relation. Coherent spaces are identified with the simple unoriented graphes of their coherence relations.

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

Definition (Clique)

A clique of the coherent space $X$ is a set of points in $\web X$ that are pairwise coherent. In other terms a clique is a subgraph of $X$ that is complete. The set of cliques of $X$ is denoted as $\mathcal{C}(X)$ .

As domains

Definition (Coherent space)

A coherent space $X$ is a family of subsets of a set $\web X$ which is closed by subset (if $x\subset y\in X$ then $x\in X$ ) and satisfies the 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$ .

The reader will easily check that one recovers the previous definition by setting $a\coh_X b$ iff $\{a,b\}\in X$ and conversely that the set of cliques of a coherent space in the graph sense is a coherent space in the domain sense.

Stable functions

From now on we will identify the coherent space (in the graph sense) $X$ with its set of cliques $\mathcal{C}(X)$ . Accordingly a function $F$ from $X$ to $Y$ is a function defined on the cliques of $X$ taking values in the cliques of $Y$ .

Definition (Stable function)

Let $X$ and $Y$ be two coherent spaces. A function $F:X\rightarrow 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\rightarrow 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)$ ).

@@ Line 30: / Line 30: @@
 The reader will easily check that one recovers the previous definition by setting <math>a\coh_X b</math> iff <math>\{a,b\}\in X</math> and conversely that the set of cliques of a coherent space in the graph sense is a coherent space in the domain sense.
+=== Stable functions ===
+From now on we will identify the coherent space (in the graph sense) <math>X</math> with its set of cliques <math>\mathcal{C}(X)</math>. Accordingly a function <math>F</math> from <math>X</math> to <math>Y</math> is a function defined on the cliques of <math>X</math> taking values in the cliques of <math>Y</math>.
+{{Definition|title=Stable function|
+Let <math>X</math> and <math>Y</math> be two coherent spaces. A function <math>F:X\rightarrow Y</math> is ''stable'' if it satisfies:
+* it is non decreasing: for any <math>x,y\in X</math> if <math>x\subset y</math> then <math>F(x)\subset F(y)</math>;
+* it is continuous (in the Scott sense): if <math>A</math> is a directed family of cliques of <math>X</math>, that is if for any <math>x,y\in A</math> there is a <math>z\in A</math> such that <math>x\cup y\subset z</math>, then <math>\bigcup_{x\in A}F(x) = F(\bigcup A)</math>;
+* it satisfies the stability condition: if <math>x,y\in X</math> are compatible, that is if <math>x\cup y\in X</math>, then <math>F(x\cap y) = F(x)\cap F(y)</math>.
+}}
+This definition is admitedly not very tractable. An equivalent and most useful caracterisation of stable functions is given by the following theorem.
+{{Theorem|
+Let <math>F:X\rightarrow Y</math> be a non-decreasing function from the coherent space <math>X</math> to the coherent space <math>Y</math>. The function <math>F</math> is stable iff it satisfies: for any <math>x\in X</math>, <math>b\in\web Y</math>, if <math>b\in F(x)</math> then there is a finite clique <math>x_0\subset x</math> such that:
+* <math>b\in F(x_0)</math>,
+* for any <math>y\subset x</math> if <math>b\in F(y)</math> then <math>x_0\subset y</math> (<math>x_0</math> is ''the'' minimum sub-clique of <math>x</math> such that <math>b\in F(x_0)</math>).
+}}

Coherent semantics

Revision as of 18:51, 7 February 2009

Contents

Preliminary definitions and notations

Coherent spaces

As graphs

As domains

Stable functions

Views

Personal tools

Navigation

Search

Tools