Teoria kategorii dla informatyków/Ćwiczenia 14: Teoria dziedzin III

==Zadanie 14.1==

Udowodnić, że w $\mathbf {Dcpo}$ są granice dowolnych diagramów.

Wskazówka:

Dowód przeprowadzimy dla szczególnego diagramu:

$D_{0}{\stackrel {f_{0}}{\leftarrow }}D_{1}{\stackrel {f_{1}}{\leftarrow }}D_{2}{\stackrel {f_{2}}{\leftarrow }}D_{3}{\stackrel {f_{3}}{\leftarrow }}D_{4}{\stackrel {f_{4}}{\leftarrow }}...$

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

$D=\{(x_{0},x_{1},...)\mid (\forall n\in \omega )(f_{n}(x_{n+1})=x_{n})\}.$

Rozwiązanie:

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 $\Pi _{n\in \omega }D_{n}$).

Jeśli $GD$, 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 {}^{\downarrow }\{x_{n}\mid x\in G\}$. Z ciągłości funkcji tworzących diagram mamy:

$f_{n}(y_{n+1})=\bigvee {}^{\downarrow }f_{n}(\{x_{n+1}\mid x\in G\})=\bigvee {}^{\downarrow }\{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 \mathbf {Dcpo}$.

Udowodnimy teraz, że $D$ wraz z projekcjami $\{\pi _{n}\colon D\to D_{n}\mid n\in \omega \}$ jest granicą. Po pierwsze, dla $GD$ mamy:

$\pi _{n}(\bigvee {}^{\downarrow }G)=y_{n}=\bigvee {}^{\downarrow }\{x_{n}\mid x\in G\}=\bigvee {}^{\downarrow }\pi _{n}[G],$

a więc projekcje są ciągłe.

Po drugie, jeśli $\{g_{k}\colon E\to D_{k}\mid k\in \omega \}$ jest dowolną inną granicą, to zdefiniujmy $h\colon 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}$. 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$.

==Zadanie 14.2==

Udowodnić Lemat 14.5.

Rozwiązanie:

Skoro $D_{\infty }$ jest granicą odwrotną diagramu

to

komutuje. W szczególności

komutuje i jak łatwo zauważyć $D_{\infty }$ jest jego granicą. Ale z ciągłości $F$ mamy, że diagram

komutuje i $F(D_{\infty })$ jest jego granicą. A zatem $D_{\infty }\cong F(D_{\infty })$ wynika z jednoznaczności granicy.

Poniższe zadania zawierają przykłady rozwiązań rekursywnych równań w kategorii $\mathbf {Dcpo} _{\bot }$. Wszystkie te rozwiązania konstruujemy w następujący sposób: mając dany lokalnie ciągły funktor $F$, definiujemy rekursywnie ciąg kolejnych dcpo, poczynając od posetu jednoelementowego $\mathbf {1}$ (czyli elementu końcowego w $\mathbf {Dcpo} _{\bot }$):

$D_{0}:=\mathbf {1} ,D_{1}:=F\mathbf {1} ,...,D_{n+1}:=F^{n}\mathbf {1} ,...$

wraz z odpowiednimi, naturalnymi parami e-p. Taki ciąg tworzy diagram. Funktor $F$, zgodnie z Lematem 14.7, rozszerza się do funktora ciągłego, a zatem Lemat 14.5 mówi, że dla granicy $D_{\infty }$ diagramu mamy $F(D_{\infty })\cong D_{\infty }$. W poniższych zadaniach zamiast podawania szczegółowych dowodów kładziemy nacisk na intuicyjne zrozumienie konstrukcji $D_{\infty }$ dla prostych funktorów.

==Zadanie 14.3==

Znaleźć punkt stały funktora $F\colon \mathbf {Dcpo} _{\bot }\to \mathbf {Dcpo} _{\bot }$, który dodaje element najmniejszy: $F(-):=(-)_{\bot }$.

Wskazówka:

Porządna definicja mogłaby wyglądać tak: dla obiektu $D$, $F(D):=D_{\bot }$. Dla morfizmu $f\colon P\to Q$,

$F(f):=f_{\bot }\colon P_{\bot }\to Q_{\bot },\ f(p\in P):=p,f(\bot ):=\bot .$

Rozwiązanie:

Najpierw pokażmy, że $F$ jest lokalnie ciągły. W tym celu musimy pokazać, że operacja $f\colon P\to Q\mapsto f_{\bot }\colon P_{\bot }\to Q_{\bot }$ typu

$\mathrm {Hom} (P,Q)\to \mathrm {Hom} (P_{\bot },Q_{\bot })$

jest ciągła w sensie Scotta. Niech $\{f_{i}\}$ będzie skierowanym podzbiorem $\mathrm {Hom} (P,Q)$. Ponieważ $\mathrm {Hom} (P,Q)$ jest dcpo, ta rodzina ma supremum $\bigvee {}_{i}^{\downarrow }f_{i}$. Wówczas: $F(\bigvee {}_{i}^{\downarrow }f_{i})(x\in P_{\bot })={\begin{cases}\bigvee {}_{i}^{\downarrow }f_{i}(x),&x\neq \bot \\\bot ,&x=\bot .\end{cases}}$ Z drugiej strony: $\bigvee {}_{i}^{\downarrow }F(f_{i})(x)=\bigvee {}_{i}^{\downarrow }f_{i\bot }(x)={\begin{cases}\bigvee {}_{i}^{\downarrow }f_{i}(x),&x\neq \bot \\\bot ,&x=\bot .\end{cases}}$ A to oznacza, że $F$ jest ciągły w sensie Scotta, czyli lokalnie ciągły.

Znajdźmy więc punkt stały tego funktora, tj. rozwiążmy rekursywne równanie:

$X\cong X_{\bot }.$

Zaczynając od posetu jednoelementowego $\mathbf {1}$, mamy $\mathbf {1} _{\bot }=2$, itd. jak na rysunku (strzałkami zaznaczono projekcje, zanurzenia są oczywiste, nieprawdaż?):

Oczywiście, granicą tego diagramu są liczby naturalne z elementem największym:

Łatwo to zobaczyć, prawda?

==Zadanie 14.4==

Znajdź rozwiązanie równania:

$X=\mathbf {1} _{\bot }+X,$

gdzie $+$ jest koproduktem w kategorii $\mathbf {Dcpo} _{\bot }$.

Wskazówka:

Koprodukt w $\mathbf {Dcpo} _{\bot }$ nie może być oczywiście tylko sumą rozłączną, tak jak w $\mathbf {Set}$, ponieważ suma dwóch obiektów nie byłaby posetem z elementem najmniejszym. Ale łatwo pokazać, że koproduktem jest suma rozłączna, w którym dwa elementy najmniejsze identyfikujemy ze sobą:

Formalnie, na obiektach koprodukt jest zdefiniowany jako:

$P+Q:=\{(p,0)\mid p\in P\}\cup \{(q,1)\mid q\in Q\}$

wraz z zanurzeniami:

$i_{P}(x):={\begin{cases}(x,0)&x\in P\\\bot &x=\bot ,\end{cases}}$

$i_{Q}(x):={\begin{cases}(x,1)&x\in Q\\\bot &x=\bot .\end{cases}}$

Rozwiązanie:

Aby wykazać lokalną ciągłość koproduktu, trzeba pokazać, że odwzorowanie:

$(f\colon P\to R,g\colon Q\to S)\ \mapsto \ f+g\colon P+Q\to R+S$

jest ciągłe w sensie Scotta. To odwzorowanie ma typ:

$\mathrm {Hom} (P,R)\times \mathrm {Hom} (Q,S)\mapsto \mathrm {Hom} (P+Q,R+S),$

a zatem zgodnie z Lematem 13.2, wystarczy wykazać ciągłość ze względu na każdy argument z osobna. To sprowadza się do pokazania dwóch (analogicznych) równości, z których jedną z nich:

$f+\bigvee {}_{i}^{\downarrow }g_{i}=\bigvee {}_{i}^{\downarrow }(f+g_{i})$

dla dowolnego zbioru skierowanego $\{g_{i}\}$ funkcji ciągłych, wykażemy. Jest jasne, że:

$f+g={\begin{cases}(i_{R}\circ f)(x),&x\in P\\(i_{S}\circ g)(x),&x\in Q\\\bot ,&x=\bot .\end{cases}}$

A zatem:

$f+\bigvee {}_{i}^{\downarrow }g_{i}={\begin{cases}(i_{R}\circ f)(x),&x\in P\\(i_{S}\circ \bigvee {}_{i}^{\downarrow }g_{i})(x),&x\in Q\\\bot ,&x=\bot \end{cases}}={\begin{cases}(i_{R}\circ f)(x),&x\in P\\\bigvee {}_{i}^{\downarrow }(i_{S}\circ g_{i})(x),&x\in Q\\\bot ,&x=\bot \end{cases}}=\bigvee {}_{i}^{\downarrow }(f+g_{i}).$

Można powiedzieć, że $+$ jest lokalnie ciągły, bo wszystkie funkcje użyte w jego definicji są ciągłe w sensie Scotta.

Rozwiązaniem równania $X\cong \mathbf {1} _{\bot }+X$, jak widzimy na rysunku:

<flash>file=tk-14.21K.swf|width=400|height=200</flash>

są płaskie liczby naturalne $\mathbb {N} _{\bot }$.

==Zadanie 14.5==

Znaleźć rozwiązanie równania:

$X\cong \mathbf {1} \oplus X,$

gdzie $F(P,Q):=P\oplus Q$ jest sumą rozłączna $P$ i $Q$, do której dodany jest nowy element najmniejszy.

Wskazówka:

Oto przykład działania funktora sumy rozłącznej na obiektach:

Rozwiązanie:

Rozwiązaniem są leniwe liczby naturalne:

<flash>file=tk-14.19.swf|width=350|height=350</flash>

==Zadanie 14.6==

Rozwiązać równanie:

$X\cong X\oplus X.$

Rozwiązanie:

Rozwiązaniem jest nieskończone drzewo binarne (dziedzina $\Sigma ^{\infty }$ znana z Przykładu 12.12). Na animacji zaznaczono część projekcji.

<flash>file=tk-14.18.swf|width=500|height=300</flash>

==Zadanie 14.7==

Rozwiązać równanie:

$X\cong \mathbf {1} _{\bot }+(\mathbb {N} _{\bot }\otimes X),$

gdzie: $\mathbb {N} _{\bot }$ to znane z Zadania 14.4 płaskie liczby naturalne, zaś $F(P,Q):=P\otimes Q$ jest funktorem przypisującym dcpo $P$,$Q$ ich produkt zredukowany (ang. smash product) $P\otimes Q$. Produkt zredukowany jest ilorazem produktu $P\times Q$ przez relację równoważności $\equiv$, która identyfikuje ze sobą wszystkie elementy produktu, w których na choćby jednej współrzędnej znajduje się $\bot$.

Rozwiązanie:

Nie tak trudno zobaczyć, że $P\otimes Q$ jest koekwalizatorem dwóch projekcji $\pi _{P}\colon \equiv \to P\times Q$ i $\pi _{Q}\colon \equiv \to P\times Q$. Ten koekwalizator $[\cdot ]\colon P\times Q\to P\otimes Q$ jest więc ciągły w sensie Scotta, a co za tym idzie, dla $f\colon P\to R$ i $g\colon Q\to S$, funkcja:

$f\otimes g:=[(f\circ \pi _{P},g\circ \pi _{Q})]$

jak na rysunku:

jest ciągła w sensie Scotta. Dlatego też $F$ jest funktorem lokalnie ciągłym.

Rozwiązaniem równania:

$X\cong \mathbf {1} _{\bot }+(\mathbb {N} _{\bot }\otimes X)$ jest dziedzina skończonych i nieskończonych list liczb naturalnych. Elementy tej dziedziny różne od $\bot$ są albo listą pustą, albo listą skończoną, albo listą nieskończoną. Powyższe równanie należy intuicyjnie czytać jako: lista jest albo pusta, albo jest parą składającą się z liczby naturalnej i listy, albo jest niezdefiniowana. Czy Czytelnik to widzi?