Teoria kategorii dla informatyków/Wykład 10: Sprzężenia II

Wstęp

Ten wykład poświęcamy związkom między sprzężeniami a równoważnością kategorii oraz problemowi istnienia sprzężeń, która wiąże się z ich najważniejszą własnością: zachowywaniem odpowiednich granic.

Sprzężenia a równoważność

W świetle Twierdzenia 9.3 i definicji równoważności widzimy, że jeśli jedność i kojedność sprzężenia są izomorfizmami, to tworzą równoważność. Z drugiej strony, jeśli $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i $G:\mathbf{𝐃}\to \mathbf{𝐂}$ są równoważnością, to naturalny izomorfizm $\theta :F\circ G\stackrel{\cong }{\to }{1}_{\mathbf{𝐃}}$ daje dla każdej strzałki $f:D\to D^{\prime }\in {\mathbf{𝐃}}_1$ przemienny diagram:

co oznacza $f={\theta }_D\circ (F\circ G)(f)\circ {\theta }_{D^{\prime }}^{-1}$. Dla dowolnych $f_1,f_2\in {\mathbf{𝐃}}_1$ mamy:

$G(f_1)=G(f_2)\Rightarrow {\theta }_D\circ (F\circ G)(f_1)\circ {\theta }_{D^{\prime }}^{-1}={\theta }_D\circ (F\circ G)(f_2)\circ {\theta }_{D^{\prime }}^{-1}\Rightarrow f_1=f_2$

a zatem $G$ jest funktorem wiernym. Z symetrii założeń wynika, że $F$ jest również wierny. Aby pokazać, że $G$ jest pełny, weźmy dowolną strzałkę $h:G(D)\to G(D^{\prime })\in {\mathbf{𝐂}}_1$. Połóżmy $f={\theta }_D\circ F(h)\circ {\theta }_{D^{\prime }}^{-1}$, co oznacza, że:

komutuje. A zatem:

$Fh={\theta }_D^{-1}f{\theta }_D={\theta }_D^{-1}{\theta }_{D}FG(f){\theta }_{D^{\prime }}^{-1}{\theta }_D=FG(f)$

Skoro $F$ jest wierny, $h=G(f)$, co dowodzi, że $G$ jest pełny. Pokazaliśmy, że $G$ jest pełny i wierny, a zatem morfizmy typu $FC\to D$ w $\mathbf{𝐃}$ są w bijekcji z morfizmami typu $GFC\to GD$ w $\mathbf{𝐂}$, czyli po złożeniu z izomorfizmem $C\cong GFC$, w odpowiedniości 1-1 z morfizmami typu $C\to GD$. To znaczy, że $F⊣G$. Z symetrii założeń wynika $G⊣F$. Udowodniliśmy następujące:

Twierdzenie 10.1 [Sprzężenia a równoważność]

Jeśli $F:\mathbf{𝐂}\to \mathbf{𝐃},G:\mathbf{𝐃}\to \mathbf{𝐂}$ są równoważnością, to $F⊣G$ i $G⊣F$.

Z dowodu powyższego twierdzenia wynika wniosek, że funktory pełne i wierne (na przykład te pochodzące z równoważności kategorii) są ze sobą sprzężone. Poniżej scharakteryzujemy prawe sprzężenia ze względu na pełność i wierność.

Twierdzenie 10.2 [wierność i pełność prawego sprzężenia]

Załóżmy, że $F⊣G$ dla $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i $G:\mathbf{𝐃}\to \mathbf{𝐂}$. Wówczas:

• $G$ jest wierny wtedy i tylko wtedy, gdy dla dowolnego $Y\in {\mathbf{𝐃}}_0$ komponent kojedności ${\epsilon }_Y:FGY\to Y$ jest epimorfizmem w $\mathbf{𝐃}$.
• $G$ jest pełny i wierny wtedy i tylko wtedy, gdy kojedność $\epsilon$ jest izomorfizmem.

Dowód

Zauważmy najpierw, że dowolny morfizm $f:A\to A^{\prime }$ w dowolnej kategorii lokalnie małej $\mathbf{𝐀}$ jest epimorfizmem (izomorfizmem) wtedy i tylko wtedy, gdy dla dowolnego $B\in {\mathbf{𝐀}}_0$ funkcja ${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐀}}(f,B)$ jest injekcją (bijekcją) w $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$.

Przechodząc do właściwego dowodu, dla $Y,Y^{\prime }\in {\mathbf{𝐃}}_0$, mamy złożenie:

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐃}}(Y,Y^{\prime })\stackrel{\mathrm{H}\mathrm{o}\mathrm{m}({\epsilon }_Y,Y^{\prime })}{⟶}{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐃}}(FGY,Y^{\prime })\stackrel{\cong }{⟶}{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(GY,G{Y}^{\prime })$ $g\mapsto g\circ {\epsilon }_Y\mapsto G(g\circ {\epsilon }_Y){\eta }_{GY}=G(g)$ A zatem $G$ jest wierny (wierny i pełny) wtedy i tylko wtedy, gdy $g\mapsto G(g)$ jest injekcją (bijekcją), co zachodzi dokładnie wtedy, gdy $\mathrm{H}\mathrm{o}\mathrm{m}({\epsilon }_Y,Y^{\prime })$ jest injekcją (bijekcją), co zgodnie z uwagą na początku dowodu jest równoważne warunkowi, że ${\epsilon }_Y$ dla dowolnego $Y$ jest epimorfizmem (izomorfizmem). To kończy dowód (prowadzony równolegle dla obu własności).

Istnienie sprzężeń

Spróbujemy teraz odpowiedzieć sobie na ważne pytanie: kiedy dany funktor ma sprzężenie. Warunkiem koniecznym okazuje się następująca własność, którą można rozumieć tak, że prawych sprzężeń należy poszukiwać wśród funktorów zachowujących granice (dualnie: lewe funktory znajdują się wśród funktorów zachowujących kogranice).

Twierdzenie 10.3 [PZG, LZK]

Prawe sprzężenia zachowują granice (PZG). Dualnie: lewe sprzężenia zachowują kogranice (LZK).

Dowód

Niech $F⊣G$ będzie sprzężeniem między $\mathbf{𝐂}$ i $\mathbf{𝐃}$. Niech $C:\mathbf{𝐉}\to \mathbf{𝐃}$ będzie diagramem, który posiada w $\mathbf{𝐃}$ granicę $\underleftarrow{\lim }{D}_j$. Wówczas dla dowolnego obiektu $X\in {\mathbf{𝐂}}_0$ mamy: ${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(X,G(\underleftarrow{\lim }{D}_j))\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐃}}(FX,\underleftarrow{\lim }{D}_j)\cong \underleftarrow{\lim }{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐃}}(FX,D_j)\cong \underleftarrow{\lim }{\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(X,G{D}_j)\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(X,\underleftarrow{\lim }G{D}_j)$ (Wykorzystaliśmy fakt, że hom-funktory zachowują granice, patrz Zadanie 8.4.) Wszystkie powyższe izomorfizmy są naturalne, a zatem lemat Yonedy implikuje, że $G(\underleftarrow{\lim }{D}_j)=\underleftarrow{\lim }G{D}_j$. Dualnie, $LZK=PZG{}^{op}$.

Powyższy dowód również bardzo łatwo wyrazić elementarnie w języku stożków i granic, bez użycia lematu Yonedy, patrz Zadanie 10.3.

Okazuje się, że w wielu przypadkach warunek konieczny: zachowywanie granic przez funktor, wystarczy do tego, by istniało sprzężenie. Dobrym przykładem są tutaj kraty zupełne (kategoryjnie: częściowe porządki, w których istnieją wszystkie suprema, a co za tym idzie - wszystkie infima) - patrz Zadanie 10.4. W związku z tym, należy przypuszczać, że zachowywanie granic jest istotnym elementem warunku wystarczającego do istnienia sprzężenia. Tak jest w istocie. Poniższe twierdzenie pochodzi od prof. Petera Freyda.

Twierdzenie 10.4 [twierdzenie Freyda]

Niech $\mathbf{𝐂}$ będzie kategorią zupełną i lokalnie małą. Dla dowolnej kategorii $\mathbf{𝐗}$ i funktora $G:\mathbf{𝐂}\to \mathbf{𝐗}$ następujące warunki są równoważne:

• $G$ ma lewe sprzężenie;
• $G$ zachowuje granice oraz dla każdego obiektu $X\in \mathbf{𝐗}$ funktor $G$ spełnia następujący warunek: (Istnienie zbioru rozwiązań) Istnieje zbiór obiektów $\{C_i{\}}_{i\in I}$ w kategorii $\mathbf{𝐂}$ taki, że dla dowolnego obiektu $C\in \mathbf{𝐂}$ oraz strzałki $f:X\to GC$ istnieje $i\in I$ oraz strzałki $\varphi :X\to G{C}_i$, $\hat{f}:C_i\to C$ takie, że $f=G(\hat{f})\circ \varphi$.

Uwaga

• warunek istnienia zbioru rozwiązań mówi po prostu, że każda strzałka $X\to GC$ faktoryzuje się przez jakiś obiekt $C_i$ ze zbioru rozwiązań, jak na diagramie:

• Jeśli $\mathbf{𝐂}$ jest kategorią małą i zupełną, to jest preporządkiem - patrz Zadanie 8.2, a więc warunek istnienia zbioru rozwiązań można całkiem pominąć - Zadanie 10.4.

• Jeśli $\mathbf{𝐂}$ nie jest lokalnie mała, to twierdzenie Freyda nic nam nie mówi o istnieniu sprzężeń.

Dowód

Krok $1$: Szczególnie prostą postać warunku istnienia zbioru rozwiązań dla lokalnie małej i zupełnej kategorii $\mathbf{𝐂}$ można wyrazić następująco: istnieje zbiór obiektów $C_i$ taki, że dla dowolnego obiektu $C\in {\mathbf{𝐂}}_0$ istnieje strzałka $C_i\to C$ dla pewnego $i\in I$. Ten warunek jest równoważny istnieniu obiektu początkowego w kategorii $\mathbf{𝐂}$, co udowodnimy w Zadaniu 10.5. Krok $2$: Zaczynamy właściwy dowód twierdzenia: jeśli $G$ ma lewe sprzężenie $F$, to oczywiście $\{FX\}$ jest zbiorem rozwiązań dla $X$, ponieważ zawsze mamy:

dla jedności sprzężenia $\eta$ i obrazu $\hat{f}$ strzałki $f$ przez sprzężenie.

Odwrotnie, aby dla $G$ stworzyć lewe sprzężenie, rozważmy następującą kategorię $(X\mid G)$, której obiektami są pary $(C,f)$, gdzie $f:X\to GC$, zaś strzałkami $g:(C,f)\to (C^{\prime },f^{\prime })$ są strzałki $g:C\to C^{\prime }$ takie, że $f^{\prime }=G(g)f$:

Wtedy $G$ ma lewe sprzężenie wtedy i tylko wtedy, gdy dla każdego $X\in \mathbf{𝐂}$ kategoria $(X\mid G)$ ma obiekt początkowy $(FX,\eta :X\to GFX)$. Pozostaje zatem: Krok $3$: sprawdzimy, czy $(X\mid G)$ spełnia warunek zbioru rozwiązań Kroku $1$. Założenia twierdzenia implikują, że istnieje zbiór par $\{(C_i,\varphi :X\to G{C}_i)\mid i\in I\}$ taki, że dla dowolnego $i\in I$ istnieje strzałka $\hat{f}:(C_i,\varphi )\to (C_i,f)$ tak, że:

Ponieważ $(X\mid G)$ jest zarówno lokalnie mała (bo $\mathbf{𝐂}$ jest) i zupełna (z tego samego powodu), więc założenia Kroku $1$ implikują, że $(X\mid G)$ ma obiekt początkowy. To kończy dowód twierdzenia.

Problemem, który pozostaje do wyjaśnienia, jest jeszcze pytanie o to, w jakich okolicznościach istnienie zbioru rozwiązań jest automatycznie spełnione. Widzieliśmy bowiem, że w przypadku (pre)porządków zachowywanie granic było dla funktora równoważne istnieniu lewego sprzężenia. O tej szczególnej sytuacji mówi drugie twierdzenie Freyda, którego nie będziemy dowodzić. Drugie twierdzenie Freyda mówi pokrótce tyle, że warunek istnienia zbioru rozwiązań jest automatycznie spełniony, gdy $\mathbf{𝐂}$ (lokalnie mała i zupełna):

• posiada wystarczająco dużo obiektów potęgowych (ang. $\mathbf{𝐂}$ is well-powered) (nie wchodząc w szczegóły znaczy to, że dla każdego obiektu $C\in {\mathbf{𝐂}}_0$ kolekcja podobiektów $S\to C$ jest zbiorem;
• posiada zbiór kogeneratorów, tzn. zbiór obiektów $C_i$, które separują uogólnione elementy, tzn. dla każdych dwóch równoległych strzałek $f,g:X\to Y$ w $\mathbf{𝐂}$, jeśli $f\ne g$, to istnieje $s:Y\to C_i$ tak, że $sf\ne sg$.

W takiej kategorii $\mathbf{𝐂}$ - podkreślmy to raz jeszcze - funktor $\mathbf{𝐂}\to \mathbf{𝐃}$ zachowuje granicę wtedy i tylko wtedy, gdy posiada lewe sprzężenie $F:\mathbf{𝐃}\to \mathbf{𝐂}$.

Oto zaawansowany przykład sytuacji, gdy działa drugie twierdzenie Freyda: funktor zapominania $U:\mathbf{𝐂}\mathbf{𝐇}\mathbf{𝐚}\mathbf{𝐮}\mathbf{𝐬}\to \mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$ z kategorii zwartych przestrzeni Hausdorffa do kategorii przestrzeni topologicznych posiada lewe sprzężenie $\beta :\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}\to \mathbf{𝐂}\mathbf{𝐇}\mathbf{𝐚}\mathbf{𝐮}\mathbf{𝐬}$. Dla przestrzeni $X$, obiekt $\beta X$ jest znany jako uzwarcenie Cecha - Stone'a. Jednym ze sposobów tworzenia $\beta X$ jest podążanie krok w krok za dowodem twierdzenia Freyda, gdyż przestrzeń $X$ zanurza się najpierw w odpowiedni produkt kopii $[0,1]$, a potem bierze domknięcie obrazu zanurzenia, które jest szukanym uzwarceniem $\beta X$.

I na koniec ciekawy kontrprzykład: niech $\mathbf{𝐜}\mathbf{𝐁}\mathbf{𝐀}$ oznacza kategorię zupełnych algebr Boole'a (tj. takich algebr Boole'a, które są kratami zupełnymi). Funktor zapominania $U:\mathbf{𝐜}\mathbf{𝐁}\mathbf{𝐀}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ zachowuje wszystkie granice. Jednakże warunek istnienia zbioru rozwiązań nie jest spełniony ze względu na następujące twierdzenie:

Twierdzenie 10.5

Istnieje przeliczalnie generowana zupełna algebra Boole'a o dowolnie dużej mocy.

Wniosek: $U$ nie posiada lewego sprzężenia, co oznacza w szczególności, że nie istnieje wolna algebra Boole'a posiadająca ${\mathrm{\aleph }}_0$ generatorów.

Sprzężenia między częściowymi porządkami

Sprzężenia między częściowymi porządkami, których liczne przykłady poznaliśmy w Ćwiczeniach do Wykładu 9., mają bardzo przyjemne własności. Warto przyjrzeć się tej sytuacji lepiej i nieco na przekór trendowi naszego wykładu: chcemy bowiem zbadać, jak własności kategoryjne porządków przekładają się na język teorii mnogości, a nie odwrotnie. Powtórzmy konieczne definicje tak, aby ten rozdział można było czytać niezależnie od pozostałych. Zwróćmy też uwagę, że pary e-p, o których mówiliśmy w Wykładzie 2. są szczególnym przypadkiem sprzężeń między posetami.

Definicja 10.6 [sprzężenia na częściowych porządkach]

Niech $S,T$ będą częściowymi porządkami. Powiemy, że para funkcji $g:S\to T$ i $d:T\to S$ jest sprzężeniem, jeśli: obie funkcje są monotoniczne oraz dla każdej pary elementów $(s,t)\in S\times T$ mamy: $d(t)\le s⟺t\le g(s)$ Funkcję $d$ nazywamy lewym sprzężeniem, zaś funkcję $g$ - prawym sprzężeniem.

Fakt 10.7

Niech $g\circ S\to T$ i $d:T\to S$ będą funkcjami między częściowymi porządkami. Wówczas następujące warunki są równoważne:

• $d⊣g$;
• $g$ jest monotoniczna oraz $d(t)=\mathrm{m}\mathrm{i}\mathrm{n}\{g^{-1}(\uparrow t)\}$ dla każdego $t\in T$;
• $d$ jest monotoniczna oraz $g(s)=\mathrm{m}\mathrm{a}\mathrm{x}\{d^{-1}(\downarrow s)\}$ dla każdego $s\in S$.

W konsekwencji, każda z funkcji biorących udział w sprzężeniu determinuje drugą.

Z twierdzenia Freyda i Zadania 10.4 wynika natychmiast:

Fakt 10.8

• Niech $g:S\to T$ będzie funkcją między posetami, z których $S$ jest kratą zupełną. Wtedy $g$ zachowuje infima wtedy i tylko wtedy, gdy ma lewe sprzężenie.
• Niech $d:T\to S$ będzie funkcją między posetami, z których $T$ jest kratą zupełną. Wtedy $d$ zachowuje suprema wtedy i tylko wtedy, gdy ma prawe sprzężenie.

Zaobserwujmy doskonałą dualność powyższego sformułowania.

Twierdzenie 9.3 tłumaczy się na język częściowych porządków następująco (nieco je tu wzbogacamy); dowód znajdziemy w Zadaniu 10.7.

Fakt 10.9

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

• $d⊣g$;
• $dg\le 1_S$ oraz $1_T\ge gd$.

Każdy z tych warunków implikuje, że:

• $d=dgd$ oraz $g=gdg$;
• $gd$ i $dg$ są idempotentne (funkcja $p:X\to X$ jest idempotentna jeśli $pp=p$).

Na samym końcu scharakteryzujemy te sprzężenia, które są sekcjami (retrakcjami), by w ten sposób nawiązać do samych początków naszego spotkania z teorią kategorii, do Wykładu 2.

Fakt 10.10

Dla sprzężenia $d⊣g$ następujące warunki są równoważne:

• $g$ jest surjekcją;
• $d(t)=\mathrm{m}\mathrm{i}\mathrm{n}{g}^{-1}(t)$ dla każdego $t\in T$;
• $gd=1_T$;
• $d$ jest injekcją.

Dualnie, mamy następujące warunki równoważne:

• $g$ jest injekcją;
• $g(s)=\mathrm{m}\mathrm{a}\mathrm{x}{s}^{-1}(s)$ dla każdego $s\in S$;
• $dg=1_S$;
• $d$ jest surjekcją.