Teoria kategorii dla informatyków/Wykład 5: Funktory i transformacje naturalne

Funktory

Definicja 5.1 [Funktor]

Funktor albo funktor kowariantny $F\colon \mathbf {C} \to \mathbf {D}$ z kategorii $\mathbf {C}$ do kategorii $\mathbf {D}$ jest dany poprzez:

• operację przypisującą jednoznacznie każdemu obiektowi

$X\in \mathbf {C} _{0}$ obiekt $F(X)\in \mathbf {D} _{1}$

• operację przypisującą jednoznacznie każdemu morfizmowi $f\in \mathbf {C} _{1}$ morfizm $F(f)\in \mathbf {D} _{1}$

w ten sposób, że:

• jeśli $f\colon X\to Y$ w $\mathbf {C}$, to $F(f)\colon F(X)\to F(Y)$ w $\mathbf {D}$,
• $F(1_{X})=1_{F(X)}$
• $F(f\circ g)=F(f)\circ F(g)$.

Funktory typu $\mathbf {C} ^{op}\to \mathbf {D}$ nazywamy często funktorami kontrawariantnymi, aby podkreślić, że jego dziedziną jest kategoria dualna do $\mathbf {C}$.

Przykład 5.2 [funktor potęgowy]

Funktorem jest operacja ${\mathcal {P}}\colon \mathbf {Set} \to \mathbf {Set}$ definiowana jako: $\mathbf {X} =\{B\mid B\subseteq X\}$ dla $X\in \mathbf {C} _{0}$ oraz dla morfizmu $f\colon X\to Y$, ${\mathcal {P}}(f)\colon {\mathcal {P}}(X)\to {\mathcal {P}}(Y)$ jest funkcją, która podzbiorowi $Z$ zbioru $X$ przyporządkowuje jego obraz $f[Z]$, który jest podzbiorem $Y$.

Sprawdźmy, czy operacja ${\mathcal {P}}$ spełnia warunki definicji funktora: po pierwsze, dla dowolnej identyczności $1_{X}\colon X\to X$, ${\mathcal {P}}(1_{X})$ jest funkcją, która każdemu podzbiorowi $Z\subseteq X$ przyporządkowuje obraz $1_{X}[Z]=Z$, czyli funkcja identycznościowa. A zatem ${\mathcal {P}}_{1_{X}}=1_{{\mathcal {P}}(X)}$, czyli operacja ${\mathcal {P}}$ zachowuje identyczności. Po drugie, dla dowolnej pary strzałek $f\colon X\to Y$ oraz $g\colon Y\to Z$ strzałka ${\mathcal {P}}(g)\circ {\mathcal {P}}(f)$ typu ${\mathcal {P}}(X)\to {\mathcal {P}}(Z)$ jest z definicji złożeniem dwóch funkcji: $A\subseteq X\mapsto f[A]\subseteq Y$ oraz $f[A]\subseteq Y\mapsto g[f[A]]\subseteq Z$, czyli tym samym co funkcja $A\subseteq X\mapsto (g\circ f)[A]\subseteq Z$ (to prosta własność obrazów funkcji), czyli - z definicji - tym samym co funkcja ${\mathcal {P}}(g\circ f)$. Dowiedliśmy w ten sposób, że ${\mathcal {P}}(g\circ f)={\mathcal {P}}(g)\circ {\mathcal {P}}(f)$. A zatem ${\mathcal {P}}\colon \mathbf {Set} \to \mathbf {Set}$ jest funktorem (kowariantnym).

Przykład 5.3

Mając dany zbiór $S$, oznaczmy przez $\mathrm {List} (S)$ zbiór wszystkich skończonych słów $\mathrm {List}$ złożonych z elementów $S$. Oczywiście lista pusta $\varepsilon$ jest elementem $\mathrm {List} (S)$. Jeśli konkatenację list oznaczymy jako $\circ$, to widzimy, że $(\mathrm {List} (S),\circ ,\varepsilon )$ jest monoidem. Niech $\mathbf {Mon}$ oznacza kategorię monoidów i homomorfizmów monoidów. Pokażemy, że $\mathrm {List} \colon \mathbf {Set} \to \mathbf {Mon}$ jest funktorem. W tym celu zauważmy, że dla dowolnej funkcji $F\colon S\to R$, operację $\mathrm {List} (f)\colon \mathrm {List} (S)\to \mathrm {List} (R)$ potrzebną do wyrażenia definicji $\mathrm {List}$ jako funktora, możemy zdefiniować jako funkcję przypisującą liście $L=[s_{1},s_{2},...,s_{n}]$ listę $f(L)=[f(s_{1}),f(s_{2}),,...,f(s_{n})]$. Własności konkatenacji implikują natychmiast, że $\mathrm {List} (f)(\varepsilon )=\varepsilon )$ oraz $\mathrm {List} (f)(L_{1}\circ L_{2})=\mathrm {List} (f)(L_{1})\circ \mathrm {List} (f)(L_{2})$. Te dwa warunki stanowią świadectwo, że $\mathrm {List} (f)$ jest homomorfizmem monoidów, czyli morfizmem w $\mathbf {Mon}$. Postawiona definicja określająca działanie operacji $\mathrm {List}$ na morfizmach jest więc poprawna. Pozostaje nam sprawdzenie, że $\mathrm {List}$ zachowuje identyczności (rzecz trywialna) i złożenia funkcji. W tym celu zauważmy, że $\mathrm {List} (f\circ g)([s_{1},s_{2},...,s_{n}])=[(f\circ g)(s_{1}),...,(f\circ g)(s_{n})]=[(f(g(s_{1})),...,(f(g(s_{n}))]=\mathrm {List} (f)([g(s_{1}),...,g(s_{n})])=\mathrm {List} (f)(\mathrm {List} (g)([s_{1},...,s_{n}]))=(\mathrm {List} (f)\circ \mathrm {List} (g))([s_{1},...,s_{n}])$, co świadczy o tym, że $\mathrm {List} (f\circ g)=\mathrm {List} (f)\circ \mathrm {List} (g)$. To kończy dowód faktu, że $\mathrm {List} \colon \mathbf {Set} \to \mathbf {Mon}$ jest funktorem.

Przykład 5.4

Niech $K$ będzie pierścieniem przemiennym z jedynką. Zbiór wszystkich macierzy odwracalnych stopnia $n$ wraz z operacją mnożenia macierzy tworzy grupę oznaczaną $\mathrm {GL} _{n}(K)$. Ponieważ każdy homomorfizm pierścieni $f\colon K\to L$ indukuje w sposób naturalny homomorfizm $\mathrm {GL} _{n}(f)\colon \mathrm {GL} _{n}(K)\to \mathrm {GL} _{n}(L)$, łatwo już sprawdzić, że dla każdego $n\in \omega$operacja $\mathrm {GL} _{n}$ jest funktorem z kategorii pierścieni przemiennych z jedynką $\mathbf {CRng}$ do kategorii grup $\mathbf {Grp}$.

Przykład 5.5

Niech $(X,\tau )$ będzie przestrzenią topologiczną. Oznaczmy poset wszystkich zbiorów otwartych uporządkowanych względem inkluzji jako $\Omega (X)$. Poset ten jest kratą zupełną (suprema to sumy, zaś infima to wnętrza przecięć), w której zachodzi prawo przemienności: $a\wedge \bigvee S=\bigvee \{a\wedge s\mid s\in S\}$

dla dowolnych $a\in \Omega (X)$ i $S\subseteq \Omega (x)$. Jeśli $f\colon X\to Y$ jest dowolną funkcją ciągłą pomiędzy przestrzeniami topologicznymi $(X,\tau )$ i $(Y,\sigma )$, to przeciwobraz $f^{-1}\colon \Omega (Y)\to \Omega (X)$ jest funkcją, która zachowuje $\wedge$ (a co za tym idzie: funkcją monotoniczną) oraz $\bigvee$ (bo przeciwobrazy zachowują sumy zbiorów).

Powyższe rozważania motywują następujące definicje dwóch kategorii:

• kategorii ram (ang. frames), oznaczanej $\mathbf {Frm}$, której obiektami są kraty zupełne spełniające powyższe prawo nieskończonej przemienności, a morfizmami funkcje zachowujące skończone infima i dowolne suprema.
• kategorii $\mathbf {Loc}$ lokali (ang. locales), która jest dualna do $\mathbf {Frm}$. Morfizmy $\mathbf {Loc}$ nazywa się często w literaturze funkcjami ciągłymi. Teoria lokali rości sobie pretensje do tzw. konstruktywnej topologii, czyli teorii przestrzeni topologicznych, w której unika się rozważań niekonstruktywnych, korzystających z pewnika wyboru, jak i rozważań dotyczących elementów przestrzeni topologicznych; w zamian teoria lokali ofiaruje topologię w języku funkcji ciągłych i ich przekształceń. Więcej informacji na ten temat można znaleźć w (zaawansowanym pojęciowo) podręczniku pt. Stone Spaces autorstwa prof. P.T. Johnstone'a.

Mając dane powyższe definicje, widzimy już, że $\Omega \colon \mathbf {Top} \to \mathbf {Loc}$ jest funktorem.

Przykład 5.6 [funktory zapominania]

Niech $\mathbf {C}$ będzie dowolną kategorią, w której obiektami są zbiory z pewną dodatkową strukturą (np. strukturą przestrzeni wektorowej, strukturą przestrzeni topologicznych, itp.), zaś morfizmami - funkcje, które zachowują tę strukturę (np. odwzorowania liniowe, funkcje ciągłe). Dla każdej takiej kategorii $\mathbf {C}$ możemy zdefiniować tak zwany funktor zapominania $U\colon \mathbf {C} \to \mathbf {Set}$ w ten sposób, że każdemu obiektowi $X\in \mathbf {C} _{0}$ przypisujemy zbiór $X=U(X)$, zaś każdemu morfizmowi $f\colon X\to Y$ przypisujemy tę samą funkcję $f=U(f)$ niejako zapominając o fakcie, że zachowuje ona zadaną na obiektach $\mathbf {C}$ strukturę. Dla przykładu funktor zapominania $U\colon \mathbf {Grp} \to \mathbf {Set}$ przypisuje każdej grupie $G$ zbiór $U(G)$ elementów grupy $G$ i każdemu homomorfizmowi grup $f\colon G\to H$ funkcję $f=U(f)\colon U(G)\to U(H)$.

Przykład 5.7

Ze strukturą każdej kategorii lokalnie małej $\mathbf {C}$ związane są tzw. hom-funktory, które odgrywają ogromną rolę w teorii kategorii. Dla każdego obiektu $X\in \mathbf {C} _{0}$ możemy bowiem zdefiniować operację, $\mathrm {Hom} _{\mathbf {C} }(-,X)\colon \mathbf {C} ^{op}\to \mathbf {Set}$

zadaną jak następuje:

$\mathbf {C} _{0}\ni Z\ \mapsto \ \mathrm {Hom} _{\mathbf {C} }(Z,X)\in Set_{0}$ $\mathbf {C} _{1}\ni f\colon A\to B\ \mapsto \ \mathrm {Hom} _{\mathbf {C} }(f,X)\colon \mathrm {Hom} _{\mathbf {C} }(B,X)\to \mathrm {Hom} _{\mathbf {C} }(A,X)\in \mathbf {Set} _{1}$ $p\colon B\to X\ \mapsto \ p\circ f\colon A\to X,$

czyli tak, jak na poniższym diagramie:

Sprawdźmy, że $\mathrm {Hom} _{\mathbf {C} }(-,X)$ jest funktorem. Mamy:

$\mathrm {Hom} _{\mathbf {C} }(1_{B},X)(p)=p\circ 1_{B}=p,$

z czego wnosimy, że:

$\mathrm {Hom} _{\mathbf {C} }(-,X)(1_{B})=\mathrm {Hom} _{\mathbf {C} }(1_{B},X)=1_{\mathrm {Hom} _{\mathbf {C} }(B,X)}=1_{\mathrm {Hom} _{\mathbf {C} }(-,X)(B)}.$

Po drugie:

$\mathrm {Hom} _{\mathbf {C} }(f\circ g,X)(p)=p\circ f\circ g=\mathrm {Hom} _{\mathbf {C} }(g,X)(p\circ f)=(\mathrm {Hom} _{\mathbf {C} }(g,X)\circ \mathrm {Hom} _{\mathbf {C} }(f,X))(p).$

Dlatego

$\mathrm {Hom} _{\mathbf {C} }(f\circ g,X)=\mathrm {Hom} _{\mathbf {C} }(g,X)\circ \mathrm {Hom} _{\mathbf {C} }(f,X)$

lub jeśli ktoś woli:

$\mathrm {Hom} _{\mathbf {C} }(-,X)(f\circ g)=\mathrm {Hom} _{\mathbf {C} }(-,X)(g)\circ \mathrm {Hom} _{\mathbf {C} }(-,X)(f).$ Zwróćmy uwagę, że złożenie $g\circ f$ po aplikacji funktora $\mathrm {Hom} _{\mathbf {C} }(-,X)$ zmienia się w: $\mathrm {Hom} _{\mathbf {C} }(-,X)(g)\circ \mathrm {Hom} _{\mathbf {C} }(-,X)(f),$

co jest spowodowane kontrawariantnością funktora.

Definicja 5.8 [Fuktory pełne, wierne]

Funktor $T\colon \mathbf {C} \to \mathbf {D}$ nazywamy pełnym, jeśli dla każdej pary obiektów $C,C'\in \mathbf {C} _{0}$ i dla każdej strzałki $g\colon T(C)\to T(C')$ w $\mathbf {D}$ istnieje strzałka $f\colon C\to C'$ w $\mathbf {C}$ taka, że $T(f)=g$. Funktor $T\colon \mathbf {C} \to \mathbf {D}$ nazywamy wiernym (lub zanurzeniem), jeśli dla każdej pary obiektów $C,C'\in \mathbf {C} _{0}$ i każdej pary strzałek $f_{1},f_{2}\colon C\to C'$ (strzałki o tej samej dziedzinie i przeciwdziedzinie nazywamy często równoległymi) równość $T(f_{1})=T(f_{2})$ implikuje $f_{1}=f_{2}$.

Kategorie konkretne

Definicja 5.9 [kategoria konkretna]

Każdą kategorię $\mathbf {C}$, w której istnieje wierny funktor $U\colon \mathbf {C} \to \mathbf {Set}$ nazywamy kategorią konkretną.

Oczywiście taki funktor jest funktorem zapominania, co możemy tu wykorzystać do ścisłej definicji pojęcia funktora zapominania (w przeciwieństwie do nieformalnej prezentacji tego pojęcia w Przykładzie 5.6): funktor $U\colon \mathbf {C} \to \mathbf {Set}$ nazywamy funktorem zapominania, jeśli jest tym funktorem, który czyni kategorię $\mathbf {C}$ kategorią konkretną. Przykładem kategorii, która nie jest konkretna, jest kategoria wszystkich zbiorów i relacji $\mathbf {Rel}$.

Transformacje naturalne

Rozważmy następujący problem: dla dowolnych kategorii $\mathbf {C} ,\mathbf {D}$ chcemy skonstruować kategorię oznaczaną $Fun(\mathbf {C} ,\mathbf {D} )$, której obiektami są wszystkie funktory z $\mathbf {C}$ do $\mathbf {D}$. Jak moglibyśmy zdefiniować morfizmy tej nowej kategorii (które dalej nazwiemy transformacjami naturalnymi funktorów)?

Otóż, postępujemy podobnie jak przy konstrukcji kategorii $\mathbf {C} ^{\to }$ (porównaj Zadanie 1.5): transformację naturalną funktora $F\colon \mathbf {C} \to \mathbf {D}$ w funktor $G\colon \mathbf {C} \to \mathbf {D}$ zapewni nam rodzina przekształceń $(\eta _{A})_{A\in \mathbf {C} _{0}}$ taka, że diagram

komutuje dla dowolnych obiektów $A,B\in \mathbf {C} _{0}$ i strzałki $f\colon A\to B\in \mathbf {C} _{1}$. Nieformalnie mówiąc, aby określić transformację naturalną między dwoma funktorami, musimy zadeklarować jak efekt działania pierwszego z funktorów na każdym obiekcie transformuje się na efekt działania drugiego z funktorów na tym samym obiekcie. To transformowanie musi odbywać się w sposób naturalny, czyli tak, by powyższy diagram komutował.

Definicja 5.10 [transformacja naturalna]

Dla równoległych funktorów $F,G\colon \mathbf {C} \to \mathbf {D}$ transformacją naturalną $\eta$ nazywamy przekształcenie przypisujące każdemu obiektowi $A\in$ strzałkę $\eta _{A}\colon F(A)\to G(A)$ w $\mathbf {D}$ takie, że dla dowolnego morfizmu $f\colon A\to B$ w $\mathbf {C}$ diagram

komutuje. Rodzinę strzałek $(\eta _{A})_{A\in \mathbf {C} _{0}}$ nazywamy komponentami transformacji naturalnej $\eta$.

Jeśli każdy komponent transformacji naturalnej $\eta$ jest izomorfizmem w kategorii $\mathbf {D}$, wówczas transformację $\eta$ nazywamy naturalnym izomorfizmem. Ten warunek jest też równoważny temu, że transformacja $\eta \colon F\to G$ traktowana jako strzałka w kategorii funktorów $Fun(\mathbf {C} ,\mathbf {D} )$ jest izomorfizmem - patrz Zadanie 5.1 (o tej sytuacji mówi się też, że $F$ i $G$ są naturalnie izomorficzne).

Zwróćmy uwagę, że jeśli np. w Zadaniu 4.10 powiedzieliśmy, że w kartezjańsko zamkniętej kategorii $\mathbf {C}$ z koproduktami istnieje naturalna bijekcja:

$A\times (B+C)\cong (A\times B)+(A\times C),$

to znaczy to, że funktory: $F(-):=(-)\times (B+C)$ i $G(-):=((-)\times B)+((-)\times C$ są naturalnie izomorficzne i tak samo dla par funktorów powstałych z pominięcia odpowiednio $B$ i $C$.

Przykład 5.11 [odwracanie list]

Dla funktora $\mathrm {List} \colon \mathbf {Set} \to \mathbf {Mon}$ operacja $\mathrm {rev} \colon \mathrm {List} \to \mathrm {List}$, która mając daną listę, odwraca jej elementy

jest transformacją naturalną. Jeśli $A$ jest zbiorem, to komponent $\mathrm {rev} _{A}\colon \mathrm {List} (A)\to \mathrm {List} (A)$ jest funkcją odwracającą dowolną listę o elementach z $A$:

$\mathrm {rev} _{A}([s_{1},...,s_{n}])=[s_{n},...,s_{1}]$

dla $[s_{1},...,s_{n}]\in \mathrm {List} (A)$.

Zauważmy, że dla dowolnej funkcji $f\colon A\to B\in \mathbf {Set} _{1}$ diagram

komutuje, co potwierdza naturalność transformacji $\mathrm {rev}$. Zwróćmy też uwagę, że w żargonie informatycznym komutowanie powyższego diagramu oznacza, że $\mathrm {rev}$ jest operacją polimorficzną, czyli, że definicja $\mathrm {rev} _{A}$ nie zależy od $A$. Nieformalny wniosek nasuwa się sam: każda funkcja polimorficzna danego języka programowania (funkcyjnego) da się opisać jako pewna transformacja naturalna w odpowiedniej kategorii funktorów.

Definicja 5.12 [kategoria funktorów]

Niech $\mathbf {C}$ i $\mathbf {D}$ będą kategoriami. Kategoria funktorów $Fun(\mathbf {C} ,\mathbf {D} )$ jest wyznaczona przez następujące dane:

• obiekty $Fun(\mathbf {C} ,\mathbf {D} )_{0}$ to funktory typu $\mathbf {C} \to \mathbf {D}$,
• morfizmy $Fun(\mathbf {C} ,\mathbf {D} )_{1}$ to transformacje naturalne funktorów typu $\mathbf {C} \to \mathbf {D}$,
• identyczności: jeśli $F\colon \mathbf {C} \to \mathbf {D}$ jest funktorem, to identycznością $1_{F}\colon F\to F$ jest transformacja naturalna zdefiniowana jako $(1_{F})_{A}=1_{F(A)}$ dla $A\in \mathbf {C} _{0}$,
• złożenie: dla $\alpha \colon F\to G,\beta \colon G\to H$, gdzie $F,G,H$ są funktorami typu $\mathbf {C} \to \mathbf {D}$, definiujemy złożenie $\beta \circ \alpha$ poprzez komponenty jako:

$(\beta \circ \alpha )_{A}=\beta _{A}\circ \alpha _{A}$

dla $A\in \mathbf {C} _{0}$.

Naturalność $\beta \circ \alpha$ w powyższej definicji weryfikujemy, jak następuje: dla $F\colon A\to B\in \mathbf {C} _{1}$, $H(f)\circ (\beta \circ \alpha )_{A})=H(f)\circ \beta _{A}\circ \alpha _{A}=\beta _{B}\circ G(f)\circ \alpha _{A}=\beta _{B}\circ \alpha _{B}\circ F(f)$ lub po prostu patrząc na komutujący diagram:

Jeśli $\mathbf {C} ,\mathbf {D}$ są kategoriami małymi, to kategoria funktorów $Fun(\mathbf {C} ,\mathbf {D} )$ jest eksponentem kategorii $\mathbf {C}$ i $\mathbf {D}$ w $\mathbf {Cat}$, co pokazaliśmy w Zadaniu 4.2. Jeśli jedna z kategorii $\mathbf {C} ,\mathbf {D}$ nie jest mała, to $Fun(\mathbf {C} ,\mathbf {D} )$ nie musi być obiektem $\mathbf {Cat}$. Mimo to umówmy się, że kategorię funktorów $Fun(\mathbf {C} ,\mathbf {D} )$ dla dowolnych kategorii $\mathbf {C} ,\mathbf {D}$ będziemy odtąd oznaczać $[\mathbf {C} ,\mathbf {D} ]$.

Oto znany z algebry liniowej przykład naturalnego izomorfizmu: przez $\mathbf {Vect} (\mathbb {R} )$ oznaczamy kategorię przestrzeni wektorowych nad ciałem liczb rzeczywistych wraz z odwzorowaniami liniowymi jako morfizmami. Każda przestrzeń wektorowa $V$ ma przestrzeń dualną $V^{*}$ składającą się z odwzorowań liniowych typu $V\to \mathbb {R}$, tzn. $V^{*}=\mathrm {Hom} _{\mathbf {Vect} (\mathbb {R} )}(V,\mathbb {R} )$ w zapisie kategoryjnym. Co więcej, $(-)^{*}$ jest w rzeczywistości hom-funktorem, tj.

$(-)^{*}=\mathrm {Hom} {\mathbf {Vect} (\mathbb {R} )}(-,\mathbb {R} )\colon \mathbf {Vect} ^{op}\to \mathbf {Vect} .$

Jak się okazuje, dowolna przestrzeń $V$ zanurza się naturalnie w przestrzeń dualną do $V^{*}$:

$\eta _{V}\colon C\to V^{**}$ $x\mapsto \mathrm {ev} _{x}\colon V^{*}\to \mathbb {R}$ $\mathrm {ev} _{x}(f):=fx.$

Słowo naturalnie, użyte powyżej, jest nieprzypadkowe: zdefiniowana przed chwilą strzałka $\eta _{V}$ jest komponentem transformacji naturalnej

$\eta 1_{\mathbf {Vect} }\to (-)^{**},$

której dziedziną jest identyczność na $\mathbf {Vect}$. Sprawdźmy, że $\eta$ jest transformacją naturalną:

$(f^{**}\circ \eta _{V})(x)(g)=f^{**}(\mathrm {ev} _{x})(g)=(\mathrm {ev} _{x}\circ f^{*})(g)=\mathrm {ev} _{x}(f^{*}(g))=\mathrm {ev} _{x}(g\circ f)=(g\circ f)(x)=g(f(x))=\mathrm {ev} _{f(x)}(g)=(\eta _{W}\circ f)(x)(g).$

Transformacja $\eta$ jest naturalnym izomorfizmem, gdy $V$ jest skończenie wymiarowa.