Teoria kategorii dla informatyków/Wykład 2: Morfizmy specjalne

From Studia Informatyczne

Podczas tego wykładu poznamy dalsze możliwości definiowania znanych pojęć matematycznych za pomocą własności obiektów i morfizmów w kategoriach. Opis kategoryjny sprawdza się szczególnie dobrze dla własności uniwersalnych, tj. tych niezależnych od specyficznych założeń danej teorii matematycznej. Jeden typ morfizmów specjalnych już poznaliśmy, a mianowicie izomorfizmy (Definicja 1.7). Tutaj poznamy dalsze przykłady.


Spis treści

Monomorfizmy, epimorfizmy, sekcje i retrakcje

Definicja 2.1

Niech \mathbf{C} będzie kategorią. Strzałka f\colon A\to B\in \mathbf{C}_1 jest mono(morfizmem), jeśli dla każdego obiektu C\in \mathbf{C}_0 i równoległych strzałek g,h\colon C\to A równość f\circ g = f\circ h implikuje g=h.

Innymi słowy, f jest mono, jeśli z faktu, że poniższy diagram komutuje:

Grafika:tk-2.1.png

wynika, że g=h.

Monomorfizmy znane są w \mathbf{Set} jako injekcje, bo przecież funkcja f\colon A\to B jest injekcją wtedy i tylko wtedy, gdy

\forall a,b\in A\ (f(a)=f(b)\Rightarrow a=b)

wtedy i tylko wtedy, gdy

\forall c\in C\ ((f\circ g)(c)= (f\circ h)(c)\Rightarrow g(c)=h(c)))

wtedy i tylko wtedy, gdy f jest mono w \mathbf{Set}.

Podobnie w \mathbf{Grp}, \mathbf{CRng}, \mathbf{Pos}: monomorfizmami są strzałki injektywne.


Definicja 2.2 [monomorfizm, epimorfizm]

Niech \mathbf{C} będzie kategorią. Strzałka f\colon A\to B\in \mathbf{C}_1 jest epi(morfizmem) jeśli dla każdego obiektu C\in \mathbf{C}_0 i równoległych strzałek g,h\colon B\to C równość g\circ f = h\circ f implikuje g=h.

A zatem aby strzałka f\colon A\to B była epi, komutowanie diagramu:

Grafika:tk-2.2.png

pociąga za sobą równość g=h.

Zauważmy, że definicje monomorfizmu i epimorfizmu są bardzo podobne. Istotnie, po odwróceniu kierunku strzałek pierwsza definicja pokrywa się z drugą i vice versa. W takim przypadku mówimy, że definicje monomorfizmu i epimorfizmu są dualne. Aby precyzyjnie wypowiedzieć znaczenie dualności, potrzebujemy następującej definicji:


Definicja 2.3 [kategoria dualna]

Jeśli \mathbf{C} jest kategorią, to kategoria dualna \mathbf{C}^{op} jest definiowana jako \mathbf{C}^{op}_0 = \mathbf{C}, \mathbf{C}^{op}_1 = \mathbf{C}_1, ale \mathrm{dom}_{\mathbf{C}^{op}}(f) = \mathrm{cod}_{\mathbf{C}}(f), \mathrm{cod}_{\mathbf{C}^{op}}(f) = \mathrm{dom}_{\mathbf{C}}(f), f\circ_{\mathbf{C}^{op}}g = g\circ_{\mathbf{C}} f.


A zatem \mathbf{C}^{op} jest utworzona z \mathbf{C} poprzez odwrócenie kierunku strzałek.

Dualność definicji monomorfizmu i epimorfizmu wyraża się więc jako:


Fakt 2.4

Strzałka f\colon A\to B jest (mono-)epomorfizmem w kategorii \mathbf{C} wtedy i tylko wtedy, gdy jest (epi-)monomorfizmem w \mathbf{C}^{op}.

Dualność i prawa, jakimi się rządzi, zbadamy dogłębnie na początku następnego wykładu. Tymczasem zauważmy proste własności mono- i epimorfizmów:


Fakt 2.5

  • Jeśli g\circ f jest mono, to f jest mono.
  • Złożenie monomorfizmów jest monomorfizmem.
  • Jeśli g\circ f jest epi, to g jest epi.
  • W \mathbf{Set}, f jest epi wtedy i tylko wtedy, gdy f jest surjekcją.
  • Złożenie epimorfizmów jest epimorfizmem.


Należy dość ostrożnie interpretować powyższe wyniki, tak by nie dać skusić się myśli, że monomorfizmy to po prostu abstrakcyjnie zdefiniowane injekcje, a epimorfizmy to abstrakcyjne surjekcje (tak oczywiście jest w \mathbf{Set}, ale w innych kategoriach niekoniecznie). Okazuje się bowiem, że:


Przykład 2.6

W \mathbf{Mon} zanurzenie liczb naturalnych w całkowite i\colon\mathbb{N}\to \mathbb{Z} jest epimorfizmem, ale nie jest surjekcją.

Dowód

Załóżmy, że poniższy diagram komutuje:
Grafika:tk-2.3.png

gdzie (M,*,e) jest dowolnym monoidem, tzn. że f\circ i=g\circ i, co nieformalnie oznacza, że morfizmy f i g zgadzają się na liczbach dodatnich. Wówczas: f(-1) = f(-1)*e = f(-1)*g(1-1) = f(-1)*g(1)*g(-1) = f(-1)*f(1)*g(-1) = e*g(-1)=g(-1) i podobnie dowiedziemy, że f(-a) = f(a) dla dowolnego a>0. To znaczy, że f i g zgadzają się na \mathbb{Z}, i.e. f=g. Jest jednak oczywiste, że injekcja i nie jest surjekcją. A zatem w \mathbf{Mon} epimorfizmy i surjekcje to nie to samo.

image:End_of_proof.gif


Czy strzałka może być jednocześnie mono i epi? Oczywiście tak: łatwo przekonać się, że izomorfizmy są zawsze mono i epi (np. w \mathbf{Set} bijekcje (izomorfizmy) są jednocześnie injekcjami (mono) i surjekcjami (epi)). Poprzedni przykład w \mathbf{Mon} wskazuje jednak, że stwierdzenie odwrotne jest w ogólności nieprawdziwe, tzn. strzałka mono i epi nie musi być izomorfizmem (poniżej zdefiniujemy pojęcia silniejsze od mono i epi, które w pełni opiszą izomorfizmy - patrz przedostatni punkt Faktu Faktu 2.9).
Karol Borsuk (1905-1982)Zobacz biografię
Enlarge
Karol Borsuk (1905-1982)
Zobacz biografię

Poznajmy więc pewne szczególnie często spotykane mono i epi:

Definicja 2.7 [sekcja]

Morfizm f\colon A\to B w kategorii \mathbf{C} jest sekcją, jeśli istnieje morfizm g\colon B\to A taki, że g\circ f = 1_A (mówi się wtedy, że f ma lewą odwrotność).

Każda sekcja jest mono: jeśli f\colon A\to B jest sekcją, to równość f\circ h = f\circ k dla pewnych strzałek h,k\colon C\to A implikuje h = 1_A\circ h = g\circ f\circ h = g\circ f\circ k = 1_A\circ k = k.

Nazwa sekcja pochodzi od pewnego znamienitego przykładu: jeśli f\colon A\to B jest morfizmem w \mathbf{Set} (albo w \mathbf{Top} czy \mathbf{Grp}), można rozważyć graf morfizmu f jako podzbiór (odpowiednio: podprzestrzeń w \mathbf{Top} lub podgrupę w \mathbf{Grp}) produktu A\times B. Wówczas zanurzenie A w A\times B zdefiniowane jako a\mapsto (a, f(a)) jest sekcją (obraz tego zanurzenia niejako przecina produkt, stąd nazwa).

Grafika:tk-2.4.png

Pojęciem dualnym do sekcji jest retrakcja. Nazwy retrakcja i retrakt pochodzą z Topologii. Teorię retraktów topologicznych stworzył i rozwinął profesor Karol Borsuk z Uniwersytetu Warszawskiego w pierwszej połowie XX wieku.


Definicja 2.8 [retrakcja]

Morfizm f\colon A\to B w kategorii \mathbf{C} jest retrakcją, jeśli istnieje morfizm g\colon B\to A taki, że f\circ g = 1_B (mówi się wtedy, że f ma prawą odwrotność). Jeśli taka retrakcja istnieje, to mówimy, że B jest retraktem A.

Własności sekcji i retrakcji są silniejsze od własności monomorfizmów i epimorfizmów: sekcje i retrakcje zachowują się bardzo porządnie pod wpływem funktorów (definicja funktora - Definicja 5.1 - i podstawowe intuicje związane z tym pojęciem są tematem Wykładu 5).


Fakt 2.9

  • Jeśli g\circ f jest sekcją, to f jest sekcją.
  • Złożenie sekcji jest sekcją.
  • Każdy funktor zachowuje sekcje (tzn. jeśli F\colon \mathbf{C}\to\mathbf{D} jest funktorem i f\colon A\to B\in \mathbf{C}_1 jest sekcją, to F(f)\colon F(A)\to F(B)\in \mathbf{D}_1 jest sekcją).
  • Każdy pełny i wierny funktor odzwierciedla sekcje (tzn. dla funktora pełnego i wiernego F\colon \mathbf{C}\to\mathbf{D} i morfizmu f\colon A\to B\in \mathbf{C}_1, jeśli F(f) jest sekcją w \mathbf{D}, to f jest sekcją w \mathbf{C}).
  • Złożenie retrakcji jest retrakcją.
  • Jeśli g\circ f jest retrakcją, to g jest retrakcją.
  • Każdy funktor zachowuje retrakcje.
  • Każdy pełny i wierny funktor odzwierciedla retrakcje.
  • Morfizm f jest izomorfizmem wtedy i tylko wtedy, gdy jest sekcją i retrakcją jednocześnie.
  • Każdy pełny i wierny funktor odzwierciedla izomorfizmy.

Podsumujmy dyskusję: w ogólności sekcje i monomorfizmy (a także retrakcje i epimorfizmy) to nie to samo. Jeśli jednak w jakiejś kategorii strzałka, która jest mono i epi jest izomorfizmem, to taką kategorię nazywa się zbalansowaną (ang. balanced). Oto kategorie zbalansowane: zbiory \mathbf{Set}, przestrzenie wektorowe \mathbf{Vec}, grupy \mathbf{Grp}, grupy abelowe \mathbf{Ab}. Zbalansowane nie są zaś: relacje \mathbf{Rel}, posety \mathbf{Pos}, topologie \mathbf{Top}, monoidy \mathbf{Mon}, pierścienie \mathbf{Rng}, kategorie \mathbf{Cat}, przestrzenie Banacha \mathbf{Ban}, i tak dalej.

Obiekty początkowe i końcowe

Grafika:ilustracja7.png

Naszym następnym zadaniem jest abstrakcyjna charakteryzacja zbioru pustego i singletonów tak, by ich uniwersalne własności dały się wypowiedzieć w dowolnych innych kategoriach.


Definicja 2.10 [obiekt początkowy, obiekt końcowy]

W dowolnej kategorii \mathbf{C}:

  • obiekt \mathbf{0} \in \mathbf{C}_0 nazywamy początkowym, jeśli dla dowolnego obiektu C\in \mathbf{C}_0 istnieje dokładnie jeden morfizm
Grafika:tk-2.5.png
  • obiekt \mathbf{1} \in \mathbf{C}_0 nazywamy końcowym, jeśli dla dowolnego obiektu C\in \mathbf{C}_0 istnieje dokładnie jeden morfizm
Grafika:tk-2.6.png


Oczywiście pojęcia obiektu początkowego i końcowego są dualne: obiekt X jest początkowy w \mathbf{C} wtedy i tylko wtedy, gdy jest końcowy w \mathbf{C}^{op}.

W \mathbf{Set} jedynym obiektem początkowym jest zbiór pusty. Rzeczywiście, ze zbioru pustego do dowolnego innego zbioru istnieje dokładnie jedna funkcja - funkcja pusta. Z drugiej strony, nie ma w \mathbf{Set} funkcji, której dziedziną jest zbiór niepusty, a kodziedziną - zbiór pusty. To znaczy, że żaden inny zbiór, poza pustym, nie nadaje się na obiekt początkowy.

Każdy singleton nadaje się na obiekt końcowy w \mathbf{Set} - to oczywiste, ale ani zbiór pusty, ani taki o mocy większej niż jeden, nie może być końcowy, bo funkcji weń będzie zbyt mało lub zbyt dużo.


Fakt 2.11

Obiekt początkowy (końcowy) jest jedyny z dokładnością do izomorfizmu.

Dowód

Pokażemy, że jeśli \mathbf{0} i \mathbf{0}' są obiektami początkowymi, to istnieje między nimi izomorfizm. Poniższy diagram pozwala to nam zobaczyć od razu:
Grafika:tk-2.7.png

Rzeczywiście, z początkowości obiektu \mathbf{0} wynika, że istnieje dokładnie jedna strzałka typu \mathbf{0}\to\mathbf{0}; skoro tak, to musi to być identyczność 1_{\mathbf{0}}. Ponieważ na diagramie złożenie g\circ f jest typu \mathbf{0}\to \mathbf{0}, więc g\circ f = 1_{\mathbf{0}}. To samo rozumowanie dla \mathbf{0}' daje nam f\circ g = 1_{\mathbf{0}'}. A zatem f i g są wzajemnie do siebie odwrotnymi izomorfizmami.

Dowód dla obiektu końcowego jest dualny: wystarczy zauważyć, że \mathbf{1} jest obiektem początkowym w \mathbf{C}^{op} i powtórzyć powyższe kroki.

image:End_of_proof.gif

Przykłady:

  • W \mathbf{Cat} obiektem początkowym jest kategoria pusta, obiektem końcowym kategoria dyskretna (z jednym obiektem i jedną strzałką).
  • W \mathbf{Grp} grupa jednoelementowa jest zarówno początkowa, jak i końcowa.
  • W posecie (P,\leq) element jest początkowy, jeśli jest elementem najmniejszym, element jest końcowy, jeśli jest elementem największym. Wnioskiem z tego jest, że w kategoriach nie muszą istnieć obiekty początkowe i końcowe (weźmy choćby odcinek (0,1) z naturalnym porządkiem).
  • W dowolnej kategorii \mathbf{C}, jeśli X\in \mathbf{C}_0, to identyczność 1_X jest obiektem końcowym w kategorii warstwowej \mathbf{C} / X (patrz Zadanie 1.6).

Elementy i uogólnione elementy

Aby wyrazić zdanie teorii mnogości: x\in X w języku teorii kategorii, posługujemy się faktem, że istnieje bijekcja między zbiorem X i zbiorem funkcji \mathbf{1}\to X, gdzie \mathbf{1} jest dowolnym ustalonym singletonem. Tak jest, posługujemy się faktem, że w \mathbf{Set} istnieje izomorfizm X\cong \mathrm{Hom}_{\mathbf{Set}}(\mathbf{1}, X). A zatem w \mathbf{Set} funkcję x\colon \mathbf{1}\to X nazywamy elementem X. Podobnie w dowolnej kategorii \mathbf{C}, która posiada obiekt końcowy \mathbf{1}, strzałkę x\colon \mathbf{1}\to X, gdzie X\in \mathbf{C}_0, nazywamy elementem obiektu X. Strzałki o dowolnej dziedzinie i kodziedzinie X, np. f\colon A\to X dla A\in \mathbf{C}_0, nazywamy uogólnionymi elementami X. I to wszystko. Należy być tylko uważnym w użyciu elementów i uogólnionych elementów w dowolnych kategoriach, gdyż nie zawsze zachowują się tak, jak w \mathbf{Set}, na co wskazują poniższe przykłady:

  • W \mathbf{Pos} rozważmy strzałki f,g\colon X\to Y. Wówczas f=g wtedy i tylko wtedy, gdy f\circ x = g \circ x dla każdego elementu x\colon \mathbf{1}\to X.
  • Tymczasem w \mathbf{Mon} dla homomorfizmów f,g\colon M\to N zawsze mamy f\circ x=g\circ x dla każdego elementu x\colon \mathbf{1}\to M. Rzeczywiście, skoro \mathbf{1}=\{e\}, gdzie e jest jedynką monoidu \mathbf{1}, to każdy homomorfizm typu \mathbf{1}\to M musi odwzorowywać e w jedynkę e_M\in M. To oznacza, że istnieje dokładnie jeden homomorfizm typu \mathbf{1}\to M, czyli w szczególności f\circ x=g\circ x.


Sekcje, retrakcje i pary e-p w kategoriach dziedzin

Ostatnia część wykładu jest poświęcona kilku szczególnym przykładom sekcji i retrakcji w kategoriach częściowych porządków (do których należą: kategoria posetów \mathbf{Pos}, kategoria posetów zupełnych \mathbf{Dcpo}, kategoria dziedzin ciągłych \mathbf{Dom} i kategoria dziedzin algebraicznych \mathbf{Alg}). Aby w pełni zrozumieć poniższy tekst, należy najpierw przeczytać Wykład 12.

Niech S,T będą częściowymi porządkami, niech strzałka (czyli funkcja monotoniczna) s\colon S\to T będzie sekcją i niech strzałka r\colon T\to S będzie retrakcją, czyli zakładamy r\circ s = 1_S. O parze (s,r) mówimy jako o parze sekcja-retrakcja; poset S - jak już wspominaliśmy - nazywamy retraktem posetu T. Zauważmy, że sekcja jest zawsze injekcją, zaś retrakcja jest zawsze surjekcją, co jest odbiciem faktu, że sekcje są mono, zaś retrakcje epi. Co ciekawe, w przypadku, gdy obie funkcje są ciągłe (tzn. zachowują suprema zbiorów skierowanych), zachodzi następujące twierdzenie:


Twierdzenie 2.12

Niech (s,r) będzie parą sekcja-retrakcja pomiędzy posetami S i T i załóżmy, że obie funkcje są ciągłe. Wówczas:
  • Jeśli T jest zupełny, to S również (jeśli A\subseteq^{\uparrow} S, to \bigvee{}^{\uparrow} A = r(\bigvee{}^{\uparrow} s[A])).
  • Jeśli T jest ciągły, to S również (jeśli B jest bazą dla T, to r[B] jest bazą dla S).

A zatem każdy retrakt dziedziny ciągłej jest dziedziną ciągłą. Twierdzenie odwrotne również zachodzi, w nieco mocniejszej wersji:


Twierdzenie 2.13

Każda dziedzina ciągłą jest retraktem dziedziny algebraicznej, tzn. jeśli D jest dziedziną ciągłą z bazą B, to funkcje s\colon D\to \mathcal{I}(B,\sqsubseteq), s(x)=\Downarrow x\cap B oraz r\colon \mathcal{I}(B,\sqsubseteq)\to D, r(I) = \bigvee{}^{\uparrow} I są ciągłe i tworzą parę sekcja-retrakcja. Poset \mathcal{I}(B,\sqsubseteq) jest zbiorem wszystkich \sqsubseteq-ideałów zbudowanych z elementów z B, uporządkowanych względem inkluzji.


Dowody dwóch powyższych twierdzeń znajdują się odpowiednio w Zadaniach 2.6 i 2.7.

Grafika:ilustracja9.png

Najciekawszymi przykładami par sekcja-retrakcja są tak zwane pary zanurzenie-projekcja, w skrócie pary e-p od angielskich słów embedding, projection.


Definicja 2.14

Niech D, E będą posetami. Parę funkcji ciągłych

e\colon D\to E, p\colon E\to D nazywamy parą e-p, jeśli p\circ e = 1_D i e\circ p \sqsubseteq 1_E.

Zauważmy, że para sekcja-retrakcja skonstruowana w Twierdzeniu 2.13 jest parą e-p. Przeróżne własności par e-p poznamy w Zadaniu 2.8 do wykładu. Ich niezwykłą użyteczność poznamy podczas Wykładu 14.