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{𝐂}$ będzie kategorią. Strzałka $f:A\to B\in {\mathbf{𝐂}}_1$ jest mono(morfizmem), jeśli dla każdego obiektu $C\in {\mathbf{𝐂}}_0$ i równoległych strzałek $g,h: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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ jako injekcje, bo przecież funkcja $f:A\to B$ jest injekcją wtedy i tylko wtedy, gdy

$\mathrm{\forall }a,b\in A(f(a)=f(b)\Rightarrow a=b)$

wtedy i tylko wtedy, gdy

$\mathrm{\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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$.

Podobnie w $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$, $\mathbf{𝐂}\mathbf{𝐑}\mathbf{𝐧}\mathbf{𝐠}$, $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$: monomorfizmami są strzałki injektywne.

Definicja 2.2 [monomorfizm, epimorfizm]

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

A zatem aby strzałka $f: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{𝐂}$ jest kategorią, to kategoria dualna ${\mathbf{𝐂}}^{op}$ jest definiowana jako ${\mathbf{𝐂}}_0^{op}=\mathbf{𝐂}$, ${\mathbf{𝐂}}_1^{op}={\mathbf{𝐂}}_1$, ale ${\mathrm{d}\mathrm{o}\mathrm{m}}_{{\mathbf{𝐂}}^{op}}(f)={\mathrm{c}\mathrm{o}\mathrm{d}}_{\mathbf{𝐂}}(f)$, ${\mathrm{c}\mathrm{o}\mathrm{d}}_{{\mathbf{𝐂}}^{op}}(f)={\mathrm{d}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f)$, $f{\circ }_{{\mathbf{𝐂}}^{op}}g=g{\circ }_{\mathbf{𝐂}}f$.

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

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

Fakt 2.4

Strzałka $f:A\to B$ jest (mono-)epomorfizmem w kategorii $\mathbf{𝐂}$ wtedy i tylko wtedy, gdy jest (epi-)monomorfizmem w ${\mathbf{𝐂}}^{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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, $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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, ale w innych kategoriach niekoniecznie). Okazuje się bowiem, że:

Przykład 2.6

W $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$ zanurzenie liczb naturalnych w całkowite $i:\mathbb{\mathbb{N}}\to \mathbb{\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{\mathbb{Z}}$, i.e. $f=g$. Jest jednak oczywiste, że injekcja $i$ nie jest surjekcją. A zatem w $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$ 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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$

bijekcje (izomorfizmy) są jednocześnie injekcjami (mono) i surjekcjami (epi)). Poprzedni przykład w

$\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$

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:A\to B$ w kategorii $\mathbf{𝐂}$ jest sekcją, jeśli istnieje morfizm $g: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:A\to B$ jest sekcją, to równość $f\circ h=f\circ k$ dla pewnych strzałek $h,k: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:A\to B$ jest morfizmem w $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ (albo w $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$ czy $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$), można rozważyć graf morfizmu $f$ jako podzbiór (odpowiednio: podprzestrzeń w $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$ lub podgrupę w $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$) 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:A\to B$ w kategorii $\mathbf{𝐂}$ jest retrakcją, jeśli istnieje morfizm $g: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:\mathbf{𝐂}\to \mathbf{𝐃}$ jest funktorem i $f:A\to B\in {\mathbf{𝐂}}_1$ jest sekcją, to $F(f):F(A)\to F(B)\in {\mathbf{𝐃}}_1$ jest sekcją).
• Każdy pełny i wierny funktor odzwierciedla sekcje (tzn. dla funktora pełnego i wiernego $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i morfizmu $f:A\to B\in {\mathbf{𝐂}}_1$, jeśli $F(f)$ jest sekcją w $\mathbf{𝐃}$, to $f$ jest sekcją w $\mathbf{𝐂}$).
• 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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, przestrzenie wektorowe $\mathbf{𝐕}\mathbf{𝐞}\mathbf{𝐜}$, grupy $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$, grupy abelowe $\mathbf{𝐀}\mathbf{𝐛}$. Zbalansowane nie są zaś: relacje $\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐥}$, posety $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$, topologie $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$, monoidy $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$, pierścienie $\mathbf{𝐑}\mathbf{𝐧}\mathbf{𝐠}$, kategorie $\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐭}$, przestrzenie Banacha $\mathbf{𝐁}\mathbf{𝐚}\mathbf{𝐧}$, 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{𝐂}$:

• obiekt $\mathbf{𝟎}\in {\mathbf{𝐂}}_0$ nazywamy początkowym, jeśli dla dowolnego obiektu $C\in {\mathbf{𝐂}}_0$ istnieje dokładnie jeden morfizm

• obiekt $\mathbf{𝟏}\in {\mathbf{𝐂}}_0$ nazywamy końcowym, jeśli dla dowolnego obiektu $C\in {\mathbf{𝐂}}_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{𝐂}$ wtedy i tylko wtedy, gdy jest końcowy w ${\mathbf{𝐂}}^{op}$.

W $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ 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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ 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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ - 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{𝟎}$ i ${\mathbf{𝟎}}^{\prime }$ 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{𝟎}$ wynika, że istnieje dokładnie jedna strzałka typu $\mathbf{𝟎}\to \mathbf{𝟎}$; skoro tak, to musi to być identyczność $1_{\mathbf{𝟎}}$. Ponieważ na diagramie złożenie $g\circ f$ jest typu $\mathbf{𝟎}\to \mathbf{𝟎}$, więc $g\circ f=1_{\mathbf{𝟎}}$. To samo rozumowanie dla ${\mathbf{𝟎}}^{\prime }$ daje nam $f\circ g=1_{{\mathbf{𝟎}}^{\prime }}$. A zatem $f$ i $g$ są wzajemnie do siebie odwrotnymi izomorfizmami.

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

Przykłady:

• W $\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐭}$ obiektem początkowym jest kategoria pusta, obiektem końcowym kategoria dyskretna (z jednym obiektem i jedną strzałką).
• W $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$ grupa jednoelementowa jest zarówno początkowa, jak i końcowa.
• W posecie $(P,\le )$ 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{𝐂}$, jeśli $X\in {\mathbf{𝐂}}_0$, to identyczność $1_X$ jest obiektem końcowym w kategorii warstwowej $\mathbf{𝐂}/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{𝟏}\to X$, gdzie $\mathbf{𝟏}$ jest dowolnym ustalonym singletonem. Tak jest, posługujemy się faktem, że w $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ istnieje izomorfizm $X\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}(\mathbf{𝟏},X)$. A zatem w $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ funkcję $x:\mathbf{𝟏}\to X$ nazywamy elementem $X$. Podobnie w dowolnej kategorii $\mathbf{𝐂}$, która posiada obiekt końcowy $\mathbf{𝟏}$, strzałkę $x:\mathbf{𝟏}\to X$, gdzie $X\in {\mathbf{𝐂}}_0$, nazywamy elementem obiektu $X$. Strzałki o dowolnej dziedzinie i kodziedzinie $X$, np. $f:A\to X$ dla $A\in {\mathbf{𝐂}}_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{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, na co wskazują poniższe przykłady:

• W $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ rozważmy strzałki $f,g:X\to Y$. Wówczas $f=g$ wtedy i tylko wtedy, gdy $f\circ x=g\circ x$ dla każdego elementu $x:\mathbf{𝟏}\to X$.
• Tymczasem w $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$ dla homomorfizmów $f,g:M\to N$ zawsze mamy $f\circ x=g\circ x$ dla każdego elementu $x:\mathbf{𝟏}\to M$. Rzeczywiście, skoro $\mathbf{𝟏}=\{e\}$, gdzie $e$ jest jedynką monoidu $\mathbf{𝟏}$, to każdy homomorfizm typu $\mathbf{𝟏}\to M$ musi odwzorowywać $e$ w jedynkę $e_M\in M$. To oznacza, że istnieje dokładnie jeden homomorfizm typu $\mathbf{𝟏}\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{𝐏}\mathbf{𝐨}\mathbf{𝐬}$, kategoria posetów zupełnych $\mathbf{𝐃}\mathbf{𝐜}\mathbf{𝐩}\mathbf{𝐨}$, kategoria dziedzin ciągłych $\mathbf{𝐃}\mathbf{𝐨}\mathbf{𝐦}$ i kategoria dziedzin algebraicznych $\mathbf{𝐀}\mathbf{𝐥}\mathbf{𝐠}$). 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:S\to T$ będzie sekcją i niech strzałka $r: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:D\to {ℐ}(B,⊑)$, $s(x)=\Downarrow x\cap B$ oraz $r:{ℐ}(B,⊑)\to D$, $r(I)=\bigvee {}^{\uparrow }I$ są ciągłe i tworzą parę sekcja-retrakcja. Poset ${ℐ}(B,⊑)$ jest zbiorem wszystkich $⊑$-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:D\to E$, $p:E\to D$ nazywamy parą e-p, jeśli $p\circ e=1_D$ i $e\circ p⊑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.