Teoria kategorii dla informatyków/Ćwiczenia 6: Równoważność kategorii

From Studia Informatyczne

W tej części skupimy się na dualności między kategorią przestrzennych ram a kategorią przestrzeni topologicznych nazywanych realnymi. Ta równoważność jest najogólniejszą z wielu coraz bardziej szczegółowych dualności, z którym najbardziej znana jest chyba dualność pomiędzy algebrami Boole'a a tzw. przestrzeniami Stone'a (czyli przestrzeniami T_0, które są zwarte i zerowymiarowe) odkryta przez Marshalla Stone'a w latach 30. XX w., która wzmacnia znany już kilka lat wcześniej wynik Lindenbauma i Tarskiego, który mówił, że algebra Boole'a jest izomorficzna z algebrą podzbiorów pewnego zbioru wtedy i tylko wtedy, gdy jest zupełna i atomowa.
Marshall H. Stone (1903-1989)Zobacz biografię
Enlarge
Marshall H. Stone (1903-1989)
Zobacz biografię

Zdecydowaliśmy się na przedstawienie najogólniejszej wersji twierdzenia Stone'a, gdyż bardzo dobrze widać mechanizm kategoryjny, na którym opiera się cała konstrukcja. Co więcej, równoważność w tej wersji nie wymaga przygotowania topologicznego. Po trzecie, wynik ten pokazuje dobitnie rolę teorii porządku w topologii i odwrotnie.


Zachęcamy do przeczytania Wykładu 12. przed przystąpieniem do rozwiązywania poniższych zadań.


==Zadanie 6.1== Niech L będzie kratą zupełną, zaś F\subseteq L. Pokaż, że następujące warunki są równoważne:

  1. F jest filtrem zupełnie pierwszym, tj. dla dowolnego podzbioru A\subseteq L, jeśli \bigvee A\in F, to A\cap F\neq \emptyset;
  2. F jest filtrem i L\setminus F = \downarrow x dla pewnego x\in L;
  3. F=h^{-1}(\{ 1\}) dla pewnego homomorfizmu ram h\colon L\to\mathbf{2}.


Uwaga
Ramy to pewne szczególne kraty zupełne, które zdefiniowaliśmy w Przykładzie Przykładzie 5.5. Homomorfizm ram to funkcja, która zachowuje dowolne suprema i binarne infima.

Rozwiązanie:

Załóżmy, że F jest zupełnie pierwszy. W szczególności jest pierwszy, więc L\setminus F jest ideałem. Co więcej, x =\bigvee (L\setminus F)\notin F, więc L\setminus F = \downarrow x.

Załóżmy (2). Definiujemy h\colon L\to\mathbf{2}:

h(z):=\begin{cases} 0, & z\leq x\\ 1, & \text{w p.p.}\end{cases}

Tak zdefiniowana funkcja jest oczywiście homomorfizmem krat, pozostaje więc wykazać, że zachowuje dowolne suprema. Jeśli h(\bigvee A)=0 dla pewnego A\subseteq L, to A\subseteq \downarrow x, więc h(a)=0 dla każdego a\in A. Stąd \bigvee h[A]=0=h(\bigvee A). Jeśli h(\bigvee A)=1, to \bigvee A nie jest poniżej x, więc istnieje a\in A taki, że h(a)=1, co oznacza, że \bigvee h[A]=1=h(\bigvee A), co należało pokazać.

W końcu, niech h\colon L\to\mathbf{2} będzie homomorfizmem ram, takim że F=h^{-1}[\{ 1\}]. Taka funkcja jest homomorfizmem krat, więc F jest filtrem, jak pokazaliśmy już w Stwierdzeniu 6.5. Ale jeśli A\subseteq L\setminus F, to musi być h(\bigvee A)=0, więc \bigvee A\notin F.


Najważniejszym przykładem filtru zupełnie pierwszego jest filtr otoczeń otwartych

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

w kracie (ramie) zbiorów otwartych (\Omega(X), \subseteq) przestrzeni topologicznej (X,\tau) (przypomnijmy znaczenie funktora \Omega z Przykładu 5.5). Zupełna pierwszość tego filtru wynika natychmiast choćby z punktu (3) poprzedniego zadania.

Niech L będzie ramą. Punktami ramy L nazwiemy jej filtry zupełnie pierwsze i ich kolekcję oznaczymy jako \mathrm{pt}(L). Wtedy \mathcal{N}^{\circ} możemy traktować jako odwzorowanie typu X\to \mathrm{pt}(\Omega(X)). Pokażmy kilka własności tego odwzorowania.

==Zadanie 6.2== Udowodnij, ze funkcja f\colon (X,\tau)\to (Y,\gamma) między przestrzeniami topologicznymi jest ciągła wtedy i tylko wtedy, gdy dla każdego x\in X,

\mathcal{N}^{\circ}(f(x)) = \Omega(f)^{-1}(\mathcal{N}^{\circ}(x)).

Wskazówka:

Oczywiście pamiętamy, że \Omega\colon \mathbf{Top}\to \mathbf{Frm} jest funktorem, więc \Omega(f) oznacza homomorfizm ram.

Rozwiązanie:

Załóżmy najpierw, że f jest ciągła. Dla x\in X i U\in \Omega(Y) dostajemy U\in \Omega(f)^{-1}(\mathcal{N}^{\circ}(x)) wtw, gdy \Omega(f)\in \mathcal{N}^{\circ}(x) wtw, gdy f^{-1}[U]\in \mathcal{N}^{\circ}(x) wtw, gdy U\in \mathcal{N}^{\circ}(f(x)). Odwrotnie, załóżmy że równość \mathcal{N}^{\circ}(f(x)) = \Omega(f)^{-1}(\mathcal{N}^{\circ}(x)) jest prawdziwa. Dla U\in \Omega(Y), jeśli f^{-1}[U] =\emptyset, to f^{-1}[U]\in \Omega(X). W przeciwnym przypadku weźmy x\in f^{-1}[U]. Wtedy U\in \mathcal{N}^{\circ}(f(x)), więc z założenia f^{-1}[U]\in \mathcal{N}^{\circ}(x), czyli f^{-1}[U]\in \Omega(X). To dowodzi, że f jest funkcją ciągłą.


Tak naprawdę wynik poprzedniego zadania można wzmocnić, wykazując, że \Omega(f)^{-1} ma typ \mathrm{pt}(\Omega(X))\to \mathrm{pt}(\Omega(Y)), czyli posyła wszystkie filtry zupełnie pierwsze na X w filtry zupełnie pierwsze na Y. Wracając do własności \mathcal{N}^{\circ}: powiemy, że przestrzeń topologiczna (X,\tau) jest T_0, jeśli dla dowolnych x,y\in X relacja

x\leq_s y \iff \mathcal{N}^{\circ}(x)\subseteq \mathcal{N}^{\circ}(y)

jest częściowym porządkiem. Porządek ten nazywamy porządkiem specjalizacji. (Taka relacja jest zawsze preporządkiem, więc antysymetria jest jedynym istotnym składnikiem definicji przestrzeni T_0.) Oczywiście to oznacza, że przestrzeń jest T_0 wtedy i tylko wtedy, gdy odwzorowanie \mathcal{N}^{\circ} jest injekcją. Przestrzeń topologiczną (X,\tau) nazywamy realną (ang. sober space), jeśli \mathcal{N}^{\circ} jest bijekcją. Każda przestrzeń realna jest więc T_0. Pokażmy, że porządek specjalizacji przestrzeni realnej ma bardzo przyjemne własności (odpowiednie definicje znajdziemy w Wykładzie 12.):


==Zadanie 6.3== Udowodnij, że w przestrzeni realnej porządek specjalizacji jest dcpo.

Wskazówka:

Musimy udowodnić, że jeśli D jest skierowanym (przez porządek specjalizacji) podzbiorem X, to D posiada supremum. Zacznijmy od pokazania, że zbiór F zbiorów otwartych U takich, że U\cap D\neq\emptyset jest filtrem zupełnie pierwszym.

Rozwiązanie:

Przy oznaczeniach ze Wskazówki przypuśćmy, że d\in U\cap D, e\in V\cap D dla U,V\in F. Zbiory otwarte są górne ze względu na porządek specjalizacji, więc \uparrow d\cap \uparrow e\subseteq U\cap V, a skoro D jest skierowany, \uparrow d\cap\uparrow e\cap D\neq \emptyset, więc U\cap V\in F. Oczywiście F jest górny, więc jest filtrem. Przypuśćmy \bigcup A\cap D\neq\emptyset dla zbioru A zbiorów otwartych. Dystrybutywność kraty podzbiorów daje \bigcup (A\cap D)\neq\emptyset, więc U\cap D\neq \emptyset dla pewnego U\in A. Wniosek: F jest zupełnie pierwszy. Skoro \mathcal{N}^{\circ} jest bijekcją, istnieje z\in X taki, że \mathcal{N}^{\circ}(z)=F. Dla dowolnego d\in D, jeśli d\in U, to d\in F, więc z\in U i d\leq_s z. Niech y będzie dowolnym ograniczeniem górnym D. Wtedy dla dowolnego U\in F, e\in U dla pewnego e\in D. Stąd U\in \mathcal{N}^{\circ}(y) i dlatego \mathcal{N}^{\circ}(z)\subseteq \mathcal{N}^{\circ}(y), tj. z\leq_s y. Wniosek: z=\bigvee D, co należało pokazać.


Uwaga
Nie jest prawdą twierdzenie odwrotne, które mówi, że na dowolnym częściowym porządku P, który jest dcpo, da się zadać topologię tak, by była realna i jej porządek specjalizacji pokrywał się z P.


==Zadanie 6.4== Niech L będzie ramą. Udowodnij, że na \mathrm{pt}(L) można zadać strukturę przestrzeni topologicznej, deklarując jako zbiory otwarte wszystkie zbiory postaci:

O_x:=\{ F\in \mathrm{pt}(L)\mid x\in F\}

dla x\in L.

Rozwiązanie:

Niech N będzie zbiorem skończonym. Oczywiście \bigcap_{n\in N}O_{x_n} = O_{\wedge_{n\in N} x_n}, ponieważ punkty L są filtrami: z\in \bigcap_{n\in N}O_{x_n} wtw, gdy z\in O_{x_n} dla każdego n\in N wtw, gdy z\in O_{\wedge_{n\in N} x_n}. Równie łatwo, zupełna pierwszość implikuje, że dla dowolnego zbioru indeksów I, \bigcup_{i\in I} O_{x_i}= O_{\vee_{i\in I} x_i}.


Od tej pory dla ramy L będziemy przestrzeń \mathrm{pt}(L) uważać za przestrzeń topologiczną z topologią zadaną tak, jak w powyższym zadaniu.


==Zadanie 6.5== Udowodnij, że \mathrm{pt}\colon \mathbf{Frm}^{op}\to \mathbf{Top} jest funktorem.

Wskazówka:

Jeśli h\colon K\to L jest homomorfizmem ram, zdefiniujemy \mathrm{pt}(h)(F):= h^{-1}[F], który to przeciwobraz jest rzeczywiście filtrem zupełnie pierwszym (to też należy pokazać).

Rozwiązanie:

Wykażemy najpierw, że h^{-1}[F], jak we Wskazówce, jest filtrem zupełnie pierwszym. Niech a\in h^{-1}[F] i a\leq b. Wtedy z monotoniczności h wynika h(a)\leq h(b), więc stąd że h(a)\in F i faktu, że F jest filtrem wynika h(b)\in F i w końcu b\in h^{-1}[F]. Jeśli a,b\in h^{-1}[F], to h(a),h(b)\in F, więc h(a)\wedge h(b)\in F, czyli h(a)\wedge h(b)\in h^{-1}[F]. Jeśli F jest zupełnie pierwszy, niech A\subseteq K tak, że \bigvee A\in h^{-1}[F]. Wtedy \bigvee h[A] =  h(\bigvee A)\in F, więc h[A]\cap F\neq \emptyset, tj. A\cap h^{-1}[F]\neq \emptyset. To kończy dowód pierwszej części.

Pokażmy teraz, że \mathrm{pt} jest funktorem. Zachowywanie identyczności jest oczywiste, zaś zachowywanie złożenia wynika z własności przeciwobrazów:

\mathrm{pt}(h\circ k)(F)=(h\circ k)^{-1}[F] = k^{-1}(h^{-1}[F]) = \mathrm{pt}(k)\circ \mathrm{pt}(h)(F).

Pozostaje wykazać, że \mathrm{pt}(h)\colon \mathrm{pt}(L)\to \mathrm{pt}(K) jest funkcją ciągłą. Niech O_a będzie zbiorem otwartym w \mathrm{pt}(L) i niech F\in \mathrm{pt}(K). Wtedy mamy F\in \mathrm{pt}(h)^{-1}[O_a] wtw, gdy \mathrm{pt}(h)(F)\in O_a wtw, gdy h^{-1}[F]\in O_a wtw, gdy h(a)\in F wtw, gdy F\in O_{h(a)}. A zatem \mathrm{pt}(h)^{-1}[O_a] jest zbiorem otwartym, co świadczy o ciągłości \mathrm{pt}(h).


Doszliśmy do najważniejszego momentu: głównym mechanizmem dualności Stone'a jest następujące sprzężenie.


==Zadanie 6.6== Udowodnij, że \Omega\dashv \mathrm{pt} dla \Omega\colon \mathbf{Top}\to\mathbf{Frm}^{op} i \mathrm{pt}\colon \mathbf{Frm}^{op}\to \mathbf{Top}.

Wskazówka:

Jednością \eta tego sprzężenia jest odwzorowanie \mathcal{N}^{\circ}.

Rozwiązanie:

Po pierwsze, pokażemy, że \mathcal{N}^{\circ}_X\colon X\to\mathrm{pt}(\Omega(X)) jest odwzorowaniem ciągłym, co natychmiast wynika z ciągu równoważności: dla dowolnego U otwartego w X

\mathcal{N}^{\circ}_X(x)\in O_U\iff U\in \mathcal{N}^{\circ}_X(x)\iff x\in U.

Ponadto, jest to transformacja naturalna: jeśli f\colon X\to Y, to mamy:

\mathrm{pt}(\Omega(f))(\mathcal{N}^{\circ}_X(x)) = \Omega(f)^{-1}(\mathcal{N}^{\circ}_X(x)) = \mathcal{N}^{\circ}_X(f(x))=\mathcal{N}^{\circ}_Y\circ f(x).

Zauważmy, że wykorzystaliśmy tutaj Zadanie 6.2.

Kojedność również już znamy: dla ramy L, komponent \varepsilon_L\colon L\to \Omega(\mathrm{pt}(L)) jest to funkcja, która x\in L posyła w zbiór otwarty O_x. Naturalność: dla homomorfizmu ram h\colon K\to L mamy:

\Omega(\mathrm{pt}(h))(\varepsilon_K(x))= \mathrm{pt}(h)^{-1}(O_x)=\varepsilon_L\circ h(x).

Na koniec sprawdzimy czy trójkątne diagramy, jak w Twierdzeniu 9.3, komutują:

Grafika:tk-6.2.png
Grafika:tk-6.3.png

Udowodnimy tylko drugą z równości, gdyż pierwsza jest dualna.

\aligned \mathrm{pt}(\varepsilon_L)(\eta_{\mathrm{pt}(L)}(F)) &=& \varepsilon_L^{-1}[\mathcal{N}^{\circ}(F)]\\ &=& \{x\in L\mid \varepsilon_L(x)\in \mathcal{N}^{\circ}(F)\}\\ &=& \{x\in L\mid O_x\in \mathcal{N}^{\circ}(F)\}\\ &=& \{x\in L\mid F \in O_x\}\\ &=& \{x\in L\mid x \in F\}\\ &=& F. \endaligned


W przypadku dowolnych przestrzeni topologicznych i dowolnych ram sprzężenie \Omega\dashv \mathrm{pt} nie indukuje równoważności. Warunkiem koniecznym i dostatecznym istnienia równoważności jest to, aby jedność \eta\colon 1\to \mathrm{pt}\circ\Omega i kojedność \varepsilon\colon 1\to \Omega\circ\mathrm{pt} były naturalnymi izomorfizmami. Jeśli topologia na X jest realna, to z definicji \eta_X jest izomorfizmem, dla dowolnego X.

Dualnie, dla dowolnego L, wiemy że \varepsilon_L jest surjekcją, bo wszystkie zbiory otwarte na \mathrm{pt}(L) są postaci O_x dla pewnego x\in L. Jeśli \varepsilon_L jest dla pewnej ramy L injekcją, to ramę tę nazywamy przestrzenną (ang. spatial frame). W tej nazwie zamyka się intuicja, że przestrzenne ramy to te, które są izomorficzne z kratą zbiorów otwartych pewnej topologii.

W ostatnim zadaniu poniżej pokażemy, że dla dowolnej ramy L przestrzeń \mathrm{L} jest realna i dla dowolnej topologii X rama \Omega(X) jest przestrzenna. Tym samym dowiedziemy ostatecznie następującego twierdzenia:


Twierdzenie [dualność Stone'a dla ram przestrzennych i topologii realnych]

Kategorie ram przestrzennych i przestrzeni topologicznych realnych są dualne.


==Zadanie 6.7== Pokaż, że dla dowolnej ramy przestrzennej L przestrzeń \mathrm{pt}(L) jest realna i dla dowolnej topologii X rama \Omega(X) jest przestrzenna.

Wskazówka:

Udowodnijmy pewną własność pomocniczą: jeśli X jest przestrzenią topologiczną, to jedność \eta_X\colon X\to \mathrm{pt}(\Omega(X)) jest surjekcją wtedy i tylko wtedy, gdy każdy nieredukowalny zbiór domknięty w X jest postaci \mathbf{cl}(x) dla pewnego x\in X. (Zbiór domknięty nazywamy nieredukowalnym, jeśli jest niepusty i nie da się wyrazić jako suma dwóch właściwych podzbiorów domkniętych przestrzeni X.) Rzeczywiście, załóżmy że \eta_X\colon X\to \mathrm{pt}(\Omega(X)) jest surjekcją i niech C będzie nieredukowalny. Wtedy rodzina F_C := \{ U\in \Omega(X)\mid U\cap C\neq \emptyset\} jest filtrem zupełnie pierwszym. Skoro jedność jest surjekcją, to każdy filtr zupełnie pierwszy jest postaci \mathcal{N}^{\circ}(x) dla x\in X. Tak więc F_C = \mathcal{N}^{\circ}(x) dla pewnego x\in X. Oczywiście \mathbf{cl}(x)= C. Odwrotnie, chcemy pokazać, że jedność jest surjekcją. Niech F będzie filtrem zupełnie pierwszym. Wtedy z Zadania 6.1 wynika, że L\setminus F=\downarrow x dla pewnego x\in L. Zbiór \downarrow x jest domknięty i nieredukowalny. A zatem F=F_{C_F} jest równy filtrowi otoczeń \mathcal{N}^{\circ}(x) dla tego szczególnego x\in X. To świadczy o tym, ze \eta_X jest surjekcją.

Rozwiązanie:

Niech L będzie ramą przestrzenną. Przestrzeń topologiczna \mathrm{pt}(L) jest oczywiście T_0, bo dla F_1,F_2\in \mathrm{pt}(L), jeśli x\in L należy do jednego z F_1, F_2, to nie może należeć do drugiego (z zupełnej pierwszości F_1,F_2). A zatem O_x zawiera jeden z F_1, F_2 i nie może zawierać drugiego. To świadczy o tym, że \eta_{\mathrm{pt}(L)} jest injekcją.

Aby pokazać, że \eta_{\mathrm{pt}(L)} jest surjekcją, skorzystamy z własności dowiedzionej we Wskazówce. Niech A będzie nieredukowalnym zbiorem domkniętym w \mathrm{pt}(L). Suma jego elementów (elementy A to filtry zupełnie pierwsze!), nazwijmy ją S, jest niepustym zbiorem górnym w L, zaś L\setminus S jest postaci \downarrow x dla pewnego x\in L. Dowód tej części kończy obserwacja, że \mathbf{cl}(L\setminus \downarrow x)=A.

Na zakończenie niech X będzie dowolną topologią. Musimy wykazać, że \Omega(X) jest kratą przestrzenną. Wystarczy więc pokazać, że \varepsilon_{\Omega(X)} jest injekcją. W tym celu weźmy U,V\in \Omega(X) i załóżmy, że są różne. A zatem istnieje x\in X, który należy do jednego z U,V i nie należy do drugiego. Bez straty ogólności przyjmijmy x\in U i x\notin V. Wtedy \mathcal{N}^{\circ}\in O_U= \varepsilon_{\Omega(X)}(U) i \mathcal{N}^{\circ}\notin O_V=\varepsilon_{\Omega(X)}(V). Tak jest \varepsilon_{\Omega(X)}(U)\neq \varepsilon_{\Omega(X)}(V), co należało pokazać.



Jednym z wniosków z ostatniego zadania jest to, że (w przyrodzie) istnieje wiele przestrzeni realnych: dla każdej (dowolnej!) topologii X, krata \Omega(X) jest przestrzenna, a zatem \mathrm{pt}(\Omega(X)) jest przestrzenią realną. Sama operacja X\mapsto \mathrm{pt}(\Omega(X)) jest nazywana urealnieniem przestrzeni X. Innym źródłem, z którego czerpiemy przykłady przestrzeni realnych są przestrzenie Hausdorffa. Można pokazać bowiem (zachęcamy Czytelnika do samodzielnej próby, to łatwe!), że każda przestrzeń T_2 jest realna, bo jedyne zbiory nieredukowalne są domknięciami singletonów . Warto też dodać, że aksjomat oddzielania T_1 jest niezależny od realności: istnieją przestrzenie realne, które nie są T_1 (wszystkie dziedziny ciągłe omawiane w Wykładzie 12.) i przestrzenie T_1, które nie są realne (np. topologia koskończona na liczbach naturalnych).

W tych Ćwiczeniach dotknęliśmy jedynie bardzo szerokiego tematu równoważności pomiędzy różnymi klasami krat i przestrzeni topologicznych. Szersze omówienie tych fascynujących zagadnień znajdzie Czytelnik w artykule S.Abramsky'ego i A. Junga pt. Domain theory pochodzącego z książki Handbook of Logic in Computer Science, Clarendon Press, 1994, dostępnym również na www drugiego z autorów tutaj.