Teoria kategorii dla informatyków/Ćwiczenia 7: Lemat Yonedy i funktory reprezentowalne

From Studia Informatyczne

==Zadanie 7.1==

Udowodnić, że \mathrm{\mathrm{ev}}_{\mathbf{C}^{op}} jest (bi)funktorem.

Wskazówka:

Należy zachować spokój.

Rozwiązanie:

Zbierzmy wszystkie potrzebne dane: potrzebne są nam obiekty X,Y,Z\in \mathbf{C}_0, morfizmy f\colon X\to Y, g\colon Y\to Z, funktory F,G, H\colon \mathbf{C}^{op}\to \mathbf{Set} oraz transformacje naturalne \phi\colon F\to G i \psi\colon G\to H.

Zachowywanie identyczności:

\mathrm{ev}_{\mathbf{C}^{op}}(1_F, 1_X) =  (1_F)_X\circ F(1_X)= 1_{F(X)}\circ 1_{F(X)} = 1_{F(X)}=1_{\mathrm{ev}_{\mathbf{C}^{op}}(F,X)}.

Zauważmy, że korzystamy z definicji funktora ewaluacji, definicji transformacji naturalnej 1_X i faktu, że F zachowuje identyczności.

Zachowywanie złożenia:

\mathrm{ev}_{\mathbf{C}^{op}}((\phi, f),(\psi, g)) &=& \mathrm{ev}_{\mathbf{C}^{op}}(\phi\circ \psi, f\circ_{\mathbf{C}^{op}} g)= \mathrm{ev}_{\mathbf{C}^{op}}(\phi\circ \psi, g\circ f)=(\phi\circ \psi)_X \circ H(g\circ f)= \phi_X\circ \psi_X \circ H(f)\circ H(g)= \phi_X\circ \psi_X \circ H(f)\circ H(g)=\phi_X\circ F(f)\circ \psi_Y\circ H(g)=\mathrm{ev}_{\mathbf{C}^{op}}(\phi,f)\circ \mathrm{ev}_{\mathbf{C}^{op}}(\psi, g).

Wykorzystaliśmy kolejno: definicję złożenia w produkcie, definicję złożenia w \mathbf{C}^{op}, definicję \mathrm{ev}_{\mathbf{C}^{op}}, kontrawariantność H, naturalność \psi wyrażoną diagramem:

Grafika:tk-7.7.png

i na końcu znów definicję \mathrm{ev}_{\mathbf{C}^{op}}.

==Zadanie 7.2==

Udowodnić, że obiekty A,B\in\mathbf{C}_0 lokalnie małej kategorii \mathbf{C} są izomorficzne, jeśli dla każdego obiektu X\in \mathbf{C}_0 istnieje bijekcja f_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

Grafika:tk-7.8.png

komutuje.

Wskazówka:

Jakie własności mają funktory pełne i wierne?

Rozwiązanie:

Założenia implikują, że \alpha_X jest naturalną bijekcją pomiędzy funktorami \mathcal{Y}(A) i \mathcal{Y}(B) w [\mathbf{C}^{op}, \mathbf{Set}], w skrócie \mathcal{Y}(A)\cong \mathcal{Y}(B). Ponieważ \mathcal{Y} jest funktorem pełnym i wiernym, więc odzwierciedla izomorfizmy (patrz Fakt 2.9). A to oznacza, że \mathcal{Y}(A)\cong \mathcal{Y}(B) implikuje A\cong B, co pozwala nam wywnioskować A\cong B i kończy dowód.

==Zadanie 7.3==

Znaleźć reprezentację kontrawariantnego funktora potęgowego.

Wskazówka:

Wiemy (Zadanie 5.5), że kontrawariantny funktor potęgowy jest izomorficzny z \mathcal{Y}(2) = \mathrm{Hom}(-,2).

Rozwiązanie:

Udowodnimy, że (2,\{ 1\}) (jak zwykle 2:=\{0,1\}) jest reprezentacją \mathcal{P}\colon \mathbf{Set}^{op}\to \mathbf{Set}. W myśl Lematu 7.5 wystarczy pokazać, że dla dowolnego zbioru Y i elementu Z\in \mathcal{P}(Y) istnieje dokładnie jedna funkcja f\colon Y\to 2 taka, że \mathcal{P}(f)(\{ 1\})=Z, czyli f^{-1}[\{ 1\}]=Z. Zauważmy, że funkcja charakterystyczna \chi_Z zbioru Z spełnia ostatnie równanie. Jeśli zaś g^{-1}[\{ 1\}]=Z dla pewnej funkcji g\colon Y\to 2, to dla dowolnego y\in Y mamy g(y)=1 dokładnie wtedy, gdy y\in Z, dokładnie wtedy, gdy \chi_Z(y)=1. Ponieważ 2 ma tylko dwa elementy, wnioskujemy, że g(y)=\chi_Z(y). Z dowolności y\in Y wynika g=\chi_Z, czyli funkcja charakterystyczna jest jedyna. To kończy dowód.

==Zadanie 7.4==

Rozwiązać Zadanie 7.2 bez odwoływania się do własności funktora \mathcal{Y}.

Wskazówka:

Nie wolno więc bezpośrednio odwołać się do faktu, że \mathcal{Y} jako pełny i wierny funktor odzwierciedla izomorfizmy.

Rozwiązanie:

Z założenia wynik, że \alpha\colon \mathcal{Y}(A)\to \mathcal{Y}(B) jest naturalnym izomorfizmem. Zdefiniujmy dwie funkcje:

f := \alpha_A(1_A)\in \mathcal{Y}(B)(A) = \mathrm{Hom}_{\mathbf{C}}(A,B),


f := \alpha^{-1}_B(1_B)\in \mathcal{Y}(A)(B) = \mathrm{Hom}_{\mathbf{C}}(B,A).

Założenie naturalności transformacji \alpha okazuje się być kluczem do rozwiązania: skoro diagram

Grafika:tk-7.9.png

komutuje, to znaczy, że f\circ g = 1_B. Dualnie, g\circ f = 1_A. A zatem A\cong B.

==Zadanie 7.5==

Wykazać, że reprezentacje funktora F\colon \mathbf{C}^{op}\to \mathbf{Set} są ze sobą izomorficzne.

Wskazówka:

Wykorzystać Lemat 7.5.

Rozwiązanie:

Niech (X,e),(X'e') będą reprezentacjami funktora F. Ponieważ e'\in F(X'), więc Lemat 7.5 daje f\colon X'\to X taką, że F(f)(e)=e'. Analogicznie istnieje h\colon X\to X' z F(h)(e')=e. A zatem F(h\circ f)=F(f)(F(h)(e'))=e' (złożenie jest napisane poprawnie, bo F jest kontrawariantny!). Ponieważ również F(1_{X'})(e')=e', to uniwersalność z drugiego warunku Lematu 7.5 implikuje h\circ f = 1_{X'}. Analogicznie pokazujemy f\circ h = 1_X, co świadczy o tym, że strzałki f i h ustanawiają izomorfizm X\cong X', zaś strzałki F(f) i F(h) dają bijekcję F(X)\cong F(X'), która przeprowadza element e w e' i vice versa.

==Zadanie 7.6==

Udowodnij, że dla lokalnie małej kategorii \mathbf{C}, operacja \mathrm{Hom}_C\colon \mathbf{C}^{op}\times \mathbf{C}\to \mathbf{Set} jest bifunktorem.

Wskazówka:

Zamiast dowodu bezpośredniego, wykorzystaj Zadanie 5.3 charakteryzujące bifunktory.

Rozwiązanie:

Na podstawie Przykładu 5.7 prezentowanego podczas Wykładu 5. i Zadania 5.8, wiemy, że operacje \mathrm{Hom}_{\mathbf{C}}(-,X) i \mathrm{Hom}_{\mathbf{C}}(X,-) są funktorami dla każdego X\in \mathbf{C}_0. Wystarczy zatem skorzystać z Zadania 5.3 i pokazać następującą równość:

\mathrm{Hom}_{\mathbf{C}}(A',g)\circ \mathrm{Hom}_{\mathbf{C}}(f,B)=\mathrm{Hom}_{\mathbf{C}}(f,B')\circ \mathrm{Hom}_{\mathbf{C}}(A,g),

dla dowolnych strzałek f\colon A'\to A i g\colon B\to B'. Zróbmy to zadanie bardzo powoli - najpierw ustalamy typy wszystkich operacji:

\mathrm{Hom}_{\mathbf{C}}(A',g)\colon \mathrm{Hom}_{\mathbf{C}}(A',B)\to \mathrm{Hom}(A',B')


\mathrm{Hom}_{\mathbf{C}}(A,g)\colon \mathrm{Hom}_{\mathbf{C}}(A,B)\to \mathrm{Hom}(A,B')


\mathrm{Hom}_{\mathbf{C}}(f,B')\colon \mathrm{Hom}_{\mathbf{C}}(A,B')\to \mathrm{Hom}_{\mathbf{C}}(A',B')


\mathrm{Hom}_{\mathbf{C}}(f,B)\colon \mathrm{Hom}_{\mathbf{C}}(A,B)\to \mathrm{Hom}_{\mathbf{C}}(A',B).

A teraz przechodzimy do właściwego dowodu:

(\mathrm{Hom}_{\mathbf{C}}(A',g)\circ \mathrm{Hom}_{\mathbf{C}}(f,B))(p\colon A\to B)= \mathrm{Hom}_{\mathbf{C}}(A',g)(p\circ f)= g\circ p\circ f)= \mathrm{Hom}_{\mathbf{C}}(f,B')(g\circ p)= \mathrm{Hom}_{\mathbf{C}}(f,B')\circ \mathrm{Hom}_{\mathbf{C}}(A,g)(p).