Teoria kategorii dla informatyków/Wykład 3: Zasada dualności i proste konstrukcje uniwersalne

Z Studia Informatyczne
< Teoria kategorii dla informatyków
Wersja z dnia 10:13, 27 lis 2006 autorstwa Pqw (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Kilkakrotnie podczas naszych wykładów pojawiła się dualność, która - jak wyjaśniliśmy w Definicji 2.3 - polega na tym, że dla dowolnej kategorii możemy zbudować kategorię poprzez odwrócenie kierunku strzałek i wszelkie własności mają swoje odbicie we własnościach . Ta intuicja jest bardzo pomocna, więc warto precyzyjnie i systematycznie zbadać pojęcie dualności w teorii kategorii, które - na pierwszy rzut oka - trywialne, ma daleko idące konsekwencje: każde udowodnione twierdzenie ma swój dualny odpowiednik, równie ciekawy jak oryginalny, którego dowód dostajemy za darmo, zgodnie z zasadą dualności.

Zasada dualności

Przypomnijmy formalną definicję kategorii: składa się ona z obiektów: , morfizmów: , czterech operacji , które podlegają siedmiu aksjomatom: , , , , , , , przy czym jest zdefiniowane tylko jeśli , więc w rzeczywistości trzy ostatnie aksjomaty powinny być zastąpione przez implikacje, np. to w rzeczywistości . Niech CT będzie zdaniem, które oznacza koniunkcję wszystkich siedmiu aksjomatów w ich pełnej wersji.

Ilustracja4k.png

Powiemy, że zdanie jest wyrażone w elementarnym języku teorii kategorii, jeśli w jest poprawnie zbudowanym wyrażeniem mówiącym jedynie o obiektach, morfizmach i operacjach , , , . Na przykład CT jest wyrażone w elementarnym języku teorii kategorii.

Dla dowolnego takiego zdania elementarnego możemy utworzyć elementarne zdanie dualne , dokonując następującej zamiany:

Widzimy, że wówczas jest poprawnie zbudowanym wyrażeniem. Przypuśćmy zatem, że ze zdania wynika inne elementarne zdanie bez użycia aksjomatów teorii kategorii. Wtedy ze zdania wynika . Ale aksjomaty teorii kategorii są samodualne: CT= CT. To znaczy, że następujące metastwierdzenie jest prawdziwe:


Fakt 3.1 [formalna zasada dualności]

Dla dowolnego zdania elementarnego w języku teorii kategorii, które wynika z aksjomatów teorii kategorii, również wynika z aksjomatów teorii kategorii.

To znaczy również, że każda interpretacja zdania w kategorii daje interpretację zdania w . Ponieważ jednak , dostajemy:


Fakt 3.2 [zasada dualności]

Jeśli zdanie jest prawdziwe w każdej kategorii, to również jest prawdziwe w dowolnej kategorii.

Dowód

Skoro jest prawdziwe w każdej kategorii , to jest prawdziwe w każdej kategorii . Stąd wynika, że jest prawdziwe w , czyli w . End of proof.gif

Produkt i koprodukt

Naszym zadaniem jest teraz zaproponowanie takiej definicji produktu obiektów kategorii, aby wszystkie znane pojęcia: produktu zbiorów, produktu grup, produktu przestrzeni wektorowych, produktu częściowych porządków, i tak dalej, stały się szczególnym przypadkiem naszej propozycji. Czy to możliwe? Okazuje się, że tak! Ta możliwość jest odbiciem bardzo ważnej własności pojęcia produktu: własności uniwersalnej. Własność ta jest wyrażona w języku strzałek i mówi, że produkt jest zdefiniowany z dokładnością do izomorfizmu, tzn. jest to taki obiekt, który jest izomorficzny z każdym możliwym dobrym kandydatem na produkt. Rozważmy najpierw produkt w , którego obserwacja wskaże nam sposób, w jaki najlepiej sformułować własność uniwersalną produktu i podać definicję kategoryjną, niezależną od specyfiki kategorii zbiorów . Często będziemy pracować w ten właśnie sposób: podglądamy jak dana konstrukcja uniwersalna wygląda dla zbiorów (bo tam mamy najlepsze intuicje), potem wyciągamy wnioski ogólne, a na końcu testujemy nasze kategoryjne definicje na dalszych przykładach.

Niech będą zbiorami. Teoria mnogości definiuje ich produkt jako następujący zbiór par uporządkowanych:

Produkt zbiorów możemy zdekonstruować za pomocą projekcji:

gdzie i . Użyliśmy słowa dekonstrukcja nieprzypadkowo: informatykowi, który przecież zna podstawy programowania obiektowego, wygodnie będzie myśleć o produkcie jako o obiekcie wyposażonym w destruktory , pozwalające z informacji zawartych w produkcie wydobyć informację o jego składowych. Ta dekonstrukcja przebiega w sposób bardzo porządny, odwracalny, ponieważ dla każdego mamy . To równanie jest niezwykle ważne, gdyż wskazuje na własność uniwersalną produktu: poniższy diagram komutuje:

Tk-3.1.png

gdzie oznacza obiekt końcowy w . Ten diagram czytamy oczywiście tak: dla dowolnych elementów , istnieje dokładnie jeden element taki, że i . Jeśli teraz zastąpimy elementy przez elementy uogólnione (patrz ten podrozdział), dostajemy:


Definicja 3.3 [produkt]

Niech będzie dowolną kategorią, zaś jej obiektami. Produktem obiektów i nazywamy obiekt wraz ze strzałkami i :

który posiada następującą własność uniwersalną:

Dla dowolnego diagramu:

w kategorii , istnieje dokładnie jedna strzałka taka, że i (czyli taka, że poniższy diagram komutuje).

Tk-3.2.png

Taką strzałkę oznaczamy zwyczajowo .


Fakt 3.4

Produkt jest jedyny z dokładnością do izomorfizmu.

Dowód

Niech

będą dwoma produktami i . Wówczas poniższy diagram komutuje:

Tk-3.3.png

ponieważ wszystkie trzy jego części komutują (a przyczyną tego jest dokładnie po trzykroć definicja produktu):

Tk-3.4.png

To znaczy, że . Zamieniając miejscami na diagramach role i , otrzymamy również zależność , co świadczy o tym, że i są izomorficzne: .

End of proof.gif

Przykłady:

  • W zbiorach z dodatkową strukturą, jak np. grupy czy monoidy, produkt konstruuje się, biorąc produkt zbiorów podkładowych wraz z operacjami po współrzędnych; np. produktem dwóch grup , jest zbiór wraz z działaniami:

i elementem neutralnym . Projekcje to homomorfizmy i .

  • Kategoria posiada produkty, to znaczy: dla dowolnych dwóch małych kategorii , istnieje ich produkt . Obiektami są uporządkowane pary obiektów z i , morfizmami - uporządkowane pary morfizmów z i projekcjami funktory oraz dane jako:

dla . Sprawdzenie, że taka definicja daje nam produkt jest bardzo łatwe - wszystko dzieje się tak, jak w .

  • W Zadaniu 1.11 zdefiniowaliśmy kategorię typów dla -rachunku. Ta kategoria posiada produkty, to znaczy: każde dwa obiekty tej kategorii posiadają produkt. Przekonajmy się o tym. Rzeczywiście, mając dane typy i , definiujemy:

Mając dane i jak na diagramie:

Tk-3.5.png

definiujemy

Sprawdźmy, że diagram rzeczywiście komutuje:

i podobnie . Jeśli teraz również spełnia i , to wtedy:

Wykazaliśmy więc, że kategoria ma produkty.

Jeszcze jeden przykład znajduje się w Zadaniu 3.1.

Dzięki zasadzie dualności, definicję i własności obiektu dualnego do produktu, tzw. koproduktu dostajemy za darmo (porównaj bardzo dokładnie(!) z Definicją 3.3):


Definicja 3.5 [koprodukt]

Niech będzie dowolną kategorią, zaś jej obiektami. Koproduktem obiektów i nazywamy obiekt wraz ze strzałkami i :

który posiada następującą własność uniwersalną:

Dla dowolnego diagramu:

w kategorii , istnieje dokładnie jedna strzałka taka, że i (czyli taka, że poniższy diagram komutuje). Strzałkę oznaczmy zwyczajowo jako .

Tk-3.6.png

Stwierdzenie dualne do Faktu 3.4 mówi nam, że koprodukt jest jedyny z dokładnością do izomorfizmu! Omówienie koproduktu w jest przedmiotem Zadania 3.2.

Ekwalizator i koekwalizator

Definicja 3.6 [ekwalizator]

Dla dwóch równoległych strzałek w kategorii , ich ekwalizatorem nazywamy obiekt wraz ze strzałką , która:

  • ekwalizuje i , tzn. oraz
  • jest uniwersalna, tzn. dla dowolnej strzałki , takiej że , istnieje dokładnie jedna strzałka taka, że , tzn. taka, że poniższy diagram komutuje:
Tk-3.7.png


W ekwalizatorem dwóch funkcji musi być zbiór, na którym funkcje się zgadzają, więc zgadujemy, że . Z takim zbiorem w oczywisty sposób jest związana inkluzja , dla . Pokażmy, że jest ekwalizatorem.

Ilustracja6.png

Niech będzie dowolnym zbiorem z funkcją tak, że . Wtedy dla każdego . Ale to oznacza, że faktoryzuje się przez . Ta faktoryzacja jest jednoznaczna, bo jest mono (jeśli i , to , stąd mono implikuje ).

To nie przypadek, że jest monomorfizmem:


Fakt 3.7

Każdy ekwalizator jest monomorfizmem.

Dowód

Rozważmy diagram:
Tk-3.8.png

gdzie zakładamy, że ekwalizuje oraz . Ponieważ jest typu oraz , więc z własności uniwersalnej wynika, że istnieje dokładnie jedna strzałka taka, że . Jako da się podstawić zarówno jak i i ostatnie równanie pozostanie prawdziwe, więc musi być . To kończy dowód, że jest mono.

End of proof.gif

W innych kategoriach, jak , , ekwalizatorem jest zbiór strzałek jest podzbiór zbioru wraz ze strukturą dziedziczoną z , zawężoną do (np. w , zbiór dostaje topologię podprzestrzeni).

Pojęciem dualnym do ekwalizatora jest koekwalizator. Co ciekawe - koekwalizatory są uogólnieniem pojęcia przestrzeni ilorazowej i odwzorowania ilorazowego przypisującego elementowi jego klasę abstrakcji.


Definicja 3.8

Koekwalizatorem pary strzałek nazywamy taki obiekt wraz ze strzałką , która:
  • koekwalizuje , tzn. oraz
  • jest uniwersalna, tzn. dla dowolnej strzałki , która koekwalizuje: , istnieje dokładnie jednak strzałka taka, że .
Tk-3.9.png

Dualność wraz z Faktem 3.7 implikują, że koekwalizator jest zawsze epimorfizmem. Sztandarowym przykładem koekwalizatora w jest koekwalizator typu

Tk-3.10.png

gdzie jest relacją równoważności na , zaś są projekcjami. Koekwalizatorem jest wtedy zbiór ilorazowy wraz z kanonicznym przekształceniem ilorazowym danym jako , gdzie jest klasą równoważności elementu przy relacji .

Oczywiście w istnieją wszystkie koekwalizatory, tzn. dla każdej pary znajdziemy koekwalizator. Jest nim zbiór podzielony przez relację równoważności daną jako przecięcie wszystkich relacji równoważności takich, że wtedy i tylko wtedy, gdy . Szczegóły techniczne nie są ciekawe, więc je pomijamy.

Pulbak i pushout

Przed nami terra incognita, gdzie znane z intuicje odszukujemy w coraz bardziej złożonych formach, trudniejszych niż w przypadku poprzednio omówionych granic. Pulbak (produkt włóknisty), który pojawia się bardzo często w matematyce, w logice w szczególności, w stanowi uogólnienie zarówno operacji przecięcia zbiorów, jak i przeciwobrazu funkcji. Jego dualnym odpowiednikiem jest pushout. (Pozwalamy sobie pozostać przy angielskich nazwach, ustępując pola lingwistom, którzy chcieliby znaleźć, choćby dla pushoutu, wygodniejszą nazwę niż koprodukt włóknisty.)


Definicja 3.9 [pulbak]

Pulbakiem strzałek takich, że w kategorii

Tk-3.11.png

nazywamy obiekt wraz ze strzałkami

Tk-3.12.png

taki, że:

  • poniższy kwadrat pulbakowy komutuje, tzn. oraz
  • uniwersalny, tzn. dla dowolnego innego kandydata na pulbak

istnieje dokładnie jedna strzałka taka, że: i , tzn. taka, że poniższy diagram komutuje:

Tk-3.13.png


Uwaga
O takiej sytuacji będziemy mówili, że jest pulbakiem wzdłuż lub że jest pulbakiem wzdłuż (stąd nazwa pulbak - od angielskiego pulling back).

Pulbak nazywa się często w literaturze produktem włóknistym i jest ku temu dobra przyczyna: w dowolnej kategorii z produktami (tzn. w takiej kategorii , w której istnieje produkt dowolnych dwóch obiektów) i ekwalizatorami, dla diagramu

rozważmy inny diagram:

Tk-3.14.png

gdzie są projekcjami produktu . Niech

Tk-3.15.png

będzie ekwalizatorem. Wtedy

Tk-3.16.png

jest pulbakiem strzałek .

Oto dowód (pomijamy dla prostoty symbol złożenia ): oczywiście , więc pierwszy punkt definicji pulbaku jest spełniony. Po drugie, jeśli

Tk-3.17.png

komutuje, to dla strzałki

z własności uniwersalnej ekwalizatora istnieje dokładnie jedna strzałka taka, że

Tk-3.18.png

komutuje. Oczywiście komutuje też

Tk-3.19.png

co kończy dowód faktu, że jest pulbakiem. q.e.d.

A zatem można sobie wyobrażać, że pulbak powstaje jako ekwalizator produktu, co w szczególności dla implikuje, że pulbak funkcji

jest zbiorem

wraz z zanurzeniem .

Podsumowując powyższą dyskusję, pokazaliśmy że:

Wniosek 3.10

W dowolnej kategorii z produktami i ekwalizatorami istnieją wszystkie pulbaki.

Prawdziwe jest również stwierdzenie odwrotne, które jest treścią Zadania 3.4. Wykład zakończymy podrozdziałem, który ilustruje własności pulbaków i do którego warto wrócić raz jeszcze po przeczytaniu Wykładu 5.

Własności pulbaków

Lemat 3.11 [Lemat Pulbakowy]

Załóżmy, że diagram
Tk-3.20.png

komutuje. Wówczas:

  • Jeśli prawy kwadrat i zewnętrzny prostokąt są kwadratami pulbakowymi, to lewy kwadrat też.
  • Jeśli dwa wewnętrzne kwadraty są pulbakami, to zewnętrzny prostokąt też jest pulbakiem.

Dowód powyższego lematu jest treścią Zadania 3.8. Konsekwencją Lematu Pulbakowego jest natychmiast:

Wniosek 3.12

Pulbak komutującego trójkąta jest komutującym trójkątem. To znaczy: jeśli na poniższym diagramie w kształcie pryzmy
Tk-3.21.png

prawy trójkąt komutuje i dla tworzymy pulbaki:

  • jako pulbak wzdłuż ,
  • jako pulbak wzdłuż ,

to istnieje dokładnie jedna strzałka taka, że lewy trójkąt komutuje i taka, że trzecia ze ścian pryzmy (górna) również jest pulbakiem.

Dowód

Wynika natychmiast z Lematu Pulbakowego, jeśli przyjmiemy jako strzałkę uniwersalną pulbaku wzdłuż i przerysujemy wygodnie pryzmę jako:
Tk-3.22K.png

(wtedy z faktu, że najbardziej zewnętrzny prostokąt i prawy kwadrat są pulbakami wynika, teza: lewy kwadrat jest pulbakiem).

End of proof.gif

Stwierdzenie 3.13

Pulbak jest funktorem tzn. w kategorii z pulbakami, dla każdej strzałki istnieje funktor definiowany na obiekcie jako:

i na strzałce jak w powyższym wniosku (tzn: : porównaj diagram-pryzmę).

Dowód

Musimy pokazać, że

i

Obie własności łatwo sprawdzić, stosując Lemat Pulbakowy. My pokażemy tylko pierwszą, pozostawiając drugą dla zainteresowanego czytelnika. Rozważmy zatem diagram:

Tk-3.23K1.png

Jeśli dolny kwadrat jest pulbakiem, to oczywiście zewnętrzny prostokąt też. Z Lematu Pulbakowego wynika, że górny kwadrat komutuje. A zatem .

End of proof.gif