==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
są identyczności w
. Rzeczywiście, dla dowolnego zbioru
diagram
komutuje, bo
, co wynika z faktu, że
jest funktorem. Po drugie, złożenie dwóch homomorfizmów
,
jest homomorfizmem
, co wynika z komutowania zewnętrznego prostokąta na poniższym diagramie i faktu, że
zachowuje złożenia:
.

Łą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
-algebra
jest początkowa.
Wskazówka:
Pokażemy, że dla dowolnej innej algebry
![{\displaystyle (X,[e,h])}](https://wazniak.mimuw.edu.pl/api/rest_v1/media/math/render/png/c9a46fa9385843c5dd18465f05445fb3e67554b9)
tego samego typu, istnieje dokładnie jeden homomorfizm algebr
![{\displaystyle f\colon (\mathbb {N} ,[0,s])\to (X,[e,h])}](https://wazniak.mimuw.edu.pl/api/rest_v1/media/math/render/png/7d6333329e12db949173c86bc8ef110430473650)
.
Rozwiązanie:
Musimy znaleźć taką funkcję
, aby diagram
komutował, czyli muszą być spełnione dwa równania:

dla dowolnego

. Widzimy, że

,

,

, i tak dalej, co prowadzi nas do definicji

jako iteracji

: bierzemy

. Ta definicja zapewnia, że

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

i

, to

, ...,

i z twierdzenia o indukcji na liczbach naturalnych dostajemy

. (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
.
Wskazówka:
Zamiast funkcji dwóch argumentów

, zdefiniujmy jej kuryfikację

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

-algebry na

.
==Zadanie 15.4==
Pokaż, że dla koalgebr
,
, funkcja
jest homomorfizmem wtedy i tylko wtedy, gdy jej graf
jest bisymulacją.
Rozwiązanie:
Niech
,
będą projekcjami
na odpowiednio pierwszą i drugą współrzędną. Jeśli
jest bisymulacją, to projekcje są bijektywnymi homomorfizmami, czyli, co łatwo zauważyć, ich odwrotności
też są homomorfizmami, np.:
. Ponieważ złożenie homomorfizmów jest homomorfizmem, a
, to
jest homomorfizmem.
Odwrotnie, niech
będzie homomorfizmem
-koalgebr. Wtedy
jest
-koalgebrą i to taką, że
jest homomorfizmem. Ale
również jest homomorfizmem, o czym przekonuje nas poniższa równość (opuszczamy symbol złożenia dla zwięzłości zapisu):

To kończy dowód.
==Zadanie 15.5==
Niech
. Wskaż bisymulacje między
-koalgebrami
i
.
==Zadanie 15.6==
Udowodnij, że: (a) przekątna
jest bisymulacją na
; (b) relacja odwrotna do bisymulacji jest bisymulacją.
==Zadanie 15.7==
Zdefiniuj koindukcyjnie dwie operacje
,
na nieskończonych listach, tak aby:
Rozwiązanie:
To bardzo proste zadanie. Funkcja
powstaje jako jedyny homomorfizm, który sprawia, że poniższy diagram komutuje:

zaś funkcja

to

.
==Zadanie 15.8==
Udowodnij koindukcyjnie, że dla funkcji
,
,
zdefiniowanych podczas wykładu zachodzi równość:
Wskazówka:
Jak zwykle spróbujmy zacząć, definiując relację:
Po pierwsze, mamy:
Po drugie, sprawdzamy że:

ale ta para nie jest w

! A zatem należy trochę sprytniej zdefiniować

. Jak?
Rozwiązanie:
O, tak:
Pozostaje teraz sprawdzić warunki bisymulacji dla nowo wprowadzonych do
par. Oto potrzebne kroki:
oraz

A więc

jest bisymulacją, a co za tym idzie, teza zadania jest udowodniona, gdy zaaplikujemy
Twierdzenie 15.3 o koindukcji.