Teoria kategorii dla informatyków/Ćwiczenia 14: Równania rekurencyjne

==Zadanie==

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, wiec 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==

Udowodnić Lemat ?.

Rozwiązanie:

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

Plik:Tk 14 7.png 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 ?, rozszerza się do funktora ciągłego, a zatem Lemat ? 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==

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, ze $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{}^\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ż?):

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

Łatwo to zobaczyć, prawda?

==Zadanie==

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 ?, 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.21.swf|width=400|height=200</flash>

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

==Zadanie==

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.

Rozwiązanie:

Rozwiązaniem są leniwe liczby naturalne:

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

==Zadanie==

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 ?). Na animacji zaznaczono część projekcji.

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

==Zadanie==

Rozwiązać równanie

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

gdzie: $\mathbb {N} _{\bot }$ to znane z Zadania  ? płaskie liczby naturalne, zaś $F(P,Q):=P\otimes Q$ jest funktorem przypisującym dcpo </math>P</math>,</math>Q</math> 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 listy 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?