Teoria kategorii dla informatyków/Ćwiczenia 15: Algebry i koalgebry endofunktorów

==Zadanie 15.1==

Udowodnij, że koalgebry i ich homomorfizmy tworzą kategorię.

Rozwiązanie:

Musimy wskazać brakujące elementy definicji podanej podczas wykładu. Po pierwsze, identycznościami w $\mathbf {Set} _{T}$ są identyczności w $\mathbf {Set}$ . Rzeczywiście, dla dowolnego zbioru $X$ diagram

komutuje, bo $T1_{X}=1_{TX}$ , co wynika z faktu, że $T$ jest funktorem. Po drugie, złożenie dwóch homomorfizmów $f\colon (X,a)\to (Y,b)$ , $g\colon (Y,b)\to (Z,c)$ jest homomorfizmem $g\colon (X,a)\to (Z,c)$ , co wynika z komutowania zewnętrznego prostokąta na poniższym diagramie i faktu, że $T$ zachowuje złożenia: $T(g\circ f)=T(G)\circ T(f)$ .

Łączność złożenia jest teraz oczywista, jak również to, że złożenia z identycznościami spełniają wymagane aksjomaty.

==Zadanie 15.2==

Udowodnij, że $\mathbf {1} +(-)$ -algebra $(\mathbb {N} ,[0,s])$ jest początkowa.

Wskazówka:

Pokażemy, że dla dowolnej innej algebry

(X,[e,h])

tego samego typu, istnieje dokładnie jeden homomorfizm algebr

f\colon (\mathbb {N} ,[0,s])\to (X,[e,h])

Rozwiązanie:

Musimy znaleźć taką funkcję $f\colon \mathbb {N} \to X$ , aby diagram

komutował, czyli muszą być spełnione dwa równania:

f(0)=e\ \ \ \ f(n+1)=h(f(n))

dla dowolnego

n\in \mathbb {N}

. Widzimy, że

f(0)=h^{0}(e)

f(1)=h(e)

f(2)=h^{2}(e)

, i tak dalej, co prowadzi nas do definicji

f

jako iteracji

h

: bierzemy

f(n):=h^{n}(e)

. Ta definicja zapewnia, że

f

jest homomorfizmem. Wykażemy teraz, że taki homomorfizm jest tylko jeden. Jeśli bowiem dla pewnego innego homomorfizmu mielibyśmy

g(0)=e

g(n+1)=h(g(n))

, to

g(0)=e=f(0)

, ...,

g(n+1)=h(g(n))=h^{n+1}(e)=f(n+1)

i z twierdzenia o indukcji na liczbach naturalnych dostajemy

g=f

. (Zwróćmy też uwagę, że jedyność homomorfizmu sprawiającego, że powyższy diagram komutuje, nie tylko wynika z twierdzenia o indukcji dla liczb naturalnych, ale to twierdzenie implikuje.) To kończy dowód.

==Zadanie 15.3==

Zdefiniować dodawanie liczb naturalnych przez indukcję, korzystając z początkowości algebry $(\mathbb {N} ,[0,s])$ .

Wskazówka:

Zamiast funkcji dwóch argumentów

p\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N}

, zdefiniujmy jej kuryfikację

{\mathtt {plus}}=\mathrm {curry} (p)\colon \mathbb {N} \to \mathbb {N} ^{\mathbb {N} }

. Rozwiązanie zadania będzie od nas wymagało stworzenia struktury

\mathbf {1} +(-)

-algebry na

\mathbb {N} ^{\mathbb {N} }

Rozwiązanie:

Po pierwsze, oto standardowa definicja dodawania $p\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N}$ :

p(m,0):=m\ \ \ \ \ p(m,n+1):=s(p(m,n)).

Jej kuryfikacja to:

{\mathtt {plus}}(0):=\lambda x.x\ \ \ \ \ p(n+1):=\lambda x.s({\mathtt {plus}}(n)(x)).

Teraz już jest oczywiste, że ${\mathtt {plus}}$ jest jedyną funkcją, która spełnia:

==Zadanie 15.4==

Pokaż, że dla koalgebr $(S,\alpha )$ , $(T,\beta )$ , funkcja $f\colon S\to T$ jest homomorfizmem wtedy i tylko wtedy, gdy jej graf $G(f)\subseteq S\times T$ jest bisymulacją.

Rozwiązanie:

Niech $\pi _{1}$ , $\pi _{2}$ będą projekcjami $G(f)$ na odpowiednio pierwszą i drugą współrzędną. Jeśli $(G(f),\gamma )$ jest bisymulacją, to projekcje są bijektywnymi homomorfizmami, czyli, co łatwo zauważyć, ich odwrotności $\pi _{1}^{-1},\pi _{2}^{-1}$ też są homomorfizmami, np.: $\pi _{1}^{-1}\colon (S,\alpha )\to (G(f),\gamma )$ . Ponieważ złożenie homomorfizmów jest homomorfizmem, a $f=\pi _{2}\circ \pi _{1}^{-1}$ , to $f$ jest homomorfizmem.

Odwrotnie, niech $f\colon S\to T$ będzie homomorfizmem $T$ -koalgebr. Wtedy

(G(f),T(\pi _{1})^{-1}\circ \alpha \circ \pi _{1})

jest $T$ -koalgebrą i to taką, że $\pi _{1}$ jest homomorfizmem. Ale $\pi _{2}$ również jest homomorfizmem, o czym przekonuje nas poniższa równość (opuszczamy symbol złożenia dla zwięzłości zapisu):

T(\pi _{2})(T(\pi _{1})^{-1}\alpha \pi _{1})=T(\pi _{2}\pi _{1}^{-1})\alpha \pi _{1}=(T(f)\alpha )\pi _{1}=\beta f\pi _{1}=\beta \pi _{2}.

To kończy dowód.

==Zadanie 15.5==

Niech $F(-)={\mathcal {P}}(A\times (-))$ . Wskaż bisymulacje między $F$ -koalgebrami $(S,\alpha _{S})$ i $(T,\alpha _{T})$ .

Wskazówka:

Pokaż, że bisymulacją między $S$ i $T$ jest relacja $R\subseteq S\times T$ posiadająca dla wszystkich $(s,t)\in R$ dwie własności:

dla każdego $s'\in S$ , jeśli $s{\stackrel {a}{\longrightarrow }}s'$ , to istnieje $t'\in T$ takie, że $t{\stackrel {a}{\longrightarrow }}t'$ i $(s',t')\in R$ ,
dla każdego $t'\in T$ , jeśli $t{\stackrel {a}{\longrightarrow }}t'$ , to istnieje $s'\in S$ takie, że $s{\stackrel {a}{\longrightarrow }}s'$ i $(s',t')\in R$ .

Rozwiązanie:

Niech więc $(R,\alpha _{R}\colon R\to FR)$ będzie bisymulacją. Koalgebra $\alpha _{R}$ indukuje relację przejścia $\longrightarrow _{R}\subseteq R\times A\times R$ w znany z Przykładu 15.9 sposób. Niech $(s,t)\in R$ i przypuśćmy, że $s{\stackrel {a}{\longrightarrow }}s'$ . Ponieważ $s=\pi _{1}(s,t)$ , to $\pi _{1}(s,t){\stackrel {a}{\longrightarrow }}s'$ , a ponieważ $\pi _{1}$ jest homomorfizmem, istnieje $(s'',t')\in R$ z $(s,t){\stackrel {a}{\longrightarrow _{R}}}(s'',t')$ i $\pi _{1}(s'',t')=s'$ . A zatem $(s',t')\in R$ . Ponieważ zaś $\pi _{2}$ jest homomorfizmem, dostajemy $t{\stackrel {a}{\longrightarrow }}t'$ , co dowodzi pierwszej własności ze Wskazówki. Drugą dowodzimy analogicznie.

Odwrotnie, przypuśćmy że $R\subseteq S\times T$ jest dowolną relacją, która ma dwie własności ze Wskazówki. Definiując $\alpha _{R}\colon R\to FR$ dla dowolnej pary $(s,t)\in R$ jako

\alpha _{R}(s,t):=\{(s',t')\in R\mid s{\stackrel {a}{\longrightarrow }}s'\ \mathrm {oraz} \ t{\stackrel {a}{\longrightarrow }}t'\},

widzimy natychmiast na podstawie własności ze wskazówki, że projekcje są homomorfizmami. A zatem

(R,\alpha _{R})

jest bisymulacją.

==Zadanie 15.6==

Udowodnij, że: (a) przekątna $\Delta _{A}\subseteq A\times A$ jest bisymulacją na $(A,\alpha )$ ; (b) relacja odwrotna do bisymulacji jest bisymulacją.

Wskazówka:

Do (a) wykorzystaj Zadanie 15.4.

Rozwiązanie:

(a) Przekątna $\Delta _{A}$ jest oczywiście grafem identyczności $1_{A}$ , który jest homomorfizmem. A zatem $\Delta _{A}$ jest bisymulacją na podstawie Zadania 15.4.

(b) Niech $(R,\alpha _{R})$ będzie bisymulacją między $(A,\alpha _{A})$ i $(B,\alpha _{B})$ . Oznaczmy przez $\pi _{B}\colon R^{-1}\to B$ , $\pi _{A}\colon R^{-1}\to A$ odpowiednie projekcje dla $R^{-1}$ , zaś przez $p_{B}\colon R\to B$ , $p_{A}\colon R\to A$ odpowiednie projekcje dla $R$ . Niech $i\colon R\to R^{-1}$ będzie izomorfizmem, który posyła $(s,t)\in R$ w $(t,s)\in R^{-1}$ . Wówczas $(R^{-1},T(i)\circ \alpha _{R}\circ i^{-1})$ jest bisymulacją między $B$ i $A$ . Po pierwsze, typem $T(i)\circ \alpha _{R}\circ i^{-1}$ jest $R^{-1}\to TR^{-1}$ . Po drugie, mamy:

T(\pi _{B})(T(i)\alpha _{R}i^{-1})=T(\pi _{B}i)\alpha _{R}i^{-1}=(T(p_{B})\alpha _{R})i^{-1}=\alpha _{B}p_{B}i^{-1}=\alpha _{B}\pi _{B}

i analogicznie dla drugiej projekcji. To kończy dowód.

==Zadanie 15.7==

Zdefiniuj koindukcyjnie dwie operacje ${\mathtt {par}}\colon A^{\omega }\to A^{\omega }$ , ${\mathtt {npar}}\colon A^{\omega }\to A^{\omega }$ na nieskończonych listach, tak aby: