Teoria kategorii dla informatyków/Wykład 6: Równoważność kategorii

From Studia Informatyczne

W trakcie naszych wykładów stało się jasne, że równość obiektów w danej kategorii jest własnością bez znaczenia - najważniejsze pojęcia zostały zdefiniowane z dokładnością do izomorfizmu. W szczególnym przypadku przypomnijmy, że dwie kategorie \mathbf{C} i \mathbf{D} są izomorficzne, jeśli istnieją funktory F\colon \mathbf{C}\to\mathbf{D} i G\colon \mathbf{D}\to \mathbf{C} takie, że F\circ G = 1_{\mathbf{D}} i G\circ F = 1_{\mathbf{C}}. Te dwie równości zgodnie z naszym dezyderatem: równość jest własnością bez znaczenia, po zastąpieniu przez izomorfizmy dają następującą ważną definicję:


Definicja równoważności i podstawowe własności

Definicja 6.1 [kategorie równoważne]

Mówimy, że dwie kategorie \mathbf{C} i \mathbf{D} są równoważne, jeśli istnieją funktory F\colon \mathbf{C}\to\mathbf{D} i G\colon \mathbf{D}\to \mathbf{C} takie, że F\circ G \cong 1_{\mathbf{D}} i G\circ F \cong 1_{\mathbf{C}}.


Równoważność \mathbf{C} i \mathbf{D} oznacza zatem, że istnieją dwie transformacje naturalne \mu\colon 1_{\mathbf{C}}\to G\circ F i \nu\colon 1_{\mathbf{D}}\to F\circ G, których komponentami są izomorfizmy.

Oto prosty przykład równoważności: niech (P,\preceq) będzie preporządkiem, zaś Q=P/\equiv porządkiem ilorazowym utworzonym z P przez podzielenie przez relację równoważności x\equiv y\iff (x\preceq y \wedge y\preceq x) dla x,y\in P i \pi\colon P\to Q niech będzie funkcją ilorazową. Wówczas \pi jest funktorem ustanawiającym równoważność P i Q, ale w ogólności nie jest to izomorfizm.


Definicja 6.2 [kategorie dualne]

Równoważność między kategoriami \mathbf{C}^{op} i \mathbf{D} (lub: \mathbf{C} i \mathbf{D}^{op}) nazywamy dualnością.


Przykładem jest tutaj dualność Stone'a, której poświęcamy Ćwiczenia do tego wykładu.

Czasami sam funktor, który bierze udział w równoważności nazywamy równoważnością. Poczyńmy kilka prostych obserwacji: jeśli F\colon \mathbf{C}\to\mathbf{D} jest równoważnością, to istnieje G\colon \mathbf{D}\to \mathbf{C} taki, że F\circ G\cong 1_{\mathbf{D}} i G\circ F\cong 1_{\mathbf{C}}, a zatem G jest również równoważnością. Równie łatwo pokazać, że złożenie dwóch równoważności jest równoważnością.

Poznajmy teraz podstawową własność równoważności:


Twierdzenie 6.3 [Własności równoważności]

Następujące dwa warunki są równoważne dla funktora F\colon \mathbf{C}\to \mathbf{D}:
  • F jest równoważnością;
  • F jest pełny i wierny oraz gęsty ze względu na izomorfizmy (tzn. dla dowolnego D\in \mathbf{D}_0 istnieje C\in \mathbf{C}_0 taki, że FC\cong D).

Dowód

Załóżmy najpierw, że F jest równoważnością. Istnieją zatem: funktor G\colon \mathbf{D}\to \mathbf{C} oraz naturalne izomorfizmy \mu\colon 1_{\mathbf{C}}\to GF i \nu\colon 1_{\mathbf{D}}\to FG wraz ze swoimi odwrotnościami \mu^{-1}\colon GF\to 1_{\mathbf{C}} i \nu^{-1}\colon FG\to 1_{\mathbf{D}}.

Pokażmy najpierw, że F jest funktorem wiernym. Niech f,g\in \mathbf{C}_1 i Ff=Fg. A zatem GFf=GFg. Z naturalności \mu wynika, że f=\mu^{-1}_{cod(f)}\circ GFf\circ \mu_{dom(f)}, a więc:

f=\mu^{-1}_{cod(f)}\circ GFf\circ \mu_{dom(f)}=\mu^{-1}_{cod(g)}\circ GFg\circ \mu_{dom(g)}=g.

Symetryczny dowód pokazuje, że również G jest funktorem wiernym - ten fakt przyda się nam za chwilę.

Pokażmy pełność F. Niech h\colon F(C)\to F(C') będzie morfizmem w \mathbf{D}. Zdefiniujmy morfizm f\colon C\to C' w \mathbf{C} jako: f := \mu^{-1}_{C'}\circ Gh\circ \mu_{C}. Wtedy Ff jest tego samego typu co h oraz:

GFf = \mu_{C'}\circ f\circ\mu_{C}^{-1}=\mu_{C'}\circ (\mu^{-1}_{C'}\circ Gh\circ \mu_{C})\circ \mu_{C}^{-1}=Gh.

Ponieważ G jest wierny, Ff=h, co dowodzi pełności F.

W końcu dla dowolnego D\in \mathbf{D}_0 izmorfizm \nu daje natychmiast D\cong GFD, gdzie FD\in \mathbf{C}_0, co dowodzi, że F jest gęsty ze względu na izomorfizmy.

Odwrotnie, załóżmy, że pewien funktor F\colon \mathbf{C}\to \mathbf{D} posiada wszystkie cechy drugiego punktu twierdzenia. Wykażemy, że jest równoważnością. To zadanie polega na skonstruowaniu funktora G\colon \mathbf{D}\to \mathbf{C} i dwóch naturalnych izomorfizmów, tak jak wymaga tego od nas definicja równoważności. Skoro F jest gęsty ze względu na izomorfizmy, dla każdego obiektu D\in \mathbf{D}_0 otrzymujemy C_D\in \mathbf{C}_0 taki, że FC\cong D. Ta informacja wystarcza, by skonstruować funktor G\colon \mathbf{D}\to \mathbf{C} na obiektach: G(D):= C_D. Izomorfizm FC\stackrel{\cong}{to}D oznaczymy jako \nu_D. Strzałki \nu_D tworzą komponenty pewnego izomorfizmu, który - jak zaraz wykażemy - jest naturalny. Mając dany morfizm h\colon D\to D' w \mathbf{D}, rozważmy diagram:

Grafika:tk-6.1.png

Ale skoro F jest pełny i wierny, możemy znaleźć dla h dokładnie jedną strzałkę G(h)\colon GD\to GD' taką, że FGh = {\nu_{D'}\circ h\circ \nu_{D}^{-1}}. Tak zdefiniowany G na strzałkach jest funktorem, a \nu jest naturalnym izomorfizmem.

Pozostaje nam znalezienie \mu, najłatwiej przez zaproponowanie komponentów \mu_C dla C\in \mathbf{C}_0. Przyjmiemy jako \mu_C jedyną strzałkę, która jest w przeciwobrazie przez F (możemy mówić o przeciwobrazie, bo F jest pełny i wierny) strzałki \nu_{FC}\colon FC\to FGFC. Oczywiście \mu_C jest izomorfizmem, bo pełne i wierne funktory odzwierciedlają izomorfizmy. Naturalność \mu wynika wprost z naturalności \nu.

image:End_of_proof.gif


Przykłady równoważności

  • Każdy izomorfizm między kategoriami jest równoważnością, tzn. kategorie izomorficzne są równoważne.
  • Częściowe porządki są równoważne wtedy i tylko wtedy, gdy są izomorficzne (bo izomorfizmy na przestrzeni funkcji monotonicznych redukują się do równości). Z drugiej strony, preporządki, jak już widzieliśmy powyżej mogą być równoważne i nie być izomorficzne.
  • Wiemy z teorii mnogości, że każdy zbiór skończony X jest izomorficzny ze swoją liczbą kardynalną, |X|, która jest liczbą jego elementów. Oznaczmy ten izomorfizm jako \alpha_X. Mając dwa dowolne zbiory skończone i funkcję f\colon X\to Y, definiujemy |f|\colon |X|\to|Y| jako |f|:=\alpha_Y\circ f\circ \alpha_X^{-1}. Oczywiście wtedy |\cdot|\colon \mathbf{Set}_{fin}\to \mathbf{Card}_{fin} jest funktorem. Z drugiej strony niech I\colon \mathbf{Card}_{fin}\to\mathbf{Set}_{fin} oznacza naturalną inkluzję skończonych liczb kardynalnych w skończone zbiory (istnienie I wyraża fakt, że każda liczba kardynalna sama jest zbiorem). Złożenie I\circ |\cdot | jest funktorem na \mathbf{Set}_{fin}. Jest on izomorficzny z identycznością 1_{\mathbf{Set}_{fin}}, ponieważ istnieje naturalny izomorfizm \beta\colon 1_{\mathbf{Set}_{fin}}\to I\circ |\cdot | dany przez komponenty jako \beta_Z(z\in Z) := \alpha_Z(z). Z drugiej strony, |I(-)|=1_{\mathbf{Card}_{fin}}, a zatem kategorie \mathbf{Set}_{fin} i \mathbf{Card}_{fin} są równoważne. Oczywiście nie są izomorficzne, bo istnienie takiego izomorfizmu pociągnęłoby za sobą istnienie bijekcji pomiędzy zbiorami skończonymi i liczbami naturalnymi, a ta - jak wiemy - nie istnieje.
  • Niech \mathbf{PPos} będzie kategorią częściowych porządków i częściowych funkcji monotonicznych. Przypomnijmy, że funkcja f\colon P\to Q jest częściowa, jeśli jest określona tylko na (być może właściwym) podzbiorze swojej dziedziny, D_f\subseteq P. Na zbiorze P\setminus D_f funkcja f pozostaje nieokreślona. Funkcję częściową f z P do Q będziemy dalej oznaczać jako f\subseteq\colon P\to Q. Te spośród funkcji częściowych, które są określone na całej swojej dziedzinie nazywamy funkcjami totalnymi. Oczywiście \mathbf{PPos} jest kategorią, w której złożenie f\subseteq \colon P\to Q i g\subseteq\colon Q\to R definiujemy jako funkcję częściową oznaczaną g\circ f\subseteq\colon P\to R zdefiniowaną na D_{g\circ f}:= f^{-1}[D_g]. Czytelnik zechce sprawdzić, że to złożenie jest łączne i że identyczności spełniają względem złożenia swoje aksjomaty.

Drugą kategorią w tym przykładzie jest \mathbf{Pos}_{\bot}, czyli kategoria częściowych porządków posiadających elementy najmniejsze wraz z funkcjami monotonicznymi zachowującymi elementy najmniejsze. Udowodnimy, że \mathbf{PPos} i \mathbf{Pos}_{\bot} są kategoriami równoważnymi.

Funktor F\colon \mathbf{PPos}\to \mathbf{Pos}_{\bot} definiujemy na obiektach jako dodatnie do posetu nowego elementu najmniejszego:

F((P,\leq)):= (P\cup\{\bot_P \}, \leq\cup\{(\bot_P,x)\mid x\in P\}).

Dla prostoty oznaczymy F jako (-)_{\bot}, tzn. F(P)=P_{\bot}. Na strzałkach ten funktor działa jako:

f\subseteq\colon P\to Q\ \mapsto\ f_{\bot}\colon P_{\bot}\to Q_{\bot},

gdzie:

f_{\bot}(x) := \begin{cases} f(x),& x\in D_f\\ \bot,& \text{wpp} \end{cases}.

Oczywiście f_{\bot}(\bot_P)=\bot_{Q}, więc definicja funktora jest poprawnie postawiona.

Funktor przeciwnie zwrócony G\colon \mathbf{Pos}_{\bot}\to \mathbf{PPos} definiujemy na obiektach odejmując element najmniejszy:

G(P_{\bot}):= P_{\bot}\setminus\{\bot_P\},

zaś na strzałkach: dla f\colon P_{\bot}\to Q_{\bot}

G(f)\subseteq P\setminus \{\bot_P\}\to Q\setminus \{ \bot_Q\}

jest funkcją częściową zdefiniowaną na podzbiorze zbioru P

D_{G(f)}:= P\setminus f^{-1}[\{\bot_Q\}].


Przy tych definicjach F\circ G jest identycznością na \mathbf{PPos}. Tymczasem G\circ F jest jedynie naturalnie izomorficzny z 1_{\mathbf{Pos}_{\bot}}, gdyż:

P_{\bot}\cong (P_{\bot}\setminus \{\bot_P\})\cup \{\bot'_{P}\}

(w ogólności \bot_P\neq \bot'_{P}). Sprawdzenie faktu, że ten izomorfizm jest naturalny i F, G są funktorami jest łatwym ćwiczeniem dla Czytelnika, które polecamy wykonać w pamięci.

  • Kategoria przestrzeni metrycznych i funkcji ciągłych jest równoważna kategorii przestrzeni topologicznych metryzowalnych i funkcji ciągłych. Te dwie kategorie nie są jednak izmomorficzne (nieformalnie wynika to z faktu, że dana topologia na zbiorze może pochodzić od wielu różnych metryk równoważnych).
  • \mathbf{Set}^{op} jest równoważna z kategorią zupełnych atomowych algebr Boole'a (dla dociekliwych: \mathbf{Set}^{op} i zupełne algebry Boole'a są zaledwie sprzężone: \mathbf{Set}^{op}\dashv \mathbf{cBA}). Ten przykład i następny podrozdział są szczególnymi przypadkami całej serii tzw. dualności Stone'a, które określają równoważność pomiędzy kratami i topologiami odpowiednich typów. W Ćwiczeniach do tego wykładu poznamy najogólniejszą z dualności Stone'a, czyli dualność pomiędzy przestrzennymi ramami(ang. spatial frames) i przestrzeniami realnymi (ang. sober spaces).


Dualność zbiorów skończonych i skończonych algebr Boole'a

Oznaczmy kategorię skończonych algebr Boole'a (o algebrach Boole'a mówiliśmy już w Wykładzie 4. w tym podrozdziale) i homomorfizmów tych algebr (homomorfizmy to te funkcje na zbiorach podkładowych, które zachowują operacje algebry) przez \mathbf{BA}_{fin} . Takie algebry są zawsze atomowe, tzn. generowane za pomocą operacji algebry ze zbioru atomów. Jeśli B\in \mathbf{BA}_{fin}, to jej zbiór atomów definiujemy jako:

\mathcal{A}(B):=\{a\in B\mid (\mathbf{0} < a)\wedge (b<a\Rightarrow b=\mathbf{0}\}.


Rozpocznijmy konstrukcję od przypomnienia podstawowych definicji teorii porządku (które są rozszerzone i uzupełnione w Wykładzie 12. Odsyłamy tam Czytelnika w przypadku, gdyby spotkał nieznane sobie oznaczenia).


Definicja 6.4 [filtr, ultrafiltr]

Filtrem w kracie L nazywamy podzbiór U\subseteq B taki, że:

  • x,y\in U implikuje x\wedge y \in U
  • U = \uparrow U, co oznacza dokładnie tyle, że x\leq y i x\in L razem implikują y\in L.

Filtr, który jest właściwym podzbiorem kraty L nazywamy filtrem właściwym. Filtr właściwy, który jest maksymalny w sensie inkluzji w kracie L nazywamy ultrafiltrem. Można łatwo przekonać się, że filtr F\subseteq L jest ultrafiltrem wtedy i tylko wtedy, gdy dla dowolnego x\in L albo x\in F, albo \neg x\in F.


Zaobserwujmy, że jeśli L posiada element najmniejszy \mathbf{0}, to każdy filtr, który go zawiera jest całym zbiorem L i w związku z tym jest filtrem niewłaściwym. Zauważmy też, że każdy filtr w algebrze Boole'a zawiera element największy \mathbf{1}.

Ideałem w kracie L nazywamy każdy filtr w L^{op}. Czy dopełnienie filtru F w L może być ideałem? Tak. Ten szczególny przypadek da się przyjemnie opisać:


Stwierdzenie 6.5 [Filtr pierwszy]

W dowolnej kracie L dla F\subseteq L następujące warunki są równoważne:
  1. F jest filtrem i L\setminus F jest ideałem;
  2. F jest filtrem właściwym i jeśli a\vee b\in F, to a\in F lub b\in F;
  3. F=h^{-1}[\{ 1\}] dla pewnego homomorfizmu krat h\colon L\to\mathbf{2}.


Filtr F spełniający dowolny z powyższych warunków nazywamy filtrem pierwszym.

Uwaga
\mathbf{2} jest kratą dwuelementową \{ 0\leq 1\}. Warunek trzeci oznacza dokładnie tyle, że h zachowuje dowolne suprema i dowolne infima w kracie L.

Dowód

Załóżmy, L\setminus F jest ideałem. Wówczas L\setminus F jest zbiorem dolnym, co pociąga \mathbf{0}\in L\setminus F. Dlatego też \mathbf{0}\notin F. Jeśli a\notin F i b\notin F, to skoro L\setminus F jest ideałem, dostajemy a\vee b\in L\setminus F, czyli a\vee b\notin F.

Załóżmy teraz warunek (2). Zdefiniujmy h\colon L\to \mathbf{2} jako

h(x):= \begin{cases} 1, & x\in F\\ 0, & x\notin F\end{cases}.

Wtedy h^{-1}[\{1\}]=F oraz h zachowuje \mathbf{1} i \wedge, bo F jest filtrem i h zachowuje \mathbf{0} i \vee ze względu na założenia z (2).

W końcu, niech h\colon L\to \mathbf{2} będzie homomorfizmem. Wówczas \{ 1\}\subseteq \mathbf{2} jest filtrem, a h^{-1} odwzorowuje filtry w filtry. Podobnie, \{ 0\}\in \mathbf{2} jest ideałem, zaś h^{-1} posyła ideały w ideały.

image:End_of_proof.gif


W kratach zupełnych istnieją ciekawe odpowiedniki filtrów pierwszych, tak zwane filtry zupełnie pierwsze.


Definicja 6.6 [filtr zupełnie pierwszy]

Niech L będzie kratą zupełną. Filtr F jest zupełnie pierwszy, jeśli dla dowolnego podzbioru A\subseteq L, z faktu, że \bigvee A\in F wynika A\cap F\neq \emptyset.


Jeśli (X,\tau) jest przestrzenią topologiczną, zaś \Omega(X) jest kratą zupełną zbiorów otwartych z X uporządkowanych względem inkluzji, to dla dowolnego x\in X zbiór otoczeń otwartych x:

\mathcal{N}^{\circ}(x) := \{U\in \tau\mid x\in U\}

jest filtrem zupełnie pierwszym w \Omega(X).

W kratach dystrybutywnych (np. w algebrach Boole'a) zachodzi:


Stwierdzenie 6.7 [filtry pierwsze w kracie dystrybutywnej]

Niech I będzie ideałem w kracie dystrybutywnej L. Jeśli F jest maksymalnym filtrem, który jest rozłączny z I, to F jest pierwszy.

Dowód

Ponieważ \mathbf{0}\in I, to F jest właściwy. Niech a\notin F i b\notin F. Zbiory:
F_a :=\{ (f\wedge a)\vee   z\mid f\in F, z\in L\},
F_b :=\{ (f\wedge b)\vee z\mid f\in F, z\in L\},

są filtrami zawierającymi w sposób właściwy F, które - ze względu na maksymalność F - muszą przecinać się z I. Wybierzmy zatem c\in F_a\cap I i d\in F_b\cap I. skoro I jest ideałem c\vee d\in I. Dystrybutywność daje nam po kilku przekształceniach: c\vee d = f\wedge (a\vee b) dla pewnego f\in F. Ponieważ F i I są rozłączne, a\vee b\in F implikowałoby f\wedge (a\vee b)\in F, czyli c\vee d\in F\cap I, sprzeczność. A zatem: a\vee b\notin F. To kończy dowód.

image:End_of_proof.gif


Warto też dodać, że lemat Zorna implikuje, że w dowolnej kracie, jeśli mamy filtr F i ideał I takie, że F\cap I\neq \emptyset, to istnieje maksymalny filtr F'\supseteq F rozłączny z I. Oczywiście na mocy poprzedniego Stwierdzenia, tenże F' jest filtrem pierwszym.

Cała nasza dyskusja pierwszości zmierzała do tego, by scharakteryzować ultrafiltry w algebrach Boole'a. Oto ten wynik:


Twierdzenie 6.8 [ultrafiltry w algebrach Boole'a]

Dla filtra F w algebrze Boole'a B następujące warunki są równoważne:
  1. F jest ultrafiltrem;
  2. F jest pierwszy;
  3. Dla dowolnego a\in B, a\in F wtedy i tylko wtedy, gdy dla dowolnego b\in B a\wedge b\neq \mathbf{0};
  4. Dla dowolnego a\in B albo a\in F, albo a\notin F.

Dowód

Załóżmy (1). Ponieważ \{\mathbf{0}\} jest ideałem, (2) wynika ze Stwierdzenia 6.7. Załóżmy (2). Niech a\in B i załóżmy, że a\notin F. Wtedy najmniejszy filtr zawierający \uparrow a i F musi być całą kratą B. To znaczy, że a\wedge b=\mathbf{0} dla pewnego b\in F. Odwrotnie, przypuśćmy że a\in F. Ponieważ F jest właściwy, a\wedge b\neq \mathbf{0} dla każdego b\in F. Załóżmy teraz (3). Ponieważ każdy ultrafiltr jest pierwszy i dla dowolnego a\in B, \mathbf{1}=a\vee \neg a \in F, dostajemy (4). W końcu, zakładając (4), jeśli a\notin F, to \neg a\in F, więc nie istnieje filtr właściwy zawierający a i F. A zatem F jest maksymalnym filtrem właściwym w kracie B. image:End_of_proof.gif


W przypadku skończonej algebry Boole'a, łatwo pokazać, że zbiór jej atomów jest w bijekcji z ultrafiltrami.


Lemat 6.9 [atomy w skończonej algebrze Boole'a]

W dowolnej skończonej algebrze Boole'a B istnieje izomorfizm między atomami \mathcal{A}(B) i ultrafiltrami \mathrm{Ult}(B) na B.

Dowód

jeśli a jest atomem, to \uparrow a jest ultrafiltrem, bo dla dowolnego b\in B albo a\wedge b=a i wtedy b\in \uparrow a, albo a\wedge b\neq a, czyli a\wedge b=\mathbf{0}, więc \neg b\in \uparrow a. Odwrotnie, jeśli F jest ultrafiltrem na B, to \bigwedge F jest atomem. Łatwo przekonać się, że \uparrow \bigwedge F = F oraz jest trywialne, że \bigwedge \uparrow a=a. image:End_of_proof.gif


Aby pokazać teraz równoważność \mathbf{Set}^{op}_{fin} i \mathbf{BA}_{fin}, zdefiniujemy odpowiednie funktory. Z jednej strony, mamy kontrawariantny funktor potęgowy \mathcal{P}\colon \mathbf{Set}^{op}_{fin}\to \mathbf{BA}_{fin}. Z drugiej strony, pokażemy, że operacja \mathcal{A}\colon \mathbf{BA}^{op}_{fin}\to \mathbf{Set}_{fin}, której działanie znamy na obiektach, da się rozszerzyć do funktora. Ale tak jest dzięki Lematowi 6.9. Jeśli h\colon B\to C jest homomorfizmem algebr Boole'a, to dla c\in C zbiór h^{-1}[\uparrow c] jest ultrafiltrem na B. Definiujemy zatem:

\mathcal{A}(h\colon B\to C)(c) := \bigwedge h^{-1}[\uparrow c].

Uważny Czytelnik zwrócił uwagę, że typ \mathcal{A}, którym jest \mathbf{BA}^{op}_{fin}\to \mathbf{Set}_{fin}, jest tym samym co typ \mathbf{BA}_{fin}\to \mathbf{Set}^{op}_{fin}.

Wraz z funktorami \mathcal{P} i \mathcal{A} dostajemy też dwie transformacje naturalne. Pierwsza, \alpha\colon 1\to \mathcal{A}\mathcal{P} jest dana na komponentach jak następuje: niech X będzie zbiorem skończonym. Atomami \mathcal{P}(X) są singletony, więc \alpha_X(x):=\{ x\} jest izomorfizmem. Drugą transformację \beta\colon 1\to \mathcal{P}\mathcal{A} określamy na komponencie B jako:

\beta_{B}(b):= \{a\in \mathcal{A}(B)\mid a\leq b\}

i również jest izomorfizmem (dowód jest łatwy i pozostawiamy go do zrobienia w pamięci).