Teoria kategorii dla informatyków/Ćwiczenia 1: Teoria kategorii jako abstrakcyjna teoria funkcji

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

Ćwiczenia do modułu 1

Zadanie 1.16. Udowodnij, że dla dwóch funkcji oraz jeśli oraz , to funkcja jest bijekcją.

Rozwiązanie: Pokażemy najpierw, że jest funkcją różnowartościową. Przypuśćmy, że dla pewnych elementów . Wówczas . Ponadto, dla dowolnego element jest jedynym takim elementem, że , co w szczególności oznacza, że jest surjekcją. Wnioskujemy więc, że jest różnowartościową surjekcją, czyli bijekcją.

Zadanie 1.17. Udowodnij Fakt 1.3 .

Wskazówka: Fakt, że liczby naturalne posiadają wspomnianą w Fakcie 1.3 jest dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie implikacji przeciwnej.

Załóżmy zatem, że jest pewnym zbiorem, który posiada wyróżniony element i funkcję spełniającą warunki zadania. Udowodnimy po kolei następujące zdania (znane jako aksjomaty Peano), które - zgodnie z wykładnią teorii mnogości - w sposób jednoznaczny determinują liczby naturalne spośród innych zbiorów, a co za tym idzie, potwierdzą, że zbiór jest zbiorem liczb naturalnych:

To wiemy z założenia.
To wiemy z założenia. 

Przypuśćmy przeciwnie, że dla pewnego mamy . Wtedy kładąc oraz , z założenia istnieje funkcja taka, że oraz . A zatem , sprzeczność.

  • jest injekcją.

Przypuśćmy, że dla pewnych . Kładąc (jest to podzbiór ) oraz , wiemy, że istnieje funkcja taka, że oraz . Taka funkcja jest tylko jedna, więc jej zawężenie do musi być równe funkcji , która spełnia warunki oraz dla . Dlatego założenie implikuje , co należało pokazać.

  • Parser nie mógł rozpoznać (nieznana funkcja „\pzb”): {\displaystyle \forall A\pzb N\ ((0\in A\wedge (a\in A\implies s(a)\in A))\implies A=N)}

W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe, a potem skorzystamy z okazji, aby ten sam dowód pokazać bardziej w duchu teorii kategorii (stopniowo ten drugi rodzaj dowodów będzie zastępował pierwszy).

Rozważmy zatem funkcję , która - będąc obcięciem do - spełnia warunek , gdzie jest inkluzją w . Zgodnie z założeniem zadania, dla funkcji istnieje dokładnie jedna funkcja taka, że oraz . Łącząc tą równość z poprzednią, dostajemy . Zwróćmy teraz uwagę na funkcję . Oczywiste spostrzeżenie, że pozwala nam stwierdzić, że jest {\it jedyną} funkcją typu , która spełnia ostatnią z równości. Skoro tak, to musi być równa identyczności na . Pokazaliśmy więc, że , a stąd - jak łatwo pokazać - wynika, że jest injekcją. A zatem Parser nie mógł rozpoznać (nieznana funkcja „\pzb”): {\displaystyle N\pzb A} , co należało wykazać.

Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru , a zatem teoria mnogości uczy nas, że jest zbiorem liczb naturalnych nat.

Dowód ostatniego z aksjomatów Peano prowadzony w duchu teorii kategorii, czyli teorii przekształceń, korzysta z dobrodziejstwa, jakim jest możliwość przedstawiania funkcji i ich złożeń na diagramach.

Po pierwsze, spróbujmy przedstawić graficznie (na diagramach) założenia, które mamy, tzn. zdanie: {\it jest zbiorem, który posiada wyróżniony element oraz funkcję takie, że dla dowolnego innego zbioru i elementu oraz funkcji istnieje dokładnie jedna funkcja spełniająca warunki oraz .}

Zauważmy więc, że element może być zawsze traktowany jako funkcja , gdzie jest dowolnym zbiorem jednoelementowym (zwróćmy uwagę, że w tej interpretacji aplikacja funkcji staje się złożeniem, np. staje się złożeniem ). Podobnie dla . Po drugie, wszelkie równości pomiędzy funkcjami przedstawiamy jako komutowanie odpowiedniego diagramu, np. równość zachodzi wtedy i tylko wtedy, gdy poniższy diagram komutuje:

Tu wstawić brakujący rysunek o numerze 1.14

Następnie umawiamy się, że jeśli funkcja w diagramie jest jedyną, która może znajdować się pomiędzy dwoma danymi obiektami, to zaznaczamy ją przerywaną linią, np. zdanie ... jest jedyną funkcją taką, że... odzwierciedla się graficznie jako:

Tu wstawić brakujący rysunek o numerze 1.15

Jeśli diagram jest bardziej skomplikowany, to umawiamy się, że odczytujemy wszystkie możliwe równania, przy czym umawiamy się, że nie musimy rysować identyczności. A zatem diagram:

Tu wstawić brakujący rysunek o numerze 1.16

komutuje wtedy i tylko wtedy, gdy , , , , (ten wniosek wynika z czterech pozostałych!) i jest jedyną taką funkcją, która spełnia wszystkie wymienione zależności. Tak więc powyższy diagram zawiera całą informację dostępną w założeniach zadania. Przystąpmy więc do kategoryjnego dowodu ostatniego aksjomatu Peano. Oto on: skoro diagram

Tu wstawić brakujący rysunek o numerze 1.17

komutuje, co możemy przedstawić również w skrócie jako:

Tu wstawić brakujący rysunek o numerze 1.18

jak również komutuje diagram:

Tu wstawić brakujący rysunek o numerze 1.19

to z warunku jednoznaczności istnienia funkcji dostajemy . To jednak implikuje, że jest injekcją, czyli Parser nie mógł rozpoznać (nieznana funkcja „\pzb”): {\displaystyle N\pzb A} , co należało pokazać.

Jak zobaczymy w toku wykładu, dowody poprzez pokazanie komutujących diagramów (czyli de facto wyeksplikowanie pewnych równości między funkcjami – czy też ogólniej: morfizmami) są bardzo często spotykane w teorii kategorii, a nawet zastępują wszelkie inne dowody

Zadanie 1.18. Znajdź przykład na to, że w kategorii Pos bijekcje nie zawsze są izomorfizmami.

Wskazówka: Wystarczy rozważyć częściowe porządki dwuelementowe.

Rozwiązanie: Rozważmy dwa posety dwuelementowe , i funkcję , , jak na rysunku:

Tu wstawić brakujący rysunek o numerze 1.20

Funkcja jest oczywiście bijekcją, ale funkcja do niej odwrotna nie jest monotoniczna, a zatem nie jest morfizmem w Pos. To oznacza, że nie może być izomorfizmem.

Zadanie 1.19. Pokaż, że każda grupa może być traktowana jako kategoria, w której

Rozwiązanie: Niech będzie grupą. Podobnie jak w przypadku monoidów, deklarujemy jako jedyny obiekt pewnej kategorii, zaś elementy zbioru jako morfizmy tejże kategorii, działanie jako złożenie morfizmów, element traktując jako identyczność na obiekcie . Zauważmy, że każdy element posiada element odwrotny, czyli dla każdego istnieje tak, że . Te równania interpretowane w naszej kategorii czynią tenże dowolnie wybrany element izomorfizmem.

Zadanie 1.20. Dla dowolnej kategorii C zaproponuj konstrukcję nowej kategorii, w której – żądamy – obiektami są morfizmy z C.

Wskazówka: Niech C będzie dowolną kategorią; dla dwóch jej dowolnych morfizmów oraz , musimy zaproponować taką operację, dla której jest dziedziną i jest kodziedziną. Gdyby przedstawić to graficznie, w postaci diagramu, łatwo przyjdzie nam na myśl definicja takiej operacji: będzie to para morfizmów z kategorii C taka, że poniższy diagram komutuje:

Tu wstawić brakujący rysunek o numerze 1.21

Teraz już łatwo dopowiedzieć szczegóły konstrukcji.

Rozwiązanie: Zaproponujemy najpierw złożenie: dwa morfizmy oraz jak poniżej:

Tu wstawić brakujący rysunek o numerze 1.22

składają się tak:

Tu wstawić brakujący rysunek o numerze 1.23

albo formalnie: . Oczywiście Parser nie mógł rozpoznać (nieznana funkcja „\dom”): {\displaystyle \dom((a\circ c, b\circ d)) = h} oraz Parser nie mógł rozpoznać (nieznana funkcja „\cod”): {\displaystyle \cod((a\circ c, b\circ d)) = g} . W końcu, identycznościami w nowej kategorii, która często oznacza się jako są pary identyczności z kategorii C. Wszelkie pozostałe czynności, które musimy wykonać, by sprawdzić, że C jest kategorią, są trywialne.

Zadanie 1.21. Niech C będzie kategorią, zaś jej ustalonym obiektem. Zaproponuj konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z C o kodziedzinie A.

Wskazówka: Wykorzystaj Zadanie 1.20.

Rozwiązanie: Tak jak w Zadaniu 1.20 morfizmami nowej kategorii, oznaczanej często C∕A i nazywanej A-warstwą C są komutujące diagramy: ponieważ wszystkie obiekty C∕A jako morfizmy C mają wspólną kodziedzinę, więc możemy przyjąć, że morfizmami są komutujące trójkąty:

Tu wstawić brakujący rysunek o numerze 1.24

albo formalnie: jeśli oraz są obiektami C / A, to morfizmem o dziedzinie i kodziedzinie jest morfizm z C taki, że powyższy diagram komutuje. Sprawdzenie, że C / A jest kategorią jest już trywialne.

Zadanie 1.22. Udowodnij, że złożenie izomorfizmów jest izomorfizmem, że morfizm odwrotny do izomorfizmu jest tylko jeden, a także, że identyczności w dowolnej kategorii są izomorfizmami.

Rozwiązanie: Pokażmy najpierw, że złożenie izomorfizmów jest izomorfizmem. Załóżmy, że oraz są izmorfizmami. Wówczas ich złożenie posiada morfizm odwrotny . Rzeczywiście, i podobnie pokazujemy drugie z równań dla izomorfizmu.

Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, że jest izomorfizmem z odwrotnością jest wyrażony przez fakt, że poniższy diagram komutuje:

Tu wstawić brakujący rysunek o numerze 1.25

(Przypomnijmy sobie umowę z Zadania 1.17 , że nie rysujemy identyczności.)

Podobnie, diagram:

Tu wstawić brakujący rysunek o numerze 1.26

komutuje, a co za tym idzie, złożenie tych dwóch diagramów komutuje:

Tu wstawić brakujący rysunek o numerze 1.27

To zaś kończy dowód faktu, że jest odwrotnością .

Po drugie, pokażmy, że morfizm odwrotny do izmorfizmu jest tylko jeden: załóżmy przeciwnie, że dla pewnego izomorfizmu istnieją dwie odwrotności . Wówczas , co należało pokazać.

Po trzecie, niech będzie dowolnym obiektem dowolnej kategorii. Identyczność spełnia oczywiście (z definicji kategorii) równanie , co świadczy o tym, że jest izomorfizmem.

Zadanie 1.23. Znajdź kategorię, która ma tę własność, że jeśli dwa obiekty są izomorficzne, to muszą być sobie równe.

Wskazówka: Można wziąć pod uwagę te szczególne kategorie, w których istnieje co najwyżej jedna strzałka pomiędzy dowolnymi dwoma obiektami.

Rozwiązanie: Niech Parser nie mógł rozpoznać (nieznana funkcja „\pod”): {\displaystyle (P,\pod)} będzie częściowym porządkiem. Traktowany jako kategoria, posiada tę własność, że pomiędzy dwoma jego obiektami (elementami) istnieje co najwyżej jeden morfizm (w przypadku, gdy elementy te są w częściowym porządku). Niech będą obiektami izomorficznymi. W języku częściowych porządków oznacza to, że Parser nie mógł rozpoznać (nieznana funkcja „\pod”): {\displaystyle p\pod q} i Parser nie mógł rozpoznać (nieznana funkcja „\pod”): {\displaystyle q\pod p} . Antysymetria relacji porządkującej daje nam , co należało pokazać.

Zadanie 1.24. Pokaż, że w kategorii Mon izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.

Wskazówka: Jedna z implikacji jest bardzo łatwa: jeśli jest izomorfizmem w Mon, to w szczególności jest morfizmem, czyli homomorfizmem monoidów. Równania dla jako izomorfizmu implikują, że jest też bijekcją, w dokładnie ten sam sposób, w jaki pokazaliśmy dla funkcji między zbiorami (patrz dyskusja po Fakcie 1.2 ). Wystarczy więc udowodnić implikację odwrotną.

Rozwiązanie: Załóżmy, że jest bijektywnym homomorfizmem z odwrotnością . Wystarczy pokazać, że jest homomorfizmem, tzn., że oraz dla dowolnych . Wykorzystując fakt, że - jako homomorfizm - zachowuje jedynkę, mamy: , czyli pierwszą z szukanych równości. Znów opierając się na własnościach mamy: , co należało pokazać.


Zadanie 1.25. Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy Cat.

Wskazówka: Przeczytaj najpierw Definicję ??, w której mówimy czym są funktory.

Rozwiązanie: Najpierw definiujemy identyczności: dla dowolnej kategorii C proponujemy przekształcenie jako

                     
                

dla dowolnych . Wtedy oczywiście jest funktorem. Złożenie funktorów definiujemy w sposób naturalny, tak jak złożenie funkcji w Set. Niech , , będą funktorami.

                  

dla i taki sam dowód działa dla morfizmów. Wnioskujemy więc, że

                  

Ponadto:

                

gdzie (-) oznacza miejsce, w które można wstawić obiekt lub morfizm z C – taka konwencja notacyjna będzie często używana w przyszłości. A zatem wnioskujemy, że złożenie funktorów jest łączne.

Zadanie 1.26. Podaj dwa dalsze przykłady kategorii.

Wskazówka: Najprościej zdefiniować nowe kategorie poprzez modyfikację istniejących przykładów (np. kategorię tworzą zbiory i funkcje częściowe). Nasz drugi przykład jest tego typu: jako język funkcyjny bierzemy -rachunek i tworzymy dla niego kategorię, tak jak opisaliśmy to w jednym z ostatnich przykładów podanych podczas wykładu.

Rozwiązanie:

  1. Automaty: Niech będzie monoidem. Definiujemy {\bf -automat} jako parę składającą się ze zbioru stanów i funkcji przejścia tak, że:
                        
                                 

dla dowolnych , . Morfizmem -automatów , jest funkcja taka, że . Sprawdzenie, że taka struktura jest kategorią jest oczywiste, nieprawdaż?

  1. Rachunek lambda: rozważamy prosty rachunek z typami. (-rachunek jest formalizmem pozwalającym na wygodną manipulację funkcjami. Umożliwia opis funkcji bez podawania jej nazwy, np: funkcja jest w rachunku lambda zapisywana jako , zaś funkcja, której wartością jest również funkcja: zapisuje się jako .) Formalnie, -rachunek składa się z:

\begin{enumerate} \item typów: \item termów, w skład których wchodzą:

 \begin{enumerate} 
 \item dla każdego typu  zmienne tego typu: , 
 \item stałe różnych typów: , 
 \item dla dowolnych , para: , 
 \item dla dowolnego , projekcja , 
 \item dla dowolnego , projekcja , 
 \item dla dowolnych , aplikacja , 
 \item dla dowolnych , abstrakcja . 
 \end{enumerate} 

\item równań:

 \begin{enumerate} 
 \item , 
 \item , 
 \item , 
 \item , 
 \item , o ile  nie występuje w . 
 \end{enumerate} 

\end{enumerate}

Definiujemy też relację na termach (nazywaną zwyczajowo -równoważnością), jako relację równoważności generowaną przez równania i zamianę nazwy zmiennych związanych: o ile nie występuje w , to

                      

Kategorię definiujemy teraz jak następuje:

  • obiekty: typy -rachunku,
  • morfizm z do to termy domknięte (identyfikowane ze sobą, jeśli ),
  • identyczności: dla każdego ,
  • złożenie: .

Sprawdźmy, że jest kategorią:

                       
                       

\begin{eqnarray*} c\circ (b\circ a) & = & \lambda x.c((b\circ a)x)\\

                 & = & \lambda x.c((\lambda y.b(ay))x)\\    
                 & = & \lambda x.c(b(ax))\\
                 & = & \lambda x.\lambda y.c((by)(ax))\\  
                 & = & \lambda x.(c\circ b)(ax)\\    
                 & = & (c\circ b)\circ a.  

\end{eqnarray*}

Kategorii przyjrzymy się jeszcze uważniej w wykładach \ref{wyklad3}, \ref{wyklad4}.