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

==Zadanie 7.1==

Udowodnić, że ${\mathrm{e}\mathrm{v}}_{{\mathbf{𝐂}}^{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{𝐂}}_0$, morfizmy $f:X\to Y$, $g:Y\to Z$, funktory $F,G,H:{\mathbf{𝐂}}^{op}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ oraz transformacje naturalne $\varphi :F\to G$ i $\psi :G\to H$.

Zachowywanie identyczności:

${\mathrm{e}\mathrm{v}}_{{\mathbf{𝐂}}^{op}}(1_F,1_X)=(1_F{)}_X\circ F(1_X)=1_{F(X)}\circ 1_{F(X)}=1_{F(X)}=1_{{\mathrm{e}\mathrm{v}}_{{\mathbf{𝐂}}^{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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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{𝐂}}^{op}$, definicję ${\mathrm{e}\mathrm{v}}_{{\mathbf{𝐂}}^{op}}$, kontrawariantność $H$, naturalność $\psi$ wyrażoną diagramem:

i na końcu znów definicję ${\mathrm{e}\mathrm{v}}_{{\mathbf{𝐂}}^{op}}$.

==Zadanie 7.2==

Udowodnić, że obiekty $A,B\in {\mathbf{𝐂}}_0$ lokalnie małej kategorii $\mathbf{𝐂}$ są izomorficzne, jeśli dla każdego obiektu $X\in {\mathbf{𝐂}}_0$ istnieje bijekcja $f_X:\mathrm{H}\mathrm{o}\mathrm{m}(X,A)\to \mathrm{H}\mathrm{o}\mathrm{m}(X,B)$, która spełnia warunek naturalności: dla każdej $g:X\to Z$ diagram

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 ${𝒴}(A)$ i ${𝒴}(B)$ w $[{\mathbf{𝐂}}^{op},\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}]$, w skrócie ${𝒴}(A)\cong {𝒴}(B)$. Ponieważ ${𝒴}$ jest funktorem pełnym i wiernym, więc odzwierciedla izomorfizmy (patrz Fakt 2.9). A to oznacza, że ${𝒴}(A)\cong {𝒴}(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 ${𝒴}(2)=\mathrm{H}\mathrm{o}\mathrm{m}(-,2)$.

Rozwiązanie:

Udowodnimy, że $(2,\{1\})$ (jak zwykle $2:=\{0,1\}$) jest reprezentacją ${𝒫}:{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}^{op}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$. W myśl Lematu 7.5 wystarczy pokazać, że dla dowolnego zbioru $Y$ i elementu $Z\in {𝒫}(Y)$ istnieje dokładnie jedna funkcja $f:Y\to 2$ taka, że ${𝒫}(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: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 ${𝒴}$.

Wskazówka:

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

Rozwiązanie:

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

$f:={\alpha }_A(1_A)\in {𝒴}(B)(A)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,B)$

$f:={\alpha }_B^{-1}(1_B)\in {𝒴}(A)(B)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(B,A)$

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

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:{\mathbf{𝐂}}^{op}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ są ze sobą izomorficzne.

Wskazówka:

Wykorzystać Lemat 7.5.

Rozwiązanie:

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

==Zadanie 7.6==

Udowodnij, że dla lokalnie małej kategorii $\mathbf{𝐂}$, operacja ${\mathrm{H}\mathrm{o}\mathrm{m}}_C:{\mathbf{𝐂}}^{op}\times \mathbf{𝐂}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ 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{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(-,X)$ i ${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(X,-)$ są funktorami dla każdego $X\in {\mathbf{𝐂}}_0$. Wystarczy zatem skorzystać z Zadania 5.3 i pokazać następującą równość:

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },g)\circ {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B^{\prime })\circ {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,g)$

dla dowolnych strzałek $f:A^{\prime }\to A$ i $g:B\to B^{\prime }$. Zróbmy to zadanie bardzo powoli - najpierw ustalamy typy wszystkich operacji:

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },g):{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },B)\to \mathrm{H}\mathrm{o}\mathrm{m}(A^{\prime },B^{\prime })$

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,g):{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,B)\to \mathrm{H}\mathrm{o}\mathrm{m}(A,B^{\prime })$

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B^{\prime }):{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,B^{\prime })\to {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },B^{\prime })$

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B):{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,B)\to {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },B)$

A teraz przechodzimy do właściwego dowodu:

$({\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },g)\circ {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B))(p:A\to B)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A^{\prime },g)(p\circ f)=g\circ p\circ f)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B^{\prime })(g\circ p)={\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(f,B^{\prime })\circ {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,g)(p)$