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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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]

Funktorem jest operacja definiowana jako: dla oraz dla morfizmu , jest funkcją, która podzbiorowi zbioru przyporządkowuje jego obraz , który jest podzbiorem .

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

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


Przykład 5.4

Niech będzie pierścieniem przemiennym z jedynką. Zbiór wszystkich macierzy odwracalnych stopnia wraz z operacją mnożenia macierzy tworzy grupę oznaczaną . Ponieważ każdy homomorfizm pierścieni indukuje w sposób naturalny homomorfizm , łatwo już sprawdzić, że dla każdego operacja jest funktorem z kategorii pierścieni przemiennych z jedynką do kategorii grup .


Przykład 5.5

Niech będzie przestrzenią topologiczną. Oznaczmy poset wszystkich zbiorów otwartych uporządkowanych względem inkluzji jako . Poset ten jest kratą zupełną (suprema to sumy, zaś infima to wnętrza przecięć), w której zachodzi prawo przemienności:

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

Ze strukturą każdej kategorii lokalnie małej związane są tzw. hom-funktory, które odgrywają ogromną rolę w teorii kategorii. Dla każdego obiektu możemy bowiem zdefiniować operację,

zadaną jak następuje:

czyli tak, jak na poniższym diagramie:

Tk-5.1.png

Sprawdźmy, że jest funktorem. Mamy:

z czego wnosimy, że:

Po drugie:

Dlatego

lub jeśli ktoś woli:

Zwróćmy uwagę, że złożenie po aplikacji funktora zmienia się w:

co jest spowodowane kontrawariantnością funktora.

Definicja 5.8 [Fuktory pełne, wierne]

Funktor nazywamy pełnym, jeśli dla każdej pary obiektów i dla każdej strzałki w istnieje strzałka w taka, że . Funktor nazywamy wiernym (lub zanurzeniem), jeśli dla każdej pary obiektów i każdej pary strzałek (strzałki o tej samej dziedzinie i przeciwdziedzinie nazywamy często równoległymi) równość implikuje .

Kategorie konkretne

Definicja 5.9 [kategoria konkretna]

Każdą kategorię , w której istnieje wierny funktor 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 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 (porównaj Zadanie 1.5): transformację naturalną funktora w funktor zapewni nam rodzina przekształceń taka, że diagram

Tk-5.2.png

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]

Dla równoległych funktorów transformacją naturalną nazywamy przekształcenie przypisujące każdemu obiektowi strzałkę w takie, że dla dowolnego morfizmu w diagram
Tk-5.3.png

komutuje. Rodzinę strzałek nazywamy komponentami transformacji naturalnej .

Jeśli każdy komponent transformacji naturalnej 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 - patrz Zadanie 5.1 (o tej sytuacji mówi się też, że i naturalnie izomorficzne).

Zwróć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]

Dla funktora operacja , która mając daną listę, odwraca jej elementy
Tk-5.4.png

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

Tk-5.5.png

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]

Niech i będą kategoriami. Kategoria funktorów jest wyznaczona przez następujące dane:
  • 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:

Tk-5.6.png

Jeśli są kategoriami małymi, to kategoria funktorów jest eksponentem kategorii i w , co pokazaliśmy w 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ć .

Oto 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 naturalnej

której dziedziną jest identyczność na . Sprawdźmy, że jest transformacją naturalną:

Tk-5.7.png

Transformacja jest naturalnym izomorfizmem, gdy jest skończenie wymiarowa.