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

From Studia Informatyczne

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

Grafika:tk-15.14.png

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

Grafika:tk-15.15.png

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

Grafika:tk-15.16.png

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

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:

Grafika:tk-15.17.png


==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_Bp_Bi^{-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:

Grafika:tk-15.18.png

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 15.3 o koindukcji.