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

Lemat Yonedy

Niech $\mathbf {C}$, $\mathbf {D}$, $\mathbf {E}$ będą kategoriami. Funktor typu $\mathbf {C} \times \mathbf {D} \to \mathbf {E}$ nazywamy bifunktorem.

Chyba najważniejszym przykładem jest tu - dla każdej kategorii lokalnie małej $\mathbf {C}$ - bifunktor typu $\mathbf {C} ^{op}\times \mathbf {C} \to \mathbf {Set}$ definiowany na obiektach $A,B\in \mathbf {C} _{0}$ jako:

$(A,B)\mapsto \mathrm {Hom} _{\mathbf {C} }(A,B)$

oraz na morfizmach $f\colon A\to B,g\colon C\to D$ w $\mathbf {C} _{1}$ jako:

$(f,g)\mapsto \mathrm {Hom} _{\mathbf {C} }(f,g),$

gdzie $\mathrm {Hom} _{\mathbf {C} }(f,g)\colon \mathrm {Hom} _{\mathbf {C} }(B,C)\to \mathrm {Hom} _{\mathbf {C} }(A,D)$ jest następującym morfizmem w $\mathbf {E}$:

$h\colon B\to C\ \mapsto \ g\circ h\circ f.$

Definicję dobrze ilustruje poniższy diagram:

Założenie, że $\mathbf {C}$ jest lokalnie mała jest konieczne, gdyż w przeciwnym wypadku nie moglibyśmy twierdzić, że kodziedziną $\mathrm {Hom} _{\mathbf {C} }$ jest $\mathbf {Set}$.

Z bifunktorem $\mathrm {Hom} _{\mathbf {C} }$ jest ściśle związany pewien funktor, który zanurza dowolną lokalnie małą kategorię $\mathbf {C}$ w kategorię funktorów $[\mathbf {C} ^{op},\mathbf {Set} ]$, która jest kartezjańsko zamknięta, zupełna i kozupełna, niezależnie od kształtu $\mathbf {C}$.

Lemat 7.1 [funktor Yonedy]

Dla lokalnie małej kategorii $\mathbf {C}$ operacja ${\mathcal {Y}}\colon \mathbf {C} \to [\mathbf {C} ^{op},\mathbf {Set} ]$, gdzie dla $X\in \mathbf {C} _{0}$: ${\mathcal {Y}}(X):=\mathrm {Hom} _{\mathbf {C} }(-,X)$

oraz dla $f\colon X\to Y\in \mathbf {C} _{1}$:

${\mathcal {Y}}(f)\colon \mathrm {Hom} _{\mathbf {C} }(-,X)\to \mathrm {Hom} _{\mathbf {C} }(-,Y)$

jest transformacją naturalną daną przez komponenty:

$({\mathcal {Y}}(f))_{Z}:=f\circ -\colon \mathrm {Hom} _{\mathbf {C} }(Z,X)\to \mathrm {Hom} _{\mathbf {C} }(Z,Y),$

jest funktorem, nazywanym funktorem Yonedy.

Dowód Dowód jest elementarny, choć pewną trudność może sprawić fakt, że pracujemy z kategorią funktorów $[\mathbf {C} ^{op},\mathbf {Set} ]$. Aby pokazać, że ${\mathcal {Y}}$ jest funktorem, musimy stwierdzić, że zachowuje on identyczności i złożenie. Niech $X$ będzie obiektem w $\mathbf {C}$. Wtedy ${\mathcal {Y}}(1_{X})$ jest, zgodnie z definicją, transformacją naturalną typu $\mathrm {Hom} _{\mathbf {C} }(-,X)\to \mathrm {Hom} _{\mathbf {C} }(-,X).$ Dla $Z\in \mathbf {C} _{0}$, jej $Z$-ty komponent jest funkcją typu $\mathrm {Hom} _{\mathbf {C} }(Z,X)\to \mathrm {Hom} _{\mathbf {C} }(Z,X),$ która dowolnemu morfizmowi $g\colon Z\to X\in \mathbf {C} _{1}$ przypisuje morfizm $({\mathcal {Y}}(1_{X}))_{Z}(g)=1_{X}\circ g=g$. Pokazaliśmy więc, że $({\mathcal {Y}}(1_{X}))_{Z}$ jest identycznością na zbiorze $\mathrm {Hom} _{\mathbf {C} }(Z,X)$, czyli ${\mathcal {Y}}(1_{X})=1_{\mathrm {Hom} _{\mathbf {C} }(-,X)}=1_{{\mathcal {Y}}(X)}.$ Innymi słowy, funktor ${\mathcal {Y}}$ zachowuje identyczności. Dla $f\colon A\to B$ i $g\colon B\to C$ oraz $Z\in CC_{0}$, $Z$-ty komponent transformacji naturalnej $({\mathcal {Y}}(g\circ f))_{Z}$ jest funkcją $g\circ f\circ -$ typu $\mathrm {Hom} _{\mathbf {C} }(Z,A)\to \mathrm {Hom} _{\mathbf {C} }(Z,C)$. Dla $h\colon Z\to A$ mamy $({\mathcal {Y}}(g\circ f))_{Z}(h)=g\circ f\circ h=g\circ ({\mathcal {Y}}(f))_{Z}(h)=(({\mathcal {Y}}(g))_{Z}\circ ({\mathcal {Y}}(f))_{Z})(h)$, co dowodzi, że ${\mathcal {Y}}(g\circ f)={\mathcal {Y}}(g)\circ {\mathcal {Y}}(f)$.

Z kategorią $[\mathbf {C} ^{op},\mathbf {Set} ]$ jest stowarzyszony pewnien funktor, tzw. (bi)funktor ewaluacji (zamiast w pełni rygorystycznie $\mathrm {ev} _{[\mathbf {C} ^{op},\mathbf {Set} ],\mathbf {C} ^{op}}$ będziemy w skrócie pisali $\mathrm {ev} _{\mathbf {C} ^{op}}$):

$\mathrm {ev} _{\mathbf {C} ^{op}}\colon [\mathbf {C} ^{op},\mathbf {Set} ]\times \mathbf {C} ^{op}\to \mathbf {Set}$

definiowany dla $F,G\in [\mathbf {C} ^{op},\mathbf {Set} ]_{0}$, $X,Y\in \mathbf {C}$, $f\colon X\to Y\in \mathbf {C} _{1}$ oraz $\phi \colon F\to G$ jako:

$\mathrm {ev} _{\mathbf {C} ^{op}}(F,X)=F(X)$ $\mathrm {ev} _{\mathbf {C} ^{op}}(\phi ,f)=F(Y){\stackrel {F(f)}{\to }}F(X){\stackrel {\phi _{X}}{\to }}G(X).$

Zauważmy, że naturalność transformacji $\phi$:

pozwala nam zdefiniować działanie $\mathrm {ev} _{\mathbf {C} ^{op}}$ na strzałkach następująco:

$\mathrm {ev} _{\mathbf {C} ^{op}}(\phi ,f)=F(Y){\stackrel {\phi _{Y}}{\to }}G(Y){\stackrel {G(f)}{\to }}G(X).$

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 $\mathbf {C}$ będzie lokalnie małą kategorią, $X\in \mathbf {C} _{0},F\colon \mathbf {C} ^{op}\to \mathbf {Set}$. Wówczas w $\mathbf {Set}$ istnieje bijekcja:

$b\colon [\mathbf {C} ^{op},\mathbf {Set} ]({\mathcal {Y}}(X),F){\stackrel {\cong }{\longrightarrow }}F(X),$

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

Uwaga

Zapis $[\mathbf {C} ^{op},\mathbf {Set} ]({\mathcal {Y}}(X),F)$ oznacza kolekcję morfizmów w kategorii $[\mathbf {C} ^{op},\mathbf {Set} ]$, czyli kolekcję transformacji naturalnych między funktorami ${\mathcal {Y}}(X)=\mathrm {Hom} (-,X)$ i $F$. Lemat Yonedy mówi zatem po pierwsze, że ta kolekcja jest zbiorem (bo istnieje bijekcja ze zbiorem $F(X))$, a co za tym idzie operacja $F,X\mapsto [\mathbf {C} ^{op},\mathbf {Set} ]({\mathcal {Y}}(X),F)$

jest obiektową częścią funktora typu $[\mathbf {C} ^{op},\mathbf {Set} ]\times \mathbf {C} ^{op}\to \mathbf {Set}$. Druga część lematu wyjaśnia, że ten bifunktor jest naturalnie izomorficzny z bifunktorem ewaluacji.

Dowód

$X$-tym komponentem transformacji naturalnej $\phi \colon {\mathcal {Y}}(X)\to F$ jest funkcja $\phi _{X}\colon \mathrm {Hom} (X,X)\to F(X)$. Identyczność $1_{X}$ jest elementem $\mathrm {Hom} (X,X)$, a zatem $\phi _{X}(1_{X})\in F(X)$. To rozumowanie pozwala nam zgadnąć definicję bijekcji $b$ jako: $b(\phi ):=\phi _{X}(1_{X}).$

Z drugiej strony, dla dowolnego elementu$x$ zbioru $F(X)$, musimy zdefiniować transformację naturalną - nazwijmy ją $\langle x\rangle$, której $Y$-ty komponent $\langle x\rangle _{Y}$ będzie typu $\mathrm {Hom} _{\mathbf {C} }(Y,X)\to F(Y)$. Połóżmy więc:

$\langle x\rangle _{Y}(f):=F(f)(x).$

Rzeczywiście, tak zdefiniowana operacja jest transformacją naturalną, gdyż dla dowolnej strzałki $g\colon Y\to Y'$ w $\mathbf {C} _{1}$ diagram:

komutuje.

Pokażemy teraz, że funkcje $b$ i $\langle \cdot \rangle$ są do siebie odwrotne (tzn. tworzą bijekcję). Mamy $b(\langle x\rangle )=(\langle x\rangle )_{X}(1_{X})=F(1_{X})(x)=1_{F(X)}(x)=x$ (wykorzystaliśmy fakt, że funktory zachowują identyczności). Po drugie, $(\langle b(\phi )\rangle )_{Y}(f)=F(f)(b(\phi ))=F(f)(\phi )_{X}(1_{X}))=\phi _{Y}(1_{X}\circ f)=\phi _{Y}(f)$, gdzie w kluczowym momencie (w przedostatniej równości) wykorzystaliśmy naturalność transformacji $\phi$. A to oznacza, że $\langle b(\phi )\rangle =\phi$, co dowodzi, że $b$ jest bijekcją z odwrotnością $\langle \cdot \rangle$. Część pierwsza lematu jest więc wykazana i pozostaje nam jeszcze przekonać się o naturalności bijekcji $b$, tzn. niezależności od wyboru $F$ i $X$.

Niech $f\colon X'\to X\in \mathbf {C} _{1}$ oraz $\phi \colon F\to F'$. Wówczas diagram:

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

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'}).}

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 $X,Y\in \mathbf {C} _{0}$ mamy bijekcję pomiędzy funkcjami typu $X\to Y$ a funkcjami typu ${\mathcal {Y}}(X)\to {\mathcal {Y}}(Y)$. Ale przecież, zgodnie z lematem Yonedy, funkcje $f\colon C\to Y$ są w bijekcji z transformacjami naturalnymi $\langle f\rangle$ typu ${\mathcal {Y}}(X)\to {\mathcal {Y}}(Y)$. Zbadajmy komponenty: $(\langle f\rangle )_{Z}(g\colon Z\to X)={\mathcal {Y}}(Y)(g)(f)=(-\circ g)(f)=f\circ =(f\circ -)(g)=({\mathcal {Y}}(f))_{Z}(g).$

Wyciągamy więc wniosek, że $\langle \cdot \rangle ={\mathcal {Y}}$, czyli, że funkcje $f\colon X\to Y$ są w bijekcji z funkcjami typu ${\mathcal {Y}}(X)\to {\mathcal {Y}}(Y)$.

Lemat Yonedy ma często następujące zastosowanie: aby pokazać, że obiekty $A,B\in \mathbf {C} _{0}$ lokalnie małej kategorii $\mathbf {C}$ są izomorficzne, wystarczy pokazać, że dla każdego obiektu $X\in \mathbf {C} _{0}$ mamy bijekcję $\alpha _{X}\colon \mathrm {Hom} (X,A)\to \mathrm {Hom} (X,B)$, która spełnia warunek naturalności: dla każdej $g\colon X\to Z$ diagram:

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

Jak już wspomnieliśmy, funktor Yonedy pełni rolę zanurzenia kategorii $\mathbf {C}$ w inną kategorię $[\mathbf {C} ^{op},\mathbf {Set} ]$, 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 $\mathbf {C} ^{op}\to \mathbf {Set}$ da się w pewnym sensie zbudować z funktorów postaci ${\mathcal {Y}}(X)$ dla $X\in \mathbf {C} _{0}$, 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 $[\mathbf {C} ^{op},\mathbf {Set} ]$, tak zwanym funktorom reprezentowalnym.

Reprezentowalność funktorów

Zdarza się, że funktor $F\colon \mathbf {C} ^{op}\to \mathbf {Set}$ jest nie tyle równy, ile izomorficzny z funktorem ${\mathcal {Y}}(X)$ dla pewnego $X\in \mathbf {C} _{0}$. Taka sytuacja jest arcyciekawa i zasługuje na osobną definicję:

Definicja 7.4 [funktor reprezentowalny]

Funktor $F\colon \mathbf {C} ^{op}\to \mathbf {Set}$ izomorficzny z ${\mathcal {Y}}(X)$ dla pewnego $X\in \mathbf {C} _{0}$ nz. funktorem reprezentowalnym.

Lemat Yonedy jest tym narzędziem, które pozwala nam zrozumieć funktory reprezentowalne. Zobaczmy bowiem, że naturalny izomorfizm $\phi \colon {\mathcal {Y}}(X){\stackrel {\cong }{\to }}F$ jest elementem zbioru $[\mathbf {C} ^{op},\mathbf {Set} ]({\mathcal {Y}}(X),F)$, który - w myśl lematu Yonedy - jest izomorficzny ze zbiorem $F(X)$. To znaczy, że transformacji $\phi$ odpowiada jednoznacznie element $e\in F(X)$ definiowany jako $e:=b(\phi )$. Element $e$ nazywamy elementem uniwersalnym dla funktora $F$, zaś para $(X,e)$ nazywa się reprezentacją funktora $F$.

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

Lemat 7.5

Następujące warunki są równoważne:

• ${\mathcal {Y}}(X)\cong F$;
• Dla każdego $y\in F(Y)$ istnieje dokładnie jeden morfizm $f\colon Y\to X\in \mathbf {C} _{0}$ taki, że $F(f)(e)=y$.

Dowód

Zauważmy, że ${\mathcal {Y}}(X)\cong F$ oznacza, że dla każdego obiektu $Y\in \mathbf {C} _{0}$ mamy bijekcję $\mathrm {Hom} _{\mathbf {C} }(Y,X)={\mathcal {Y}}(X)(Y)\cong F(Y)$ (przy oznaczeniach z lematu Yonedy ta bijekcja nazywa się $(\phi )_{Y}$), co w takim razie możemy przeczytać tak, że dla dowolnego elementu $y\in F(Y)$ istnieje dokładnie jeden element (funkcja) $f\in \mathrm {Hom} _{\mathbf {C} }(Y,X)$ taki, że $y=(\phi )_{Y}(f)=(\langle b(\phi )\rangle )_{Y}(f)=(\langle e\rangle )_{Y}(f)=F(f)(e)$, co należało wykazać.

Ł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 $\mathbf {C}$ będzie lokalnie małą kategorią, $X,Y\in \mathbf {C} _{0}$. Definiujemy funktor $\Pi _{X,Y}\colon \mathbf {C} ^{op}\to \mathbf {Set}$ następująco: $Z\mapsto \mathrm {Hom} _{\mathbf {C} }(Z,X)\times \mathrm {Hom} _{\mathbf {C} }(Z,Y)$ $f\colon Z'\to Z\ \mapsto \ \mathrm {Hom} _{\mathbf {C} }(Z,X)\times \mathrm {Hom} _{\mathbf {C} }(Z,Y){\stackrel {(-\circ f)\times (-\circ f)}{\longrightarrow }}\mathrm {Hom} _{\mathbf {C} }(Z',X)\times \mathrm {Hom} _{\mathbf {C} }(Z',Y).$

Sprawdzimy, że produkt wraz z projekcjami $(X\times Y,(\pi _{X},\pi _{Y}))$ jest reprezentacją funktora $\Pi _{X,Y}$.

Niech $h\in \Pi _{X,Y}(Z)=\mathrm {Hom} _{\mathbf {C} }(Z,X)\times \mathrm {Hom} _{\mathbf {C} }(Z,Y)$. Produkt jest reprezentacją $\Pi _{X,Y}(Z)$ wtedy i tylko wtedy, gdy istnieje dokładnie jedna taka para morfizmów $(f,g)\in \mathrm {Hom} _{\mathbf {C} }(Z,X)\times \mathrm {Hom} _{\mathbf {C} }(Z,Y)$ taka, że:

$\Pi _{X,Y}((f,g))(\pi _{X},\pi _{Y})=h.$

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

$((-\circ (f,g))\times (-\circ (f,g)))(\pi _{X},\pi _{Y})=h$

wtedy i tylko wtedy, gdy:

$(\pi _{X}\circ (f,g),\pi _{Y}\circ (f,g))=h$

wtedy i tylko wtedy, gdy:

$(f,g)=h,$

ale ta równość jest prawdziwa, bo, z definicji produktu, para $(f,g)$ jest wyznaczona jednoznacznie (i jest równa $(\phi _{X}\circ h,\pi _{Y}\circ h)$).

Przykład 7.7

Funktor zapominania $U\colon \mathbf {Grp} \to \mathbf {Set}$ jest reprezentowany przez parę $((\mathbb {Z} ,+),1)$.

Dowód

W myśl Lematu 7.5 wystarczy przekonać się, że dla dowolnej grupy $(G,\circ ,e)$ i jej elementu $g\in G$ istnieje dokładnie jeden homomorfizm grup $f\colon \mathbb {Z} \to G$ taki, że $U(f)(1)=g$, to znaczy $f(1)=g$. Rzeczywiście, wystarczy położyć $f(n+m):=f(n)\circ f(m)$, $f(n^{-1}):=f(n)^{-1}$. Przy tej definicji $f$ jest homomorfizmem i jako jedyny spełnia $f(1)=g$. Rzeczywiście, $f$ jest homomorfizmem z definicji (w szczególności $f(0)=f(n-n)=f(n)\circ f(n)^{-1}=e$), a jeśli $h$ jest dowolnym innym homomorfizmem, który ma własność $h(1)=g$, to $f(n)=g^{n}=h(n)$ dla dowolnego $n$, czyli $f=h$.

Powyższy przykład pokazuje, że $U(G)\cong \mathrm {Hom} _{\mathbf {Grp} }(\mathbb {Z} ,G)$

Kategorię $\mathbf {C}$ nazywamy kartezjańską, jeśli posiada obiekt końcowy, produkty i ekwalizatory. Jeśli $\mathbf {C}$ 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 $\mathbf {C}$ jest kartezjańsko zamknięta wtedy i tylko wtedy, gdy dla każdej pary obiektów $X,Y\in \mathbf {C} _{0}$ funktor $G\colon \mathbf {C} ^{op}{\stackrel {-\times X}{\longrightarrow }}\mathbf {C} ^{op}{\stackrel {{\mathcal {Y}}(Y)}{\longrightarrow }}\mathbf {Set}$ jest reprezentowalny.

Dowód

Pokażemy, że reprezentacją tego funktora jest para składająca się z eksponentu $([X,Y],\mathrm {ev} _{X,Y})$ (porównaj Definicję 4.1).

Zauważmy po pierwsze, że $\mathrm {ev} _{X,Y}\in G([X,Y])={\mathcal {Y}}(Y)([X,Y]\times X)=\mathrm {Hom} _{\mathbf {C} }([X,Y]\times X,Y)$, czyli $\mathrm {ev} _{X,Y}$ ma rzeczywiście typ $[X,Y]\times X\to Y$. Dalej, zgodnie z definicją $\mathrm {ev} _{X,Y}$ jest elementem uniwersalnym $G$ jeśli dla każdego morfizmu $f\colon Z\times X\to Y$ istnieje dokładnie jeden morfizm (oznaczmy go jak zwykle $\mathrm {curry} (f)$) $\mathrm {curry} (f)\colon Z\to [X,Y]$ taki, że $G(\mathrm {curry} (f))(\mathrm {ev} _{X,Y})=f$. Musimy teraz już tylko rozszyfrować znaczenie ostatniego równania:

$G(\mathrm {curry} (f))(\mathrm {ev} _{X,Y})={\mathcal {Y}}(Y)(\mathrm {curry} (f)\times 1_{X})(\mathrm {ev} _{X,Y})=\mathrm {ev} _{X,Y}\circ (\mathrm {curry} (f)\times 1_{X}),$

a zatem ostatnie powyższe równanie to:

$\mathrm {ev} _{X,Y}\circ (\mathrm {curry} (f)\times 1_{X})=f,$

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

To kończy nasz dowód.