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

From Studia Informatyczne

==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 G\subseteqdir D, 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 G\subseteqdir D 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

Grafika:tk-14.7.png
to
Grafika:tk-14.12.png

komutuje. W szczególności

Grafika:tk-14.13.png

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

Grafika:tk-14.14.png

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{}^\downarrow_i f_i. Wówczas: F(\bigvee{}^\downarrow_i f_i)(x\in P_{\bot}) =  \begin{cases} \bigvee{}^\downarrow_i f_i(x), & x\neq \bot\\ \bot , & x=\bot. \end{cases} Z drugiej strony: \bigvee{}^\downarrow_i F(f_i)(x) =  \bigvee{}^\downarrow_i f_{i\bot}(x) = \begin{cases}  \bigvee{}^\downarrow_i 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ż?):

Grafika:tk-14.15.png

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

Grafika:tk-14.16.png

Ł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ą:

Grafika:tk-14.20.png

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{}^\downarrow_i g_i =  \bigvee{}^\downarrow_i (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{}^\downarrow_i g_i = \begin{cases}  (i_R\circ f)(x),& x\in P\\ (i_S\circ \bigvee{}^\downarrow_i  g_i)(x), & x\in Q\\ \bot,& x=\bot \end{cases} = \begin{cases}  (i_R\circ f)(x),& x\in P\\ \bigvee{}^\downarrow_i (i_S\circ  g_i)(x), & x\in Q\\ \bot,& x=\bot  \end{cases} = \bigvee{}^\downarrow_i (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>

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:

Grafika:tk-14.17.png

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:

Grafika:tk-14.22.png

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?