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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

Tk-8.1.png

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

Tk-8.2.png

(gdzie z premedytacją piszemy zamiast , zamiast itd.). Widzimy, że obraz kategorii w kategorii jest... diagramem! Pamiętając to spostrzeżenie, bez większych wahań zaakceptujemy następującą definicję:


Definicja 8.1 [Diagram]

Niech i będą kategoriami. Diagramem typu w nazywamy funktor

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

Ilustracja8.png

Granice i kogranice

Stożek nad diagramem składa się z obiektu i rodziny strzałek

po jednej dla każdego obiektu , takich że dla każdej strzałki diagram

Tk-8.3.png

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

Ktoś spostrzegawczy zapewne zauważył już, że rodzina strzałek nadaje się na komponenty pewnej transformacji naturalnej. Tak jest rzeczywiście: wystarczy potraktować jako transformację z funktora stałego :

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

Stożek o wierzchołku oznaczamy jako lub lub

Stożki również tworzą kategorię: morfizmem stożków nazywamy strzałkę taką, że:

Tk-8.4.png

komutuje dla każdego , tzn. . Kategorię stożków nad diagramem oznaczamy .

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


Definicja 8.2 [granica diagramu]

Granicą (stożkiem granicznym) diagramu nazywamy obiekt końcowy w i oznaczamy go jako lub .


Innymi słowy, stożek nad jest granicą, jeśli dla dowolnego innego stożka istnieje dokładnie jedna strzałka , która jest morfizmem stożków, tzn. taka że poniższy diagram komutuje dla każdego :

Tk-8.5.png

Dualnie, kogranicą lub granicą odwrotną nazywamy obiekt początkowy w kategorii kostożków . (Kostożek nad diagramem składa się z obiektu i rodziny strzałek

po jednej dla każdego obiektu , takich że dla każdej strzałki mamy .) Kogranicę oznaczymy jako lub .

Przykłady:

  • Produkt jest granicą diagramu typu:
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 kategorię dyskretną z dwoma obiektami i i dwoma morfizmami (tzn. nie ma strzałek innych poza identycznościami) (rysunek jak wyżej). Diagramem jest para obiektów . Stożkiem nad jest obiekt wraz z dwoma strzałkami i , tzn.

Tk-8.7.png

Zgodnie z tym, co tłumaczyliśmy tuż pod Definicją 5.2, tenże jest granicą , jeśli dla dowolnego innego stożka

Tk-8.8.png

istnieje dokładnie jedna strzałka taka, że diagram

Tk-8.9.png

komutuje. Innymi słowy, jest produktem:

  • Granicą diagramu , gdzie jest kategorią pustą, jest obiekt końcowy w . Kogranicą jest obiekt początkowy w . Co więcej, jest kategorią izomorficzną z w .
  • Ekwalizator jest granicą diagramu typu
Tk-8.10.png
  • Pulbak jest granicą diagramu typu
Tk-8.11.png
  • Pushout jest kogranicą diagramu typu
Tk-8.12.png

Uogólniając dwa pierwsze przykłady powyżej, jeśli jest zbiorem (tj. kategorią dyskretną), zaś jest indeksowaną kolekcją obiektów z , to ich produktem

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

Dowód

Niech będzie diagramem. Połóżmy:

Niech będą jedynymi strzałkami, dla których poniższe diagramy komutują (dla każdego ):

Tk-8.13.png
Tk-8.13A.png

Niech

Tk-8.14.png

będzie ekwalizatorem i . Zdefiniujmy:

dla każdego . Te strzałki tworzą stożek nad , ponieważ dla dowolnego

Co więcej, dla dowolnego innego stożka mamy morfizm z . Dlatego:

dla dowolnego . A zatem . Mamy więc następującą sytuację:

Tk-8.15.png

tzn. z faktu, że jest ekwalizatorem wynika, że istnieje dokładnie jedna strzałka , która spełnia . Tak więc:

czyli jest morfizmem stożków. To kończy dowód faktu, że jest granicą .

End of proof.gif


Wniosek 8.4

  1. Kategoria ma wszystkie granice danej mocy wtedy i tylko wtedy, gdy ma wszystkie produkty i ekwalizatory tej mocy.
  2. Kategoria ma wszystkie kogranice danej mocy wtedy i tylko wtedy, gdy ma koprodukty i koekwalizatory tejże mocy.
  3. Kategoria ma skończone granice wtedy i tylko wtedy, gdy ma skończone koprodukty i skończone koekwalizatory.
  4. Jeśli ma ekwalizatory i wszystkie małe produkty, to ma wszystkie małe granice.
  5. Jeśli 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). 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 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 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 mamy:

razem z projekcjami , .

  • Poset 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 posiada dowolne suprema.
  • Uogólnieniem poprzedniego przykładu jest stwierdzenie: każda kategoria , 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 jest duża. Dalsze informacje zawiera Zadanie 8.2.

(Ko)granice w kategoriach funktorów

Jest znanym faktem, że jeśli jest kratą zupełną, to zbiór wszystkich funkcji monotonicznych o kodziedzinie , 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 będzie lokalnie mała. Jeśli kategoria ma (ko)granice typu , to kategoria funktorów też.

Dowód

Zauważmy, że diagram może być traktowany jako funktor

. Z założenia, dla każdego diagram:

ma pewną granicę, nazwijmy ją:

Dla dowolnej strzałki dostajemy zatem stożek nad :

który faktoryzuje się przez granicę diagramu , jak na rysunku:

Tk-8.17.png

Jedyność strzałki implikuje, że oraz . To znaczy, że jest funktorem, . Co więcej, powyższy rysunek pokazuje też, że jest strzałką w . Ponieważ każda kolekcja

jest stożkiem, dostajemy:

Tk-8.18.png

któryż to diagram komutuje dla każdego . To znaczy, że

jest stożkiem nad .

Mając dany dowolny inny stożek

nad ,

jest stożkiem nad , który w związku z tym faktoryzuje się przez stożek graniczny:

Tk-8.19.png

A zatem jedyność sprawia, że jest transformacją naturalną i jedyną strzałką w , która sprawia, że poniższy diagram komutuje:

Tk-8.20.png

dla każdego . A zatem pokazaliśmy, że

jest granicą diagramu w . End of proof.gif

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

dla , 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 i kategorii (ko)zupełnej , granice w są liczone po współrzędnych, tj. istnieje naturalny izomorfizm
dla dowolnego funktora i obiektu .