TD8 : DCPO, Topologie de Scott

EX 1

1.

graph mon_graphe {
  rankdir=TB;
     0 -- ⊥;
     1 -- ⊥;
 }

2.

graph mon_graphe {
  rankdir=BT;
     0 -- 1;
     1 -- 2;
     2 -- 3;
     3 -- ⋯;

 }

3.

graph mon_graphe {
  rankdir=TB;
     0 -- ⊥;
     1 -- ⊥;
     2 -- ⊥;
     3 -- ⊥;
     ⋯ -- ⊥;
 }

4.

graph mon_graphe {
  rankdir=BT;
     0 -- 1;
     1 -- 2;
     2 -- 3;
     3 -- ⋯;
     ⋯ -- ∞;

 }

5.

$[0,1]$ est le minimum, et les singletons $\lbrace x \rbrace$ (pour $x∈[0,1]$) sont les maxima.

Si $([x_j, y_j])_{j∈J}$

  • $\sup = \bigcap_{j∈J} [x_j, y_j]$

6.

Pas un DCPO : si $(u_n)$ est une suite de rationnels tendant vers $1/\sqrt{2}$, la famille d’intervalles

\[([0, u_n])_n\]

n’a pas de $\sup$ pour l’ordre donné.

EX 2

1.

Trivial : ce n’est pas un treillis, mais un DCPO pointé.

2.

Les seuls ouverts sont $Bool_\bot$, $∅$, $\lbrace 1 \rbrace$ et $\lbrace 0 \rbrace$, et $\lbrace 0, 1 \rbrace$

Les fermés sont leurs complémentaires.

3.

La donnée d’une fonction de $Bool_\bot ⟶ Bool_\bot$ correspond à la donnée d’un triplet de $(Bool_\bot)^3$ (images respectives de $0$, $1$, et $\bot$).

Soit $f$ une fonction croissante :

Si

  • $f(\bot) = \bot$ : tout est permis pour les autres images
  • $f(\bot) = 0$ : la fonction vaut nécessairement zéro partout ailleurs.
  • $f(\bot) = 1$ : la fonction vaut nécessairement 1 partout ailleurs.

4.

  • $f$ est bien monotone
  • Toute famille dirigée de $Bool_\bot$ est finie : son sup vaut donc son max. De même, l’image de cette famille est finie, donc max des images vaut l’image du max, par croissance de $f$.

5.

graph mon_graphe {
  rankdir=TB;
     10 -- ⊥0;
     01 -- ⊥1;
     11 -- ⊥1;
     00 -- ⊥0;
     01 -- "0⊥";
     10 -- "1⊥";
     11 -- "1⊥";
     00 -- "0⊥";
     ⊥0 -- ⊥⊥;
     ⊥1 -- ⊥⊥;
     "0⊥" -- ⊥⊥;
     "1⊥" -- ⊥⊥;

 }

NB :

  • un graphe est planaire ssi il n’y a pas d’instance de $K_{3,3}$ ni de $K_5$

6.

$f:Bool_\bot \times Bool_\bot ⟶ Bool_\bot$

tq \(f_{\vert Bool_\bot \times Bool_\bot} = ∨\)

graph mon_graphe {
  rankdir=TB;
     10 -- ⊥0;
     01 -- ⊥1;
     11 -- ⊥1;
     00 -- ⊥0;
     01 -- "0⊥";
     10 -- "1⊥";
     11 -- "1⊥";
     00 -- "0⊥";
     ⊥0 -- ⊥⊥;
     ⊥1 -- ⊥⊥;
     "0⊥" -- ⊥⊥;
     "1⊥" -- ⊥⊥;

 }

⇓

graph mon_graphe {
  rankdir=TB;
     10.1 -- ⊥0_⊥;
     01.1 -- ⊥1;
     11.1 -- ⊥1;
     00.0 -- ⊥0_⊥;
     01.1 -- "0⊥_⊥";
     10.1 -- "1⊥";
     11.1 -- "1⊥";
     00.0 -- "0⊥_⊥";
     ⊥0_⊥ -- ⊥⊥_⊥;
     ⊥1 -- ⊥⊥_⊥;
     "0⊥_⊥" -- ⊥⊥_⊥;
     "1⊥" -- "⊥⊥_⊥";

 }
$f :$ $Bool_\bot$ $\mapsto$ all classic left lazy right lazy parallel
  $(0,0)$   $0$        
  $(0,1)$   $1$        
  $(1,0)$   $1$        
  $(1,1)$   $1$        
               
  $(\bot,\bot)$     $\bot$ $\bot$ $\bot$ $\bot$
  $(\bot,0)$     $\bot$ $\bot$ $\bot$ $\bot$
  $(\bot,1)$     $\bot$ $\bot$ $1$ $1$
  $(0,\bot)$     $\bot$ $\bot$ $\bot$ $\bot$
  $(1,\bot)$     $\bot$ $1$ $\bot$ $1$

EX 4

1.

DCPO : cf. exo 1

Treillis : non, singletons $\lbrace x \rbrace$, $\lbrace y \rbrace$ pour $x≠y$ n’a pas de majorant.

2.

Ex :

\[f = [x, y] \mapsto \begin{cases} 0 \text{ si } x=y \\ \bot \text{ sinon.} \end{cases}\]

$f$ croît clairement.

$f$ n’est pas Scott-continue :

\[D = ([x - \frac 1 n, x + \frac 1 n])_{n∈ℕ}\] \[\sup D = \lbrace x \rbrace \\ f(\sup D) = 0 ≠ \bot = \sup f(D)\]

3.

Les singletons sont les éléments maximaux.

4.

Évident si on utilise la caractérisation par topologie de Scott.

5.

Soit $x∈ℝ$.

$g(x) = i ≠ \bot$.

Or :

\[\Big[x-\frac 1 n, x + \frac 1 n\Big] ⟶ \lbrace x \rbrace\]

Comme

$g^{-1}(\lbrace i \rbrace)$ est inaccessible par le bas,

\[∃n; g(\Big[x-\frac 1 n, x + \frac 1 n\Big]) = g(\lbrace x \rbrace)\] \[∀y∈\Big[x-\frac 1 n, x + \frac 1 n\Big], \, \, g(\lbrace y \rbrace)= g(\lbrace x \rbrace)\]

Donc en posant :

\[y ≝ \inf(\lbrace y; g(\lbrace y \rbrace) = i\rbrace)\]

Si, par l’absurde : $y > -∞$

Alors en considérant un voisinage de $y$ sur lequel $g$ est constante.

Il existe des éléments de ce voisinage strictement plus grands que $y$, dont l’image par $g$ vaut donc $i$, donc l’image de $y$ vaut $i$ : absurde.

6.

Soit la fonction d’égalité :

  • n’est pas définie partout (de temps en temps elle vaut $\bot$)
  • soit elle est constante, ce qui n’est pas satisfaisant, car :
    • la fonction $x \mapsto x=\sqrt{2}$ (par exemple) n’est pas censée être constante.

NB :

  • cf les domaines de Scott, dans le $𝜆$-calcul.
  • même résultat en calculabilité : les fonctions calculables sont continues, au sens “classique”.

EX 5

Leave a comment