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

==Zadanie 1.1==

Udowodnij, że dla dwóch funkcji $f : A \to B$ oraz $g : B \to A$ , jeśli $f \circ g = 1_{B}$ oraz $g \circ f = 1_{A}$ , to funkcja $f$ jest bijekcją.

Rozwiązanie:

Pokażemy najpierw, że $f$ jest funkcją różnowartościową. Przypuśćmy, że $f (x) = f (y)$ dla pewnych elementów $x, y \in A$ . Wówczas $x = 1_{A} (x) = (g \circ f) (x) = g (f (x)) = g (f (y)) = (g \circ f) (y) = 1_{A} (y) = y$ . Ponadto, dla dowolnego $z \in B$ , element $g (z)$ jest jedynym takim elementem, że $f (g (z)) = z$ , co w szczególności oznacza, że $f$ jest surjekcją. Wnioskujemy więc, że $f$ jest różnowartościową surjekcją, czyli bijekcją.

==Zadanie 1.2==

Udowodnij Fakt 1.2.

Wskazówka:

Rozwiązanie:

Załóżmy zatem, że

N

jest pewnym zbiorem, który posiada wyróżniony element

0 \in N

i funkcję

s : N \to N

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

N

jest zbiorem liczb naturalnych:

Giuseppe Peano (1858-1932)
Zobacz biografię

$\exists 0 \in N$

To wiemy z założenia.

$\forall n \in N s (n) \in N$

To wiemy z założenia.

$\forall n \in N s (n) \neq 0$

Przypuśćmy przeciwnie, że dla pewnego $n \in N$ mamy $s (n) = 0$ . Wtedy, kładąc $X = {e, a}$ oraz $g (e) = g (a) = a$ , z założenia istnieje funkcja $f : N \to X$ taka, że $f (0) = e$ oraz $f (s (n)) = g (f (n))$ . A zatem $f (s (n)) = f (0) = e \neq a = g (f (n))$ , sprzeczność.

$s$ jest injekcją.

Przypuśćmy, że $s (n) = s (m)$ dla pewnych $n, m \in N$ . Kładąc $X : = {0, s (0), s (s (0)), . . .}$ (jest to podzbiór $N$ ) oraz $e : = 0$ , wiemy, że istnieje funkcja $f : N \to X$ taka, że $f (0) = 0$ oraz $f (s (n)) = s (f (n))$ . Taka funkcja jest tylko jedna, więc jej zawężenie do $X$ musi być równe funkcji $h : X \to X$ , która spełnia warunki $h (0) = 0$ oraz $h (s (n)) = n$ dla $n \neq 0$ . Dlatego założenie $s (n) = s (m)$ implikuje $n = h (s (n)) = h (s (m)) = m$ , co należało pokazać.

$\forall A \subseteq N ((0 \in A \land (a \in A ⟹ s (a) \in A)) ⟹ 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ę $s^{'} : A \to A$ , która - będąc obcięciem $s$ do $A$ - spełnia warunek $s \circ i = i \circ s^{'}$ , gdzie $i : A \to N$ jest inkluzją $A$ w $N$ . Zgodnie z założeniem zadania, dla funkcji $s^{'}$ istnieje dokładnie jedna funkcja $f : N \to A$ taka, że $f (0) = 0$ oraz $s^{'} \circ f = f \circ s$ . Łącząc tą równość z poprzednią, dostajemy $s \circ i \circ f = i \circ f \circ s$ . Zwróćmy teraz uwagę na funkcję $i \circ f : N \to N$ . Oczywiste spostrzeżenie, że $i \circ f (0) = 0$ pozwala nam stwierdzić, że $i \circ f$ jest jedyną funkcją typu $N \to N$ , która spełnia ostatnią z równości. Skoro tak, to musi być równa identyczności na $N$ . Pokazaliśmy więc, że $i \circ f = 1_{N}$ , a stąd - jak łatwo pokazać - wynika, że $f : N \to A$ jest injekcją. A zatem $N \subseteq A$ , co należało wykazać.

Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru $N$ , a zatem teoria mnogości uczy nas, że $N$ 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: $N$ jest zbiorem, który posiada wyróżniony element $0$ oraz funkcję $s : N \to N$ takie, że dla dowolnego innego zbioru $X$ i elementu $e \in X$ oraz funkcji $g : X \to X$ istnieje dokładnie jedna funkcja $f : N \to X$ spełniająca warunki $f (0) = e$ oraz $f \circ s = g \circ f$ .

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

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 ... $f : N \to X$ jest jedyną funkcją taką, że... odzwierciedla się graficznie jako:

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:

komutuje wtedy i tylko wtedy, gdy $0 \in N$ , $e \in X$ , $f (0) = e$ , $f \circ s = g \circ f$ , $(f \circ s) (0) = g (e)$ (ten wniosek wynika z czterech pozostałych!) i $f$ 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

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

jak również komutuje diagram:

to z warunku jednoznaczności istnienia funkcji dostajemy $i \circ f = 1_{N}$ . To jednak implikuje, że $f$ jest injekcją, czyli $N \subseteq 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.3==

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

Wskazówka:

Rozwiązanie:

Rozważmy dwa posety dwuelementowe $P = {x, y}$ , $Q = {z, w}$ i funkcję $g : Q \to P$ , $g (z) = x, g (w) = y$ , jak na rysunku:

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

==Zadanie 1.4==

Pokaż, że każda grupa może być traktowana jako kategoria, w której każdy morfizm jest izomorfizmem.

Rozwiązanie:

Niech $(G, \circ, e)$ będzie grupą. Podobnie jak w przypadku monoidów, deklarujemy $G$ jako jedyny obiekt pewnej kategorii, zaś elementy zbioru $G$ jako morfizmy tejże kategorii, działanie $\circ$ jako złożenie morfizmów, element $e$ traktując jako identyczność na obiekcie $G$ . Zauważmy, że każdy element posiada element odwrotny, czyli dla każdego $g \in G$ istnieje $g^{- 1} \in G$ tak, że $g \circ g^{- 1} = e = g^{- 1} \circ g$ . Te równania interpretowane w naszej kategorii czynią tenże dowolnie wybrany element $g$ izomorfizmem.

==Zadanie 1.5==

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

Wskazówka:

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

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

Rozwiązanie:

Zaproponujemy najpierw złożenie: dwa morfizmy $(a, b)$ oraz $(c, d)$ jak poniżej:

składają się tak:

albo formalnie: $(a, b) \circ (c, d) = (a \circ c, b \circ d)$ . Oczywiście $((a \circ c, b \circ d)) = h$ oraz $((a \circ c, b \circ d)) = g$ . W końcu, identycznościami w nowej kategorii, którą często oznacza się jako $𝐂^{\to}$ są pary identyczności z kategorii $𝐂$ . Wszelkie pozostałe czynności, które musimy wykonać, by sprawdzić, że $𝐂$ jest kategorią, są trywialne.

==Zadanie 1.6==

Niech $𝐂$ będzie kategorią, zaś $A \in 𝐂_{0}$ jej ustalonym obiektem. Zaproponuj konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z $𝐂$ o kodziedzinie $A$ .

Wskazówka:

Rozwiązanie:

Tak jak w Zadaniu1.5 morfizmami nowej kategorii, oznaczanej często $𝐂 / A$ i nazywanej $A$ -warstwą $𝐂$ , są komutujące diagramy: ponieważ wszystkie obiekty $𝐂 / A$ jako morfizmy $𝐂$ mają wspólną kodziedzinę, więc możemy przyjąć, że morfizmami są komutujące trójkąty:

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

==Zadanie 1.7==

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 $f : A \to B$ oraz $g : B \to C$ są izmorfizmami. Wówczas ich złożenie $g \circ f : A \to C$ posiada morfizm odwrotny $f^{- 1} \circ g^{- 1}$ . Rzeczywiście, $(g \circ f) \circ (f^{- 1} \circ g^{- 1}) = g \circ) f \circ f^{- 1}) \circ g^{- 1} = g \circ 1_{B} \circ g^{- 1} = g \circ g^{- 1} = 1_{C}$ i podobnie pokazujemy drugie z równań dla izomorfizmu.

Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, iż $f$ jest izomorfizmem z odwrotnością $f^{- 1}$ jest wyrażony przez fakt, że poniższy diagram komutuje:

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

Podobnie, diagram:

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

To zaś kończy dowód faktu, że $f^{- 1} \circ g^{- 1}$ jest odwrotnością $g \circ f$ .

Po drugie, pokażmy, że morfizm odwrotny do izmorfizmu jest tylko jeden: załóżmy przeciwnie, że dla pewnego izomorfizmu $f : A \to B$ istnieją dwie odwrotności $g, h : B \to A$ . Wówczas $g = g \circ 1_{B} = g \circ (f \circ h) = (g \circ f) \circ h = 1_{A} \circ h = h$ , co należało pokazać.

Po trzecie, niech $A$ będzie dowolnym obiektem dowolnej kategorii. Identyczność $1_{A}$ spełnia oczywiście (z definicji kategorii) równanie $1_{A} = 1_{A} \circ 1_{A}$ , co świadczy o tym, że jest izomorfizmem.

==Zadanie 1.8==

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

Wskazówka:

Rozwiązanie:

Niech $(P, ⊑)$ 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 $p, q$ będą obiektami izomorficznymi. W języku częściowych porządków oznacza to, że $p ⊑ q$ i $q ⊑ p$ . Antysymetria relacji porządkującej daje nam $p = q$ , co należało pokazać.

==Zadanie 1.9==

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

Wskazówka:

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

Rozwiązanie:

Załóżmy, że $f : M \to N$ jest bijektywnym homomorfizmem z odwrotnością $g : N \to M$ . Wystarczy pokazać, że $g$ jest homomorfizmem, tzn., że $g (e_{N}) = e_{M}$ oraz $g (n_{1} \circ_{N} n_{2}) = g (n_{1}) \circ_{M} g (n_{2})$ dla dowolnych $n_{1}, n_{2} \in N$ . Wykorzystując fakt, że $f$ - jako homomorfizm - zachowuje jedynkę, mamy: $e_{M} = g (f (e_{M})) = g (e_{N})$ , czyli pierwszą z szukanych równości. Znów, opierając się na własnościach $f$ , mamy: $g (n_{1}) \circ_{M} g (n_{2}) = g (f (g (n_{1}) \circ_{M} g (n_{2}))) = g (f (g (n_{1})) \circ_{N} f (g (n_{2}))) = g (n_{1} \circ_{N} n_{2})$ , co należało pokazać.

==Zadanie 1.10==

Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy $𝐂 𝐚 𝐭$ .

Wskazówka:

Rozwiązanie:

Najpierw definiujemy identyczności: dla dowolnej kategorii $𝐂$ proponujemy przekształcenie $1_{C}$ jako

1_{𝐂} (A) : = A

1_{𝐂} (f : A \to B) : = f

dla dowolnych $A \in C_{𝟎}, f \in C_{𝟏}$ . Wtedy oczywiście $1_{C}$ jest funktorem. Złożenie funktorów definiujemy w sposób naturalny, tak jak złożenie funkcji w $𝐒 𝐞 𝐭$ . Niech $F : 𝐂 \to 𝐃$ , $G : 𝐃 \to 𝐀$ , $H : 𝐀 \to 𝐁$ będą funktorami.

(1_{D} \circ F) (A) = 1_{D} (F (A)) = F (A) = F (1_{C}) (A) = (F \circ 1_{C}) (A)

dla $A \in C_{𝟎}$ i taki sam dowód działa dla morfizmów. Wnioskujemy więc, że:

1_{D} \circ F = F = F \circ 1_{C}

Ponadto:

H \circ (G \circ F) (-) = H ((G \circ F) (-)) = H (G (F (-))) = (H \circ G) (F (-)) = ((H \circ G) \circ F) (-)

gdzie $(-)$ oznacza miejsce, w które można wstawić obiekt lub morfizm z $𝐂$ – 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.11==

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:

Przykład pierwszy: Automaty. Niech $M = (M, *, e)$ będzie monoidem. Definiujemy $M$ -automat jako parę $(S, δ)$ składającą się ze zbioru stanów $S$ i funkcji przejścia $δ : M \times S \to S$ tak, że:

δ (x * y, s) : = δ (x, δ (y, s))

,

$δ (e, s) = s$

dla dowolnych $x, y \in M$ , $s \in S$ . Morfizmem $M$ -automatów $(S, δ)$ , $(Z, η)$ jest funkcja $f : S \to Z$ taka, że $f (δ (x, s)) = η (x, f (s))$ . Sprawdzenie, że taka struktura jest kategorią jest oczywiste, nieprawdaż?

Drugi przykład: 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 $x \mapsto x^{2}$ jest w rachunku lambda zapisywana jako $λ x . x^{2}$ , zaś funkcja, której wartością jest również funkcja: $y \mapsto (x \mapsto x^{2} + 2 y)$ zapisuje się jako $λ y . λ x . x^{2} + 2 y$ .) Formalnie, $λ$ -rachunek składa się z:

typów: $A, B, A \times B, A \to B, . .$
termów, w skład których wchodzą:
- dla każdego typu $A$ zmienne tego typu: $x : A, y : A, z : A, . .$ ,
- stałe różnych typów: $a : A, b : B, . .$ ,
- dla dowolnych $a : A, b : B$ , para: $⟨ a, b ⟩ : A \times B$ ,
- dla dowolnego $c : A \times, B$ , projekcja $π_{1} (c) : A$ ,
- dla dowolnego $c : A \times B$ , projekcja $π_{2} (c) : B$ ,
- dla dowolnych $c : A \times B, a : A$ , aplikacja $c a : B$ ,
- dla dowolnych $x : A, b : B$ , abstrakcja $λ x . b : A \to B$ .
równań:
- $π_{1} (⟨ a, b ⟩) = a$ ,
- $π_{2} (⟨ a, b ⟩) = b$ ,
- $⟨ π_{1} (c), π_{2} (c) ⟩ = c$ ,
- $(λ x . b) a = b [a / x]$ ,
- $λ x . c x = c$ , o ile $x$ nie występuje w $c$ .

Definiujemy też relację $a \approx b$ 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 $y$ nie występuje w $b$ , to:

λ x . b = λ y . b [y / x]

Kategorię $C (λ)$ definiujemy teraz, jak następuje:

obiekty: typy $λ$ -rachunku,
morfizm z $A$ do $B$ to termy domknięte $c : A \to B$ (identyfikowane ze sobą, jeśli $c \approx c^{'}$ ),
identyczności: $1_{A} = λ x . x$ dla każdego $x : A$ ,
złożenie: $c \circ b = λ x . c (b x)$ .

Sprawdźmy, że $C (λ)$ jest kategorią:

c \circ 1_{B} = λ x . c ((λ y . y) x) = λ x . c (y [x / y]) = λ x . c x = c

,

$1_{C} \circ c = λ x . (λ y . y) (c x) = λ x . y [c x / y] = λ x . c x = c$ ,

$c \circ (b \circ a) = λ x . c ((b \circ a) x) = λ x . c ((λ y . b (a y)) x) = λ x . c (b (a x)) = λ x . λ y . c ((b y) (a x)) = λ x . (c \circ b) (a x) = (c \circ b) \circ a$ .

Kategorii $C (λ)$ przyjrzymy się jeszcze uważniej w Wykładach 3. i 4.

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

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia