Execises 3: Coherence spaces and lazy integers
Teacher: Thomas Ehrhard
\[\newcommand\xto\xrightarrow \newcommand\xfrom\xleftarrow \newcommand{\Tr}{\mathop{\mathrm{Tr}}}\]Recap: about Scott-continuity
Let $P, Q$ be two partially ordered sets.
- $f: P ⟶ Q$ is Scott-continuous:
-
iff for every directed subset $D ⊆ P$ such that $\bigvee D ∈ P$, $\bigvee f(D)$ exists in $Q$ and \(f\left(\bigvee D\right) = \bigvee f(D)\)
- The Scott topology on $P$:
-
is the topology whose opens are upper sets (sets upper-closed) that are inaccessible by directed joins (i.e. if $D$ is directed and $\bigvee D ∈ O$, then $D ∩ O ≠ ∅$)
Lemma: $f: P ⟶ Q$ is Scott-continuous iff it is continuous for the Scott-topology
$⟹$: Let $V ⊆ Q$ be an open set. Let’s show that $f^{-1}(V) ⊆ P$ is open.
-
upper set: if $x ∈ f^{-1}(V)$ and $y ≥ x$, then as $f$ is monotone:
\[V \ni f(x) ≤ f(y) \overset{\text{as } V \text{ is an upper-set}}{∈} V\] -
inaccessible by directed joins: if $D$ is directed and $\bigvee D ∈ f^{-1}(V)$, then if there existed a $x ∈ f^{-1}(V) ∩ D$, then we would have $f(x) ∈ V ∩ f(D) = ∅$ as $f(D)$ is directed, $\bigvee f(D) = f(\bigvee D) ∈ V$, but $V$ is inaccessible by directed joins.
$⟸$: Let $D ⊆ P$ be a directed set such that $\bigvee D ∈ P$.
$f: Cl(E) ⟶ Cl(F)$ monotone is Scott-continuous iff \(∀ x ∈ Cl(E), ∀ b ∈ \vert F \vert, \quad b ∈ f(x) ⟹ ∃ x_0 ∈ 𝒫_f(x); \; b ∈ f(x_0)\)
Exercise Sheet: Problem statement
1.
Let $f: Cl(E) ⟶ Cl(F)$
Assume $f$ is linear. Let $(x_i)_{i ∈ I} ∈Cl(E)^I$ such that
- $I$ is at most countable
- $i≠j ⟹ x_i ∩ x_j = ∅$
- $\bigcup\limits_{i∈ I} x_i ∈ Cl(E)$
Let’s show that $f$ preserves disjointness, compatibility of the family, and preserves the sup of $(x_i)$.
-
Disjointness preservation: If $i ≠ j$
$x_i ∪ x_j ⊆ \bigcup x_k ∈ Cl(E)$, so $x_i ↑ x_j$, and by conditional multiplicativity and linearity:
\[∅ = f(∅) = f(x_i ∩ x_j) = f(x_i) ∩ f(x_j)\] -
Preserves the sup:
\[f\Big(\bigcup\limits_{i ∈ I} x_i\Big) = f\Big(\bigcup\limits_{J ⊆_{finite} I} \bigcup\limits_{j ∈ J} x_j\Big) \overset{\text{continuity}}{=} \bigcup\limits_{J ⊆_{finite} I} f\Big( \bigcup\limits_{j ∈ J} x_j\Big)\]since $(\bigcup\limits_{j ∈ J} x_j)_{J ⊆_f I}$ is directed in $Cl(E)$, and
\[\bigcup\limits_{J ⊆_{finite} I} f\Big( \bigcup\limits_{j ∈ J} x_j\Big) \overset{\text{linearity}}{=} \bigcup\limits_{J ⊆_{finite} I} \bigcup\limits_{j ∈ J} f(x_j) = \bigcup\limits_{i ∈ I} f(x_i)\]
Conversely, suppose $f$ preserves disjointness, compatibility of the family, and preserves the sup of $(x_i)$.
$f$ is monotone
Let $x ⊆ y$. As $y \backslash x$ is a clique of $E$ and $y \backslash x$ and $x$ are disjoint:
\[f(x) ⊆ f(x) ∪ f(y \backslash x) = f(x ∪ y \backslash x) = f(y)\]Scott-continuity of $f$
Fact: $f: Cl(E) ⟶ Cl(F)$ monotone is Scott-continuous iff
\[∀ x ∈ Cl(E), ∀ b ∈ \vert F \vert, \quad b ∈ f(x) ⟹ ∃ x_0 ∈ 𝒫_f(x); \; b ∈ f(x_0)\]
Scott-continuity: to have a finite approximation in the output, you only need a finite approximation in the input.
Let $x ∈ Cl(E), \; b ∈ \vert F \vert$ such that $b ∈ f(x)$.
Then
\[b ∈ f(x) = f\Big( \bigcup\limits_{a ∈ x} \lbrace a\rbrace\Big) = \bigcup\limits_{a ∈ x} f(\lbrace a\rbrace)\]And there exists a singleton $\lbrace a \rbrace$ that is suitable.
Actually, we have shown:
Lemma:
\[∀ x ∈ Cl(E), ∀b ∈ f(x), \; ∃! a ∈ x; \; b ∈ f(\lbrace a \rbrace)\]
Uniqueness comes from the fact that if you have two distinct suitable $a$ and $a’$, then as $f$ preserves disjointness $b ∈ f(\lbrace a \rbrace) ∩ f(\lbrace a’ \rbrace) = ∅$: contradiction.
Conditional multiplicativity
As $f$ is monotone, $f(x ∩ y) ⊆ f(x) ∩ f(y)$. So we need to show
\[f(x) ∩ f(y) ⊆ f(x ∩ y) \quad \text{ if } x,y ∈ Cl(E) \text{ and } x ∪ y ∈ Cl(E)\]Let $b ∈ f(x) ∩ f(y)$, then there exists unique $a ∈ x$, $a’ ∈ y$ such that
\[b ∈ f(\lbrace a\rbrace) ∩ f(\lbrace a'\rbrace)\]So as $\lbrace a, a’\rbrace ∈ Cl(E)$ (since $x ∪ y ∈ Cl(E)$), $a=a’$.
Other conditions
$f(∅) = ∅$ for the empty family
Let $x, y ∈ Cl(E)$ st $x ∪ y ∈ Cl(E)$. As $f$ is monotone:
\[f(x) ∪ f(y) ⊆ f(x ∪ y)\]And conversely:
\[f(x ∪ y) = f(x \backslash x ∩ y) ∪ f(y \backslash x ∩ y) ∪ f(x ∩ y) \\ = (f(x \backslash x ∩ y) ∪ f(x ∩ y)) ∪ (f(y \backslash x ∩ y) ∪ f(x ∩ y)) = f(x) ∪ f(y)\]2.
2.1.
\[f: Cl(E_1) × Cl(E_2) ≅ Cl(E_1 \& E_2) ⟶ Cl(F)\]Assume $f$ is bilinear, show that it is stable.
Monotone
\[(x_1, x_2) ⊆ (y_1, y_2) ⟺ \begin{cases} x_1 ⊆ y_1 \\ x_2 ⊆ y_2 \\ \end{cases}\] \[f(x_1, x_2) ⊆ f(y_1, x_2) ⊆ f(y_1, y_2)\]Continuous
Let $D ≝ (x_i, y_i)_{i ∈ I}$ be a directed set.
Then
- $D_1 ≝ (x_i)_{i ∈ I}$ directed in $Cl(E_1)$
- $D_2 ≝ (y_i)_{i ∈ I}$ directed in $Cl(E_2)$
Stable
- $(x_1, x_2)$ and $(y_1, y_2)$ compatible
- i.e. $x_1, y_1$ compatible and $x_2, y_2$ compatible
Lemma: $f: Cl(E) ⟶ Cl(F)$ is stable iff $f$ is monotone and
\[∀ x ∈ Cl(E), ∀b ∈ f(x), \; ∃ x_0 ∈ 𝒫_f(x); \; b ∈ f(x_0) \\ \text{ and } x_0 \text{ is minimal: } ∀ x'⊆ x, (b ∈ f(x') ⟹ x_0 ⊆ x')\]
and
If $f: Cl(E_1) × Cl(E_2) ⟶ Cl(F)$ is separately stable, then it is stable
Bilinear and linear
\[f((x_1, x_2) ∪ (y_1, y_2)) = f((x_1, x_2)) ∪ f((x_1, y_2)) ∪ f((y_1, x_2)) ∪ f((y_1, y_2))\]So suppose $f$ is linear and bilinear: then for all $x_1, x_2$
\[f((x_1, x_2)) = \underbrace{f((∅, x_2))}_{= ∅} ∪ f((x_1, ∅)) = ∅\]Example of a function which is bilinear but not linear:
- $E_1 = E_2 = F = \lbrace \ast\rbrace$
- $f((∅, ∅)) = ∅$
- $f((∅, \lbrace \ast\rbrace)) = ∅$
- $f((\lbrace \ast\rbrace, ∅)) = ∅$
- $f((\lbrace \ast\rbrace, \lbrace \ast\rbrace)) = \lbrace \ast\rbrace$
2.2.
You can straightforwardly use the characterisation of question 1, as intersection and union is taken pointwise.
2.3.
$f, g: Cl(E) ⟶ Cl(F)$ linear: \(f=g ⟺ ∀ a ∈ \vert E \vert, f(\lbrace a\rbrace) = g(\lbrace a\rbrace)\)
$\widetilde f$ defined on singletons:
\[\widetilde f (\lbrace (a, b)\rbrace) = f(\lbrace a\rbrace, \lbrace b\rbrace)\]Uniqueness:
\[f_1( \lbrace (a, b)\rbrace) = f_1 \circ τ (\lbrace a\rbrace, \lbrace b\rbrace) = f_2 \circ τ (\lbrace a\rbrace, \lbrace b\rbrace) = f_2 ( \lbrace (a,b)\rbrace)\]
Leave a comment