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

From Studia Informatyczne

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:

Grafika:tk-8.16.png

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

Grafika:tk-8.21.png

jest ekwalizatorem, to rozważmy diagram:

Grafika:tk-8.22.png

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).