Teoria kategorii dla informatyków/Wykład 5: Funktory i transformacje naturalne
Funktory
Definicja 5.1 [Funktor]
Funktor albo funktor kowariantny
z kategorii do kategorii jest dany poprzez:- operację przypisującą jednoznacznie każdemu obiektowi
obiekt
- operację przypisującą jednoznacznie każdemu morfizmowi morfizm
w ten sposób, że:
- jeśli w , to w ,
- .
Funktory typu nazywamy często funktorami kontrawariantnymi, aby podkreślić, że jego dziedziną jest kategoria dualna do .
Przykład 5.2 [funktor potęgowy]
Sprawdźmy, czy operacja
spełnia warunki definicji funktora: po pierwsze, dla dowolnej identyczności , jest funkcją, która każdemu podzbiorowi przyporządkowuje obraz , czyli funkcja identycznościowa. A zatem , czyli operacja zachowuje identyczności. Po drugie, dla dowolnej pary strzałek oraz strzałka typu jest z definicji złożeniem dwóch funkcji: oraz , czyli tym samym co funkcja (to prosta własność obrazów funkcji), czyli - z definicji - tym samym co funkcja . Dowiedliśmy w ten sposób, że . A zatem jest funktorem (kowariantnym).
Przykład 5.3
Przykład 5.4
Przykład 5.5
dla dowolnych
i . Jeśli jest dowolną funkcją ciągłą pomiędzy przestrzeniami topologicznymi i , to przeciwobraz jest funkcją, która zachowuje (a co za tym idzie: funkcją monotoniczną) oraz (bo przeciwobrazy zachowują sumy zbiorów).Powyższe rozważania motywują następujące definicje dwóch kategorii:
- kategorii ram (ang. frames), oznaczanej , 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 lokali (ang. locales), która jest dualna do . Morfizmy 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
jest funktorem.
Przykład 5.6 [funktory zapominania]
Niech
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 możemy zdefiniować tak zwany funktor zapominania w ten sposób, że każdemu obiektowi przypisujemy zbiór , zaś każdemu morfizmowi przypisujemy tę samą funkcję niejako zapominając o fakcie, że zachowuje ona zadaną na obiektach strukturę. Dla przykładu funktor zapominania przypisuje każdej grupie zbiór elementów grupy i każdemu homomorfizmowi grup funkcję .
Przykład 5.7
zadaną jak następuje:
czyli tak, jak na poniższym diagramie:

Sprawdźmy, że
jest funktorem. Mamy:z czego wnosimy, że:
Po drugie:
Dlatego
lub jeśli ktoś woli:
co jest spowodowane kontrawariantnością funktora.
Definicja 5.8 [Fuktory pełne, wierne]
Kategorie konkretne
Definicja 5.9 [kategoria konkretna]
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 nazywamy funktorem zapominania, jeśli jest tym funktorem, który czyni kategorię kategorią konkretną. Przykładem kategorii, która nie jest konkretna, jest kategoria wszystkich zbiorów i relacji .
Transformacje naturalne
Rozważmy następujący problem: dla dowolnych kategorii
chcemy skonstruować kategorię oznaczaną , której obiektami są wszystkie funktory z do . Jak moglibyśmy zdefiniować morfizmy tej nowej kategorii (które dalej nazwiemy transformacjami naturalnymi funktorów)?Otóż, postępujemy podobnie jak przy konstrukcji kategorii 1.5): transformację naturalną funktora w funktor zapewni nam rodzina przekształceń taka, że diagram
(porównaj Zadanie
komutuje dla dowolnych obiektów
i strzałki . 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]

komutuje. Rodzinę strzałek
nazywamy komponentami transformacji naturalnej .Jeśli każdy komponent transformacji naturalnej Zadanie 5.1 (o tej sytuacji mówi się też, że i są naturalnie izomorficzne).
jest izomorfizmem w kategorii , wówczas transformację nazywamy naturalnym izomorfizmem. Ten warunek jest też równoważny temu, że transformacja traktowana jako strzałka w kategorii funktorów jest izomorfizmem - patrzZwróćmy uwagę, że jeśli np. w Zadaniu 4.10 powiedzieliśmy, że w kartezjańsko zamkniętej kategorii z koproduktami istnieje naturalna bijekcja:
to znaczy to, że funktory:
i są naturalnie izomorficzne i tak samo dla par funktorów powstałych z pominięcia odpowiednio i .
Przykład 5.11 [odwracanie list]

jest transformacją naturalną. Jeśli
jest zbiorem, to komponent jest funkcją odwracającą dowolną listę o elementach z :dla
.Zauważmy, że dla dowolnej funkcji
diagram
komutuje, co potwierdza naturalność transformacji
. Zwróćmy też uwagę, że w żargonie informatycznym komutowanie powyższego diagramu oznacza, że jest operacją polimorficzną, czyli, że definicja nie zależy od . 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]
- obiekty to funktory typu ,
- morfizmy to transformacje naturalne funktorów typu ,
- identyczności: jeśli jest funktorem, to identycznością jest transformacja naturalna zdefiniowana jako dla ,
- złożenie: dla , gdzie są funktorami typu , definiujemy złożenie poprzez komponenty jako:
dla
.
Naturalność w powyższej definicji weryfikujemy, jak następuje: dla , lub po prostu patrząc na komutujący diagram:

Jeśli Zadaniu 4.2. Jeśli jedna z kategorii nie jest mała, to nie musi być obiektem . Mimo to umówmy się, że kategorię funktorów dla dowolnych kategorii będziemy odtąd oznaczać .
są kategoriami małymi, to kategoria funktorów jest eksponentem kategorii i w , co pokazaliśmy wOto znany z algebry liniowej przykład naturalnego izomorfizmu: przez
oznaczamy kategorię przestrzeni wektorowych nad ciałem liczb rzeczywistych wraz z odwzorowaniami liniowymi jako morfizmami. Każda przestrzeń wektorowa ma przestrzeń dualną składającą się z odwzorowań liniowych typu , tzn. w zapisie kategoryjnym. Co więcej, jest w rzeczywistości hom-funktorem, tj.Jak się okazuje, dowolna przestrzeń
zanurza się naturalnie w przestrzeń dualną do :Słowo naturalnie, użyte powyżej, jest nieprzypadkowe: zdefiniowana przed chwilą strzałka
jest komponentem transformacji naturalnejktórej dziedziną jest identyczność na
. Sprawdźmy, że jest transformacją naturalną:
Transformacja
jest naturalnym izomorfizmem, gdy jest skończenie wymiarowa.