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

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.

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:

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:

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} _{0}^{op}=\mathbf {C}$, $\mathbf {C} _{1}^{op}=\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:

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.

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ę

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

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

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

• 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

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:

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.

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.

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.