Teoria kategorii dla informatyków/Wykład 12: Teoria dziedzin I

From Studia Informatyczne

Spis treści

Dziedziny jako częściowe porządki

Ten wykład jest wprowadzeniem w teorię dziedzin, którą zapoczątkowały badania Dany Scotta i Christophera Stracheya nad semantyką funkcyjnych języków programowania pod koniec lat 60. Dziedziny są to pewne częściowe porządki, które posiadają suprema zbiorów skierowanych i dodatkową relację binarną nazywaną relacją aproksymacji. Przeróżne kategorie dziedzin zostały wykorzystane jako matematyczne modele języków programowania, w sensie, który wyjaśnimy w Wykładzie 13. Kategorie dziedzin są znakomitym uniwersum, w którym za pomocą ścisłych matematycznych metod można opisywać rekursywne definicje procedur, struktur danych i innych mechanizmów języków programowania.

Uwaga dla dociekliwych
Klasycznym przykładem jest tu język nietypowanego \lambda-rachunku. Aby stworzyć semantykę tego języka, należy zaproponować pewną kategorię składającą się z obiektów typu D w taki sposób, aby termy \lambda-rachunku były interpretowane jako elementy D, zaś aplikacja funkcji do argumentu była rozumiana jako aplikacja strzałki f\colon D\to E do argumentu typu D. Jeśli teraz rozważymy \lambda-term \lambda x.xx, widzimy, że pierwsze wolne wystąpienie x musi być typu D\to D, zaś drugie typu D. A zatem musimy wymagać, by D\cong [D,D]. W naszej kategorii semantycznej muszą zatem istnieć nietrywialne punkty stałe funktora [,]. Pokażemy, że to możliwe w Wykładzie 14.

Ten wykład wprowadza wszystkie wstępne pojęcia teorii dziedzin w języku częściowych porządków i jest niezależny od wcześniejszych wykładów.


Dziedziny jako częściowe porządki

Porządek (inaczej: częściowy porządek, zbiór częściowo uporządkowany, poset) to zbiór wyposażony w relację \sqsubseteq, która jest zwrotna, przechodnia i antysymetryczna.

Niech (P, \sqsubseteq) będzie częściowym porządkiem. Element a\in P jest ograniczeniem górnym zbioru X\subseteq P, jeśli x\sqsubseteq a dla każdego x\in X (co zapisujemy również X\sqsubseteq a). Podobnie, element b\in P jest ograniczeniem dolnym zbioru X\sqsubseteq P, jeśli b\sqsubseteq x dla każdego x\in X (czyli b\sqsubseteq X). Jeśli dwa dowolne elementy x,y\in P posiadają w P ograniczenie górne, to oznaczamy to jako x\uparrow y. W przeciwnym wypadku piszemy x\# y. Najmniejsze ograniczenie górne zbioru X\subseteq P (jeśli istnieje) nazywamy supremum X i oznaczamy \bigvee X. Największe ograniczenie dolne zbioru X\subseteq P (jeśli istnieje) nazywamy infimum X i oznaczamy \bigwedge X. Jeśli X\subseteq P jest dwuelementowy, np. X =\{x,y\}, i posiada supremum (infimum), to piszemy \bigvee X = x\vee y (\bigwedge X = x\wedge y) i mówimy o supremum (infimum) binarnym.
Dana S. Scott ur. 1932Zobacz biografię
Enlarge
Dana S. Scott ur. 1932
Zobacz biografię

Poset jest kratą, jeśli ma wszystkie suprema i infima binarne. Poset jest kratą zupełną, jeśli dowolny jego podzbiór posiada zarówno supremum, jak i infimum.

Podzbiór D porządku P nazywamy skierowanym, co oznaczamy D\subseteq^{\uparrow} P, jeśli jest niepusty i każde dwa elementy z D posiadają ograniczenie górne w D (tzn. D\neq  \emptyset i x,y\in D\Rightarrow x,y\sqsubseteq  z dla pewnego z\in D). Łańcuchem nazywamy każdy zbiór skierowany, który jest liniowy. Supremum zbioru skierowanego D\subseteq^{\uparrow} P oznaczamy \bigvee^{\uparrow} D, kiedykolwiek istnieje. Podzbiór F porządku P nazywamy filtrowanym, jeśli jest niepusty i każde dwa elementy z F posiadają ograniczenie dolne w F (tzn. F\neq \emptyset i x,y\in  F\Rightarrow z\sqsubseteq x,y dla pewnego z\in  F). Infimum zbioru filtrowanego F (jeśli istnieje) oznaczamy \bigwedge_{\downarrow} F.

Poset P nazywamy bc-zupełnym, jeśli P posiada element najmniejszy \bot oraz każde dwa elementy x, y\in P takie, że x\uparrow y, posiadają supremum x\vee y\in  P.

Oznaczamy:

\downarrow X = \{ z\in P\mid \exists x\in X\mid  z\sqsubseteq x\}


\uparrow X = \{ w\in P\mid \exists x\in X\mid  x\sqsubseteq w\}


\downarrow x = \downarrow\{x\}


\uparrow x = \uparrow\{x\}.


X\subseteq P jest zbiorem dolnym, jeśli X = \downarrow X. X\subseteq  P jest zbiorem górnym, jeśli X = \uparrow  X. X\subseteq P jest ideałem, jeśli jest skierowany i dolny. X\subseteq P jest filtrem, jeśli jest filtrowany i górny. Ideałem głównym nazywamy każdy ideał postaci \downarrow x dla x\in  P. Filtrem głównym jest każdy filtr postaci \uparrow x dla pewnego x\in P.

Poset P nazywamy dcpo) (od angielskiego określenia: directed-complete partial order), jeśli każdy zbiór skierowany posiada supremum w P.

W każdym zbiorze częściowo uporządkowanym P możemy zdefiniować relację aproksymacji (ang. way-below relation) w następujący sposób: dla x,y\in P mamy x\ll y (czytamy: x aproksymuje y lub x jest skończony względem y) wtedy i tylko wtedy, gdy dla każdego zbioru skierowanego D\subseteq^{\uparrow} P takiego, że y\sqsubseteq \bigvee^{\uparrow} D mamy x\sqsubseteq d dla pewnego d\in D. W jednym zdaniu:

x\ll y \iff \forall D\subseteq^{\uparrow} \! P\  (y\sqsubseteq \bigvee {}^{\uparrow} D \Rightarrow (\exists d\in D \ (x\sqsubseteq d))).

Element x\in P nazywamy zwartym lub skończonym, gdy x\ll x. Zbiór wszystkich elementów zwartych posetu P oznaczamy zwykle K(P). Dla relacji \ll przyjmujemy podobne oznaczenia, jak dla porządku:

\Downarrow X = \{ z\in P\mid \exists x\in X\mid z\ll  x\}


\Uparrow X = \{ w\in P\mid \exists x\in X\mid x\ll  w\}


\Downarrow x = \Downarrow\{x\}


\Uparrow x = \Uparrow\{x\}.


Relacja aproksymacji w dowolnym posecie P posiada następujące własności:

  • (\forall x,y\in P)\ (x\ll y\Rightarrow x\sqsubseteq y),
  • (\forall x,y,z,w\in P)\ (x\sqsubseteq y\ll z\sqsubseteq w\Rightarrow x\ll w),
  • (\bot \in P\Rightarrow (\forall x\in P\ (\bot \ll x))).


Bazą posetu P nazywamy każdy podzbiór B taki, że dla każdego x\in P zbiór \Downarrow x \cap B jest skierowany i posiada supremum x.

Definicja 12.1

Poset P jest ciągły jeśli posiada bazę. Jeśli K(P) jest bazą, to mówimy, że P jest algebraiczny.


Twierdzenie 12.2

Poset P jest ciągły wtedy i tylko wtedy, gdy dla każdego x\in P, zbiór \Downarrow x jest skierowany i mamy x = \bigvee{}^\downarrow \Downarrow x.

Dowód

Niech P będzie ciągły i B będzie bazą dla P. Niech x\in P będzie dowolnym elementem P. Pokażemy, że \Downarrow x jest zbiorem skierowanym i jego supremum to x. Niech a,b\ll x. Skoro z założenia zbiór \Downarrow x\cap B jest skierowany z supremum x, to z definicji relacji aproksymacji istnieją dwa elementy a',b'\in B takie, że a\sqsubseteq  a'\ll x oraz b\sqsubseteq b'\ll x. Ale ze skierowania zbioru \Downarrow x\cap B wynika istnienie elementu c\in B takiego, że a'\sqsubseteq c\ll  x oraz b'\sqsubseteq c\ll x. A zatem z własności (w2) mamy a, b\sqsubseteq c\ll x, czyli wykazaliśmy, że zbiór \Downarrow x jest skierowany. Zauważmy, że x jest ograniczeniem górnym zbioru \Downarrow x. Jeśli z\in P jest dowolnym innym ograniczeniem górnym, to skoro \Downarrow x \cap B\subseteq  \Downarrow x, to x = \bigvee{}^\downarrow (\Downarrow x\cap B)  \sqsubseteq z. A zatem x = \bigvee{}^\downarrow \Downarrow  x. Z drugiej strony, jeśli P jest dowolnym posetem takim, że x = \bigvee{}^\downarrow \Downarrow x, to P jest bazą, a więc P jest ciągły. image:End_of_proof.gif

Zauważmy, że drobna modyfikacja pierwszej części powyższego dowodu pozwala nam wywnioskować, że jeśli B jest bazą dla P, to dowolny nadzbiór B jest również bazą dla P.

Twierdzenie 12.3 [interpolatywność aproksymacji]

Jeśli poset jest ciągły, to relacja aproksymacji posiada własność interpolacji:
  • (\forall M\subseteq_{fin} P)(\forall x\in P)\ ( M\ll x\Rightarrow (\exists y\in P\ (M\ll y\ll x))).


Definicja 12.4 [dziedzina]

Poset P nazywamy dziedziną lub dziedziną ciągłą, jeśli jest ciągłym dcpo.

Dziedziną algebraiczną nazywamy każdy dcpo algebraiczny P. Poset P jest dziedziną \omega-ciągłą, jeśli posiada przeliczalną bazę. Dziedzina algebraiczna z przeliczalną bazą jest nazywana dziedziną \omega-algebraiczną lub dziedziną Scotta. (Zauważmy, że na to, by dziedzina algebraiczna P była \omega-algebraiczna potrzeba i wystarcza, by baza K(P) była przeliczalna. Dowód tego stwierdzenia jest bardzo prosty i wynika z dwóch faktów: z tego, że K(P)\subseteq B dla każdej bazy B dziedziny P oraz z tego, że w dowolnym posecie każdy nadzbiór bazy jest również bazą).

Rozważmy następujące sztandarowe przykłady zbiorów częściowo uporządkowanych:

Przykład 12.5 [poset skończony]

Każdy poset skończony P jest dcpo, ponieważ każdy jego podzbiór skierowany posiada element największy. Co więcej, każdy element P jest zwarty, a więc P jest dziedziną Scotta.

Przykład 12.6 [liczby naturalne]

W posecie liczb naturalnych \omega z porządkiem naturalnym każdy element jest zwarty, tak więc \omega jest posetem algebraicznym. Poset \omega nie jest jednak dcpo, ponieważ łańcuch \omega nie ma supremum.
Grafika:tk-12.1.png


Przykład 12.7 [odcinek]

Odcinek [0,1] z naturalnym porządkiem jest ciągły, co łatwo wynika z faktu, że x\ll y wtedy i tylko wtedy, gdy x<y lub x=0. Jest to również krata zupełna, a więc w szczególności dziedzina ciągła i poset bc-zupełny.
Grafika:tk-12.2.png


Przykład 12.8 [zbiór potęgowy]

Niech X będzie dowolnym zbiorem. Zbiór potęgowy \mathcal{P}(X) jest kratą zupełną i dla każdego Y\subseteq X mamy \bigvee Y = \bigcup Y i \bigwedge Y = \bigcap Y. \mathcal{P}(X) jest więc w szczególności dcpo i bc-zupełny. Najmniejszym elementem \mathcal{P}(X) jest \emptyset, a największym X.
Grafika:tk-12.3.png

Pokażemy, że dla A,B\subseteq X mamy A\ll  B wtedy i tylko wtedy, gdy A jest skończonym podzbiorem B. Rzeczywiście, załóżmy, że A\ll  B. Ponieważ

B = \bigcup \{F \subseteq X \mid F\subseteq_{fin}  B\}

i tenże zbiór jest skierowany, istnieje F\subseteq_{fin} B taki, że A\subseteq F. Zbiór A jest więc skończony, jako podzbiór zbioru skończonego F.

Załóżmy, że A\subseteq_{fin} B. Przypuśćmy, że B\subseteq \bigcup \mathcal{D} dla pewnego zbioru skierowanego \mathcal{D} w \mathcal{P}(X). Mamy więc A\subseteq \bigcup  \mathcal{D}, co oznacza, że dla każdego a\in  A istnieje D_a\in \mathcal{D} taki, że a\in D_a. Ponieważ \mathcal{D} jest skierowany, istnieje D\in \mathcal{D}, który zawiera wszystkie zbiory D_a. To oznacza, że A\subseteq D\in \mathcal{D}, co należało pokazać.


Przykład 12.9 [dziedzina podprzedziałów odcinka]

Niech \mathbf{I}[0,1] oznacza zbiór wszystkich podprzedziałów domkniętych, niepustych przedziału [0,1] uporządkowany względem odwrotnej inkluzji, to znaczy:
[a,b] \sqsubseteq [c,d] \iff [a,b]\supseteq  [c,d]

dla a,b,c,d\in [0,1]. Poset \mathbf{I}[0,1] jest dcpo, bc-zupełny, \omega-ciągły i nie jest algebraiczny. Elementem najmniejszym jest [0,1], a element największy nie istnieje. Elementami maksymalnymi są wszystkie przedziały postaci [a,a] dla a\in [0,1], które utożsamiamy w sposób naturalny z liczbami rzeczywistymi z odcinka [0,1]. Relacja aproksymacji jest dana jako:

[a,b] \ll [c,d] \iff [a,b]\supseteq  (c,d).

Bazą przeliczalną w \mathbf{I}[0,1] jest rodzina wszystkich podprzedziałów odcinka [0,1] o końcach wymiernych.

Grafika:tk-12.4.png


Przykład 12.10 [dziedzina przedziałów]

Zbiór wszystkich domkniętych, niepustych przedziałów osi liczb rzeczywistych uporządkowany względem odwrotnej inkluzji, z dodanym elementem najmniejszym, oznaczamy \mathbf{I} \mathbb{R}. Poset \mathbf{I} \mathbb{R} jest izomorficzny z \mathbf{I}[0,1], więc posiada dokładnie te same cechy co \mathbf{I}[0,1].


Przykład 12.11 [dziedzina kul]

Niech (X,d) będzie przestrzenią metryczną. Rozważmy rodzinę wszystkich par postaci (x,r), gdzie x\in X i r>0 i zdefiniujmy relację \sqsubseteq w następujący sposób:
(x,r)\sqsubseteq (y,s) \iff d(x,y)\leq  r-s.

Można pokazać, że relacja \sqsubseteq jest częściowym porządkiem. Poset

\mathbf{B}X = (\{(x,r)\mid x\in X, r>0\}, \sqsubseteq)

jest ciągły, a relacja aproksymacji może być opisana jako:

(x,r)\ll (y,s) \iff d(x,y) < r-s.

Poset \mathbf{B}X jest dziedziną (tj. jest dcpo) wtedy i tylko wtedy, gdy X jest przestrzenią metryczną zupełną. Poset \mathbf{B}X jest \omega-ciągły wtedy i tylko wtedy, gdy przestrzeń metryczna X jest ośrodkowa.

Grafika:tk-12.5.png


Przykład 12.12 [model zbioru Cantora]

Zbiór wszystkich skończonych i nieskończonych ciągów zerojedynkowych \Sigma^{\infty} (oczywiście \Sigma =  \{0,1\}) w porządku prefiksowym jest dziedziną Scotta. Każdy zbiór skierowany jest łańcuchem. Elementem najmniejszym jest ciąg pusty \varepsilon. Zbiór elementów maksymalnych pokrywa się ze zbiorem wszystkich ciągów nieskończonych, który z kolei, jak wiadomo, posiada strukturę zbioru Cantora. Każdy element z \Sigma^{\infty}, który nie jest maksymalny, jest zwarty.
Grafika:tk-12.6.png

Funkcje monotoniczne

Funkcję f\colon P\to Q między posetami nazywamy monotoniczną, jeśli zachowuje porządek, tj. jeśli x\sqsubseteq y w P, to f(x)\sqsubseteq f(y) w Q. Funkcja f jest ciągła, jeśli zachowuje suprema zbiorów skierowanych, to znaczy: jeśli D\subseteq P jest skierowany i posiada supremum \bigvee{}^\downarrow D\in P, to f[D] posiada supremum \bigvee f[D] = f(\bigvee{}^\downarrow D). Zauważmy, że każda funkcja ciągła jest monotoniczna. Rzeczywiście, jeśli x\sqsubseteq y w P, to zbiór \{ x,y\} jest skierowany i ma supremum y. Tak więc f(y) = f(x\vee y) = \bigvee \{f(x), f(y)\} = f(x) \vee f(y) \sqsupseteq f(x). Z kolei, monotoniczność f implikuje, że dla D skierowanego, zbiór f[D] jest również skierowany. Wnioskujemy więc, że funkcja f jest ciągła wtedy i tylko wtedy, gdy dla dowolnego zbioru skierowanego D posiadającego supremum, zbiór f[D] jest skierowany oraz zachodzi \bigvee{}^\downarrow f[D] =  f(\bigvee{}^\downarrow D).

Uwaga
Jeśli funkcja monotoniczna f\colon D\to E jest traktowana kategoryjnie, jako funktor między kategoriami D i E, to pojęcie ciągłości, które tu wprowadziliśmy nie zgadza się z definicją ciągłości funktora. Przyjmijmy jednak, że w tym i dwóch następnych wykładach ciągłość funkcji między posetami będzie oznaczać tylko i wyłącznie zachowywanie supremów skierowanych.


Dziedziny jako topologie

Topologią na zbiorze X nazywamy dowolną rodzinę \tau podzbiorów zbioru X zamkniętą zewzględu na skończone przecięcia i dowolne sumy, a parę (X,\tau) nazywamy przestrzenią topologiczną.Definicję powyższą możemy wypowiedzieć na wiele równoważnych sposobów, na przykład: topologią nazywamy każdy podzbiór \tau porządku (\mathcal{P}(X),\subseteq) zamknięty ze względu na dowolne suprema i skończone infima. O elementach \tau mówimy, że są to zbiory otwarte. Z definicji mamy więc, że skończone przecięcie zbiorów otwartych jest zbiorem otwartym i dowolna suma zbiorów otwartych jest zbiorem otwartym. Tak więc rodzina \Omega(X) = (\tau, \subseteq) jest kratą, w której istnieją wszystkie suprema. To znaczy, że \Omega(X) jest w rzeczywistości kratą zupełną, ponieważ infimum dowolnego podzbioru \mathcal{M} zbioru \tau jest równe supremum zbioru wszystkich ograniczeń dolnych \mathcal{M}. W szczególności, każda topologia na zbiorze X zawiera zbiór pusty (który jest równy \bigvee \mathcal{M} dla \mathcal{M} = \emptyset) i całą przestrzeń X (=  \bigwedge \emptyset).

Jeśli \tau = \mathcal{P}(X), to \tau nazywamy topologią dyskretną; jeśli \tau = \{\emptyset, X\}, to \tau nazywamy topologią trywialną}.

Niech (X,\tau) będzie przestrzenią topologiczną. Otoczeniempunktu x\in X nazywamy dowolny zbiór A taki, że x\in U\subseteq A dla pewnego U\in \tau. Można łatwo pokazać, że dowolny podzbiór B zbioru X jest otwarty (to znaczy B\in \tau) wtedy i tylko wtedy, gdy B jest otoczeniem każdego swojego elementu. Zbiór otoczeń x\in X oznaczymy \mathcal{N}(x). Jak łatwo zauważyć, zbiór \mathcal{N}(x) jest filtrem w kracie (\mathcal{P}(X), \subseteq) i dlatego nazywamy go często filtrem otoczeń punktu x. Zauważmy też, że dla dowolnego x\in X, filtr otoczeń \mathcal{N}(x) jest wyznaczony jednoznacznie, a więc w rzeczywistości odwzorowanie \mathcal{N}\colon X\to  \mathcal{P}(\mathcal{P}(X)) dane przez

x\mapsto \{A\subseteq X \mid (\exists U\in  \tau)(x\in U\subseteq A)\}

jest dobrze określoną funkcją.

Niech (X,\tau) będzie przestrzenią topologiczną i niech A\subseteq X. Wnętrzem zbioru A nazywamy największy zbiór otwarty zawarty w A, który będziemy oznaczać dalej jako \mathbf{int}_{\tau}(A) lub po prostu \mathbf{int}(A), jeśli jest jasne o jakiej topologii \tau jest właśnie mowa. Zauważmy, że odwzorowanie \mathbf{int} \colon \mathcal{P}(X)\to \mathcal{P}(X) dane przez

A\mapsto \bigcup \{O\mid O \subseteq  A\}

jest dobrze określoną funkcją. Ponadto, zbiór O\subseteq  X jest otwarty wtedy i tylko wtedy, gdy O=\mathbf{int}(O), to znaczy, gdy O jest punktem stałym odwzorowania \mathbf{int}\colon \mathcal{P}(X)\to \mathcal{P}(X). Co więcej, \tau = \{\mathbf{int}(A)\mid A\subseteq X\}.

Dopełnienia zbiorów otwartych w przestrzeni topologicznej nazywamy zbiorami domkniętymi. Rodzina zbiorów domkniętych posiada własności dualne do własności zbiorów otwartych, a więc jest zamknięta ze względu na dowolne przecięcia i skończone sumy i tworzy kratę zupełną, zarówno względem inkluzji, jak i względem odwrotnej inkluzji. Kratę zbiorów domkniętych oznaczamy dalej jako \Gamma(X). Ponieważ \Gamma(X) jest podzbiorem \mathcal{P}(X) zamkniętym ze względu na dowolne infima, więc dla dowolnego A\subseteq X istnieje najmniejszy zbiór domknięty zawierający A, który jest niczym innym, jak tylko infimum zbioru ograniczeń górnych A w \Gamma(X) (czyli przecięciem wszystkich domkniętych nadzbiorów A). Zbiór ten oznaczamy \mathbf{cl}_{\tau}(A) albo po prostu \mathbf{cl}(A), jeśli \tau jest ustalona. Podobnie, jak w przypadku operacji wnętrza, odwzorowanie \mathbf{cl} \colon \mathcal{P}(X)\to  \mathcal{P}(X) jest dobrze określoną funkcją, a zbiór C\subseteq X jest domknięty wtedy i tylko wtedy, gdy jest punktem stałym odwzorowania \mathbf{cl}, to jest, gdy C = \mathbf{cl}(C).


Bazy w przestrzeniach topologicznych

Niech (X,\tau) będzie przestrzenią topologiczną. Bazątopologii \tau nazywamy każdą podrodzinę \beta\subseteq \tau taką, że dla każdego otoczenia A punktu x istnieje B\in\beta taki, że x\in B\subseteq A. W szczególności, cała rodzina \tau jest bazą topologii \tau.

Przypomnijmy, że jeśli P jest częściowym porządkiem, to jego podzbiory A,Bwspółkońcowe, jeśli \downarrow A = \downarrow B. Ponadto, jeśli A\subseteq B oraz \downarrow A = \downarrow  B, to mówimy, że A jest współkońcowy w B. Rozważmy więc kratę (\mathcal{P}(X), \supseteq) dla przestrzeni topologicznej (X,\tau). W tej kracie rodzina \mathcal{N}(x) dla dowolnego x\in X jest zbiorem skierowanym. Zauważmy, że podrodzina \beta topologii \tau na X jest bazą wtedy i tylko wtedy, gdy dla każdego x\in  X, zbiór \beta(x) jest współkońcowy w \mathcal{N}(X), gdzie \beta(x) = \{B\in  \beta\mid x\in B\}.

Zbiory zwarte

Podzbiór K przestrzeni topologicznej (X,\tau) nazywamy zwartym, jeśli dowolne pokrycie K zbiorami otwartymi zawiera podpokrycie skończone, to jest: jeśli K\subseteq \bigcup  \mathcal{M} dla dowolnej rodziny \mathcal{M}\subseteq \tau, to istnieje podrodzina \mathcal{F}\subseteq_{fin} \mathcal{M} taka, że K\subseteq \bigcup \mathcal{F}. W praktyce będziemy mieli bardzo często do czynienia z rodzinami indeksowanymi, więc definicja zwartości upraszcza się do następującej: K\subseteq X jest zwarty wtedy i tylko wtedy, gdy K\subseteq \bigcup_{i\in I} A_i dla A_i\in  \tau implikuje K\subseteq A_{i_1}\cup ...  A_{i_n} dla i_1, ..., i_n\in I, gdzie n\in \omega.


Porządek specjalizacji i aksjomaty oddzielania

W dowolnej przestrzeni topologicznej (X,\tau) możemy zdefiniować relację przechodnią i zwrotną między elementami x,y\in X w następujący sposób:

x\sqsubseteq_{\tau} y \iff (\forall U\in \tau)(x\in U\Rightarrow  y\in U),      ()

którą nazywamy preporządkiem specjalizacji. Mówimy, że przestrzeń topologiczna X spełnia aksjomat oddzielaniaT_0 (lub: jest przestrzenią T_0) jeśli \sqsubseteq_{\tau} jest częściowym porządkiem, to znaczy wtedy i tylko wtedy, gdy \sqsubseteq_{\tau} jest relacją antysymetryczną. Dalej, mówimy, że przestrzeń topologiczna X spełnia aksjomat oddzielania T_1 (jest przestrzenią T_1) wtedy i tylko wtedy, gdy \sqsubseteq_{\tau} redukuje się do równości. Oczywiście definicje powyższe implikują, że każda przestrzeń T_1 jest T_0, ale nie jest odwrotnie, jak pokazuje przykład topologii \{\emptyset, \{1\}, \{0,1\}  \} na zbiorze dwuelementowym \{0,1\}.

Nazwy aksjomaty oddzielania pochodzą stąd, że w przestrzeniach topologicznych o własnościach T_0 czy T_1 zbiory otwarte oddzielają punkty w odpowiedni sposób. W dalszej części wykładu będziemy mówić głównie o przestrzeniach T_0, które nie są przestrzeniami T_1 (konkretnie, tak zwana topologia Scotta na nietrywialnych dziedzinach posiada te własności, co wykażemy poniżej). Z drugiej strony, niemal wszystkie przestrzenie topologiczne rozważane w analizie, geometrii itd., itp. spełniają aksjomaty silniejsze niż T_1. Nasz wykład będzie więc różnił się znacznie od standardowego wykładu topologii ogólnej.


Funkcje ciągłe na dziedzinach

Można śmiało powiedzieć, że struktura topologiczna na zbiorach jest wprowadzana po to, aby w sposób ścisły móc mówić o ciągłości funkcji. Przedmiot Topologia jest więc przede wszystkim nauką o funkcjach ciągłych między przestrzeniami topologicznymi.


Definicja 12.13

Niech (X,\tau), (Y, \alpha) będą przestrzeniami topologicznymi. Mówimy, że funkcja f\colon X\to Y jest ciągła wtedy i tylko wtedy, gdy dla każdego zbioru otwartego A w Y, przeciwobraz f^{-1}[A] jest otwarty w X (tj. (\forall A\subseteq Y)(A\in \alpha \Rightarrow  f^{-1}[A]\in \tau)).


Dowodzi się w prosty sposób, że funkcja jest ciągła wtedy i tylko wtedy, gdy przeciwobraz dowolnego zbioru domkniętego jest domknięty.


Topologia Scotta na porządkach

W tej części wykładu pokażemy, że każdy zbiór częściowo uporządkowany może być traktowany jako przestrzeń topologiczna. Topologia, którą w naturalny sposób można zdefiniować na każdym posecie nazywa się topologią Scotta i pochodzi od nazwiska słynnego logika Dany S. Scotta (prof. Scott wykłada i bierze udział w konferencjach matematycznych i informatycznych do dziś).


Definicja 12.14

Niech P będzie częściowym porządkiem. Zbiór U nazywamy otwartym w sensie Scotta, jeśli spełnia dwa warunki:
  • U = \uparrow U (U jest zbiorem górnym),
  • Jeśli dla zbioru skierowanego D\subseteq^{\uparrow} P mamy \bigvee{}^\downarrow D \in U, to istnieje element d\in D taki, że d\in U.
O zbiorze U\subseteq P mającym własność (S2) mówimy, że jest nieosiągalny przez suprema zbiorów skierowanych. Rodzinę zbiorów otwartych w sensie Scotta oznaczamy \sigma(P) lub po prostu \sigma.


Twierdzenie 12.15

Niech P będzie częściowym porządkiem. Zbiory otwarte w sensie Scotta tworzą topologię.

Dowód

Niech O,U\in \sigma. Pokażemy, że O\cap U\in \sigma. Jest oczywiste, że O\cap U jest zbiorem górnym, więc pokażemy tylko własność (S2). Niech D będzie dowolnym zbiorem skierowanym w P, który posiada supremum x =  \bigvee{}^\downarrow D\in P. Jeśli x\in O\cap  U, to x \in O i x\in U, a więc istnieją elementy o\in D\cap O i u\in D\cap  U. Ale D jest skierowany, więc istnieje y\in D taki, że o,u\sqsubseteq y. Ponieważ O i U są zbiorami górnymi, y\in D\cap (O\cap U), co należało pokazać. Niech A_i będzie dowolną rodziną zbiorów otwartych. Jest jasne, że \bigcup_{i\in I} A_i jest zbiorem górnym. Następnie, jeśli \bigvee{}^\downarrow D = x \in  \bigcup_{i\in I} A_i dla D\subseteq^{\uparrow}  D, to x\in A_i dla pewnego i\in  I. A zatem istnieje d\in D taki, że d\in A_i. Element d należy więc do \bigcup_{i\in I} A_i, a więc D\cap  \bigcup_{i\in I} A_i, czego należało dowieść. image:End_of_proof.gif

Można pokazać, że zbiór C\subseteq P jest domknięty w sensie Scotta, jeśli jest zbiorem dolnym i zawiera wszystkie suprema swoich podzbiorów skierowanych (o tej drugiej własności mówimy, że zbiór domknięty w sensie Scotta jest zamknięty ze względu na suprema zbiorów skierowanych). Najprostszymi przykładami zbiorów domkniętych są ideały główne \downarrow x dla x\in P.

Okazuje się, że porządek specjalizacji dla topologii Scotta na P jest zawsze porządkiem częściowym, który pokrywa się z tym na P.


Twierdzenie 12.16

Niech (P,\sqsubseteq) będzie częściowym porządkiem. Dla dowolnych elementów x,y\in P następujące warunki są równoważne:
  • x\sqsubseteq y,
  • x\sqsubseteq_{\sigma} y,
  • x\in \mathbf{cl}(\{y\}).

Co więcej, topologia Scotta jest T_0.


Dowód

(1)\Rightarrow(2) wynika z tego, że zbiory otwarte są górne. (2)\Rightarrow(3): przypuśćmy, że x\notin \mathbf{cl}(\{y\}). Wówczas istnieje C domknięty w sensie Scotta, taki, że y\in C i x\notin C. A zatem dla zbioru otwartego U = P\setminus C mamy x\in U i y\notin U. To znaczy, że x\nepod_{\sigma}  y, co należało pokazać (3)\Rightarrow(1): ponieważ ideał \downarrow y jest domknięty w sensie Scotta i zawiera y, więc \mathbf{cl}(\{y\})\subseteq \downarrow y, a zatem x\in \downarrow y. Własność T_0 wynika z równoważności (1) i (2) powyżej. image:End_of_proof.gif

Topologia Scotta na dziedzinach

Niech P będzie porządkiem ciągłym. Łatwo pokazać, że w topologii Scotta na P mamy \mathbf{int}(\uparrow x) = \Uparrow x dla każdego x\in P. Lecz o tej sytuacji możemy powiedzieć nawet więcej:


Twierdzenie 12.17

Niech P będzie porządkiem ciągłym, a B jego bazą. Wówczas rodzina \beta = \{\Uparrow x\mid x\in B\} jest bazą dla topologii Scotta.

Dowód

Wiemy już, że elementy \beta są zbiorami otwartymi w sensie Scotta. Niech x\in U dla dowolnego x\in B i U\in \sigma(P). Skoro \Downarrow x\cap B jest skierowany z supremum x, to z otwartości U wynika, że istnieje d\in \Downarrow x\cap B\cap U. A zatem x\in \Uparrow  d\subseteq U dla pewnego d\in B, co należało pokazać. image:End_of_proof.gif

Funkcje ciągłe w sensie Scotta

Na zakończenie pokażemy, że funkcje ciągłe między posetami są dokładnie funkcjami ciągłymi w sensie Scotta. Jest to jedna z przyczyn, dla których topologia Scotta odgrywa podstawową rolę w teorii dziedzin.


Twierdzenie 12.18

Niech P, Q będą posetami. Dla funkcji f\colon P\to Q następujące warunki są równoważne:
  • f jest ciągła,
  • f jest funkcją ciągłą między topologiami (P,\sigma(P)) i (Q, \sigma(Q)).

Dowód

Niech f będzie ciągła i O\in \sigma(Q). Ponieważ funkcje ciągłe są monotoniczne, f^{-1}[O] jest zbiorem górnym. Jeśli x = \bigvee{}^\downarrow D \in f^{-1}[O] dla pewnego zbioru skierowanego D, to f(x) \in O, to istnieje d\in D taki, że f(d)\in O. To oznacza, że d\in D\cap f^{-1}[O], co należało pokazać. Z drugiej strony, załóżmy, że f jest ciągła w sensie Scotta. Niech x\sqsubseteq y w P. Wtedy f^{-1}[\downarrow f(y)] jest zbiorem domkniętym w sensie Scotta zawierającym y, a więc zbiór ten musi zawierać również x. To daje f(x)\sqsubseteq f(y). Funkcja f jest więc monotoniczna. Niech D\subseteq P będzie skierowany. Rozważmy przeciwobraz zbioru domkniętego \downarrow (\bigvee{}^\downarrow f[D]). Jest on domknięty w P i zawiera D, a więc musi też zawierać \bigvee{}^\downarrow D. Pokazaliśmy, że f(\bigvee{}^\downarrow D)\in \downarrow (\bigvee{}^\downarrow f[D]), czyli f(\bigvee{}^\downarrow D)\sqsubseteq \bigvee{}^\downarrow f[D]. Ale monotoniczność f implikuje, że \bigvee{}^\downarrow f[D]\sqsubseteq f(\bigvee{}^\downarrow D), co należało pokazać. image:End_of_proof.gif