Teoria kategorii dla informatyków/Wykład 8: Diagramy, granice i kogranice

Podczas tego wykładu zobaczymy, że diagramy, które tak przecież promuje teoria kategorii, są również funktorami. Przekonamy się też, że obiekty i strzałki uniwersalne, które poznaliśmy do tej pory, np. produkt, pulbak, ekwalizator, koprodukt, pushout, itd. są szczególnymi przypadkami pojęć granicy i kogranicy.

Diagramy

Niech $\mathbf{𝐉}$ i $\mathbf{𝐂}$ będą kategoriami. Zastanówmy się, w jaki sposób interpretować dowolny funktor - niech nazywa się $D$ - typu $\mathbf{𝐉}\to \mathbf{𝐂}$. Wiemy - Definicja 5.1 - że funktor $D:\mathbf{𝐉}\to \mathbf{𝐂}$ jest operacją przypisującą obiektom ${\mathbf{𝐉}}_0$ obiekty ${\mathbf{𝐂}}_0$ i morfizmom ${\mathbf{𝐉}}_1$ morfizmy ${\mathbf{𝐂}}_1$. Innymi słowy, funktor $D$ jest operacją, która indeksuje obiekty i morfizmy kategorii $\mathbf{𝐂}$ obiektami i morfizmami kategorii $\mathbf{𝐉}$. Aksjomaty, którym podlegają funktory, narzucają nam pewien porządek, styl indeksowania: po pierwsze - identyczności w $\mathbf{𝐂}$ mogą być indeksowane jedynie przez identyczności, po drugie - poindeksowane strzałki w $\mathbf{𝐂}$ składają się dokładnie wtedy, gdy są obrazem pewnego złożenia w $\mathbf{𝐉}$. Oto przykład: jeśli $\mathbf{𝐉}$ jest następującą kategorią:

(jak zwykle nie musimy rysować identyczności!), to jej obraz w kategorii $\mathbf{𝐂}$ wygląda tak:

(gdzie z premedytacją piszemy $D_i$ zamiast $D(i)$, $D_{\alpha }$ zamiast $D(\alpha )$ itd.). Widzimy, że obraz kategorii$\mathbf{𝐉}$ w kategorii $\mathbf{𝐂}$ jest... diagramem! Pamiętając to spostrzeżenie, bez większych wahań zaakceptujemy następującą definicję:

Definicja 8.1 [Diagram]

Niech $\mathbf{𝐉}$ i $\mathbf{𝐂}$ będą kategoriami. Diagramem typu $\mathbf{𝐉}$ w $\mathbf{𝐂}$ nazywamy funktor $D:\mathbf{𝐉}\to \mathbf{𝐂}$

Mimo uderzającej prostoty powyższej definicji niektóre diagramy mogą mieć skomplikowany kształt:

Granice i kogranice

Stożek nad diagramem $D$ składa się z obiektu $X\in {\mathbf{𝐂}}_0$ i rodziny strzałek

$c_j:X\to D_j$

po jednej dla każdego obiektu $j\in {\mathbf{𝐉}}_0$, takich że dla każdej strzałki $\alpha :i\to j\in {\mathbf{𝐉}}_1$ diagram

komutuje. Powyższy rysunek, miejmy nadzieję, wyjaśnia nazwę stożek. Obiekt $X$ nazywa się często wierzchołkiem stożka.

Ktoś spostrzegawczy zapewne zauważył już, że rodzina strzałek $\{c_j{\}}_{j\in {\mathbf{𝐉}}_0}$ nadaje się na komponenty pewnej transformacji naturalnej. Tak jest rzeczywiście: wystarczy potraktować $c:{\mathrm{\Delta }}_X\to D$ jako transformację z funktora stałego ${\mathrm{\Delta }}_X:\mathbf{𝐉}\to \mathbf{𝐂}$:

${\mathrm{\Delta }}_X(j):=X$ ${\mathrm{\Delta }}_X(\alpha ):=1_X$

do funktora $D$. Komutowanie diagramu powyżej to nic innego, tylko odbicie naturalności transformacji $c$, nieprawdaż?

Stożek o wierzchołku $X$ oznaczamy jako $(X,c_j)$ lub $(X,c)$ lub

$\{c_j:X\to D_j\mid j\in {\mathbf{𝐉}}_0\}$

Stożki również tworzą kategorię: morfizmem stożków $f:(X,c)\to (Y,d)$ nazywamy strzałkę $f:X\to Y\in {\mathbf{𝐂}}_0$ taką, że:

komutuje dla każdego $j\in {\mathbf{𝐉}}_0$, tzn. $\mathrm{\forall }j\in {\mathbf{𝐉}}_0{d}_j\circ f=c_j$. Kategorię stożków nad diagramem $D$ oznaczamy $\mathbf{𝐂}\mathbf{𝐨}\mathbf{𝐧}\mathbf{𝐞}(D)$.

Pewne stożki są uniwersalne. Nazywają się granicami (lub stożkami granicznymi):

Definicja 8.2 [granica diagramu]

Granicą (stożkiem granicznym) diagramu $D:\mathbf{𝐉}\to \mathbf{𝐂}$ nazywamy obiekt końcowy w $\mathbf{𝐂}\mathbf{𝐨}\mathbf{𝐧}\mathbf{𝐞}(D)$ i oznaczamy go jako $\underset{\leftarrow \mathbf{𝐉}}{\lim }D$ lub $\underset{\leftarrow j}{\lim }{D}_j$.

Innymi słowy, stożek $(X,c)$ nad $D:\mathbf{𝐉}\to \mathbf{𝐂}$ jest granicą, jeśli dla dowolnego innego stożka $(Y,d)$ istnieje dokładnie jedna strzałka $g:Y\to X$, która jest morfizmem stożków, tzn. taka że poniższy diagram komutuje dla każdego $j\in {\mathbf{𝐉}}_0$:

Dualnie, kogranicą lub granicą odwrotną

$D:\mathbf{𝐉}\to \mathbf{𝐂}$

nazywamy obiekt początkowy w kategorii kostożków

$\mathbf{𝐂}\mathbf{𝐨}\mathbf{𝐜}\mathbf{𝐨}\mathbf{𝐧}\mathbf{𝐞}(D)$

. (Kostożek nad diagramem

$D$

składa się z obiektu

$X\in {\mathbf{𝐂}}_0$

i rodziny strzałek

$c_j:D_j\to X$

po jednej dla każdego obiektu

$j\in {\mathbf{𝐉}}_0$

, takich że dla każdej strzałki

$\alpha :i\to j\in {\mathbf{𝐉}}_1$

mamy

$c_j\circ D_{\alpha }=c_i$

.) Kogranicę oznaczymy jako

$\underset{\to \mathbf{𝐉}}{\lim }D$

lub

$\underset{\to j}{\lim }{D}_j$

.

Przykłady:

• Produkt jest granicą diagramu typu:

Ponieważ jest to pierwszy przykład tego typu, bardzo wnikliwie opiszemy go i dowiedziemy prawdziwości powyższego, przedstawionego w telegraficznym skrócie, stwierdzenia. A zatem bierzemy $\mathbf{𝐉}=\{1,2\}$ kategorię dyskretną z dwoma obiektami $1$ i $2$ i dwoma morfizmami (tzn. nie ma strzałek innych poza identycznościami) (rysunek jak wyżej). Diagramem $D:\mathbf{𝐉}\to \mathbf{𝐂}$ jest para obiektów $D_1,D_2\in {\mathbf{𝐂}}_0$. Stożkiem nad $D$ jest obiekt $X\in {\mathbf{𝐂}}_0$ wraz z dwoma strzałkami $c_1:X\to D_1$ i $c_2:X\to D_2$, tzn.

Zgodnie z tym, co tłumaczyliśmy tuż pod Definicją 5.2, tenże $(X,\{c_1,c_2\})$ jest granicą $D$, jeśli dla dowolnego innego stożka

istnieje dokładnie jedna strzałka $g:Y\to X$ taka, że diagram

komutuje. Innymi słowy, $(X,\{c_1,c_2\})$ jest produktem:

$\underset{\leftarrow \mathbf{𝐉}}{\lim }(D)=X=D_1\times D_2$

• Granicą diagramu $D:\mathbf{𝟎}\to \mathbf{𝐂}$, gdzie $\mathbf{𝟎}$ jest kategorią pustą, jest obiekt końcowy w $\mathbf{𝐂}$. Kogranicą $D$ jest obiekt początkowy w $\mathbf{𝐂}$. Co więcej, $\mathbf{𝐂}\mathbf{𝐨}\mathbf{𝐧}\mathbf{𝐞}(D)$ jest kategorią izomorficzną z $\mathbf{𝐂}$ w $\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐭}$.
• Ekwalizator jest granicą diagramu typu

• Pulbak jest granicą diagramu typu

• Pushout jest kogranicą diagramu typu

Uogólniając dwa pierwsze przykłady powyżej, jeśli $I$ jest zbiorem (tj. kategorią dyskretną), zaś $\{X_i\mid i\in I\}$ jest indeksowaną kolekcją obiektów z $\mathbf{𝐂}$, to ich produktem

${\mathrm{\Pi }}_{i\in I}{X}_i\stackrel{{\pi }_i}{⟶}{X}_i$

nazywamy granicę diagramu $I\to \mathbf{𝐂}$. Mówimy, że ten produkt ma moc równą mocy zbioru $I$. W ogólności, dla małej kategorii $\mathbf{𝐉}$, jej moc będziemy definiować jako moc kolekcji morfizmów ${\mathbf{𝐉}}_1$. Wtedy mocą granicy diagramu $\mathbf{𝐉}\to \mathbf{𝐂}$ nazwiemy moc kategorii $\mathbf{𝐉}$. Na przykład: małą granicą nazwiemy granicę diagramu małego typu.

Pokażmy następujące twierdzenie, które jest naturalnym uogólnieniem Wniosku 3.10:

Twierdzenie 8.3

Niech $\mathbf{𝐂}$ będzie kategorią, w której istnieją wszystkie ekwalizatory. Jeśli $\mathbf{𝐉}$ jest małą kategorią i w $\mathbf{𝐂}$ istnieją wszystkie produkty mocy mniejszej lub równej mocy $\mathbf{𝐉}$, to w $\mathbf{𝐂}$ istnieją wszystkie granice typu $\mathbf{𝐉}$.

Dowód

Niech $D:\mathbf{𝐉}\to \mathbf{𝐂}$ będzie diagramem. Połóżmy: $X:={\mathrm{\Pi }}_{i\in {\mathbf{𝐉}}_0}{D}_i$ $Y:={\mathrm{\Pi }}_{\alpha \in {\mathbf{𝐉}}_1}{D}_{\mathrm{c}\mathrm{o}\mathrm{d}(\alpha )}$

Niech $f,g:X\to Y$ będą jedynymi strzałkami, dla których poniższe diagramy komutują (dla każdego $\alpha$):

Niech

będzie ekwalizatorem $f$ i $g$. Zdefiniujmy:

$c_j:E\stackrel{e}{⟶}X\stackrel{{\pi }_j}{⟶}{D}_j$

dla każdego $j\in {\mathbf{𝐉}}_0$. Te strzałki tworzą stożek nad $D$, ponieważ dla dowolnego $\alpha :i\to j\in {\mathbf{𝐉}}_1$

$D_{\alpha }\circ c_j=D_{\alpha }\circ {\pi }_i\circ e={\pi }_{\alpha }\circ f\circ e={\pi }_{\alpha }\circ g\circ e={\pi }_j\circ e=c_j$

Co więcej, dla dowolnego innego stożka $(Z,d_j)$ mamy morfizm $h:Z\to X$ z ${\pi }_j\circ h=d_j$. Dlatego:

${\pi }_{\alpha }\circ f\circ h=D_{\alpha }\circ {\pi }_{\mathrm{d}\mathrm{o}\mathrm{m}(\alpha )}\circ h=D_{\alpha }\circ d_{\mathrm{d}\mathrm{o}\mathrm{m}(\alpha )}=d_{\mathrm{c}\mathrm{o}\mathrm{d}(\alpha )}={\pi }_{\alpha }\circ g\circ h$

dla dowolnego $\alpha \in {\mathbf{𝐉}}_1$. A zatem $f\circ h=g\circ h$. Mamy więc następującą sytuację:

tzn. z faktu, że $E$ jest ekwalizatorem wynika, że istnieje dokładnie jedna strzałka $k:Z\to E$, która spełnia $e\circ k=h$. Tak więc:

$d_j=c_j\circ k={\pi }_j\circ e\circ k={\pi }_j\circ h$

czyli $h$ jest morfizmem stożków. To kończy dowód faktu, że $(E,c)$ jest granicą $D$.

Wniosek 8.4

1. Kategoria $\mathbf{𝐂}$ ma wszystkie granice danej mocy wtedy i tylko wtedy, gdy ma wszystkie produkty i ekwalizatory tej mocy.
2. Kategoria $\mathbf{𝐂}$ ma wszystkie kogranice danej mocy wtedy i tylko wtedy, gdy ma koprodukty i koekwalizatory tejże mocy.
3. Kategoria $\mathbf{𝐂}$ ma skończone granice wtedy i tylko wtedy, gdy ma skończone koprodukty i skończone koekwalizatory.
4. Jeśli $\mathbf{𝐂}$ ma ekwalizatory i wszystkie małe produkty, to ma wszystkie małe granice.
5. Jeśli $\mathbf{𝐂}$ ma obiekt końcowy i pulbaki, to ma wszystkie skończone granice.

Dowód

(1),(2),(4) to oczywiste wnioski. (3) wynika z (2), co też czyni go oczywistym wnioskiem. (5) Istnienie obiektu końcowego i pulbaków daje skończone produkty i ekwalizatory (Zadanie 3.4), więc (5) wynika teraz z (4).

Kategorie kartezjańsko zamknięte zdefiniowaliśmy już w Wykładzie 4., patrz Definicja 4.2. Uzupełnijmy naszą wiedzę o pojęcia pokrewne:

Definicja 8.5

Kategoria $\mathbf{𝐂}$ jest:

• kartezjańska jeśli posiada wszystkie skończone granice;
• właściwie kartezjańsko zamknięta jeśli jest lokalnie mała, posiada wszystkie skończone granice i eksponent.
• (ko)zupełna jeśli posiada wszystkie małe (ko)granice.

Przykłady:

• Kategoria zbiorów $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ ma (ko)ekwalizatory i wszystkie małe (ko)produkty. Zgodnie z powyższym Wnioskiem 8.4, ma wszystkie małe (ko)granice, a zatem jest (ko)zupełna. Dla $D:\mathbf{𝐉}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ mamy:

$\underset{\leftarrow \mathbf{𝐉}}{\lim }D=\{(x_j{)}_{j\in {\mathbf{𝐉}}_0}\in {\mathrm{\Pi }}_{j\in {\mathbf{𝐉}}_0}{d}_j\mid \mathrm{\forall }\alpha :i\to j{D}_{\alpha }(x_i)=x_j\}$

razem z projekcjami ${\pi }_j:\underset{\leftarrow \mathbf{𝐉}}{\lim }D\to d_j$, $(x_j{)}_{j\in {\mathbf{𝐉}}_0}\mapsto x_j$.

• Poset $(P,\le )$ jako kategoria jest zupełny wtedy i tylko wtedy, gdy jest zupełny w sensie teorii porządku, tj. gdy posiada wszystkie infima. Ten warunek jest równoważny (dowód Zadania 12.4 da się łatwo zmodyfikować, by wykazać tę równoważność) warunkowi, że $P$ posiada dowolne suprema.
• Uogólnieniem poprzedniego przykładu jest stwierdzenie: każda kategoria $\mathbf{𝐂}$, która jest małym preporządkiem jest zupełna wtedy i tylko wtedy, gdy jest kozupełna. To stwierdzenie nie pozostaje w mocy, gdy $\mathbf{𝐂}$ jest duża. Dalsze informacje zawiera Zadanie 8.2.

(Ko)granice w kategoriach funktorów

Jest znanym faktem, że jeśli $L$ jest kratą zupełną, to zbiór wszystkich funkcji monotonicznych o kodziedzinie $L$, uporządkowany po współrzędnych, jest również kratą zupełną. Innymi słowy, przestrzenie funkcyjne zwykle dziedziczą' strukturę z kodziedziny. To zjawisko jest uniwersalne, co pokażemy poniżej.

Twierdzenie 8.6 [(Ko)granice w kategoriach funktorów]

Niech $\mathbf{𝐂}$ będzie lokalnie mała. Jeśli kategoria $\mathbf{𝐃}$ ma (ko)granice typu $\mathbf{𝐉}$, to kategoria funktorów $[\mathbf{𝐂},\mathbf{𝐃}]$ też.

Dowód

Zauważmy, że diagram $D:\mathbf{𝐉}\to [\mathbf{𝐂},\mathbf{𝐃}]$ może być traktowany jako funktor

$D:\mathbf{𝐉}\times \mathbf{𝐂}\to \mathbf{𝐃}$. Z założenia, dla każdego $X\in {\mathbf{𝐂}}_0$ diagram:

$D(-,X):\mathbf{𝐉}\to \mathbf{𝐃}$

ma pewną granicę, nazwijmy ją:

$\{c_{j,X}:L(X)\to D(j,X)\mid j\in {\mathbf{𝐉}}_0\}$

Dla dowolnej strzałki $f:X\to X^{\prime }$ dostajemy zatem stożek nad $D(-,X^{\prime })$:

$\{L(X)\stackrel{c_{j,X}}{⟶}D(j,X)\stackrel{D(1_j,f)}{⟶}D(j,X^{\prime })\mid j\in {\mathbf{𝐉}}_0\}$

który faktoryzuje się przez granicę diagramu $D(-,X^{\prime })$, jak na rysunku:

Jedyność strzałki $L(f)$ implikuje, że $L(1_X)=1_{L(X)}$ oraz $L(g\circ f)=L(g)\circ L(f)$. To znaczy, że $L$ jest funktorem, $L\in [\mathbf{𝐂},\mathbf{𝐃}{]}_0$. Co więcej, powyższy rysunek pokazuje też, że $c_{j,-}:L\to D(j)$ jest strzałką w $[\mathbf{𝐂},\mathbf{𝐃}]$. Ponieważ każda kolekcja

$\{c_{j,X}\mid j\in {\mathbf{𝐉}}_0\}$

jest stożkiem, dostajemy:

któryż to diagram komutuje dla każdego $\alpha :i\to j\in {\mathbf{𝐉}}_1$. To znaczy, że

$\{c_j:L\to D(j)\mid j\in {\mathbf{𝐉}}_0\}$

jest stożkiem nad $D$.

Mając dany dowolny inny stożek

$\{d_j:M\to D(j)\mid j\in {\mathbf{𝐉}}_0\}$

nad $D$,

$\{d_{j,X}:M(X)\to D(j,X)\mid j\in {\mathbf{𝐉}}_0\}$

jest stożkiem nad $D(-,X)$, który w związku z tym faktoryzuje się przez stożek graniczny:

A zatem jedyność ${\varphi }_X$ sprawia, że $\varphi :M\to L$ jest transformacją naturalną i jedyną strzałką w $[\mathbf{𝐂},\mathbf{𝐃}]$, która sprawia, że poniższy diagram komutuje:

dla każdego $j\in {\mathbf{𝐉}}_0$. A zatem pokazaliśmy, że

$\{c_j:L\to D(j)\mid j\in {\mathbf{𝐉}}_0\}$ jest granicą diagramu $D$ w $[\mathbf{𝐂},\mathbf{𝐃}]$.

W szczególności, kategoria $[{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}]$, o której mówiliśmy już wielokrotnie, jest zupełna i kozupełna (bo $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ jest zupełna i kozupełna). Można również udowodnić - dowód jest nietrudny, ale nie przedstawimy go podczas naszego wykładu - że $[{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}]$ jest kartezjańsko zamknięta. W tym celu musielibyśmy w końcu dokładnie pokazać dowód istnienia naturalnego izomorfizmu:

$[{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}](A\times B,C)\cong [{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}](A,[B,C])$

dla $A,B,C\in [{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}{]}_0$, czego - niestety - nie podejmiemy się tutaj.

Innym wnioskiem wynikającym z dowodu powyższego twierdzenia jest:

Wniosek 8.7 [granice w kategoriach funktorów]

Dla dowolnej lokalnie małej kategorii $\mathbf{𝐂}$ i kategorii (ko)zupełnej $\mathbf{𝐃}$, granice w $[\mathbf{𝐂},\mathbf{𝐃}]$ są liczone po współrzędnych, tj. istnieje naturalny izomorfizm $(\underset{\leftarrow \mathbf{𝐉}}{\lim }F)(X)\cong \underset{\leftarrow \mathbf{𝐉}}{\lim }F(X)$ dla dowolnego funktora $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i obiektu $X\in {\mathbf{𝐂}}_0$.