Teoria kategorii dla informatyków/Ćwiczenia 8: Diagramy, granice i kogranice

Na początku zobaczmy, że istnienie granic da się w pełni wyrazić w języku funktorów reprezentowalnych.

==Zadanie 8.1==

Niech $\mathbf {J}$ będzie kategorią, $\mathbf {C}$ - kategorią lokalnie małą, $D\colon \mathbf {J} \to \mathbf {C}$ diagramem. Udowodnić, że $D$ ma granicę $(X,c)$ wtedy i tylko wtedy, gdy funktor $\mathrm {cone} (-,D)\colon \mathbf {C} ^{op}\to \mathbf {Set}$ jest reprezentowalny.

Funktor ten definiujemy następująco:

$\mathrm {cone} (-,D)(X):=\mathrm {cone} (X,D)$ (zbiór stożków o wierzchołku $X$), $\mathrm {cone} (-,D)(f\colon X\to Y):=\mathrm {cone} (f,D)\colon \mathrm {cone} (Y,D)\to \mathrm {cone} (X,D)$ $(Y,d_{j})\mapsto (X,d_{j}\circ f).$

Rozwiązanie:

Sprawdźmy, co to znaczy, że $\mathrm {cone} (-,D)$ jest reprezentowalny. Zgodnie z charakterystyką reprezentowalności -Lemat 7.5 - dzieje się tak, gdy istnieje stożek $(X,c)\in \mathrm {cone} (X,D)$ taki, że dla dowolnego innego stożka $(Y,d)$ nad $D$ istnieje dokładnie jedna strzałka $f\colon Y\to X$ w $\mathbf {C}$ taka, że:

$\mathrm {cone} (f,D)((X,c))=(Y,d).$

Ale przecież ten warunek jest równoważny stwierdzeniu, że $d_{j}=c_{j}\circ f$ dla każdego $j\in \mathbf {J} _{0}$. Co należało wykazać.

==Zadanie 8.2==

Udowodnij następujące twierdzenie Petera Freyda: Jeśli mała kategoria jest zupełna, to jest preporządkiem.

Wskazówka:

Przypuśćmy, że tak nie jest i weźmy $A,B\in \mathbf {C} _{0}$ takie, że $\mathrm {Hom} (A,B)\geq 2$. Rozważmy moc zbioru $\mathrm {Hom} (A,\Pi _{i\in I}B)$ dla $I=\mathbf {C} _{1}$.

Rozwiązanie:

Postępujemy zgodnie ze Wskazówką. Z jednej strony mamy:

$|\mathbf {C} _{1}|\geq |\mathrm {Hom} (A,\Pi _{i\in I}B)|,$

zaś z drugiej strony, ze względu na izomorfizm:

$\mathrm {Hom} (A,\Pi _{i\in I}B)\cong \Pi _{i\in I}\mathrm {Hom} (A,B)\cong \mathrm {Hom} (A,B)^{J}$

mamy:

$|\mathrm {Hom} (A,\Pi _{i\in I}B)|=|\mathrm {Hom} (A,B)|^{|J|}\geq |{\mathcal {P}}(J)|,$

co daje sprzeczność z twierdzeniem Cantora z teorii mnogości.

==Zadanie 8.3==

Niech $\mathbf {C}$ będzie kategorią, w której istnieją wszystkie granice typu $\mathbf {J}$. Udowodnij, że $\lim _{\leftarrow \mathbf {J} }$ jest funktorem typu $[\mathbf {J} ,\mathbf {C} ]\to \mathbf {C}$.

Wskazówka:

Oczywiście działanie $\lim _{\leftarrow \mathbf {J} }$ na obiektach jest następujące: $D\mapsto \lim _{\leftarrow \mathbf {J} }(D)$, gdzie

$\{c_{j}^{D}\colon \lim _{\leftarrow \mathbf {J} }D\to D(j)\mid j\in \mathbf {J} _{0}\}$

jest stożkiem granicznym. Dla dowolnego przekształcenia diagramów $\delta \colon D\to D'$ kolekcja

$\{\lim _{\mathbf {J} }D{\stackrel {c_{j}^{D}}{\to }}D(j){\stackrel {\delta _{j}}{\to }}D'(j)\mid j\in \mathbf {J} _{0}\}$

jest stożkiem granicznym nad $D'$ (tj. granicą $D'$). Z warunku uniwersalnego istnieje więc dokładnie jedna strzałka, oznaczmy ją $\lim _{\leftarrow \mathbf {J} }\delta \colon \lim _{\leftarrow \mathbf {J} }(D)\to \lim _{\leftarrow \mathbf {J} }(D')$, która sprawia, że poniższy diagram komutuje:

Rozwiązanie:

To, że $\lim _{\leftarrow \mathbf {J} }$ jest funktorem wynika wprost z własności uniwersalnej diagramu we Wskazówce. Na przykład, dla złożenia:

$D{\stackrel {\delta }{\to }}D'{\stackrel {\delta '}{\to }}D'',$

obie strzałki $\lim _{\leftarrow \mathbf {J} }(\delta '\circ \delta )$ oraz $\lim _{\leftarrow \mathbf {J} }\delta '\circ \lim _{\leftarrow \mathbf {J} }\delta$ są faktoryzacjami diagramu:

$\{\delta '_{j}\circ \delta \circ c_{j}^{D}\mid j\in \mathbf {J} _{0}\},$

a co za tym idzie - są równe. Zachowywanie identyczności wynika od razu z faktu, że dla dowolnej granicy

$\{c_{j}^{D}\colon \lim _{\leftarrow \mathbf {J} }D\to D(j)\mid j\in \mathbf {J} _{0}\}$ zarówno identyczność na $\lim _{\leftarrow \mathbf {J} }D$, jak i $\lim _{\leftarrow \mathbf {J} }\delta$ dla $\delta =1_{D}\colon D\to D$ są faktoryzacjami diagramu $D$, a zatem muszą być równe.

Uwaga

Mówimy, że funktor $F\colon \mathbf {C} \to \mathbf {D}$ zachowuje granice typu $\mathbf {J}$, jeśli z faktu, że $c_{j}\colon L\to D_{j}$ jest granicą diagramu $D\colon \mathbf {J} \to \mathbf {C}$ wynika, że stożek $Fc_{j}\colon FL\to FD_{j}$ jest granicą diagramu $F\circ D\colon \mathbf {J} \to \mathbf {D}$. W skrócie można to zapisać tak: $F(\lim _{\leftarrow \mathbf {J} }D_{j})\cong \lim _{\leftarrow \mathbf {J} }F(D_{j}).$

Funktor zachowujący wszystkie granice nazywa się ciągłym.

==Zadanie 8.4==

Udowodnić, że hom-funktory są ciągłe.

Wskazówka:

Niech $\mathbf {J}$ będzie małą kategorią. Pokażemy, że hom-funktory: $\mathrm {Hom} (C,-)\colon \mathbf {C} \to \mathbf {Set}$ dla $C\in \mathbf {C} _{0}$ zachowują ekwalizatory i wszystkie produkty mocy mniejszej lub równej mocy $\mathbf {J}$, a potem użyjemy Twierdzenia 8.3. Gwoli wyjaśnienia, produkt o mocy $0$ jest po prostu obiektem końcowym (nieprawdaż?).

Rozwiązanie:

Po pierwsze, załóżmy, że $\mathbf {C}$ ma obiekt końcowy $\mathbf {1}$ i zauważmy, że $\mathrm {Hom} (C,\mathbf {1} )=\{C\}\cong \mathbf {1} _{\mathbf {Set} }$ (bo wszystkie singletony są izomorficzne w $\mathbf {Set}$). Po drugie, wiemy już z Zadania 3.5, że hom-funktory zachowują produkty binarne. Podobnie da się pokazać, że hom-funktory zachowują produkty dowolnej mocy. Oto argument: dla dowolnego produktu $\Pi _{i\in I}Z_{i}$ wraz z projekcjami $\Pi _{i\in I}Z_{i}\to Z_{i}$ każda strzałka $f\colon C\to \Pi _{i\in I}Z_{i}$ rozkłada się na strzałki $f_{i}:=p_{i}\circ f$. Odwrotnie, dla rodziny strzałek $\{f_{i}\colon C\to Z_{i}\mid i\in I\}$, gdzie $f_{i}\colon C\to Z_{i}$, z własności uniwersalnej produktu, istnieje dokładnie jedna strzałka $(f_{i})\colon C\to \Pi _{i\in I}Z_{i}$ taka, że $f_{i}=p_{i}\circ f$. Jest więc oczywiste, że odwzorowanie:

$f\colon X\to \Pi _{i\in I}Z_{i}\ \mapsto \ p_{i}\circ f$

jest szukanym izomorfizmem z odwrotnością:

$\{f_{i}\colon Z\to X_{i}\mid i\in I\}\ \mapsto \ (f_{i}).$

To znaczy, że:

$\mathrm {Hom} (C,\Pi _{i}Z_{i})\cong \Pi _{i}\mathrm {Hom} (C,Z_{i}).$

W końcu, po trzecie, jeśli

jest ekwalizatorem, to rozważmy diagram:

Musimy pokazać, że jest to ekwalizator w $\mathbf {Set}$. Rzeczywiście, dla dowolnej strzałki $h\colon C\to E$ takiej, że $(f\circ -)h=(g\circ -)h$ mamy $f\circ h=g\circ h$. Ponieważ $E$ jest ekwalizatorem, istnieje dokładnie jedna strzałka $k\colon C\to E$ taka, że $e\circ k=h$. Innymi słowy, to znaczy, że mamy dokładnie jedną strzałkę $k$ taką, że $(e\circ -)(k)=h$. To znaczy, że:

$(e\circ -)\colon \mathrm {Hom} (C,E)\to \mathrm {Hom} (C,X)$ jest ekwalizatorem $(f\circ -)$ i $(g\circ -)$. Pokazaliśmy, że założenia Twierdzenia 8.3 są spełnione, a zatem hom-funktor zachowuje dowolne granice, tj. jest ciągły.

==Zadanie 8.5==

Pokażmy, że dla lokalnie małej kategorii $\mathbf {C}$, funktor ewaluacji

$\mathrm {ev} _{\mathbf {C} ^{op}}\colon [\mathbf {C} ^{op},\mathbf {Set} ]\times \mathbf {C} ^{op}\to \mathbf {Set}$

znany z Wykładu 7. i Zadania 7.1 jest ciągły.

Rozwiązanie:

Niech $\mathbf {J}$ będzie małą kategorią. Niech $F\colon \mathbf {J} \to [\mathbf {C} ^{op},\mathbf {Set} ]$ będzie diagramem w $[\mathbf {C} ^{op},\mathbf {Set} ]$. Wówczas jego granica, jeśli istnieje, jest obiektem $[\mathbf {C} ^{op},\mathbf {Set} ]$, czyli funktorem $(\lim _{\leftarrow j}F_{j})\in [\mathbf {C} ^{op},\mathbf {Set} ].$ Zgodnie z lematem Yonedy, dla każdego obiektu $X\in \mathbf {C} _{0}$, istnieje naturalny izomorfizm:

$(\lim _{\leftarrow j}F_{j})(X)\cong \mathrm {Hom} ({\mathcal {Y}}(X),\lim _{\leftarrow j}F_{j}).$

Ale hom-funktory są ciągłe, Zadanie 8.4,więc używając po kolei: tego faktu i lematu Yonedy raz jeszcze, dostajemy:

$\mathrm {Hom} ({\mathcal {Y}}(X),\lim _{\leftarrow j}F_{j})\cong \lim _{\leftarrow j}\mathrm {Hom} ({\mathcal {Y}}(X),F_{j})\cong \lim _{\leftarrow j}F_{j}(X).$ Ta równość jest właśnie dowodem na to, że ewaluacja zachowuje granice.

==Zadanie 8.6==

Udowodnij, że funktor Yonedy ${\mathcal {Y}}\colon \mathbf {C} \to [\mathbf {C} ^{op},\mathbf {Set} ]$ jest ciągły.

Wskazówka:

Ponieważ granice w kategoriach funktorów są liczone po współrzędnych, mając dany diagram $D\colon \mathbf {J} \to \mathbf {C}$ wraz z granicą

$L=\{c_{j}\colon L\to D(j)\mid j\in \mathbf {J} _{0}\},$

wystarczy pokazać, że dla dowolnego $X\in \mathbf {C} _{0}$

$\{(c_{j}\circ -)\colon \mathrm {Hom} _{\mathbf {C} }(X,L)\to \mathrm {Hom} _{\mathbf {C} }(X,D(j))\}$

jest stożkiem granicznym dla diagramu

$\mathrm {Hom} _{\mathbf {C} }(X,D(-))={\mathcal {Y}}(D(-))(X)\colon \mathbf {J} \to \mathbf {Set} .$

Rozwiązanie:

Niech zatem:

$\{d_{j}\colon S\to \mathrm {Hom} _{\mathbf {C} }(X,D(j))\mid j\in \mathbf {J} _{0}\}$

będzie dowolnym innym stożkiem nad $\mathrm {Hom} _{\mathbf {C} }(X,D(-))$. Wówczas dla każdego $s\in S$

$\{d_{j}(s)\colon X\to D(j))\mid j\in \mathbf {J} _{0}\}$

jest stożkiem nad $D$, więc istnieje dokładnie jedna strzałka $f(s)\colon X\to L$ taka, że $c_{j}\circ f(s)=d_{j}(s)$ dla każdego $j\in \mathbf {J} _{0}$. A zatem strzałka $s\mapsto f(s)$ jest jedyną typu $S\to \mathrm {Hom} _{\mathbf {C} }(X,L)$ taką, że $(c_{j}\circ -)\circ f=d_{j}$, co należało pokazać.

Uwaga dla dociekliwych

Funktor Yonedy zwykle nie zachowuje kogranic. Na przykład ${\mathcal {Y}}\colon \mathbf {Set} _{fin}\to [\mathbf {Set} _{fin}^{op},\mathbf {Set} ]$ nie zachowuje obiektu początkowego $\emptyset$.

==Zadanie 8.7==

Pokaż, że hom-funktor $\mathrm {Hom} _{\mathbf {C} }(-,X)\colon \mathbf {C} ^{op}\to \mathbf {Set}$ jest ciągły, tj.

$\mathrm {Hom} _{\mathbf {C} }(\lim _{\leftarrow j}Z_{j},X)\cong \lim _{\rightarrow j}\mathrm {Hom} _{\mathbf {C} }(Z_{j},X).$

Wskazówka:

Zadanie można zrobić łatwo na trzy sposoby.

Rozwiązanie:

Sposób pierwszy: przez szczegółowy dowód dualny do Zadania 8.4. Sposób drugi: przez odwołanie się do zasady dualności względem Zadania 8.4 (czyli sposób pierwszy dla leniwych...). Sposób trzeci: wykorzystując Zadania 8.5, 8.6. Oto ten sposób: dowód dualny do tego w Zadaniu 8.6 pokazuje, że dualny funktor Yonedy ${\mathcal {Y}}^{op}\colon \mathbf {C} ^{op}\to [\mathbf {C} ,\mathbf {Set} ]$ zmienia granice na kogranice. Dowód identyczny do tego w Zadaniu 8.5 pokazuje, że funktor ewaluacji $\mathrm {ev} \colon [\mathbf {C} ,\mathbf {Set} ]\times \mathbf {C} \to \mathbf {Set}$ jest ciągły, a zatem złożenie:

$\mathrm {Hom} (-,X)=\mathbf {C} {\stackrel {{\mathcal {Y}}^{op}}{\to }}[\mathbf {C} ^{op},\mathbf {Set} ]{\stackrel {\mathrm {ev} }{\to }}\mathbf {Set}$ jest funktorem ciągłym (tzn. ze względu na kontrawariantność zamienia granice na kogranice).