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

From Studia Informatyczne

==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ę
Enlarge
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:

Grafika:Tk-1.14.png

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:

Grafika:Tk-1.15.png

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:

Grafika:Tk-1.16.png

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

Grafika:Tk-1.17.png

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

Grafika:Tk-1.18.png

jak również komutuje diagram:

Grafika:Tk-1.19.png

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:

Grafika:Tk-1.20.png

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:

Grafika:tk-1.21.png

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

Rozwiązanie:

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

Grafika:tk-1.22.png

składają się tak:

Grafika:tk-1.23.png

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:

Grafika:Tk_1_24.jpg

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:

Grafika:Tk_1_25.jpg

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

Podobnie, diagram:

<center>Grafika:Tk_1_26.jpg

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

<center>Grafika:Tk_1_27.jpg

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.