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

\begin{diagram} X & \rTo^{1_X} & X\\ \dTo^{a} & & \dTo_{a}\\ TX & \rTo_{T1_X} & TX\\ \end{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\circ (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)$.

\begin{diagram} X & \rTo^{f} & Y & \rTo^{g} & Z\\ \dTo^{a} & & \dTo_{b} & & \dTo_{c}\\ TX & \rTo_{Tf} & TY & \rTo_{Tg} & TZ\\ \end{diagram}

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

\begin{diagram} \mathbf{1} +\mathbb{N} & \rTo^{1_{\mathbf{1}} + f} & \mathbf{1} +X\\ \dTo^{[0,s]} & & \dTo_{[e,h]}\\ \mathbb{N} & \rDotsto_{f} & X\\ \end{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$ i $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}$, którą znamy z Wykładu ???:

$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:

\begin{diagram} \mathbf{1} +\mathbb{N} & & \rTo^{1_{\mathbf{1}} + \mathtt{plus}} & \mathbf{1} +\mathbb{N}^{\mathbb{N}}\\ \dTo^{[0,s]} & & & \dTo_{[\lambda fx.x,\lambda fx.s(f(x))]}\\ \mathbb{N} & & \rDotsto_{\mathtt{plus}} & \mathbb{N}^{\mathbb{N}}\\ \end{diagram}

==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  ? 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  ?.

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  ?.

(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:

${\mathtt {par}}(\sigma ):=(\sigma (0),\sigma (2),\sigma (4),...),$

${\mathtt {npar}}(\sigma ):=(\sigma (1),\sigma (3),\sigma (5),...).$

Rozwiązanie:

To bardzo proste zadanie. Funkcja ${\mathtt {npar}}$ powstaje jako jedyny homomorfizm, który sprawia, że poniższy diagram komutuje:

\begin{diagram} A^{\omega} & \rTo^{\mathtt{npar}} & & A^{\omega}\\ \dTo^{\lambda x.(o(x),t(t(x)))} & & &\dTo_{(o,t)}\\ A\times A^{\omega} & \rTo_{1_A\times \mathtt{npar}} & & A\times A^{\omega}\\ \end{diagram}

zaś funkcja ${\mathtt {par}}$ to ${\mathtt {par}}:={\mathtt {npar}}\circ t$.

==Zadanie 15.8==

Udowodnij koindukcyjnie, że dla funkcji ${\mathtt {zip}}$, ${\mathtt {par}}$, ${\mathtt {npar}}$ zdefiniowanych podczas wykładu zachodzi równość:

${\mathtt {zip}}({\mathtt {par}}(\sigma ),{\mathtt {npar}}(\sigma ))=\sigma .$

Wskazówka:

Jak zwykle spróbujmy zacząć definiując relację

$R:=\{({\mathtt {zip}}({\mathtt {par}}(\sigma ),{\mathtt {npar}}(\sigma )),\sigma )\mid \sigma \in A^{\omega }\}.$

Po pierwsze, mamy:

${\mathtt {zip}}({\mathtt {par}}(\sigma ),{\mathtt {npar}}(\sigma ))(0)={\mathtt {par}}(\sigma )(0)=\sigma (0).$

Po drugie, sprawdzamy że: \aligned (\mathtt{zip}(\mathtt{par}(\sigma),\mathtt{npar}(\sigma))',\sigma ') &=& (\mathtt{zip}(\mathtt{npar}(\sigma),\mathtt{par}(\sigma)'),\sigma ')\\ &=& (\mathtt{zip}(\mathtt{npar}(\sigma),\mathtt{par}(\sigma)),\sigma ') \endaligned

ale ta para nie jest w $R$! A zatem należy trochę sprytniej zdefiniować $R$. Jak?

Rozwiązanie:

O tak:

$R:=\{({\mathtt {zip}}({\mathtt {par}}(\sigma ),{\mathtt {npar}}(\sigma )),\sigma )\mid \sigma \in A^{\omega }\}\cup \{({\mathtt {zip}}({\mathtt {npar}}(\sigma ),{\mathtt {par}}(\sigma '')),\sigma ')\mid \sigma \in A^{\omega }\}.$

Pozostaje teraz sprawdzić warunki bisymulacji dla nowo wprowadzonych do $R$ par. Oto potrzebne kroki:

${\mathtt {zip}}({\mathtt {npar}}(\sigma ),{\mathtt {par}}(\sigma ''))(0)={\mathtt {npar}}(\sigma )(0)=\sigma '(0)$

oraz \aligned (\mathtt{zip}(\mathtt{npar}(\sigma),\mathtt{par}(\sigma))',\sigma ) &=& (\mathtt{zip}(\mathtt{par}(\sigma ),\mathtt{npar}(\sigma)'),\sigma )\\ &=& (\mathtt{zip}(\mathtt{par}(\sigma ),\mathtt{npar}(\sigma)),\sigma )\in R. \endaligned

A więc $R$ jest bisymulacją, a co za tym idzie teza zadania jest udowodniona, gdy zaaplikujemy Twierdzenie  ? o koindukcji.