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.