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

From Studia Informatyczne


Spis treści

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\colon \mathbf{C}\to\mathbf{D} i G\colon \mathbf{D}\to\mathbf{C} są równoważnością, to naturalny izomorfizm \theta\colon F\circ G\stackrel{\cong}{\to}1_{\mathbf{D}} daje dla każdej strzałki f\colon D\to D'\in \mathbf{D}_1 przemienny diagram:

Grafika:tk-10.1.png

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


G(f_1)=G(f_2)\Rightarrow \theta_{D}\circ (F\circ G)(f_1)\circ \theta^{-1}_{D'}= \theta_{D}\circ(F\circ G)(f_2)\circ \theta^{-1}_{D'} \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\colon G(D)\to G(D')\in \mathbf{C}_1. Połóżmy f = \theta_{D}\circ F(h)\circ \theta^{-1}_{D'}, co oznacza, że:

Grafika:tk-10.2K.png

komutuje. A zatem:

Fh=\theta_D^{-1}f\theta_D=\theta_D^{-1}\theta_{D}FG(f) \theta^{-1}_{D'}\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{D} są w bijekcji z morfizmami typu GFC\to GD w \mathbf{C}, 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\dashv G. Z symetrii założeń wynika G\dashv F. Udowodniliśmy następujące:


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

Jeśli F\colon \mathbf{C}\to\mathbf{D}, G\colon \mathbf{D}\to\mathbf{C} są równoważnością, to F\dashv G i G\dashv 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\dashv G dla F\colon \mathbf{C}\to\mathbf{D} i G\colon\mathbf{D}\to\mathbf{C}. Wówczas:
  • G jest wierny wtedy i tylko wtedy, gdy dla dowolnego Y\in \mathbf{D}_0 komponent kojedności \varepsilon_Y\colon FGY\to Y jest epimorfizmem w \mathbf{D}.
  • G jest pełny i wierny wtedy i tylko wtedy, gdy kojedność \varepsilon jest izomorfizmem.

Dowód

Zauważmy najpierw, że dowolny morfizm f\colon A\to A' w dowolnej kategorii lokalnie małej \mathbf{A} jest epimorfizmem (izomorfizmem) wtedy i tylko wtedy, gdy dla dowolnego B\in \mathbf{A}_0 funkcja \mathrm{Hom}_{\mathbf{A}}(f,B) jest injekcją (bijekcją) w \mathbf{Set}.

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

\mathrm{Hom}_{\mathbf{D}}(Y,Y') \stackrel{\mathrm{Hom}(\varepsilon_Y,Y')}{\longrightarrow}\mathrm{Hom}_{\mathbf{D}}(FGY,Y')  \stackrel{\cong}{\longrightarrow}\mathrm{Hom}_{\mathbf{C}}(GY,GY')
g\mapsto g\circ \varepsilon_Y\mapsto G(g\circ \varepsilon_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{Hom}(\varepsilon_Y,Y') jest injekcją (bijekcją), co zgodnie z uwagą na początku dowodu jest równoważne warunkowi, że \varepsilon_Y dla dowolnego Y jest epimorfizmem (izomorfizmem). To kończy dowód (prowadzony równolegle dla obu własności). image:End_of_proof.gif

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\dashv G będzie sprzężeniem między \mathbf{C} i \mathbf{D}. Niech C\colon \mathbf{J}\to\mathbf{D} będzie diagramem, który posiada w \mathbf{D} granicę \lim_{\leftarrow}D_j. Wówczas dla dowolnego obiektu X\in\mathbf{C}_0 mamy:
\mathrm{Hom}_{\mathbf{C}}(X,G(\lim_{\leftarrow}D_j))\cong \mathrm{Hom}_{\mathbf{D}}(FX,\lim_{\leftarrow}D_j)\cong \lim_{\leftarrow}\mathrm{Hom}_{\mathbf{D}}(FX,D_j) \cong   \lim_{\leftarrow}\mathrm{Hom}_{\mathbf{C}}(X,GD_j) \cong \mathrm{Hom}_{\mathbf{C}}(X,\lim_{\leftarrow}GD_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(\lim_{\leftarrow}D_j) = \lim_{\leftarrow}GD_j. Dualnie, LZK = PZG{}^{op}. image:End_of_proof.gif

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{C} będzie kategorią zupełną i lokalnie małą. Dla dowolnej kategorii \mathbf{X} i funktora G\colon \mathbf{C}\to\mathbf{X} następujące warunki są równoważne:
  • G ma lewe sprzężenie;
  • G zachowuje granice oraz dla każdego obiektu X\in\mathbf{X} 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{C} taki, że dla dowolnego obiektu C\in \mathbf{C} oraz strzałki f\colon X\to GC istnieje i\in I oraz strzałki \phi\colon X\to GC_i, \hat{f}\colon C_i\to C takie, że f=G(\hat{f})\circ \phi.


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:
Grafika:tk-10.5.png
  • Jeśli \mathbf{C} 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{C} 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{C} można wyrazić następująco: istnieje zbiór obiektów C_i taki, że dla dowolnego obiektu C\in \mathbf{C}_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{C}, 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:
Grafika:tk-10.8.png

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\colon X\to GC, zaś strzałkami g\colon (C,f)\to (C',f') są strzałki g\colon C\to C' takie, że f'=G(g)f:

Grafika:tk-10.9.png

Wtedy G ma lewe sprzężenie wtedy i tylko wtedy, gdy dla każdego X\in \mathbf{C} kategoria (X\mid G) ma obiekt początkowy (FX,\eta\colon 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, \phi\colon X\to GC_i)\mid i\in I\} taki, że dla dowolnego i\in I istnieje strzałka \hat{f}\colon (C_i,\phi)\to (C_i,f) tak, że:

Grafika:tk-10.5.png
Ponieważ (X\mid G) jest zarówno lokalnie mała (bo \mathbf{C} 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. image:End_of_proof.gif


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{C} (lokalnie mała i zupełna):

  • posiada wystarczająco dużo obiektów potęgowych (ang. \mathbf{C} is well-powered) (nie wchodząc w szczegóły znaczy to, że dla każdego obiektu C\in\mathbf{C}_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\colon X\to Y w \mathbf{C}, jeśli f\neq g, to istnieje s\colon Y\to C_i tak, że sf\neq sg.

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

Oto zaawansowany przykład sytuacji, gdy działa drugie twierdzenie Freyda: funktor zapominania U\colon \mathbf{CHaus}\to \mathbf{Top} z kategorii zwartych przestrzeni Hausdorffa do kategorii przestrzeni topologicznych posiada lewe sprzężenie \beta\colon \mathbf{Top}\to \mathbf{CHaus}. 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{cBA} oznacza kategorię zupełnych algebr Boole'a (tj. takich algebr Boole'a, które są kratami zupełnymi). Funktor zapominania U\colon \mathbf{cBA}\to \mathbf{Set} 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 \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\colon S\to T i d\colon 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)\leq s\iff t\leq 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\colon T\to S będą funkcjami między częściowymi porządkami. Wówczas następujące warunki są równoważne:
  • d\dashv g;
  • g jest monotoniczna oraz d(t) = \mathrm{min}\{ g^{-1}(\uparrow t)\} dla każdego t\in T;
  • d jest monotoniczna oraz g(s) = \mathrm{max}\{ 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\colon 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\colon 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\dashv g;
  • dg\leq 1_S oraz 1_T\geq gd.

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

  • d=dgd oraz g=gdg;
  • gd i dg są idempotentne (funkcja p\colon 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\dashv g następujące warunki są równoważne:
  • g jest surjekcją;
  • d(t)=\mathrm{min} 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{max} s^{-1}(s) dla każdego s\in S;
  • dg=1_S;
  • d jest surjekcją.