Teoria kategorii dla informatyków/Ćwiczenia 1: Teoria kategorii jako abstrakcyjna teoria funkcji

==Zadanie 1.1==

Udowodnij, że dla dwóch funkcji $f\colon A\to B$ oraz $g\colon B\to A$, jeśli $f\circ g=1_{B}$ oraz $g\circ f=1_{A}$, to funkcja $f$ jest bijekcją.

Rozwiązanie:

Pokażemy najpierw, że $f$ jest funkcją różnowartościową. Przypuśćmy, że $f(x)=f(y)$ dla pewnych elementów $x,y\in A$. Wówczas $x=1_{A}(x)=(g\circ f)(x)=g(f(x))=g(f(y))=(g\circ f)(y)=1_{A}(y)=y$. Ponadto, dla dowolnego $z\in B$, element $g(z)$ jest jedynym takim elementem, że $f(g(z))=z$, co w szczególności oznacza, że $f$ jest surjekcją. Wnioskujemy więc, że $f$ jest różnowartościową surjekcją, czyli bijekcją.

==Zadanie 1.2==

Udowodnij Fakt 1.2.

Wskazówka:

Fakt, że liczby naturalne posiadają własność wspomnianą w Fakcie 1.2 jest dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie implikacji przeciwnej.

Rozwiązanie:

Załóżmy zatem, że $N$ jest pewnym zbiorem, który posiada wyróżniony element $0\in N$ i funkcję $s\colon N\to N$ spełniającą warunki zadania. Udowodnimy po kolei następujące zdania (znane jako aksjomaty Peano), które - zgodnie z wykładnią teorii mnogości - w sposób jednoznaczny determinują liczby naturalne spośród innych zbiorów, a co za tym idzie, potwierdzą, że zbiór $N$ jest zbiorem liczb naturalnych:

Giuseppe Peano (1858-1932)
Zobacz biografię

• $\exists 0\in N.$

To wiemy z założenia.

• $\forall n\in N\ s(n)\in N.$

To wiemy z założenia.

• $\forall n\in N\ s(n)\neq 0.$

Przypuśćmy przeciwnie, że dla pewnego $n\in N$ mamy $s(n)=0$. Wtedy, kładąc $X=\{e,a\}$ oraz $g(e)=g(a)=a$, z założenia istnieje funkcja $f\colon N\to X$ taka, że $f(0)=e$ oraz $f(s(n))=g(f(n))$. A zatem $f(s(n))=f(0)=e\neq a=g(f(n))$, sprzeczność.

• $s$ jest injekcją.

Przypuśćmy, że $s(n)=s(m)$ dla pewnych $n,m\in N$. Kładąc $X:=\{0,s(0),s(s(0)),...\}$ (jest to podzbiór $N$) oraz $e:=0$, wiemy, że istnieje funkcja $f\colon N\to X$ taka, że $f(0)=0$ oraz $f(s(n))=s(f(n))$. Taka funkcja jest tylko jedna, więc jej zawężenie do $X$ musi być równe funkcji $h\colon X\to X$, która spełnia warunki $h(0)=0$ oraz $h(s(n))=n$ dla $n\neq 0$. Dlatego założenie $s(n)=s(m)$ implikuje $n=h(s(n))=h(s(m))=m$, co należało pokazać.

• $\forall A\subseteq N\ ((0\in A\wedge (a\in A\implies s(a)\in A))\implies A=N).$

W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe, a potem skorzystamy z okazji, aby ten sam dowód pokazać bardziej w duchu teorii kategorii (stopniowo ten drugi rodzaj dowodów będzie zastępował pierwszy).

Rozważmy zatem funkcję $s'\colon A\to A$, która - będąc obcięciem $s$ do $A$ - spełnia warunek $s\circ i=i\circ s'$, gdzie $i\colon A\to N$ jest inkluzją $A$ w $N$. Zgodnie z założeniem zadania, dla funkcji $s'$ istnieje dokładnie jedna funkcja $f\colon N\to A$ taka, że $f(0)=0$ oraz $s'\circ f=f\circ s$. Łącząc tą równość z poprzednią, dostajemy $s\circ i\circ f=i\circ f\circ s$. Zwróćmy teraz uwagę na funkcję $i\circ f\colon N\to N$. Oczywiste spostrzeżenie, że $i\circ f(0)=0$ pozwala nam stwierdzić, że $i\circ f$ jest jedyną funkcją typu $N\to N$, która spełnia ostatnią z równości. Skoro tak, to musi być równa identyczności na $N$. Pokazaliśmy więc, że $i\circ f=1_{N}$, a stąd - jak łatwo pokazać - wynika, że $f\colon N\to A$ jest injekcją. A zatem $N\subseteq A$, co należało wykazać.

Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru $N$, a zatem teoria mnogości uczy nas, że $N$ jest zbiorem liczb naturalnych nat.

Dowód ostatniego z aksjomatów Peano prowadzony w duchu teorii kategorii, czyli teorii przekształceń, korzysta z dobrodziejstwa, jakim jest możliwość przedstawiania funkcji i ich złożeń na diagramach.

Po pierwsze, spróbujmy przedstawić graficznie (na diagramach) założenia, które mamy, tzn. zdanie: $N$ jest zbiorem, który posiada wyróżniony element $0$ oraz funkcję $s\colon N\to N$ takie, że dla dowolnego innego zbioru $X$ i elementu $e\in X$ oraz funkcji $g\colon X\to X$ istnieje dokładnie jedna funkcja $f\colon N\to X$ spełniająca warunki $f(0)=e$ oraz $f\circ s=g\circ f$.

Zauważmy więc, że element $0\in N$ może być zawsze traktowany jako funkcja $0\colon \top \to N$, gdzie $\top$ jest dowolnym zbiorem jednoelementowym (zwróćmy uwagę, że w tej interpretacji aplikacja funkcji staje się złożeniem, np. $f(0)$ staje się złożeniem $f\circ 0$). Podobnie dla $e\in X$. Po drugie, wszelkie równości pomiędzy funkcjami przedstawiamy jako komutowanie odpowiedniego diagramu, np. równość $f\circ s=g\circ f$ zachodzi wtedy i tylko wtedy, gdy poniższy diagram komutuje:

Następnie umawiamy się, że jeśli funkcja w diagramie jest jedyną, która może znajdować się pomiędzy dwoma danymi obiektami, to zaznaczamy ją przerywaną linią, np. zdanie ...$f\colon N\to X$ jest jedyną funkcją taką, że... odzwierciedla się graficznie jako:

Jeśli diagram jest bardziej skomplikowany, to umawiamy się, że odczytujemy wszystkie możliwe równania, przy czym umawiamy się, że nie musimy rysować identyczności. A zatem diagram:

komutuje wtedy i tylko wtedy, gdy $0\in N$, $e\in X$, $f(0)=e$, $f\circ s=g\circ f$, $(f\circ s)(0)=g(e)$ (ten wniosek wynika z czterech pozostałych!) i $f$ jest jedyną taką funkcją, która spełnia wszystkie wymienione zależności. Tak więc powyższy diagram zawiera całą informację dostępną w założeniach zadania. Przystąpmy więc do kategoryjnego dowodu ostatniego aksjomatu Peano. Oto on: skoro diagram

komutuje, co możemy przedstawić również w skrócie jako:

jak również komutuje diagram:

to z warunku jednoznaczności istnienia funkcji dostajemy $i\circ f=1_{N}$. To jednak implikuje, że $f$ jest injekcją, czyli $N\subseteq A$, co należało pokazać.

Jak zobaczymy w toku wykładu, dowody poprzez pokazanie komutujących diagramów (czyli de facto wyeksplikowanie pewnych równości między funkcjami – czy też ogólniej: morfizmami) są bardzo często spotykane w teorii kategorii, a nawet zastępują wszelkie inne dowody

==Zadanie 1.3==

Znajdź przykład na to, że w kategorii Pos bijekcje nie zawsze są izomorfizmami.

Wskazówka:

Wystarczy rozważyć częściowe porządki dwuelementowe.

Rozwiązanie:

Rozważmy dwa posety dwuelementowe $P=\{x,y\}$, $Q=\{z,w\}$ i funkcję $g\colon Q\to P$, $g(z)=x,g(w)=y$, jak na rysunku:

Funkcja $g$ jest oczywiście bijekcją, ale funkcja do niej odwrotna nie jest monotoniczna, a zatem nie jest morfizmem w Pos. To oznacza, że $g$ nie może być izomorfizmem.

==Zadanie 1.4==

Pokaż, że każda grupa może być traktowana jako kategoria, w której każdy morfizm jest izomorfizmem.

Rozwiązanie:

Niech $(G,\circ ,e)$ będzie grupą. Podobnie jak w przypadku monoidów, deklarujemy $G$ jako jedyny obiekt pewnej kategorii, zaś elementy zbioru $G$ jako morfizmy tejże kategorii, działanie $\circ$ jako złożenie morfizmów, element $e$ traktując jako identyczność na obiekcie $G$. Zauważmy, że każdy element posiada element odwrotny, czyli dla każdego $g\in G$ istnieje $g^{-1}\in G$ tak, że $g\circ g^{-1}=e=g^{-1}\circ g$. Te równania interpretowane w naszej kategorii czynią tenże dowolnie wybrany element $g$ izomorfizmem.

==Zadanie 1.5==

Dla dowolnej kategorii $\mathbf {C}$ zaproponuj konstrukcję nowej kategorii, w której – żądamy – obiektami są morfizmy z $\mathbf {C}$.

Wskazówka:

Niech $\mathbf {C}$ będzie dowolną kategorią; dla dwóch jej dowolnych morfizmów $f\colon A\to B$ oraz $g\colon C\to D$, musimy zaproponować taką operację, dla której $f$ jest dziedziną i $g$ jest kodziedziną. Gdyby przedstawić to graficznie, w postaci diagramu, łatwo przyjdzie nam na myśl definicja takiej operacji: będzie to para morfizmów $(a\colon A\to C,b\colon B\to D)$ z kategorii $\mathbf {C}$ taka, że poniższy diagram komutuje:

Teraz już łatwo dopowiedzieć szczegóły konstrukcji.

Rozwiązanie:

Zaproponujemy najpierw złożenie: dwa morfizmy $(a,b)$ oraz $(c,d)$ jak poniżej:

składają się tak:

albo formalnie: $(a,b)\circ (c,d)=(a\circ c,b\circ d)$. Oczywiście $\mathrm {(} (a\circ c,b\circ d))=h$ oraz $\mathrm {(} (a\circ c,b\circ d))=g$. W końcu, identycznościami w nowej kategorii, którą często oznacza się jako $\mathbf {C} ^{\to }$ są pary identyczności z kategorii $\mathbf {C}$. Wszelkie pozostałe czynności, które musimy wykonać, by sprawdzić, że $\mathbf {C}$ jest kategorią, są trywialne.

==Zadanie 1.6==

Niech $\mathbf {C}$ będzie kategorią, zaś $A\in \mathbf {C} _{0}$ jej ustalonym obiektem. Zaproponuj konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z $\mathbf {C}$ o kodziedzinie $A$.

Wskazówka:

Wykorzystaj Zadanie 1.5

Rozwiązanie:

Tak jak w Zadaniu1.5 morfizmami nowej kategorii, oznaczanej często $\mathbf {C} /A$ i nazywanej $A$-warstwą $\mathbf {C}$, są komutujące diagramy: ponieważ wszystkie obiekty $\mathbf {C} /A$ jako morfizmy $\mathbf {C}$ mają wspólną kodziedzinę, więc możemy przyjąć, że morfizmami są komutujące trójkąty:

albo formalnie: jeśli $f\colon B\to A$ oraz $g\colon C\to A$ są obiektami $\mathbf {C} /A$, to morfizmem o dziedzinie $f$ i kodziedzinie $g$ jest morfizm $h\colon B\to C$ z $\mathbf {C} /A$ taki, że powyższy diagram komutuje. Sprawdzenie, że $\mathbf {C} /A$ jest kategorią jest już trywialne.

==Zadanie 1.7==

Udowodnij, że złożenie izomorfizmów jest izomorfizmem, że morfizm odwrotny do izomorfizmu jest tylko jeden, a także, że identyczności w dowolnej kategorii są izomorfizmami.

Rozwiązanie:

Pokażmy najpierw, że złożenie izomorfizmów jest izomorfizmem. Załóżmy, że $f\colon A\to B$ oraz $g\colon B\to C$ są izmorfizmami. Wówczas ich złożenie $g\circ f\colon A\to C$ posiada morfizm odwrotny $f^{-1}\circ g^{-1}$. Rzeczywiście, $(g\circ f)\circ (f^{-1}\circ g^{-1})=g\circ )f\circ f^{-1})\circ g^{-1}=g\circ 1_{B}\circ g^{-1}=g\circ g^{-1}=1_{C}$ i podobnie pokazujemy drugie z równań dla izomorfizmu.

Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, iż $f$ jest izomorfizmem z odwrotnością $f^{-1}$ jest wyrażony przez fakt, że poniższy diagram komutuje:

(Przypomnijmy sobie umowę z Zadania 1.2, że nie rysujemy identyczności.)

Podobnie, diagram:

komutuje, a co za tym idzie, złożenie tych dwóch diagramów komutuje:

To zaś kończy dowód faktu, że $f^{-1}\circ g^{-1}$ jest odwrotnością $g\circ f$.

Po drugie, pokażmy, że morfizm odwrotny do izmorfizmu jest tylko jeden: załóżmy przeciwnie, że dla pewnego izomorfizmu $f\colon A\to B$ istnieją dwie odwrotności $g,h\colon B\to A$. Wówczas $g=g\circ 1_{B}=g\circ (f\circ h)=(g\circ f)\circ h=1_{A}\circ h=h$, co należało pokazać.

Po trzecie, niech $A$ będzie dowolnym obiektem dowolnej kategorii. Identyczność $1_{A}$ spełnia oczywiście (z definicji kategorii) równanie $1_{A}=1_{A}\circ 1_{A}$, co świadczy o tym, że jest izomorfizmem.

==Zadanie 1.8==

Znajdź kategorię, która ma tę własność, że jeśli dwa obiekty są izomorficzne, to muszą być sobie równe.

Wskazówka:

Można wziąć pod uwagę te szczególne kategorie, w których istnieje co najwyżej jedna strzałka pomiędzy dowolnymi dwoma obiektami.

Rozwiązanie:

Niech $(P,\sqsubseteq )$ będzie częściowym porządkiem. Traktowany jako kategoria, posiada tę własność, że pomiędzy dwoma jego obiektami (elementami) istnieje co najwyżej jeden morfizm (w przypadku, gdy elementy te są w częściowym porządku). Niech $p,q$ będą obiektami izomorficznymi. W języku częściowych porządków oznacza to, że $p\sqsubseteq q$ i $q\sqsubseteq p$. Antysymetria relacji porządkującej daje nam $p=q$, co należało pokazać.

==Zadanie 1.9==

Pokaż, że w kategorii Mon izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.

Wskazówka:

Jedna z implikacji jest bardzo łatwa: jeśli $f$ jest izomorfizmem w Mon, to w szczególności jest morfizmem, czyli homomorfizmem monoidów. Równania dla $f$ jako izomorfizmu implikują, że $f$ jest też bijekcją, w dokładnie ten sam sposób, w jaki pokazaliśmy dla funkcji między zbiorami (patrz dyskusja po Fakcie 1.1). Wystarczy więc udowodnić implikację odwrotną.

Rozwiązanie:

Załóżmy, że $f\colon M\to N$ jest bijektywnym homomorfizmem z odwrotnością $g\colon N\to M$. Wystarczy pokazać, że $g$ jest homomorfizmem, tzn., że $g(e_{N})=e_{M}$ oraz $g(n_{1}\circ _{N}n_{2})=g(n_{1})\circ _{M}g(n_{2})$ dla dowolnych $n_{1},n_{2}\in N$. Wykorzystując fakt, że $f$ - jako homomorfizm - zachowuje jedynkę, mamy: $e_{M}=g(f(e_{M}))=g(e_{N})$, czyli pierwszą z szukanych równości. Znów, opierając się na własnościach $f$, mamy: $g(n_{1})\circ _{M}g(n_{2})=g(f(g(n_{1})\circ _{M}g(n_{2})))=g(f(g(n_{1}))\circ _{N}f(g(n_{2})))=g(n_{1}\circ _{N}n_{2})$, co należało pokazać.

==Zadanie 1.10==

Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy $\mathbf {Cat}$.

Wskazówka:

Przeczytaj najpierw Definicję 5.1, w której mówimy czym są funktory.

Rozwiązanie:

Najpierw definiujemy identyczności: dla dowolnej kategorii $\mathbf {C}$ proponujemy przekształcenie $1_{C}$ jako

$1_{\mathbf {C} }(A):=A$ $1_{\mathbf {C} }(f\colon A\to B):=f$

dla dowolnych $A\in \mathbf {C_{0}} ,f\in \mathbf {C_{1}}$. Wtedy oczywiście $1_{C}$ jest funktorem. Złożenie funktorów definiujemy w sposób naturalny, tak jak złożenie funkcji w $\mathbf {Set}$. Niech $F\colon \mathbf {C} \to \mathbf {D}$, $G\colon \mathbf {D} \to \mathbf {A}$, $H\colon \mathbf {A} \to \mathbf {B}$ będą funktorami.

$(1_{D}\circ F)(A)=1_{D}(F(A))=F(A)=F(1_{C})(A)=(F\circ 1_{C})(A)$

dla $A\in \mathbf {C_{0}}$ i taki sam dowód działa dla morfizmów. Wnioskujemy więc, że:

$1_{D}\circ F=F=F\circ 1_{C}.$

Ponadto:

$H\circ (G\circ F)(-)=H((G\circ F)(-))=H(G(F(-)))=(H\circ G)(F(-))=((H\circ G)\circ F)(-),$

gdzie $(-)$ oznacza miejsce, w które można wstawić obiekt lub morfizm z $\mathbf {C}$ – taka konwencja notacyjna będzie często używana w przyszłości. A zatem wnioskujemy, że złożenie funktorów jest łączne.

==Zadanie 1.11==

Podaj dwa dalsze przykłady kategorii.

Wskazówka:

Najprościej zdefiniować nowe kategorie poprzez modyfikację istniejących przykładów (np. kategorię tworzą zbiory i funkcje częściowe). Nasz drugi przykład jest tego typu: jako język funkcyjny bierzemy $\lambda$-rachunek i tworzymy dla niego kategorię, tak jak opisaliśmy to w jednym z ostatnich przykładów podanych podczas wykładu.

Rozwiązanie:

Przykład pierwszy: Automaty. Niech $M=(M,*,e)$ będzie monoidem. Definiujemy $M$-automat jako parę $(S,\delta )$ składającą się ze zbioru stanów $S$ i funkcji przejścia $\delta \colon M\times S\to S$ tak, że:

$\delta (x*y,s):=\delta (x,\delta (y,s))$,

$\delta (e,s)=s$

dla dowolnych $x,y\in M$, $s\in S$. Morfizmem $M$-automatów $(S,\delta )$, $(Z,\eta )$ jest funkcja $f\colon S\to Z$ taka, że $f(\delta (x,s))=\eta (x,f(s))$. Sprawdzenie, że taka struktura jest kategorią jest oczywiste, nieprawdaż?

Drugi przykład: Rachunek lambda. Rozważamy prosty rachunek $\lambda$ z typami. ($\lambda$-rachunek jest formalizmem pozwalającym na wygodną manipulację funkcjami. Umożliwia opis funkcji bez podawania jej nazwy, np: funkcja $x\mapsto x^{2}$ jest w rachunku lambda zapisywana jako $\lambda x.x^{2}$, zaś funkcja, której wartością jest również funkcja: $y\mapsto (x\mapsto x^{2}+2y)$ zapisuje się jako $\lambda y.\lambda x.x^{2}+2y$.) Formalnie, $\lambda$-rachunek składa się z:

• typów: $A,B,A\times B,A\to B,...$
• termów, w skład których wchodzą:
  • dla każdego typu $A$ zmienne tego typu: $x:A,y:A,z:A,...$,
  • stałe różnych typów: $a:A,b:B,...$,
  • dla dowolnych $a:A,b:B$, para: $\langle a,b\rangle :A\times B$,
  • dla dowolnego $c:A\times ,B$, projekcja $\pi _{1}(c):A$,
  • dla dowolnego $c:A\times B$, projekcja $\pi _{2}(c):B$,
  • dla dowolnych $c:A\times B,a:A$, aplikacja $ca:B$,
  • dla dowolnych $x:A,b:B$, abstrakcja $\lambda x.b:A\to B$.
• równań:
  • $\pi _{1}(\langle a,b\rangle )=a$,
  • $\pi _{2}(\langle a,b\rangle )=b$,
  • $\langle \pi _{1}(c),\pi _{2}(c)\rangle =c$,
  • $(\lambda x.b)a=b[a/x]$,
  • $\lambda x.cx=c$, o ile $x$ nie występuje w $c$.

Definiujemy też relację $a\approx b$ na termach (nazywaną zwyczajowo $\beta \eta$-równoważnością), jako relację równoważności generowaną przez równania i zamianę nazwy zmiennych związanych: o ile $y$ nie występuje w $b$, to:

$\lambda x.b=\lambda y.b[y/x].$

Kategorię $C(\lambda )$ definiujemy teraz, jak następuje:

• obiekty: typy $\lambda$-rachunku,
• morfizm z $A$ do $B$ to termy domknięte $c\colon A\to B$ (identyfikowane ze sobą, jeśli $c\approx c'$),
• identyczności: $1_{A}=\lambda x.x$ dla każdego $x:A$,
• złożenie: $c\circ b=\lambda x.c(bx)$.

Sprawdźmy, że $C(\lambda )$ jest kategorią:

$c\circ 1_{B}=\lambda x.c((\lambda y.y)x)=\lambda x.c(y[x/y])=\lambda x.cx=c$,

$1_{C}\circ c=\lambda x.(\lambda y.y)(cx)=\lambda x.y[cx/y]=\lambda x.cx=c$,

$c\circ (b\circ a)=\lambda x.c((b\circ a)x)=\lambda x.c((\lambda y.b(ay))x)=\lambda x.c(b(ax))=\lambda x.\lambda y.c((by)(ax))=\lambda x.(c\circ b)(ax)=(c\circ b)\circ a$.

Kategorii $C(\lambda )$ przyjrzymy się jeszcze uważniej w Wykładach 3. i 4.