Teoria kategorii dla informatyków/Wykład 7: Lemat Yonedy i funktory reprezentowalne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Lemat Yonedy

Niech , , będą kategoriami. Funktor typu nazywamy bifunktorem.

Chyba najważniejszym przykładem jest tu - dla każdej kategorii lokalnie małej - bifunktor typu definiowany na obiektach jako:

oraz na morfizmach w jako:

gdzie jest następującym morfizmem w :

Definicję dobrze ilustruje poniższy diagram:

Tk-7.1.png

Założenie, że jest lokalnie mała jest konieczne, gdyż w przeciwnym wypadku nie moglibyśmy twierdzić, że kodziedziną jest .

Z bifunktorem jest ściśle związany pewien funktor, który zanurza dowolną lokalnie małą kategorię w kategorię funktorów , która jest kartezjańsko zamknięta, zupełna i kozupełna, niezależnie od kształtu .


Lemat 7.1 [funktor Yonedy]

Dla lokalnie małej kategorii operacja , gdzie dla :

oraz dla :

jest transformacją naturalną daną przez komponenty:

jest funktorem, nazywanym funktorem Yonedy.

Dowód

Dowód jest elementarny, choć pewną trudność może sprawić fakt, że pracujemy z kategorią funktorów .

Aby pokazać, że jest funktorem, musimy stwierdzić, że zachowuje on identyczności i złożenie. Niech będzie obiektem w . Wtedy jest, zgodnie z definicją, transformacją naturalną typu

Dla , jej -ty komponent jest funkcją typu

która dowolnemu morfizmowi przypisuje morfizm . Pokazaliśmy więc, że jest identycznością na zbiorze , czyli

Innymi słowy, funktor zachowuje identyczności.

Dla i oraz , -ty komponent transformacji naturalnej jest funkcją typu . Dla mamy , co dowodzi, że .

End of proof.gif
Ilustracja5.png

Z kategorią jest stowarzyszony pewnien funktor, tzw. (bi)funktor ewaluacji (zamiast w pełni rygorystycznie będziemy w skrócie pisali ):

definiowany dla , , oraz jako:

Zauważmy, że naturalność transformacji :

Tk-7.2.png

pozwala nam zdefiniować działanie na strzałkach następująco:

Teraz jesteśmy przygotowani na to, aby wypowiedzieć centralny wynik tego wykładu, zaskakujący i posiadający zaskakująco wiele zastosowań w teorii kategorii.


Twierdzenie 7.2 [Lemat Yonedy]

Niech będzie lokalnie małą kategorią, . Wówczas w istnieje bijekcja:

która jest naturalna ze względu na i na .


Uwaga
Zapis oznacza kolekcję morfizmów w kategorii , czyli kolekcję transformacji naturalnych między funktorami i . Lemat Yonedy mówi zatem po pierwsze, że ta kolekcja jest zbiorem (bo istnieje bijekcja ze zbiorem , a co za tym idzie operacja

jest obiektową częścią funktora typu . Druga część lematu wyjaśnia, że ten bifunktor jest naturalnie izomorficzny z bifunktorem ewaluacji.

Dowód

-tym komponentem transformacji naturalnej jest funkcja . Identyczność jest elementem , a zatem . To rozumowanie pozwala nam zgadnąć definicję bijekcji jako:

Z drugiej strony, dla dowolnego elementu zbioru , musimy zdefiniować transformację naturalną - nazwijmy ją , której -ty komponent będzie typu . Połóżmy więc:

Rzeczywiście, tak zdefiniowana operacja jest transformacją naturalną, gdyż dla dowolnej strzałki w diagram:

Tk-7.3.png

komutuje.

Pokażemy teraz, że funkcje i są do siebie odwrotne (tzn. tworzą bijekcję). Mamy (wykorzystaliśmy fakt, że funktory zachowują identyczności). Po drugie, , gdzie w kluczowym momencie (w przedostatniej równości) wykorzystaliśmy naturalność transformacji . A to oznacza, że , co dowodzi, że jest bijekcją z odwrotnością . Część pierwsza lematu jest więc wykazana i pozostaje nam jeszcze przekonać się o naturalności bijekcji , tzn. niezależności od wyboru i .

Niech oraz . Wówczas diagram:

Tk-7.4K.png

komutuje, co sprawdzamy następująco (pierwsza równość wynika z naturalności ):

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \phi_{X'}(F(f)(\psi_X(1_X))) &=& \phi_{X'}(\psi_{X'}(1_X\circ f))=\phi_{X'}(\psi ){X'}(f\circ 1_{X'})) = \phi_{X'}(\psi_{X'}(\mathcal{Y}(f)_{X'}(1_{X'}))) = (\phi\circ\psi\circ \mathcal{Y}(f))_{X'}(1_{X'}).}
End of proof.gif


Najważniejszym wnioskiem z lematu jest niewątpliwie stwierdzenie, że:


Wniosek 7.3

Funktor Yonedy jest pełny i wierny.

Dowód

Musimy pokazać, że dla dowolnych obiektów mamy bijekcję pomiędzy funkcjami typu a funkcjami typu . Ale przecież, zgodnie z lematem Yonedy, funkcje są w bijekcji z transformacjami naturalnymi typu . Zbadajmy komponenty:

Wyciągamy więc wniosek, że , czyli, że funkcje są w bijekcji z funkcjami typu .

End of proof.gif


Lemat Yonedy ma często następujące zastosowanie: aby pokazać, że obiekty lokalnie małej kategorii są izomorficzne, wystarczy pokazać, że dla każdego obiektu mamy bijekcję , która spełnia warunek naturalności: dla każdej diagram:

Tk-7.5.png

komutuje. Dlaczego? Odpowiedź znajduje się w Zadaniu 7.2.

Jak już wspomnieliśmy, funktor Yonedy pełni rolę zanurzenia kategorii w inną kategorię , która posiada wiele przyjemnych własności (jest m.in. kartezjańsko zamknięta). Pełność funktora Yonedy dodatkowo implikuje, że każdy funktor typu da się w pewnym sensie zbudować z funktorów postaci dla , mniej więcej w taki sposób jak liczby naturalne powstają z liczb pierwszych. Uściślenie tej intuicji jest poza zasięgiem wykładu, ale spróbujmy przyjrzeć się chociaż pewnej szczególnej klasie funktorów z , tak zwanym funktorom reprezentowalnym.

Reprezentowalność funktorów

Zdarza się, że funktor jest nie tyle równy, ile izomorficzny z funktorem dla pewnego . Taka sytuacja jest arcyciekawa i zasługuje na osobną definicję:


Definicja 7.4 [funktor reprezentowalny]

Funktor izomorficzny z dla pewnego nz. funktorem reprezentowalnym.


Lemat Yonedy jest tym narzędziem, które pozwala nam zrozumieć funktory reprezentowalne. Zobaczmy bowiem, że naturalny izomorfizm jest elementem zbioru , który - w myśl lematu Yonedy - jest izomorficzny ze zbiorem . To znaczy, że transformacji odpowiada jednoznacznie element definiowany jako . Element nazywamy elementem uniwersalnym dla funktora , zaś para nazywa się reprezentacją funktora .

Reprezentacje funktorów są scharakteryzowane w sposób następujący:

Lemat 7.5

Następujące warunki są równoważne:
  • ;
  • Dla każdego istnieje dokładnie jeden morfizm taki, że .

Dowód

Zauważmy, że oznacza, że dla każdego obiektu mamy bijekcję (przy oznaczeniach z lematu Yonedy ta bijekcja nazywa się ), co w takim razie możemy przeczytać tak, że dla dowolnego elementu istnieje dokładnie jeden element (funkcja) taki, że , co należało wykazać. End of proof.gif

Łatwo pokazać, że każde dwie reprezentacje tego samego funktora są ze sobą izomorficzne, patrz Zadanie 7.5.

Okazuje się, że każda konstrukcja uniwersalna (np. produkt, eksponent, pulbak, itd.) da się opisać jako reprezentacja odpowiedniego funktora, co świadczy o fundamentalnym charakterze pojęcia reprezentowalności w teorii kategorii. Oto przykład:


Przykład 7.6 [Produkt]

Niech będzie lokalnie małą kategorią, . Definiujemy funktor następująco:

Sprawdzimy, że produkt wraz z projekcjami jest reprezentacją funktora .

Niech . Produkt jest reprezentacją wtedy i tylko wtedy, gdy istnieje dokładnie jedna taka para morfizmów taka, że:



Ta ostatnia równość jest równoważna kolejno:



wtedy i tylko wtedy, gdy:



wtedy i tylko wtedy, gdy:



ale ta równość jest prawdziwa, bo, z definicji produktu, para jest wyznaczona jednoznacznie (i jest równa ).


Przykład 7.7

Funktor zapominania jest reprezentowany przez parę .

Dowód

W myśl Lematu 7.5 wystarczy przekonać się, że dla dowolnej grupy i jej elementu istnieje dokładnie jeden homomorfizm grup taki, że , to znaczy . Rzeczywiście, wystarczy położyć , . Przy tej definicji jest homomorfizmem i jako jedyny spełnia . Rzeczywiście, jest homomorfizmem z definicji (w szczególności ), a jeśli jest dowolnym innym homomorfizmem, który ma własność , to dla dowolnego , czyli . End of proof.gif

Powyższy przykład pokazuje, że

Kategorię nazywamy kartezjańską, jeśli posiada obiekt końcowy, produkty i ekwalizatory. Jeśli jest kartezjańska i ma eksponenty, to jest kartezjańsko zamknięta. Pokażemy, że, podobnie jak w przypadku produktu, posiadanie przez kategorię eksponentów jest równoważne reprezentowalności pewnego funktora.


Fakt 7.8

Lokalnie mała i kartezjańska kategoria jest kartezjańsko zamknięta wtedy i tylko wtedy, gdy dla każdej pary obiektów funktor jest reprezentowalny.

Dowód

Pokażemy, że reprezentacją tego funktora jest para składająca się z eksponentu (porównaj Definicję 4.1).

Zauważmy po pierwsze, że , czyli ma rzeczywiście typ . Dalej, zgodnie z definicją jest elementem uniwersalnym jeśli dla każdego morfizmu istnieje dokładnie jeden morfizm (oznaczmy go jak zwykle ) taki, że . Musimy teraz już tylko rozszyfrować znaczenie ostatniego równania:

a zatem ostatnie powyższe równanie to:

co przekłada się dokładnie na komutowanie znanego już diagramu:

Tk-7.6K.png

To kończy nasz dowód.

End of proof.gif