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

==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:

Wtedy funkcje $(p_{2},p_{1},f)\colon (A\times B)\times C\to A\times (B\times C)$ i $(g,p_{4}p_{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:

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:

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 ${\displaystyle ?}$ pasują zarówno $1_{A}\times 1_{B}$, jak i $1_{A\times B}$. A zatem muszą być równe.

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 ${\displaystyle ?}$ 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.

==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:

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:

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:

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:

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

Rozwiązanie:

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

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}$

nazywamy obiekt $Q$ wraz ze strzałkami

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:

To jest właśnie szukana definicja.