Teoria kategorii dla informatyków/Ćwiczenia 3: Zasada dualności i proste konstrukcje uniwersalne

From Studia Informatyczne

==Zadanie 3.1==

Kiedy w częściowym porządku (P,\leq) istnieje produkt dwóch elementów p,q\in P?

Rozwiązanie:

Przypuśćmy, że p\times q jest produktem p i q. Wówczas istnieją projekcje p\times q\leq p i p\times q\leq q, co świadczy o tym, że element p\times q jest ograniczeniem dolnym zbioru \{ p,q\}. Własność uniwersalna produktu mówi, że dla dowolnego z\in P, jeśli z\leq p,q, to z\leq p\times q, a zatem p\times q jest infimum elementów p i q (największym ograniczeniem dolnym p i q). Dualnie, koproduktem jest supremum. Jak widać, posety stanowią kategorie, gdzie produkt i koprodukt dowolnych dwóch elementów nie muszą istnieć. Poset z produktami i koproduktami dla każdej pary elementów nazywa się kratą.

==Zadanie 3.2==

Omówić koprodukt w \mathbf{Set}.

Rozwiązanie:

Na początku musimy zgadnąć, jakim zbiorem jest A+B i funkcje i_A,i_B. Intuicja podpowiada, że skoro koprodukt jest dualny do produktu, to A+B może być sumą A\cup B, zaś i_A,i_B - zanurzeniami. Niestety, gdy wybierzemy A=\{ a,b\}, B=\{ b,c\}, X =\{ a,b,b',c\} oraz dwie funkcje f\colon A\to X: f(a)=a i f(b)=b, g\colon B\to X: g(b)=b', g(c)=c, to nie znajdziemy żadnej funkcji h\colon A\cup B\to X takiej, że f=h\circ i_A i g=g\circ i_B. Widać, że to z tej przyczyny, iż iloczyn A\cap B jest niepusty i element b\in A\cap B jest albo posyłany w b\in Z, albo w b'\in Z przez funkcje f i g. Żądajmy więc, aby suma zbiorów A i B była rozłączna! Po chwili zastanowienia okazuje się, że to dobry pomysł. Pokażmy zatem, że koproduktem zbiorów A, B jest suma rozłączna:

S := \{(a,1)\mid a\in A\}\cup \{(b,2)\mid b\in B\}

wraz z zanurzeniami

i_1(a):= (a,1), \ i_2(b) := (b,2).

Jeśli dla dowolnych funkcji f\colon A\to Z, g\colon B\to Z zdefiniujemy:

[f,g](x,n) := \begin{cases} f(x)& n=1\\ g(x)& n=2,  \end{cases}

to jeśli h\circ i_A = f oraz h \circ i_B = g dla h\colon S\to Z, to [f,g](x,n)=(f(x)\vee g(x))=(hi_A(x)\vee hi_B(x))=h((x,n)), czyli [f,g]=h. To dowodzi, że S=A+B, co należało pokazać.

==Zadanie 3.3==

Wykaż, że (A\times B)\times C \cong A\times (B\times C) dla A,B,C\in \mathbf{C}_0 w dowolnej kategorii \mathbf{C}, w której oba produkty istnieją. Jakie jest stwierdzenie dualne?

Rozwiązanie:

Rozważamy dwa diagramy, na których wszystkie nie nazwane strzałki są odpowiednimi projekcjami:

Grafika:tk-3.25.png
Grafika:tk-3.26.png

Wtedy funkcje (p_2,p_1,f)\colon (A\times B)\times C\to A\times (B\times C) i (g,p_4p_3)\colon A\times (B\times C)\to (A\times B)\times C składają się w obie strony do jedności (co łatwo sprawdzić, śledząc diagramy), a zatem są wzajemnie odwrotnymi izomorfizmami, co należało pokazać.

Zdanie dualne to oczywiście (A+B)+C\cong A+(B+C), ponieważ \times^{op} = + oraz \cong^{op}= \cong (tzn. izomorfizm jest pojęciem samodualnym).

==Zadanie 3.4==

Udowodnić, że jeśli w kategorii \mathbf{C} istnieje obiekt końcowy i wszystkie pulbaki, to istnieją także produkty i ekwalizatory. Jak brzmi twierdzenie dualne?

Wskazówka:

Twierdzenie dualne brzmi: w kategorii \mathbf{C} z obiektem początkowym, jeśli istnieją pushouty, to istnieją także koprodukty i koekwalizatory.

Rozwiązanie:

Niech X,Y\in \mathbf{C}_0. Rozważmy strzałki do obiektu końcowego:

X\stackrel{X}{\longrightarrow}\mathbf{1}\stackrel{Y}{\longleftarrow}Y
i niech X\stackrel{p}{\leftarrow}P\stackrel{q}{\rightarrow}Y będzie ich pulbakiem. Wówczas ten sam
X\stackrel{p}{\leftarrow}P\stackrel{q}{\rightarrow}Y

jest produktem X i Y. Rzeczywiście, złożenia X\circ p i Y\circ q są strzałkami, które posyłają P w \mathbf{1}. Ale strzałka w obiekt końcowy może być tylko jedna, więc X\circ p = Y\circ q. Jeśli zaś weźmiemy dowolny inny obiekt Q i strzałki f\colon Q\to X, g\colon Q\to Y, to mamy X\circ f = Y\circ g z własności uniwersalnej \mathbf{1}, a zatem z własności uniwersalnej pulbaku istnieje dokładnie jedna strzałka h\colon Q\to P taka, że p\circ h = q\circ h, co należało pokazać.

Weźmy teraz dwie równoległe strzałki f,g\colon X\to Y. Tworzymy pulbak:

Grafika:tk-3.27.png

i wtedy E\stackrel{e}{\to}X jest ekwalizatorem f i g. Szczegóły są tu równie łatwe jak w przypadku produktu.

==Zadanie 3.5==

Udowodnij, że w dowolnej lokalnie małej kategorii \mathbf{C} hom-funktor \mathrm{Hom}(A,-)\colon \mathbf{C}\to \mathbf{Set}, gdzie A\in\mathbf{C}_0, zachowuje produkty.

Wskazówka:

Sformułowanie zdania, które należy dowieść, to połowa sukcesu.

Rozwiązanie:

Zdanie, które musimy wykazać, to:

\mathrm{Hom}(A,B\times C)\cong \mathrm{Hom}(A,B)\times \mathrm{Hom}(A,C),

a to w przypadku \mathbf{C}=\mathbf{Set} jest znany z teorii mnogości izomorfizm pomiędzy zbiorami wyznaczony przez funkcję:

A\stackrel{f}{\to}B\times C\ \mapsto \ (p_B\circ f, p_C\circ f),

gdzie p_B,p_C są odpowiednimi projekcjami. Zwróćmy uwagę, że powyższa definicja da się wypowidzieć w przypadku dowolnej kategorii \mathbf{C}. Jej postać jest uniwersalna i z definicji produktu natychmiast wynika, że strzałka ta jest szukanym izomorfizmem.

==Zadanie 3.6==

Widzieliśmy, że pulbak jest funktorem. Udowodnij, że produkt jest funktorem.

Wskazówka:

Niech \mathbf{C} będzie dowolną kategorią z produktami. Musimy w pierwszej kolejności wskazać dwie operacje:

A,B\mapsto A\times B
f,g\mapsto f\times g

odpowiednio dla obiektów A,B\in\mathbf{C}_0 i strzałek f,g\in \mathbf{C}_1. Tylko druga z nich wymaga zastanowienia. Proponujemy dla f\colon A\to B, g\colon C\to D, produkt f\times g\colon A\times C\to B\times D jako jedyną strzałkę, dla której poniższy diagram komutuje:

Grafika:tk-3.28.png

gdzie nie nazwane strzałki są projekcjami (jedyność f\times g wynika z własności uniwersalnej produktu B\times D).

Rozwiązanie:

Pokażmy, że identyczności są zachowane, tzn. że 1_{A\times B}=1_A\times 1_B. To proste: w poniższym komutującym diagramie w miejsce jedynej strzałki ? pasują zarówno 1_A\times 1_B, jak i 1_{A\times B}. A zatem muszą być równe.

Grafika:tk-3.29.png

Aby zakończyć dowód należy pokazać, że:

(g\circ f)\times (h\circ k) = (g\times h)\circ (f\times k),

co z kolei natychmiast wynika z komutowania poniższego diagramu (zwróćmy uwagę, że w miejsce jedynej strzałki ? pasuje zarówno (g\circ f)\times (h\circ k), jak i (g\times h)\circ (f\times k), co sprawia, że te strzałki muszą być równe.

Grafika:tk-3.30.png

==Zadanie 3.7==

Udowodnij, że produkt zachowuje izomorfizmy, tzn. jeśli A\cong A' i B\cong B', to A\times B\cong A'\times B'.

Wskazówka:

Wykorzystaj wzory z Zadania 3.6.

Rozwiązanie:

Załóżmy, że mamy izomorfizmy:

g\circ f = 1_{A}, f\circ g = 1_{A'}, h\circ k = 1_B, k\circ h = 1_{B'}. Wtedy

(f\times k)\circ (g\times h) = (f\circ g)\times (k\circ h) = 1_{A'}\times 1_{B'}=1_{A'\times B'}

i analogicznie

(g\times h)\circ (f\times k)=(g\circ f)\times (h\circ k) = 1_{A}\times 1_B = 1_{A\times B}.

Udowodniliśmy zatem, że g\times h i f\times k są wzajemnie odwrotnymi izomorfizmami.


==Zadanie 3.8==

Udowodnij Lemat Pulbakowy.

Rozwiązanie:

Udowodnimy tylko połowę lematu; drugą część rozwiązuje się w taki sam sposób - obserwując komutujące diagramy.

Pokażemy zatem, że jeśli dwa wewnętrzne kwadraty są pulbakami, to zewnętrzny prostokąt też. Pracujemy na następującym diagramie:

Grafika:tk-3.31.png

Załóżmy: (1) gy=gcx. Z prawego pulbaku istnieje dokładnie jedna strzałka k taka, że: (2) ek=y, oraz: (3) cx=dk. Z lewego pulbaku, w świetle (3), istnieje dokładnie jedna strzałka l taka, że: (4) al=k, oraz: (5) bl=x. Z (5),(4),(2) wynika więc eal=ek=y, co kończy dowód.

==Zadanie 3.9==

Pokaż, że twierdzenie odwrotne do Faktu 3.7 nie zachodzi.

Wskazówka:

Szukamy takiej kategorii, w której istnieje monomorfizm, który nie jest ekwalizatorem żadnych dwóch równoległych strzałek tej kategorii. Poszukajmy takiego mono w monoidzie liczb naturalnych (\mathbf{N},+,0).

Rozwiązanie:

Wszystkie strzałki w (\mathbf{N},+,0) są mono, w szczególności 1. Ale 1 nie ekwalizuje żadnej pary (m,n). Gdyby tak było, to mielibyśmy m+1=n+1. Stąd m=n i dalej: m+0=n+0. Z własności uniwersalnej, 0 musiałoby się faktoryzować przez 1, czyli musiałaby istnieć taka liczba naturalna k, że 1+k=0, sprzeczność.

==Zadanie 3.10==

Pokazać, że w \mathbf{Set} dowolny monomorfizm jest ekwalizatorem.

Wskazówka:

Dla funkcji f\colon A\to B rozważamy dwie funkcje B\to \{ 0,1\} - funkcję charakterystyczną obrazu Im(f):

\chi_f(b) :=  \begin{cases} 1, & \text{dla } b\in Im(f)\\ 0 & \text{w przeciwnym przypadku}. \end{cases}

i stałą funkcję tt\colon B\to \{ 0,1\} równą 1 dla każdego b\in B.

Rozwiązanie:

Pracujemy na następującym diagramie:

Grafika:tk-3.32.png

Oczywiście (\chi_f\circ f)(a)=\chi_f(f(a))=1=tt(f(a))=(tt\circ f)(a), czyli \chi_f\circ f=tt\circ f. Jeśli dla pewnego g mamy \chi_f\circ g = tt\circ g, to \chi_f(g(z))=1, co oznacza, że g(z)\in Im(f), czyli istnieje a_z\in A takie, że g(z) = f(a_z). Wystarczy więc zdefiniować funkcję k\colon Z\to A jako k(z) := a_z. Jest oczywiste, że taka funkcja jest jedyną, która spełnia g=f\circ k.

Dla studentów, którzy zetknęli się z toposami, warto w tym miejscu dodać, że monomorfizmy są ekwalizatorami w dowolnym toposie.

==Zadanie 3.11==

Pokazać, że w dowolnej kategorii epi ekwalizator jest izomorfizmem.

Rozwiązanie:

Rozważmy diagram:

Grafika:tk-3.33.png

Skoro e jest ekwalizatorem f,g, mamy f\circ e = g\circ e. Epimorficzność daje f=g, czyli f\circ 1_A =g\circ 1_A. Dla identyczności 1_A spełniony jest warunek (1) definicji ekwalizatora, a zatem istnieje dokładnie jedna strzałka k\colon A\to E taka, że e\circ k =1_A. Pokażemy, że k\circ e=1_E, co zakończy dowód. Ale przecież e\circ k = 1_A implikuje e\circ k\circ e = 1_A\circ e = e = e\circ 1_E. Każdy ekwalizator jest mono, więc upraszcza się z lewej strony, co daje: k\circ e = 1_E.

==Zadanie 3.12==

Wykazać, że w posecie (P, \leq) ekwalizatorami są identyczności.

Rozwiązanie:

Element e\in P będzie ekwalizatorem p\leq q, jeśli z faktu s\leq p\leq q wynika s\leq e, dla każdego s\in P. To jest możliwe tylko, gdy e=p, czyli gdy ekwalizator jest identycznością e\leq e.

==Zadanie 3.13==

Wykazać, że jeśli f\colon A\to B jest funkcją i C\subseteq B, to przeciwobraz f^{-1} jest pulbakiem f i inkluzji i\colon C\to B.

Rozwiązanie:

W \mathbf{Set} wiemy dokładnie, jak wygląda pulbak f\colon A\to B i zanurzenia i\colon C\to B:

A\times_B C = \{ (a,c)\in A\times C\mid f(a)=i(c)\},

czyli:

A\times_B C = \{ (a,f(a))\in A\times C\mid f(a)\in C\},

który to zbiór jest izomorficzny z f^{-1}[C].

==Zadanie 3.14==

W \mathbf{Set}, czym jest pulbak dla diagramu: A\stackrel{f}{\rightarrow}B\stackrel{f}{\leftarrow}A?

Rozwiązanie:

Jest to zbiór \{(a,b)\in A\times A\mid f(a)=f(b)\}, czyli relacja równoważności, którą wyznacza f na A\times A.

==Zadanie 3.15==

Udowodnij, że w pulbak monomorfizmu jest monomorfizmem.

Wskazówka:

Musimy pokazać, że w diagramie:

Grafika:tk-3.34.png

jeśli f jest mono, to g też.

Rozwiązanie:

Załóżmy, że f mono i na diagramie:

Grafika:tk-3.35.png

niech gk=gh. Skoro bgh=bgk=fak, to istnieje dokładnie jedna strzałka z taka, że az=ak i gh=gz. Oczywiście, podstawiając k za z, widzimy, że z=k, z jedyności. Podstawiając h za z, wystarczy sprawdzić, że ah=ak, ale to prawda, bo fah=bgh=bgk=fak i f jest mono, co daje upragnioną równość: ah=ak. Pokazaliśmy, że k=z=h, czyli g jest mono.

==Zadanie 3.16==

Zdefiniuj pushout, posługując się Zasadą Dualności.

Rozwiązanie:

Biorąc definicję pulbaku i stosując ściśle zasadę dualności, dostajemy tekst:

Pushoutem strzałek f, g takich, że \mathrm{dom}(f)=\mathrm{dom}(g) w kategorii \mathbf{C}

Grafika:tk-3.36.png

nazywamy obiekt Q wraz ze strzałkami

Grafika:tk-3.37.png

taki, że:

  • poniższy kwadrat pushoutowy komutuje, tzn. p\circ f = q\circ g oraz
  • uniwersalny, tzn. dla dowolnego innego kandydata na pushout
A\stackrel{r}{\longleftarrow}R\stackrel{s}{\longrightarrow}B

istnieje dokładnie jedna strzałka u\colon Q\to R taka, że: r = u\circ p i s = u\circ q, tzn. taka, że poniższy diagram komutuje:

Grafika:tk-3.38.png

To jest właśnie szukana definicja.