TKI Moduł 13

Udowodnijmy teraz podstawowe twierdzenie na temat diagramów w kategorii Dcpo.

Twierdzenie. W Dcpo istnieją granice dowolnych diagramów.

Dowód: Dowód przeprowadzimy dla szczególnego diagramu:

[DIAGRAM]

(Dowód ogólny jest analogiczny lecz wymaga bardziej technicznego zapisu, wiec go pominiemy.) Pokażemy, że granica powyższego diagramu jest dana jako

$D=\{(x_0,x_1,...)\mid (\mathrm{\forall }n\in \omega )(f_n(x_{n+1})=x_n)\}.$

Zauważmy, że zbiór $D$ jest posetem, w którym elementy są uporządkowane po współrzędnych (to znaczy, że porządek jest dziedziczony z produktu ${\mathrm{\Pi }}_{n\in \omega }{D}_n$. Jeśli $G\subseteq D$ jest zbiorem skierowanym, to dla każdego $n\in \omega$zbiór ${\pi }_n[G]=\{x_n\mid x\in G\}$jest skierowanym podzbiorem $D_n$. Niech $y_n=\bigvee \{x_n\mid x\in G\}$. Z ciągłości funkcji tworzących diagram mamy: $f_n(y_{n+1})=\bigvee f_n(\{x_{n+1}\mid x\in G\})=\bigvee \{x_n\mid x\in G\}=y_n$. To znaczy, że $(y_0,y_1,...)\in D$ i, jak łatwo zauważyć, element ten jest supremum skierowanym zbioru $G$. Pokazaliśmy więc, że $D\in$ Dcpo.

Udowodnimy teraz, że $D$ wraz z projekcjami $\{{\pi }_n:D\to D_n\mid n\in \omega \}$ jest granicą. Po pierwsze, dla $G\subseteq D$ mamy

${\pi }_n(\bigvee G)=y_n=\bigvee \{x_n\mid x\in G\}=\bigvee {\pi }_n[G],$

a więc projekcje są ciągłe. Po drugie, jeśli $\{g_k:E\to D_k\mid k\in \omega \}$ jest dowolną inną granicą, to zdefiniujmy $h:E\to D$ jako $h(x)=(g_0(x),g_1(x),...)$. Z definicji powyższej wynika, że dla każdego $k\in \omega$ mamy $\pi_k \circ h = g_k</math>. Zauważmy, że to świadczy o jednoznaczności wyboru $h$. A zatem $D$ jest granicą omawianego diagramu. Co więcej, z jednoznaczności granicy wnioskujemy, że $D\cong E$. QED

Uwaga! Powyższe twierdzenie nie zachodzi dla klas dziedzin ciągłych i algebraicznych w ogólności. Aby granica była również posetem odpowiedniej klasy, musimy nałożyć poewne restrykcje zarówno na kształ diagramów, jak i na własności funkcji tworzących diagram.

Twierdzenie o zgodności granicy prostej i odwrotnej

Przedstawimy teraz twierdzenie o zgodności granicy prostej i odwrotnej pewnych szczególnych diagramów w kategorii posetów zupełnych. Wynik ten jest znany w literaturze angielskojęzycznej jako limit-colimt coincidence i jest jednym z kamieni milowych w teorii dziedzin. Twierdzenie to wykorzystuje się przede wszystkim przy rozwiązywaniu tak zwanych rekursywnych równań dziedzinowych (ang. recursive domain equations). Przykładem takiego równania jest $D\cong [D\to D]$. Okazuje się, że jego nietrywialne rozwiązania istnieja! Tak więc istnieją posety, które są izomorficzne z przestrzenią swoich ciągłych endofunkcji! Jeden z takich częściowych porządków skonstruujemy poniżej, pod koniec wykładu.

Twierdzenie. Rozważmy diagram $F$ w kategorii Dcpo taki, że:

1. Wierzchołkami $F$ są posety $D_0,D_1,D_2,...$;

2. Dla $n\le m$ istnieją funkcje $e_{mn}:D_n\to D_m$ i $p_{nm}:D_m\to D_n$ tworzące parę e-p; 3. Dla każdego $n\in \omega$ mamy $e_{nn}=1_{D_n}$;

4. Dla $n\le m\le k$ mamy $e_{kn}=e_{km}\circ e_{mn}$ oraz $p_{nk}=p_{nm}\circ p_{mk}$.

Zdefiniujmy:

$D=\{(x_0,x_1,...)\mid (\mathrm{\forall }n\le m)(x_n=p_{nm}(x_m))\},$

$p_m:D\to D_m,(x_0,x_1,...)\mapsto x_m,m\in \omega$

$e_m:D_m\to D,x\mapsto (\underset{k\ge n,m}{\bigvee }{p}_{nk}\circ e_{km}(x)\mid n\in \omega ).$

Wtedy:

5. Para $(e_m,p_m)$ jest parą e-p i zachodzi $\underset{n\in \omega }{\bigvee }{e}_n\circ p_n=1_D$,

6.$\{p_n:D\to D_n\}$ jest granicą diagramu $F$. Jeśli $\{g_n:C\to D_n\}$ jest dowolną inną granicą, to izmorfizm $h:C\to D$ jest dany jako $h(x)=(g_n(x)\mid n\in \omega )$ lub $h=\underset{n}{\bigvee }{e}_n\circ g_n$;

7.$\{e_n:D_n\to D\}$ jest granicą odwrotną diagramu $F$. Jeśli $\{f_n:E\to D_n\}$ jest dowolną inną granicą, to izmorfizm $f:D\to E$ jest dany jako $f(x_n\mid n\in \omega )=\underset{n}{\bigvee }{f}_n(x_n)$ lub $f=\underset{n}{\bigvee }{f}_n\circ p_n$.

Dowód: W Twierdzeniu ??? pokazaliśmy już, że granicą diagramu jest $\{p_n:D\to D_n\}$ i że izomorfizm $h:C\to D$ ma (pierwszą z) postulowanych postaci. Pokażmy teraz, że funkcje $e_m$ są dobrze zdefiniowane, tj. że $y=e_m(x)$ należy do $D$ dla dowolnego $m\in \omega$. Niech $m$ będzie dowolne i załóżmy, że $n\le n^{\prime }$. Mamy:

$p_{n{n}^{\prime }}(y_{n^{\prime }})=p_{n{n}^{\prime }}(\underset{k\ge n^{\prime },m}{\bigvee }{p}_{n^{\prime }k}\circ e_{km}(x))=\underset{k\ge n^{\prime },m}{\bigvee }{p}_{n{n}^{\prime }}\circ p_{n^{\prime }k}\circ e_{km}(x)=\underset{k\ge n^{\prime },m}{\bigvee }{p}_{nk}\circ e_{km}(x)=y_n.$

W dowodzie korzystaliśmy kolejno z: definicji $y_{n^{\prime }}$, ciągłości $p_{n{n}^{\prime }}$ i definicji $y_n$. A zatem $y=(y_0,y_1,...)\in D$. Co więcej, funkcje $e_m$ są ciągłe, gdyż tylko funkcje ciągłe zostały użyte w ich definicji.

Przejdźmy do dowodu (5). Niech $m\in \omega$. Mamy: