Teoria kategorii dla informatyków/Ćwiczenia 5: Funktory i transformacje naturalne

From Studia Informatyczne

==Zadanie 5.1==

Udowodnij, że transformacja naturalna \eta funktorów typu \mathbf{C}\to\mathbf{D} jest naturalnym izomorfizmem wtedy i tylko wtedy, gdy jest izomorfizmem w kategorii Fun(\mathbf{C},\mathbf{D}).

Wskazówka:

Używamy definicji złożenia transformacji naturalnych i transformacji, która jest identycznością.

Rozwiązanie:

Niech \eta będzie naturalnym izomorfizmem funktorów F,G\colon \mathbf{C}\to\mathbf{D}. Wtedy strzałka \eta_A\colon FA\to GA jest z definicji izomorfizmem dla każdego A\in \mathbf{C}_0. Skoro tak, to każda taka strzałka posiada odwrotność \eta_A^{-1}\colon GA\to FA:

\eta_A\circ \eta_A^{-1} = 1_{GA}\ \mathrm{oraz} \ \eta_A^{-1}\circ \eta_A = 1_{FA}.

Pokażemy, że \eta_A^{-1} jest transformacją naturalną typu G\to F. Rzeczywiście, dla f\colon A\to B, skoro \eta_A jest naturalna: Gf\circ \eta_A = \eta_B\circ Ff, a zatem Gf= \eta_B\circ Ff\circ \eta_A^{-1}, co z kolei pociąga: \eta_B^{-1}\circ Gf = Ff\circ \eta_A^{-1}, co należało pokazać.

Odwrotnie, załóżmy że F\cong G. To znaczy, że istnieją dwie transformacje naturalne \eta\colon F\to G oraz \varepsilon\colon G\to F, takie że \eta\circ \varepsilon = 1_G i \varepsilon\circ \eta = 1_F. Z definicji złożenia transformacji naturalnych i definicji identyczności mamy natychmiast: \eta_A\circ \varepsilon_A = 1_{GA} oraz \varepsilon_A\circ \eta_A=1_{FA} dla dowolnego A\in\mathbf{C}_0. To kończy dowód.

==Zadanie 5.2==

Udowodnij, że funktor inkluzji \mathbf{Pos}\to \mathbf{Cat} zachowuje strukturę kategorii kartezjańsko zamkniętej, zaś funktor inkluzji \mathbf{Grp}\to \mathbf{Cat} tej struktury nie zachowuje w ogólności.

Wskazówka:

Czy eksponent zostaje zachowany?

Rozwiązanie:

W pierwszej części zadania funktor inkluzji I działa tak, że poset (P,\leq) traktuje jako kategorię, zaś funkcję monotoniczną f\colon (P,\leq)\to (Q,\leq) jako funktor. Czy ta definicja jest dobrze postawiona? Tak, trywialnie tak, ponieważ zachowywanie identyczności przez f sprowadza się do implikacji (dla p,q,r\in P): p\leq p\Rightarrow f(p)\leq f(p), zaś zachowanie złożenia do implikacji p\leq q\leq r\Rightarrow f(p)\leq f(q)\leq f(r), co jest równoważne monotoniczności f. Wniosek: funktory między kategoriami (P,\leq) i (Q,\leq) to dokładnie funkcje monotoniczne. Wniosek drugi: I jest dobrze zdefiniowany.

Czym są zatem transformacja naturalna \eta\colon f\to g, gdzie f,g\colon P\to Q są funktorami? Dla każdego p\in P musimy mieć komponent: \eta_P\colon fp\leq gp, zaś naturalność oznacza, że musimy mieć komutujący diagram, w którym fp\leq fq i gp\leq gq dla p,q\in P, co jest zawsze spełnione. A zatem jedynym warunkiem, aby \eta była transformacją naturalną jest to, że w posecie Q^P (= Fun(P,Q)) mamy \eta\colon f\to q wtedy i tylko wtedy, gdy dla każdego p\in P, fp\leq gp, co oznacza, że porządek na Q^P jest po współrzędnych. To jednak wystarcza, by powiedzieć, że Q^P jest eksponentem P i Q w \mathbf{Pos}, tzn. Q^P = [P,Q]. Ostatnie zdanie mówi dokładnie tyle, że I zachowuje eksponent, a to chcieliśmy wykazać. (Zachowanie obiektu końcowego i produktów w \mathbf{Pos} pokazuje się tak samo.)

Zajmijmy się teraz kategorią grup \mathbf{Grp}. Naszkicujemy dowód, że inkluzja I\colon \mathbf{Grp}\to\mathbf{Cat} nie zachowuje eksponentu. Dzieje się tak, ponieważ H^G dla grup G, H nie jest zwykle grupą (często posiada więcej niż jeden obiekt - a przypomnijmy sobie, że grupą nazywamy kategorię, która ma dokładnie jeden obiekt i w której każdy morfizm jest izomorfizmem), tzn. może być w ogólności wiele homomorfizmów grup typu G\to H.

==Zadanie 5.3==

Niech \mathbf{A},\mathbf{B},\mathbf{C} będą kategoriami. Udowodnić, że operacja F\colon \mathbf{A}\times\mathbf{B}\to\mathbf{C} zdefiniowana na obiektach i strzałkach jest funktorem wtedy i tylko wtedy, gdy:

  • F jest funktorem ze względu na każdy z argumentów osobno, tzn. dla każdego A\in \mathbf{A}_0, F(A,-)\colon \mathbf{B}\to\mathbf{C} jest funktorem i dla każdego B\in \mathbf{B}_0, F(-,B)\colon \mathbf{A}\to\mathbf{C} jest funktorem oraz:
  • F spełnia następujące prawo przemienności:
Grafika:tk-5.A.png

dla dowolnych f\colon A\to A'\in \mathbf{A}_1, g\colon B\to B'\in \mathbf{B}_1.

Rozwiązanie:

Jeśli F jest funktorem, to ponieważ dla każdej strzałki w \mathbf{A}\times\mathbf{B}

(f,g)\colon (A,B)\to (A',B')

mamy

(f,1_{B'})\circ (1_A, g)= (f\circ 1_A,1_{B'}\circ g)=(f,g)= (1_{A'}\circ f,g\circ 1_B)= (1_{A'},g)\circ (f,1_B),

więc

F(f,1_{B'})\circ F(1_A, g)= F(1_{A'},g)\circ F(f,1_B),

a zatem (1),(2) zachodzą. Odwrotnie, mając dane (1),(2), musimy pokazać, że operacja F jest funktorem. Oczywiście definicje:

F((A,B)) := F(A,B)\in \mathbf{C}_0,
F((f,g)) := F(A',g)\circ F(f,B)

są dobrze postawione. Używając prawa przemienności, mamy dla f\colon A\to A',f'\colon A'\to A'',g\colon B\to B',g'\colon B'\to B'':

F(f',g')\circ F(f,g) &=& (F(A'',g')\circ F(f,B'))\circ F(f,g)=(F(A'',g')\circ F(f,B'))\circ (F(A',g)\circ F(f,B))=F(A'',g')\circ (F(f,B')\circ F(A',g))\circ F(f,B)=F(A'',g')\circ (F(A'',B)\circ F(f',B))\circ F(f,B)=(F(A'',g')\circ F(A'',B))\circ (F(f',B)\circ F(f,B))\\  &=& F((f',g')\circ(f,g)).

==Zadanie 5.4==

Zdefiniować produkt dwóch funktorów.

Wskazówka:

Należy to zrobić tak, aby ten produkt posiadał własność uniwersalną.

Rozwiązanie:

Jeśli F\colon \mathbf{A}\to\mathbf{B} i G\colon \mathbf{C}\to \mathbf{D} są funktorami między małymi kategoriami, to potraktujmy je jako strzałki w \mathbf{Cat}. Wiemy już, że w dowolnej kategorii z produktami, a taką przecież jest \mathbf{Cat} - patrz przykłady do Podrozdziału nt. produktów., produkt dwóch strzałek da się kanonicznie zdefiniować tak, by posiadał wymaganą własność uniwersalną (tj. był jedyną strzałką taką, że odpowiedni diagram komutuje). W naszym przypadku będzie to:

F\times G = (F\circ P_{\mathbf{A}}, G\circ P_{\mathbf{C}}),

gdzie P_{\mathbf{A}}\colon \mathbf{A}\times \mathbf{B}\to \mathbf{A} i P_{\mathbf{C}}\colon \mathbf{C}\times \mathbf{D}\to\mathbf{C} są odpowiednimi funktorami-projekcjami. Sprawdzenie, że F\times G jest rzeczywiście funktorem wynika wprost z definicji i jest polecane jako ćwiczenie tylko w ostateczności.

Na koniec wystarczy zauważyć, że jeśli kategorie \mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D} są dowolne (niekoniecznie małe), to powyższy dowód (kropka w kropkę) również działa.

==Zadanie 5.5==

Udowodnij, że operacja \mathcal{P}\colon \mathbf{Set}^{op}\to \mathbf{Set}:

A\mapsto \mathcal{P}(A)
f\colon A\to B\ \mapsto \ f^{-1}\colon \mathcal{P}(B)\to\mathcal{P}(A)

jest funktorem. Udowodnij, że funktor ten jest naturalnie izomorfizczny z hom-funktorem \mathrm{Hom}_{\mathbf{Set}}(-,2), gdzie 2:=\{0,1\} jest dowolnym zbiorem dwuelementowym.

Wskazówka:

Tenże funktor \mathcal{P}\colon \mathbf{Set}^{op}\to \mathbf{Set} jest znany jako kontrawariantny funktor potęgowy.

Rozwiązanie:

Sprawdzimy najpierw, że \mathcal{P} zachowuje identyczności:

\mathcal{P}(1_X)(Z\subseteq X) = 1^{-1}[Z]=Z,

co oznacza, że \mathcal{P}(1_X) = 1_{\mathcal{P}(X)}. Zachowanie złożenia:

\mathcal{P}(f\circ g)(Z)=(f\circ g)^{-1}[Z] = g^{-1}[f^{-1}[Z]]= \mathcal{P}(g)(f^{-1}[Z])=(\mathcal{P}(g)\circ \mathcal{P}(f))(Z),

co daje \mathcal{P}(f\circ g)=\mathcal{P}(g)\circ \mathcal{P}(f). A zatem \mathcal{P} jest funktorem.

Sprawdzimy teraz, że izomorfizm \mathcal{P} \cong \mathrm{Hom}_{\mathbf{Set}}(-,2) jest zadany przez parę wzajemnie do siebie odwrotnych transformacji naturalnych \phi\colon \mathrm{Hom}_{\mathbf{Set}}(-,2)\to \mathcal{P} i \psi\colon \mathcal{P}\to \mathrm{Hom}_{\mathbf{Set}}(-,2) znanych nam powszechnie jako bijekcja między podzbiorami danego zbioru i funkcjami charakterystycznymi podzbiorów: dla X\in \mathbf{Set}_0

\phi_X\colon \mathrm{Hom}_{\mathbf{Set}}(X,2)\to \mathcal{P}(X)
f\mapsto \{x\mid f(x)=1\}

oraz

\psi_X\colon \mathcal{P}(X)\to \mathrm{Hom}_{\mathbf{Set}}(X,2)

S\mapsto \chi_S := \begin{cases} 1& x\in S\\ 0& x\notin S. \end{cases}

Sprawdzenie, że \phi,\psi są transformacjami naturalnymi jest czynnością rutynową, na przykład dla \phi musimy pokazać, że poniższy diagram komutuje (dla dowolnej funkcji h\colon Y\to X):

Grafika:tk-5.8.png

co sprowadza się do obliczenia dla f\colon X\to 2:

\phi_Y(f\circ h) = h^{-1}[\phi_X(f)],

czyli pokazania równości zbiorów:

\{z\mid f(h(z))=1\} = h^{-1}[\{w\mid f(w)=1\}],

co jest oczywiście prawdą.

Dowód dla \psi jest równie łatwy i pomijamy go. Na zakończenie pokażemy tylko, że każda ze strzałek \phi_X dla X\in \mathbf{Set}_0 jest izomorfizmem z odwrotnością \psi_X. Oto uzasadnienie:

(\phi_X\circ \psi_X)(S)=\phi_X(\chi_S) = \{z\mid \chi_S(z)=1\}=S,

co daje \phi_X\circ \psi_X=1_{\mathcal{P}(X)} oraz:

(\psi_X\circ \phi_X)(f\colon X\to 2) = \psi_X(\{x\mid f(x)=1\})=\chi_{\{x\mid f(x)=1\}}=f,

co pokazuje \psi_X\circ \phi_X = 1_{\mathrm{Hom}_{\mathbf{Set}}(X,2)}.

==Zadanie 5.6==

Udowodnij, że dla zbiorów A,B,C istnieje następująca bijekcja pomiędzy zbiorami potęgowymi:

\mathcal{P}(B+C)\cong \mathcal{P}(B)\times\mathcal{P}(C).

Wskazówka:

Pokazać najpierw naturalną bijekcję dla zbiorów:

[B+C,A]\cong [B,A]\times [C,A].

Rozwiązanie:

Zgodnie ze wskazówką pokazujemy, że dla dowolnego zbioru Z mamy:

\mathrm{Hom}(Z,[B+C,A])\cong  \mathrm{Hom}(Z\times (B+C),A) \cong \mathrm{Hom}((Z\times B)+(Z\times C),A) \cong  \mathrm{Hom}((Z\times B),A)\times \mathrm{Hom}(Z\times C,A) \cong \mathrm{Hom}((Z\times B),A)\times \mathrm{Hom}(Z\times C,A)\cong\mathrm{Hom}(Z,[B,A])\times \mathrm{Hom}(Z,[C,A])

i korzystając z techniki używanej już w zadaniach do Wykładu 4., uwierzytelnionej w Wykładzie 7., wnioskujemy, że [B+C,A]\cong [B,A]\times [C,A]. W szczególności, dla A=2:=\{0,1\} dostajemy \mathrm{Hom}(B+C,2)\cong \mathrm{Hom}(B,2)\times \mathrm{Hom}(C,2) (musimy zauważyć też, że w \mathbf{Set} eksponentem [X,Y] jest zbiór wszystkich funkcji z X do Y, czyli \mathrm{Hom}(X,Y)). Ponieważ jednak z poprzedniego zadania (Zadanie 5.5) wynika, że funktor \mathrm{Hom}(-,2) jest w bijekcji z funktorem potęgowym \mathcal{P}, istnieją bijekcje (patrz Zadanie 5.1.)

\mathrm{Hom}(B+C,2)\cong \mathcal{P}(B+C),
\mathrm{Hom}(B,2)\cong \mathcal{P}(B),
\mathrm{Hom}(C,2)\cong \mathcal{P}(C),

które wraz z pokazanym już \mathrm{Hom}(B+C,2)\cong \mathrm{Hom}(B,2)\times \mathrm{Hom}(C,2) pozwala nam stwierdzić, że:

\mathcal{P}(B+C)\cong \mathcal{P}(B)\times\mathcal{P}(C).

==Zadanie 5.7==

Na dowolnym posecie (P,\leq) zadajemy tzw. topologię Aleksandrowa, deklarując zbiory górne jako otwarte. Pokaż, że ta konstrukcja da się rozszerzyć do funktora typu \mathbf{Pos}\to\mathbf{Top}. Czy ten funktor jest pełny? Wierny?

Wskazówka:

Definicje pojęć dotyczące częściowych porządków (np. czym jest zbiór górny?) znajdziemy we wstępie do Wykładu 12.

Rozwiązanie:

Dla częściowego porządku (P,\leq) topologię Aleksandrowa będziemy oznaczać jako \alpha(P). Jeśli więc nasza konstrukcja nazywa się I\colon \mathbf{Pos}\to \mathbf{Top}, to możemy napisać I((P\,leq)) := (P,\alpha(P)). Aby operacja I była funktorem, musi przede wszystkim posyłać każdą funkcję monotoniczną f\colon (P,\leq)\to (Q,\leq) w pewną funkcję ciągłą I(f)\colon (P,\alpha(P))\to(Q,\alpha(Q)). Najprostszym możliwym rozwiązaniem jest przyjęcie I(f):= f, ale aby ta definicja była poprawna, musi być tak, że każda funkcja monotoniczna jest funkcją ciągłą między topologiami Aleksandrowa. Sprawdźmy, czy tak jest w istocie. Załóżmy zatem, że

f\colon (P,\leq)\to (Q,\leq) jest funkcją monotoniczną. Wystarczy pokazać, że przeciwobraz dowolnego zbioru górnego w Q jest zbiorem górnym w P. Niech zatem U\subseteq Q będzie górny, niech x\in f^{-1}[U] oraz niech x\leq y dla x,y\in P. Z monotoniczności f dostajemy: f(x)\leq f(y), zaś z założeń: f(x)\in U - i co za tym idzie - f(y)\in U, bo U górny. Dlatego też y\in f^{-1}[U], co dowodzi, że f^{-1}[U] jest górnym podzbiorem P. Możemy więc bez obaw zdefiniować operację I na strzałkach jako: I(f\colon (P,\leq)\to (Q,\leq)):= f\colon (P,\alpha(P))\to(Q,\alpha(Q)).

Operacja I jest oczywiście funktorem - przy tak prostej definicji I dowód jest trywialny. Na zakończenie zauważmy więc, że I będzie funktorem pełnym i wiernym wtedy i tylko wtedy, gdy dowolna funkcja P\colon P\to Q jest monotoniczna dokładnie wtedy, gdy jest ciągła względem topologii Aleksandrowa (pełność jest istotna; wierność przy tak prostej definicji I trywializuje się). Ponieważ dowiedliśmy tej własności w jedną stronę, pozostaje nam implikacja odwrotna: załóżmy, że f\colon P\to Q jest ciągła. Pokażemy, że jest monotoniczna. Niech x\leq y w P i rozważmy zbiór A:=f^{-1}[\uparrow f(x)], który - jak wynika z założenia ciągłości - jest górnym podzbiorem P. Oczywiście x\in A, a skoro A górny, również y\in A. Dlatego f(y)\in \uparrow f(x), co czytamy inaczej jako f(x)\leq f(y). To kończy uzasadnienie faktu, że f jest monotoniczna, jak również dowód tego, że I jest funktorem pełnym i wiernym.

==Zadanie 5.8==

Zdefiniuj funktor dualny do hom-funktora zaproponowanego w Przykładzie 5.7.

Rozwiązanie:

Hom-funktorem kowariantnym w lokalnie małej kategorii \mathbf{C} będzie następująca operacja dla każdego X\in \mathbf{C}_0:

\mathrm{Hom}_{\mathbf{C}}(X,-)\colon \mathbf{C}\to\mathbf{Set}


\mathbf{C}_0\ni Y\ \mapsto \ \mathrm{Hom}_{\mathbf{C}}(X,Y)


\mathbf{C}_1\ni f\colon A\to B\ \mapsto \ \mathrm{Hom}_{\mathbf{C}}(X,f)\colon \mathrm{Hom}_{\mathbf{C}}(X,A)\to \mathrm{Hom}_{\mathbf{C}}(X,B)


p\colon X\to A \mapsto f\circ p\colon X\to B.


Pokażmy, że jest to funktor:


\mathrm{Hom}_{\mathbf{C}}(X,1_Z)(q) = 1_Z\circ q = q,


\mathrm{Hom}_{\mathbf{C}}(X,h\circ k)(q) = h\circ k\circ q = \mathrm{Hom}_{\mathbf{C}}(X,h)(k\circ q) = (\mathrm{Hom}_{\mathbf{C}}(X,h)\circ \mathrm{Hom}_{\mathbf{C}}(X,k))(q),

co kończy dowód.