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

From Studia Informatyczne

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

Grafika:tk-8.1.png

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

Grafika:tk-8.2.png

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

Grafika:ilustracja8.png

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

Grafika:tk-8.3.png

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:

Grafika:tk-8.4.png

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:

Grafika:tk-8.5.png
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:
Grafika:tk-8.6.png

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.

Grafika:tk-8.7.png

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

Grafika:tk-8.8.png

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

Grafika:tk-8.9.png

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
Grafika:tk-8.10.png
  • Pulbak jest granicą diagramu typu
Grafika:tk-8.11.png
  • Pushout jest kogranicą diagramu typu
Grafika:tk-8.12.png

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

Grafika:tk-8.13.png
Grafika:tk-8.13A.png

Niech

Grafika:tk-8.14.png

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

Grafika:tk-8.15.png

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.

image:End_of_proof.gif


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). image:End_of_proof.gif

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:

Grafika:tk-8.17.png

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:

Grafika:tk-8.18.png

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:

Grafika:tk-8.19.png

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:

Grafika:tk-8.20.png

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}]. image:End_of_proof.gif

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.