Teoria kategorii dla informatyków/Wykład 9: Sprzężenia I

Pojęcie sprzężenia jest jednym z najważniejszych w kursie teorii kategorii. Sprzężenie jest pewną prostą zależnością pomiędzy dwoma przeciwnie zwróconymi funktorami, która, jak się okazuje, występuje niezwykle często w matematyce.

Definicja 9.1 [sprzężenie I]

Dwa funktory $F\colon \mathbf {X} \to \mathbf {A}$ i $G\colon \mathbf {A} \to \mathbf {X}$

tworzą sprzężenie, jeśli dla dowolnej pary obiektów $X\in \mathbf {X} _{0},A\in \mathbf {A} _{0}$ istnieje naturalna bijekcja:

$\phi _{X,A}\colon \mathbf {X} (FX,A)\cong \mathbf {A} (X,GA).$

W takim wypadku $F$ nazywamy lewym sprzężeniem, $G$ nazywamy prawym sprzężeniem i całą sytuację opisujemy krótko jako:

$F\dashv G.$

Taka definicja wyjaśnia dobrze ideę sprzężenia, ale szczegóły trzeba rozszyfrować: naturalność bijekcji $\phi _{X,A}$ oznacza, że $\phi$ jest naturalnym izomorfizmem pomiędzy pewnymi funktorami (dociekliwym należy się wyjaśnienie, że oba te funktory są typu $\mathbf {X} ^{op}\times \mathbf {A} \to \mathbf {Set}$), a naturalność $\phi$, pomijając nieciekawe przekształcenia techniczne, sprowadza się ni mniej, ni więcej do faktu, że poniższe dwa diagramy komutują dla dowolnych morfizmów $k\colon A\to A'\in \mathbf {A} _{1}$ i $h\colon X\to X'\in \mathbf {X} _{1}$:

Równoważnie do Definicji 9.1 powiemy więc, że:

Definicja 9.2

Dwa funktory $F\colon \mathbf {X} \to \mathbf {A}$ i $G\colon \mathbf {A} \to \mathbf {X}$ tworzą sprzężenie, jeśli dla dowolnej pary obiektów $X\in \mathbf {X} _{0},A\in \mathbf {A} _{0}$ istnieje naturalna bijekcja (piszmy niepoprawnie $\phi$ zamiast uciążliwego $\phi _{X,A}$), która dowolnej strzałce $f\colon FX\to A$ przypisuje strzałkę $\phi (f)\colon X\to GA$ tak, że $\phi (k\circ f)=G(k)\circ \phi (f)$ oraz $\phi (f\circ F(h))=\phi (f)\circ h$ dla dowolnych strzałek $k\colon A\to A'$ i $h\colon X\to X'$.

Wkrótce wykażemy, że jeśli funktor $G$ ma lewe sprzężenie $F$ (tzn. istnieje funktor $F$ taki, że $F\dashv G$), to $F$ jest jedyny z dokładnością do izomorfizmu (tzn. $(F\dashv G\wedge H\dashv G)\Rightarrow F\cong H$). Istnienie lewego lub prawego sprzężenia jest często ciekawym problemem matematycznym i jeśli da się udowodnić, sam dowód jest pożyteczną konstrukcją. Nie ma potrzeby dłużej strzępić języka, zobaczmy przykłady.

• Wolne funktory są lewymi sprzężeniami do funktorów zapominania. Np. jeśli $G$ jest grupą, zaś $X$ jest zbiorem, to funkcje $X\to G$ są w bijekcji z homomorfizmami typu $F(X)\to G$, gdzie $F(X)$ jest wolną grupą nad $X$. A zatem $F\dashv U$, gdzie $U\colon \mathbf {Grp} \to \mathbf {Set}$ jest funktorem zapominania, zaś $F\colon \mathbf {Set} \to \mathbf {Grp}$ jest funktorem tworzącym wolną grupę nad $X$. Inny przykład tego typu znajduje się w Zadaniu 9.1.

Uwaga

Problem istnienia lewego sprzężenia do funktora zapominania $U\colon \mathbf {C} \to \mathbf {D}$ jest w zasadzie pytaniem o to, jak w sposób jednorodny zadać strukturę wymaganą przez $\mathbf {C}$ na obiektach i strzałkach $\mathbf {D}$. Pytania o lewe sprzężenie są więc pytaniami typu: w jaki sposób na dowolnym zbiorze zadać topologię? Czy dla dowolnego zbioru da się znaleźć działanie grupowe tak, by elementy tego zbioru były elementami powstałej grupy? Czy każda przestrzeń metryczna da się rozszerzyć do przestrzeni zupełnej? I tak dalej. Niezwykle interesującą klasą kategorii, które posiadają lewe sprzężenie do funktora zapominania z kodziedziną w $\mathbf {Set}$ są tzw. kategorie algebraiczne. Mówimy o nich więcej w Wykładzie 15.

• Przypuśćmy, że $\mathbf {C}$ jest kategorią kartezjańsko zamkniętą. Niech $X\in \mathbf {C} _{0}$. Wówczas funktor:

$[X,-]\colon \mathbf {C} \to \mathbf {C}$

jest lewym sprzężeniem funktora $-\times X\colon \mathbf {C} \to \mathbf {C}$ (przypomnijmy sobie definicje pierwszego z tych funktorów podaną w Zadaniu 4.1 - definicja drugiego jest oczywista po przeczytaniu Zadania 3.6), co oznacza, że istnieje naturalna bijekcja pomiędzy morfizmami typu $Z\times X\to Y$ i morfizmami typu $Z\to [X,Y]$ (dla $Y,Z\in \mathbf {C} _{0}$).

• Jeśli $\mathbf {J} ,\mathbf {C}$ są dowolnymi kategoriami, to funktor diagonalny $\Delta \colon \mathbf {C} \to [\mathbf {J} ,\mathbf {C} ]$ jest lewym sprzężeniem do funktora $\lim _{\leftarrow \mathbf {J} }\colon [\mathbf {J} ,\mathbf {C} ]\to \mathbf {C}$. Rzeczywiście, wprost z Zadania 8.1, obiekt $X\in \mathbf {C} _{0}$ jest granicą diagramu $D\colon J\to \mathbf {C}$ wtedy i tylko wtedy, gdy istnieje naturalny izomorfizm:

$[J,\mathbf {C} ](\Delta X,D)\cong \mathrm {cone} _{\mathbf {C} }(X,D)\cong \mathbf {C} (X,\lim _{\leftarrow \mathbf {J} }D).$

A zatem $\Delta \dashv \lim _{\leftarrow \mathbf {J} }$. Szczególne przypadki tego sprzężenia omówimy w Zadaniach 9.2, 9.3.

• Dla posetów $P,Q$ para funkcji monotonicznych $r\colon P\to Q$, $s\colon Q\to P$ jest sprzężeniem wtedy i tylko wtedy, gdy

$\forall x\in P\ \forall y\in Q\ (x\leq s(y)\iff r(x)\leq y).$

Na przykład, inkluzja $U\colon (\mathbb {Z} ,\leq )\to (\mathbb {R} ,\leq )$ posiada lewe sprzężenie, które powszechnie nazywa się funkcją sufit $\lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z}$}:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil x\rceil := \mathrm{najmniejsza\ liczba\ całkowita} \geq x.}

Rzeczywiście, równoważność definiująca sprzężenie:

$x\leq U(y)\iff \lceil x\rceil \leq y$

zachodzi wtedy i tylko wtedy, gdy $\lceil x\rceil$ jest najmniejszą liczbą całkowitą większą bądź równą $x$.

• Dualność Stone'a (patrz Ćwiczenia do Wykładu 6.). Twierdzenie Stone'a jest jednym z najważniejszych wyników matematyki XX wieku. W ograniczonym brzmieniu (tj. dualność między algebrami Boole'a a przestrzeniami Stone'a) udowodnione przez Marshalla Stone'a w 1939 roku, twierdzenie to po raz pierwszy jednoznacznie potwierdziło użyteczność metod topologii ogólnej w algebrze i dało początek topologii algebraicznej. Wspaniałe omówienie roli dualności Stone'a znajduje się w książce Stone Spaces P.T.Johnstone'a (Cambridge University Press, 1982).

Wracając do głównego wątku wykładu, zanalizujmy głębiej strukturę sprzężenia. Przy ustalonych oznaczeniach z Definicji 9.2 (pominiemy też wszelkie zbędne nawiasy) zauważmy, że jeśli przyjmiemy $A=F(X)$, to $1_{X}\in \mathbf {A} (FX,FX)$. Możemy więc położyć dla każdego $X\in \mathbf {X}$ morfizm typu $X\to GFX$:

$\eta _{X}:=\phi (1_{FX}).$

Sama operacja $\eta$, która obiektowi $X$ przypisuje strzałkę $\eta _{X}$ jest transformacją naturalną typu $1_{\mathbf {X} }\to GF$, ponieważ każdy diagram:

komutuje. Rzeczywiście,

$GFh\circ \eta _{X}=GFh\circ \phi (1_{FX})=\phi (Fh\circ 1_{FX})=\phi (1_{FX'}\circ Fh)=\phi (1_{FX'})\circ h=\eta _{X'}\circ h,$

gdzie dwukrotnie wykorzystaliśmy naturalność $\phi$. Transformację $\eta$ nazywamy jednością sprzężenia $F\dashv G$.

Pokażemy teraz, że bijekcja $\phi$ może być całkowicie odtworzona za pomocą $\eta$, to znaczy, że kolekcja komponentów $\{\eta _{X}\}_{X\in \mathbf {X} }$ wystarcza do zrekonstruowania bijekcji $\phi$. Niech $f\colon FX\to A$. Wówczas $\phi _{X,A}(f)=\phi (f\circ 1_{FX})=Gf\circ \phi (1_{FX})=Gf\circ \eta _{X}$. Warto zapamiętać:

$\phi _{X,A}(f)=Gf\circ \eta _{X}.$      (9.1)

Dualnie, jeśli przyjmiemy w Definicji 9.2, że $X=GA$, to możemy zdefiniować dla każdego $A\in \mathbf {A}$ strzałkę $\varepsilon _{A}\colon FGA\to A$:

$\varepsilon _{A}:=\phi ^{-1}(1_{GA}).$

Transformację naturalną $\varepsilon$ nazywamy kojednością sprzężenia $F\dashv G$. Mając na uwadze, że $\phi ^{-1}(g\circ h)=\phi ^{-1}(g)\circ Fh$ oraz $\phi ^{-1}(Gk\circ g)=k\circ \phi ^{-1}(g)$ dla dowolnej $g\circ X\to GA$ mamy:

$\phi ^{-1}(g):=\varepsilon _{A}\circ Fg,$      (9.2)

co oznacza, że kojedność wystarcza do odtworzenia $\phi ^{-1}$, a co za tym idzie, $\phi$.

W końcu, zauważmy, że:

$G(\varepsilon _{A})\circ \eta _{GA}=\phi (\varepsilon _{A}\circ \eta _{FGA})=\phi (\varepsilon _{A})=\phi (\phi ^{-1}(1_{GA}))=1_{GA}$

i podobnie:

$\varepsilon _{FX}\circ F(\eta _{X})=\phi ^{-1}(\eta _{X})=\phi ^{-1}(\phi (1_{FX}))=1_{FX}.$

Pokazaliśmy najważniejsze kroki następującego twierdzenia:

Twierdzenie 9.3

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

• $F\dashv G$,
• Istnieją dwie transformacje naturalne $\eta \colon 1_{\mathbf {X} }\to GF$ i $\varepsilon \colon FG\to 1_{\mathbf {A} }$ takie, że następujące diagramy trójkątne komutują:

Uwaga

aby w pełni zrozumieć treść powyższego twierdzenia, należy zauważyć, że transformacje naturalne można złożyć z funktorami (i to na dwa sposoby). Na przykład, $\eta G$ jest transformacją naturalną będącą złożeniem transformacji $\eta$ i funktora $G$. To złożenie definiujemy przez komponenty jako $(\eta G)_{A}:=\eta _{GA}$; podobnie $G\eta$ jest transformacją naturalną daną przez komponenty $(G\eta )_{A}:=G(\eta _{A})$. I tak dalej. Uważny czytelnik powinien udowodnić, że złożenia, które tu opisujemy są rzeczywiście transformacjami naturalnymi.

Przejdźmy do ostatniej charakteryzacji sprzężenia, które uwypukla uniwersalny charakter jedności sprzężenia. Przypomnijmy sobie definicję elementu uniwersalnego dla funktora reprezentowalnego $F\colon \mathbf {C} ^{op}\to \mathbf {Set}$ (Definicja 7.4): element $e\in F$ jest uniwersalny jeśli dla każdego obiektu $Y\in \mathbf {C} _{0}$ i elementu $y\in FY$ istnieje dokładnie jedna funkcja $f\colon Y\to X$ taka, że $F(f)(e)=y$. Ale $e$ może być traktowany jako strzałka $\mathbf {1} \to FX$ w $\mathbf {Set}$ ($\mathbf {1}$ jest dowolnym singletonem - obiektem końcowym $\mathbf {Set}$), Definicja elementu uniwersalnego może być więc uogólniona i postawiona dla funktorów dowolnego typu:

Definicja 9.4

Niech $F\colon \mathbf {D} \to \mathbf {C}$ będzie funktorem i niech $C\in \mathbf {C} _{0}$. Strzałką uniwersalną z $C$ do $F$ jest para $(X,e)$ składająca się z obiektu $X\in \mathbf {C} _{0}$ i strzałki $e\colon C\to FX\in \mathbf {C} _{1}$ taka, że dla dowolnego obiektu $Y\in \mathbf {C} _{0}$ i strzałki $y\colon C\to FX$ istnieje dokładnie jedna strzałka $f\colon X\to Y$ spełniająca $Ff\circ e=y$.

Innymi słowy: każda strzałka $y$ faktoryzuje się przez $e$.

Jak się okazuje, sprzężenie jest w pełni scharakteryzowane przez fakt, że jedność $\eta _{X}$ jest strzałką uniwersalną z $X$ do $G$ (przy oznaczeniach Definicji 9.2).

Twierdzenie 9.5

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

• $F\dashv G$
• $\eta \colon 1_{\mathbf {X} }\to GF$ jest transformacją naturalną taką, że dla każdego $X\in \mathbf {C} _{0}$, $\eta _{X}$ jest strzałką uniwersalną z $X$ do $G$.

Dowód

Strzałka $\eta _{X}$ jest uniwersalna wtedy i tylko wtedy, gdy dla dowolnego morfizmu $f\colon X\to GA$ istnieje dokładnie jeden morfizm $g\colon FX\to A$ tak, że następujący diagram komutuje: Ale to oznacza, że $\theta (g):=Gg\circ \eta _{X}$ jest bijekcją pomiędzy $\mathbf {A} (FX,A)$ i $\mathbf {X} (X,GA)$. Ta bijekcja jest naturalna względem $X$, bo $\eta$ jest naturalna; jest naturalna względem $A$, bo $G$ jest funktorem. To dowodzi $F\dashv G$.

Uwaga: Powyższe twierdzenie jest jednym z najpopularniejszych sposobów prezentowania sprzężenia. Śmiało możemy więc ująć je jako definicję:

Definicja 9.6 [Sprzężenie II]

Dla $F\colon \mathbf {X} \to \mathbf {A}$ i $G\colon \mathbf {A} \to \mathbf {X}$ mamy $F\dashv G$ wtedy tylko wtedy, gdy dla każdego $X\in \mathbf {X} _{0}$ istnieje strzałka $\eta _{X}\colon X\to GFX$ taka, że: dla dowolnego morfizmu $f\colon X\to GA$ istnieje dokładnie jeden morfizm $g\colon FX\to A$ tak, że następujący diagram komutuje:

Oto dalsze przykłady sprzężeń:

• Funktor $\mathrm {List} \colon \mathbf {Set} \to \mathbf {Mon}$ (patrz Przykład 5.3) jest lewym sprzężeniem do funktora zapominania $U\colon \mathbf {Mon} \to \mathbf {Set}$ (bo $\mathrm {List}$ jest funktorem wolnym). Dla zbioru $X$ jedność sprzężenia $\eta _{X}\colon X\to \mathrm {List} (X)$ jest funkcją $x\mapsto [x]$, czyli przekształca elementy $X$ na listy jednoelementowe. W tym przykładzie, dla funkcji $f\colon X\to \mathbb {N}$, $f(x):=1$ jedyną funkcją (oznaczoną $l$), która sprawia, że diagram:

komutuje, jest funkcja przypisująca liście jej długość.

• Niech $\mathbf {Met}$ oznacza kategorię przestrzeni metrycznych i funkcji niepowiększających odległości, zaś $\mathbf {CMet}$ - kategorię przestrzeni metrycznych zupełnych, z takimi samymi morfizmami. Wówczas dla funktora zapominania $U\colon \mathbf {CMet} \to \mathbf {Met}$ istnieje lewe sprzężenie, które każdej przestrzeni metrycznej przypisuje jej uzupełnienie. Jednością tego sprzężenia jest rodzina odwzorowań, które elementowi $x$ przestrzeni metrycznej $X$ przypisują stały ciąg Cauchy'ego $(x,x,x,...)$.

W Ćwiczeniach do tego wykładu omówimy szczegółowo zarówno przykłady, które już się pojawiły, jak i całkiem nowe, często być może zaskakujące Czytelnika sytuacje, których ukrytym mechanizmem jest sprzężenie.