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

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

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

Definicja 8.1 [Diagram]

Niech $\mathbf {J}$ i $\mathbf {C}$ będą kategoriami. Diagramem typu $\mathbf {J}$ w $\mathbf {C}$ nazywamy funktor $D\colon \mathbf {J} \to \mathbf {C} .$

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 {C} _{0}$ i rodziny strzałek

$c_{j}\colon X\to D_{j},$

po jednej dla każdego obiektu $j\in \mathbf {J} _{0}$, takich że dla każdej strzałki $\alpha \colon i\to j\in \mathbf {J} _{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 {J} _{0}}$ nadaje się na komponenty pewnej transformacji naturalnej. Tak jest rzeczywiście: wystarczy potraktować $c\colon \Delta _{X}\to D$ jako transformację z funktora stałego $\Delta _{X}\colon \mathbf {J} \to \mathbf {C}$:

$\Delta _{X}(j):=X,$ $\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}\colon X\to D_{j}\mid j\in \mathbf {J} _{0}\}.$

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

komutuje dla każdego $j\in \mathbf {J} _{0}$, tzn. $\forall j\in \mathbf {J} _{0}\ d_{j}\circ f=c_{j}$. Kategorię stożków nad diagramem $D$ oznaczamy $\mathbf {Cone} (D)$.

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

Definicja 8.2 [granica diagramu]

Granicą (stożkiem granicznym) diagramu $D\colon \mathbf {J} \to \mathbf {C}$ nazywamy obiekt końcowy w $\mathbf {Cone} (D)$ i oznaczamy go jako $\lim _{\leftarrow \mathbf {J} }D$ lub $\lim _{\leftarrow j}D_{j}$.

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

Dualnie, kogranicą lub granicą odwrotną $D\colon \mathbf {J} \to \mathbf {C}$ nazywamy obiekt początkowy w kategorii kostożków $\mathbf {Cocone} (D)$. (Kostożek nad diagramem $D$ składa się z obiektu $X\in \mathbf {C} _{0}$ i rodziny strzałek

$c_{j}\colon D_{j}\to X,$

po jednej dla każdego obiektu $j\in \mathbf {J} _{0}$, takich że dla każdej strzałki $\alpha \colon i\to j\in \mathbf {J} _{1}$ mamy $c_{j}\circ D_{\alpha }=c_{i}$.) Kogranicę oznaczymy jako $\lim _{\rightarrow \mathbf {J} }D$ lub $\lim _{\rightarrow j}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 {J} =\{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\colon \mathbf {J} \to \mathbf {C}$ jest para obiektów $D_{1},D_{2}\in \mathbf {C} _{0}$. Stożkiem nad $D$ jest obiekt $X\in \mathbf {C} _{0}$ wraz z dwoma strzałkami $c_{1}\colon X\to D_{1}$ i $c_{2}\colon 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\colon Y\to X$ taka, że diagram

komutuje. Innymi słowy, $(X,\{c_{1},c_{2}\})$ jest produktem:

$\lim _{\leftarrow \mathbf {J} }(D)=X=D_{1}\times D_{2}.$

• Granicą diagramu $D\colon \mathbf {0} \to \mathbf {C}$, gdzie $\mathbf {0}$ jest kategorią pustą, jest obiekt końcowy w $\mathbf {C}$. Kogranicą $D$ jest obiekt początkowy w $\mathbf {C}$. Co więcej, $\mathbf {Cone} (D)$ jest kategorią izomorficzną z $\mathbf {C}$ w $\mathbf {Cat}$.
• 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 {C}$, to ich produktem

$\Pi _{i\in I}X_{i}{\stackrel {\pi _{i}}{\longrightarrow }}X_{i}$

nazywamy granicę diagramu $I\to \mathbf {C}$. Mówimy, że ten produkt ma moc równą mocy zbioru $I$. W ogólności, dla małej kategorii $\mathbf {J}$, jej moc będziemy definiować jako moc kolekcji morfizmów $\mathbf {J} _{1}$. Wtedy mocą granicy diagramu $\mathbf {J} \to \mathbf {C}$ nazwiemy moc kategorii $\mathbf {J}$. 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 {C}$ będzie kategorią, w której istnieją wszystkie ekwalizatory. Jeśli $\mathbf {J}$ jest małą kategorią i w $\mathbf {C}$ istnieją wszystkie produkty mocy mniejszej lub równej mocy $\mathbf {J}$, to w $\mathbf {C}$ istnieją wszystkie granice typu $\mathbf {J}$.

Dowód

Niech $D\colon \mathbf {J} \to \mathbf {C}$ będzie diagramem. Połóżmy: $X:=\Pi _{i\in \mathbf {J} _{0}}D_{i},$ $Y:=\Pi _{\alpha \in \mathbf {J} _{1}}D_{\mathrm {cod} (\alpha )}.$

Niech $f,g\colon 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}\colon E{\stackrel {e}{\longrightarrow }}X{\stackrel {\pi _{j}}{\longrightarrow }}D_{j}$

dla każdego $j\in \mathbf {J} _{0}$. Te strzałki tworzą stożek nad $D$, ponieważ dla dowolnego $\alpha \colon i\to j\in \mathbf {J} _{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\colon Z\to X$ z $\pi _{j}\circ h=d_{j}$. Dlatego:

$\pi _{\alpha }\circ f\circ h=D_{\alpha }\circ \pi _{\mathrm {dom} (\alpha )}\circ h=D_{\alpha }\circ d_{\mathrm {dom} (\alpha )}=d_{\mathrm {cod} (\alpha )}=\pi _{\alpha }\circ g\circ h$

dla dowolnego $\alpha \in \mathbf {J} _{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\colon 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 {C}$ ma wszystkie granice danej mocy wtedy i tylko wtedy, gdy ma wszystkie produkty i ekwalizatory tej mocy.
2. Kategoria $\mathbf {C}$ ma wszystkie kogranice danej mocy wtedy i tylko wtedy, gdy ma koprodukty i koekwalizatory tejże mocy.
3. Kategoria $\mathbf {C}$ ma skończone granice wtedy i tylko wtedy, gdy ma skończone koprodukty i skończone koekwalizatory.
4. Jeśli $\mathbf {C}$ ma ekwalizatory i wszystkie małe produkty, to ma wszystkie małe granice.
5. Jeśli $\mathbf {C}$ 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 {C}$ 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 {Set}$ 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\colon \mathbf {J} \to \mathbf {Set}$ mamy:

$\lim _{\leftarrow \mathbf {J} }D=\{(x_{j})_{j\in \mathbf {J} _{0}}\in \Pi _{j\in \mathbf {J} _{0}}d_{j}\mid \forall \alpha \colon i\to j\ \ D_{\alpha }(x_{i})=x_{j}\},$

razem z projekcjami $\pi _{j}\colon \lim _{\leftarrow \mathbf {J} }D\to d_{j}$, $(x_{j})_{j\in \mathbf {J} _{0}}\mapsto x_{j}$.

• Poset $(P,\leq )$ 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 {C}$, 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 {C}$ 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 {C}$ będzie lokalnie mała. Jeśli kategoria $\mathbf {D}$ ma (ko)granice typu $\mathbf {J}$, to kategoria funktorów $[\mathbf {C} ,\mathbf {D} ]$ też.

Dowód

Zauważmy, że diagram $D\colon \mathbf {J} \to [\mathbf {C} ,\mathbf {D} ]$ może być traktowany jako funktor

$D\colon \mathbf {J} \times \mathbf {C} \to \mathbf {D}$. Z założenia, dla każdego $X\in \mathbf {C} _{0}$ diagram:

$D(-,X)\colon \mathbf {J} \to \mathbf {D}$

ma pewną granicę, nazwijmy ją:

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

Dla dowolnej strzałki $f\colon X\to X'$ dostajemy zatem stożek nad $D(-,X')$:

$\{L(X){\stackrel {c_{j,X}}{\longrightarrow }}D(j,X){\stackrel {D(1_{j},f)}{\longrightarrow }}D(j,X')\mid j\in \mathbf {J} _{0}\},$

który faktoryzuje się przez granicę diagramu $D(-,X')$, 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 {C} ,\mathbf {D} ]_{0}$. Co więcej, powyższy rysunek pokazuje też, że $c_{j,-}\colon L\to D(j)$ jest strzałką w $[\mathbf {C} ,\mathbf {D} ]$. Ponieważ każda kolekcja

$\{c_{j,X}\mid j\in \mathbf {J} _{0}\}$

jest stożkiem, dostajemy:

któryż to diagram komutuje dla każdego $\alpha \colon i\to j\in \mathbf {J} _{1}$. To znaczy, że

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

jest stożkiem nad $D$.

Mając dany dowolny inny stożek

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

nad $D$,

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

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

A zatem jedyność $\phi _{X}$ sprawia, że $\phi \colon M\to L$ jest transformacją naturalną i jedyną strzałką w $[\mathbf {C} ,\mathbf {D} ]$, która sprawia, że poniższy diagram komutuje:

dla każdego $j\in \mathbf {J} _{0}$. A zatem pokazaliśmy, że

$\{c_{j}\colon L\to D(j)\mid j\in \mathbf {J} _{0}\}$ jest granicą diagramu $D$ w $[\mathbf {C} ,\mathbf {D} ]$.

W szczególności, kategoria $[\mathbf {C} ^{op},\mathbf {Set} ]$, o której mówiliśmy już wielokrotnie, jest zupełna i kozupełna (bo $\mathbf {Set}$ 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 {C} ^{op},\mathbf {Set} ]$ jest kartezjańsko zamknięta. W tym celu musielibyśmy w końcu dokładnie pokazać dowód istnienia naturalnego izomorfizmu:

$[\mathbf {C} ^{op},\mathbf {Set} ](A\times B,C)\cong [\mathbf {C} ^{op},\mathbf {Set} ](A,[B,C])$

dla $A,B,C\in [\mathbf {C} ^{op},\mathbf {Set} ]_{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 {C}$ i kategorii (ko)zupełnej $\mathbf {D}$, granice w $[\mathbf {C} ,\mathbf {D} ]$ są liczone po współrzędnych, tj. istnieje naturalny izomorfizm $(\lim _{\leftarrow \mathbf {J} }F)(X)\cong \lim _{\leftarrow \mathbf {J} }F(X),$ dla dowolnego funktora $F\colon \mathbf {C} \to \mathbf {D}$ i obiektu $X\in \mathbf {C} _{0}$.