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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 będzie kategorią. Strzałka jest mono(morfizmem), jeśli dla każdego obiektu i równoległych strzałek równość implikuje .

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

Tk-2.1.png

wynika, że .

Monomorfizmy znane są w jako injekcje, bo przecież funkcja jest injekcją wtedy i tylko wtedy, gdy

wtedy i tylko wtedy, gdy

wtedy i tylko wtedy, gdy jest mono w .

Podobnie w , , : monomorfizmami są strzałki injektywne.


Definicja 2.2 [monomorfizm, epimorfizm]

Niech będzie kategorią. Strzałka jest epi(morfizmem) jeśli dla każdego obiektu i równoległych strzałek równość implikuje .

A zatem aby strzałka była epi, komutowanie diagramu:

Tk-2.2.png

pociąga za sobą równość .

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 jest kategorią, to kategoria dualna jest definiowana jako , , ale , , .


A zatem jest utworzona z poprzez odwrócenie kierunku strzałek.

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


Fakt 2.4

Strzałka jest (mono-)epomorfizmem w kategorii wtedy i tylko wtedy, gdy jest (epi-)monomorfizmem w .

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 jest mono, to jest mono.
  • Złożenie monomorfizmów jest monomorfizmem.
  • Jeśli jest epi, to jest epi.
  • W , jest epi wtedy i tylko wtedy, gdy 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 , ale w innych kategoriach niekoniecznie). Okazuje się bowiem, że:


Przykład 2.6

W zanurzenie liczb naturalnych w całkowite jest epimorfizmem, ale nie jest surjekcją.

Dowód

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

gdzie jest dowolnym monoidem, tzn. że , co nieformalnie oznacza, że morfizmy i zgadzają się na liczbach dodatnich. Wówczas: i podobnie dowiedziemy, że dla dowolnego . To znaczy, że i zgadzają się na , i.e. . Jest jednak oczywiste, że injekcja nie jest surjekcją. A zatem w epimorfizmy i surjekcje to nie to samo.

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 bijekcje (izomorfizmy) są jednocześnie injekcjami (mono) i surjekcjami (epi)). Poprzedni przykład w 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 w kategorii jest sekcją, jeśli istnieje morfizm taki, że (mówi się wtedy, że ma lewą odwrotność).

Każda sekcja jest mono: jeśli jest sekcją, to równość dla pewnych strzałek implikuje .

Nazwa sekcja pochodzi od pewnego znamienitego przykładu: jeśli jest morfizmem w (albo w czy ), można rozważyć graf morfizmu jako podzbiór (odpowiednio: podprzestrzeń w lub podgrupę w ) produktu . Wówczas zanurzenie w zdefiniowane jako jest sekcją (obraz tego zanurzenia niejako przecina produkt, stąd nazwa).

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 w kategorii jest retrakcją, jeśli istnieje morfizm taki, że (mówi się wtedy, że ma prawą odwrotność). Jeśli taka retrakcja istnieje, to mówimy, że jest retraktem .

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 jest sekcją, to jest sekcją.
  • Złożenie sekcji jest sekcją.
  • Każdy funktor zachowuje sekcje (tzn. jeśli jest funktorem i jest sekcją, to jest sekcją).
  • Każdy pełny i wierny funktor odzwierciedla sekcje (tzn. dla funktora pełnego i wiernego i morfizmu , jeśli jest sekcją w , to jest sekcją w ).
  • Złożenie retrakcji jest retrakcją.
  • Jeśli jest retrakcją, to jest retrakcją.
  • Każdy funktor zachowuje retrakcje.
  • Każdy pełny i wierny funktor odzwierciedla retrakcje.
  • Morfizm 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 , przestrzenie wektorowe , grupy , grupy abelowe . Zbalansowane nie są zaś: relacje , posety , topologie , monoidy , pierścienie , kategorie , przestrzenie Banacha , i tak dalej.

Obiekty początkowe i końcowe

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 :

  • obiekt nazywamy początkowym, jeśli dla dowolnego obiektu istnieje dokładnie jeden morfizm
Tk-2.5.png
  • obiekt nazywamy końcowym, jeśli dla dowolnego obiektu istnieje dokładnie jeden morfizm
Tk-2.6.png


Oczywiście pojęcia obiektu początkowego i końcowego są dualne: obiekt jest początkowy w wtedy i tylko wtedy, gdy jest końcowy w .

W 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 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 - 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 i są obiektami początkowymi, to istnieje między nimi izomorfizm. Poniższy diagram pozwala to nam zobaczyć od razu:
Tk-2.7.png

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

Dowód dla obiektu końcowego jest dualny: wystarczy zauważyć, że jest obiektem początkowym w i powtórzyć powyższe kroki.

End of proof.gif

Przykłady:

  • W obiektem początkowym jest kategoria pusta, obiektem końcowym kategoria dyskretna (z jednym obiektem i jedną strzałką).
  • W grupa jednoelementowa jest zarówno początkowa, jak i końcowa.
  • W posecie 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 z naturalnym porządkiem).
  • W dowolnej kategorii , jeśli , to identyczność jest obiektem końcowym w kategorii warstwowej (patrz Zadanie 1.6).

Elementy i uogólnione elementy

Aby wyrazić zdanie teorii mnogości: w języku teorii kategorii, posługujemy się faktem, że istnieje bijekcja między zbiorem i zbiorem funkcji , gdzie jest dowolnym ustalonym singletonem. Tak jest, posługujemy się faktem, że w istnieje izomorfizm . A zatem w funkcję nazywamy elementem . Podobnie w dowolnej kategorii , która posiada obiekt końcowy , strzałkę , gdzie , nazywamy elementem obiektu . Strzałki o dowolnej dziedzinie i kodziedzinie , np. dla , nazywamy uogólnionymi elementami . 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 , na co wskazują poniższe przykłady:

  • W rozważmy strzałki . Wówczas wtedy i tylko wtedy, gdy dla każdego elementu .
  • Tymczasem w dla homomorfizmów zawsze mamy dla każdego elementu . Rzeczywiście, skoro , gdzie jest jedynką monoidu , to każdy homomorfizm typu musi odwzorowywać w jedynkę . To oznacza, że istnieje dokładnie jeden homomorfizm typu , czyli w szczególności .


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 , kategoria posetów zupełnych , kategoria dziedzin ciągłych i kategoria dziedzin algebraicznych ). Aby w pełni zrozumieć poniższy tekst, należy najpierw przeczytać Wykład 12.

Niech będą częściowymi porządkami, niech strzałka (czyli funkcja monotoniczna) będzie sekcją i niech strzałka będzie retrakcją, czyli zakładamy . O parze mówimy jako o parze sekcja-retrakcja; poset - jak już wspominaliśmy - nazywamy retraktem posetu . 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 będzie parą sekcja-retrakcja pomiędzy posetami i i załóżmy, że obie funkcje są ciągłe. Wówczas:
  • Jeśli jest zupełny, to również (jeśli , to ).
  • Jeśli jest ciągły, to również (jeśli jest bazą dla , to jest bazą dla ).

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 jest dziedziną ciągłą z bazą , to funkcje , oraz , są ciągłe i tworzą parę sekcja-retrakcja. Poset jest zbiorem wszystkich -ideałów zbudowanych z elementów z , uporządkowanych względem inkluzji.


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

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 , będą posetami. Parę funkcji ciągłych

, nazywamy parą e-p, jeśli i .

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.