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

From Studia Informatyczne

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 \omegaoperacja \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:

Grafika:tk-5.1.png

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

Grafika:tk-5.2.png

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
Grafika:tk-5.3.png

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 Gnaturalnie 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
Grafika:tk-5.4.png

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

Grafika:tk-5.5.png

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:

Grafika:tk-5.6.png

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ą:

Grafika:tk-5.7.png
(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.