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

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

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''$:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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$):

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.