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: 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)$
f\Big(\bigcup\limits_{i ∈ I} (x_i, y_i)\Big) = f\Big (\bigcup\limits_{i ∈ I} x_i, \bigcup\limits_{i ∈ I} y_i)\Big) \\ \overset{\text{linearity ×2}}{=} \bigcup\limits_{i ∈ I} \bigcup\limits_{j ∈ I} f\Big((x_i, y_j)\Big) \overset{D \text{ directed}}{⊆} \bigcup\limits_{i ∈ I} f\Big((x_i, y_i)\Big)

Stable

  • $(x_1, x_2)$ and $(y_1, y_2)$ compatible
  • i.e. $x_1, y_1$ compatible and $x_2, y_2$ compatible
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)) ⊆ f((x_1, x_2)) ∩ f((y_1, y_2))

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