Teoria kategorii dla informatyków/Wykład 12: Teoria dziedzin I: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
Linia 3: Linia 3:
 
==Dziedziny jako częściowe porządki==
 
==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 60tych. 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  [[Teoria_kategorii_dla_informatyków/Wykład_13:_Teoria_dziedzin_II#wyklad13|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.
+
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  [[Teoria_kategorii_dla_informatyków/Wykład_13:_Teoria_dziedzin_II#wyklad13|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 <math>\lambda</math>-rachunku. Aby stworzyć semantykę tego języka, należy zaproponować pewną kategorię składającą się z obiektów typu <math>D</math> w taki sposób, aby termy <math>\lambda</math>-rachunku były interpretowane jako elementy <math>D</math>, zaś aplikacja funkcji do argumentu była rozumiana jako aplikacja strzałki <math>f\colon D\to E</math> do argumentu typu <math>D</math>. Jeśli teraz rozważymy <math>\lambda</math>-term <math>\lambda x.xx</math>, widzimy, że pierwsze wolne wystąpienie <math>x</math> musi być typu <math>D\to D</math>, zaś drugie typu <math>D</math>. A zatem ''musimy'' wymagać, by <math>D\cong [D,D]</math>. W naszej kategorii semantycznej muszą zatem istnieć nietrywialne punkty stałe funktora <math>[,]</math>. Pokażemy, że to możliwe w  [[Teoria_kategorii_dla_informatyków/Wykład_14:_Teoria_dziedzin_III#wyklad14|Wykładzie 14]]. }}
 
{{uwaga|dla dociekliwych|| Klasycznym przykładem jest tu język nietypowanego <math>\lambda</math>-rachunku. Aby stworzyć semantykę tego języka, należy zaproponować pewną kategorię składającą się z obiektów typu <math>D</math> w taki sposób, aby termy <math>\lambda</math>-rachunku były interpretowane jako elementy <math>D</math>, zaś aplikacja funkcji do argumentu była rozumiana jako aplikacja strzałki <math>f\colon D\to E</math> do argumentu typu <math>D</math>. Jeśli teraz rozważymy <math>\lambda</math>-term <math>\lambda x.xx</math>, widzimy, że pierwsze wolne wystąpienie <math>x</math> musi być typu <math>D\to D</math>, zaś drugie typu <math>D</math>. A zatem ''musimy'' wymagać, by <math>D\cong [D,D]</math>. W naszej kategorii semantycznej muszą zatem istnieć nietrywialne punkty stałe funktora <math>[,]</math>. Pokażemy, że to możliwe w  [[Teoria_kategorii_dla_informatyków/Wykład_14:_Teoria_dziedzin_III#wyklad14|Wykładzie 14]]. }}
Linia 16: Linia 16:
 
Niech <math>(P, \sqsubseteq)</math> będzie częściowym porządkiem. Element <math>a\in P</math> jest '''ograniczeniem górnym''' zbioru <math>X\subseteq P</math>, jeśli <math>x\sqsubseteq a</math> dla każdego <math>x\in X</math> (co zapisujemy również <math>X\sqsubseteq a</math>). Podobnie, element <math>b\in P</math> jest '''ograniczeniem dolnym''' zbioru <math>X\sqsubseteq P</math>, jeśli <math>b\sqsubseteq x</math> dla każdego <math>x\in X</math> (czyli <math>b\sqsubseteq X</math>). Jeśli dwa dowolne elementy <math>x,y\in P</math> posiadają w <math>P</math> ograniczenie górne, to oznaczamy to jako <math>x\uparrow y</math>. W przeciwnym wypadku piszemy <math>x\# y</math>. Najmniejsze ograniczenie górne zbioru <math>X\subseteq P</math> (jeśli istnieje) nazywamy '''supremum''' <math>X</math> i oznaczamy <math>\bigvee X</math>. Największe ograniczenie dolne zbioru <math>X\subseteq P</math> (jeśli istnieje) nazywamy '''infimum''' <math>X</math> i oznaczamy <math>\bigwedge X</math>. Jeśli <math>X\subseteq P</math> jest dwuelementowy, np. <math>X =\{x,y\}</math>, i posiada supremum (infimum), to piszemy <math>\bigvee X = x\vee y</math> (<math>\bigwedge X = x\wedge y</math>) i mówimy o '''supremum''' ('''infimum''') '''binarnym'''. [[grafika:Scott-portret.gif|thumb|right||Dana S. Scott ur. 1932<br>[[Biografia Scotta|Zobacz biografię]]]]  
 
Niech <math>(P, \sqsubseteq)</math> będzie częściowym porządkiem. Element <math>a\in P</math> jest '''ograniczeniem górnym''' zbioru <math>X\subseteq P</math>, jeśli <math>x\sqsubseteq a</math> dla każdego <math>x\in X</math> (co zapisujemy również <math>X\sqsubseteq a</math>). Podobnie, element <math>b\in P</math> jest '''ograniczeniem dolnym''' zbioru <math>X\sqsubseteq P</math>, jeśli <math>b\sqsubseteq x</math> dla każdego <math>x\in X</math> (czyli <math>b\sqsubseteq X</math>). Jeśli dwa dowolne elementy <math>x,y\in P</math> posiadają w <math>P</math> ograniczenie górne, to oznaczamy to jako <math>x\uparrow y</math>. W przeciwnym wypadku piszemy <math>x\# y</math>. Najmniejsze ograniczenie górne zbioru <math>X\subseteq P</math> (jeśli istnieje) nazywamy '''supremum''' <math>X</math> i oznaczamy <math>\bigvee X</math>. Największe ograniczenie dolne zbioru <math>X\subseteq P</math> (jeśli istnieje) nazywamy '''infimum''' <math>X</math> i oznaczamy <math>\bigwedge X</math>. Jeśli <math>X\subseteq P</math> jest dwuelementowy, np. <math>X =\{x,y\}</math>, i posiada supremum (infimum), to piszemy <math>\bigvee X = x\vee y</math> (<math>\bigwedge X = x\wedge y</math>) i mówimy o '''supremum''' ('''infimum''') '''binarnym'''. [[grafika:Scott-portret.gif|thumb|right||Dana S. Scott ur. 1932<br>[[Biografia Scotta|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.
+
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 <math>D</math> porządku <math>P</math> nazywamy '''skierowanym''', co oznaczamy <math>D\subseteq^{\uparrow} P</math>,  jeśli jest niepusty i każde dwa elementy z <math>D</math>  posiadają ograniczenie górne w <math>D</math> (tzn. <math>D\neq  \emptyset</math> i <math>x,y\in D\Rightarrow x,y\sqsubseteq  z</math> dla pewnego <math>z\in D</math>). '''Łańcuchem'''  nazywamy każdy zbiór skierowany, który jest liniowy. Supremum  zbioru skierowanego <math>D\subseteq^{\uparrow} P</math>  oznaczamy <math>\bigvee^{\uparrow} D</math>, kiedykolwiek  istnieje. Podzbiór <math>F</math> porządku <math>P</math>  nazywamy '''filtrowanym''', jeśli jest niepusty i każde dwa  elementy z <math>F</math> posiadają ograniczenie dolne w  <math>F</math> (tzn. <math>F\neq \emptyset</math> i <math>x,y\in  F\Rightarrow z\sqsubseteq x,y</math> dla pewnego <math>z\in  F</math>). Infimum zbioru filtrowanego <math>F</math> (jeśli  istnieje) oznaczamy <math>\bigwedge_{\downarrow} F</math>.
 
Podzbiór <math>D</math> porządku <math>P</math> nazywamy '''skierowanym''', co oznaczamy <math>D\subseteq^{\uparrow} P</math>,  jeśli jest niepusty i każde dwa elementy z <math>D</math>  posiadają ograniczenie górne w <math>D</math> (tzn. <math>D\neq  \emptyset</math> i <math>x,y\in D\Rightarrow x,y\sqsubseteq  z</math> dla pewnego <math>z\in D</math>). '''Łańcuchem'''  nazywamy każdy zbiór skierowany, który jest liniowy. Supremum  zbioru skierowanego <math>D\subseteq^{\uparrow} P</math>  oznaczamy <math>\bigvee^{\uparrow} D</math>, kiedykolwiek  istnieje. Podzbiór <math>F</math> porządku <math>P</math>  nazywamy '''filtrowanym''', jeśli jest niepusty i każde dwa  elementy z <math>F</math> posiadają ograniczenie dolne w  <math>F</math> (tzn. <math>F\neq \emptyset</math> i <math>x,y\in  F\Rightarrow z\sqsubseteq x,y</math> dla pewnego <math>z\in  F</math>). Infimum zbioru filtrowanego <math>F</math> (jeśli  istnieje) oznaczamy <math>\bigwedge_{\downarrow} F</math>.
Linia 86: Linia 86:
 
{{definicja|12.4 [dziedzina]|| Poset <math>P</math> nazywamy '''dziedziną''' lub '''dziedziną ciągłą''', jeśli jest ciągłym dcpo. }}
 
{{definicja|12.4 [dziedzina]|| Poset <math>P</math> nazywamy '''dziedziną''' lub '''dziedziną ciągłą''', jeśli jest ciągłym dcpo. }}
  
Dziedziną algebraiczną nazywamy każdy dcpo algebraiczny <math>P</math>. Poset <math>P</math> jest dziedziną <math>\omega</math>-'''ciągłą''', jeśli posiada przeliczalną bazę. Dziedzina algebraiczna z przeliczalną bazą jest nazywana dziedziną '''<math>\omega</math>-algebraiczną''' lub '''dziedziną Scotta'''. (Zauważmy, że na to by dziedzina algebraiczna <math>P</math> była <math>\omega</math>-algebraiczna potrzeba i wystarcza, by baza <math>K(P)</math> była przeliczalna. Dowód tego stwierdzenia jest bardzo prosty i wynika z dwóch faktów: z tego, że  <math>K(P)\subseteq B</math> dla każdej bazy <math>B</math>  dziedziny <math>P</math> oraz z tego, że w dowolnym posecie każdy  nadzbiór bazy jest również bazą.)
+
Dziedziną algebraiczną nazywamy każdy dcpo algebraiczny <math>P</math>. Poset <math>P</math> jest dziedziną <math>\omega</math>-'''ciągłą''', jeśli posiada przeliczalną bazę. Dziedzina algebraiczna z przeliczalną bazą jest nazywana dziedziną '''<math>\omega</math>-algebraiczną''' lub '''dziedziną Scotta'''. (Zauważmy, że na to, by dziedzina algebraiczna <math>P</math> była <math>\omega</math>-algebraiczna potrzeba i wystarcza, by baza <math>K(P)</math> była przeliczalna. Dowód tego stwierdzenia jest bardzo prosty i wynika z dwóch faktów: z tego, że  <math>K(P)\subseteq B</math> dla każdej bazy <math>B</math>  dziedziny <math>P</math> 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:
 
Rozważmy następujące sztandarowe przykłady zbiorów częściowo uporządkowanych:
Linia 133: Linia 133:
  
  
{{przyklad|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 <math>\mathbf{I} \mathbb{R}</math>. Poset <math>\mathbf{I} \mathbb{R}</math> jest izomorficzny z <math>\mathbf{I}[0,1]</math>, więc posiada dokładnie te same cechy co <math>\mathbf{I}[0,1]</math>. }}
+
{{przyklad|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 <math>\mathbf{I} \mathbb{R}</math>. Poset <math>\mathbf{I} \mathbb{R}</math> jest izomorficzny z <math>\mathbf{I}[0,1]</math>, więc posiada dokładnie te same cechy co <math>\mathbf{I}[0,1]</math>. }}
  
  
Linia 169: Linia 169:
 
==Dziedziny jako topologie==
 
==Dziedziny jako topologie==
  
'''Topologią''' na zbiorze <math>X</math> nazywamy dowolną rodzinę <math>\tau</math> podzbiorów zbioru <math>X</math> zamkniętą zewzględu na skończone przecięcia i dowolne sumy, a parę <math>(X,\tau)</math> 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 <math>\tau</math> porządku  <math>(\mathcal{P}(X),\subseteq)</math> zamknięty ze względu na dowolne suprema i skończone infima. O elementach  <math>\tau</math> 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 <math>\Omega(X) = (\tau, \subseteq)</math> jest kratą, w której istnieją wszystkie suprema. To znaczy, ze <math>\Omega(X)</math> jest w rzeczywistości kratą zupełną, ponieważ infimum dowolnego  podzbioru <math>\mathcal{M}</math> zbioru <math>\tau</math> jest równe supremum zbioru wszystkich ograniczeń dolnych  <math>\mathcal{M}</math>. W szczególności, każda topologia na zbiorze <math>X</math> zawiera zbiór pusty (który jest równy  <math>\bigvee \mathcal{M}</math> dla <math>\mathcal{M} = \emptyset</math>) i całą przestrzeń <math>X</math> (<math>=  \bigwedge \emptyset</math>).
+
'''Topologią''' na zbiorze <math>X</math> nazywamy dowolną rodzinę <math>\tau</math> podzbiorów zbioru <math>X</math> zamkniętą zewzględu na skończone przecięcia i dowolne sumy, a parę <math>(X,\tau)</math> 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 <math>\tau</math> porządku  <math>(\mathcal{P}(X),\subseteq)</math> zamknięty ze względu na dowolne suprema i skończone infima. O elementach  <math>\tau</math> 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 <math>\Omega(X) = (\tau, \subseteq)</math> jest kratą, w której istnieją wszystkie suprema. To znaczy, że <math>\Omega(X)</math> jest w rzeczywistości kratą zupełną, ponieważ infimum dowolnego  podzbioru <math>\mathcal{M}</math> zbioru <math>\tau</math> jest równe supremum zbioru wszystkich ograniczeń dolnych  <math>\mathcal{M}</math>. W szczególności, każda topologia na zbiorze <math>X</math> zawiera zbiór pusty (który jest równy  <math>\bigvee \mathcal{M}</math> dla <math>\mathcal{M} = \emptyset</math>) i całą przestrzeń <math>X</math> (<math>=  \bigwedge \emptyset</math>).
  
 
Jeśli <math>\tau = \mathcal{P}(X)</math>, to <math>\tau</math> nazywamy '''topologią dyskretną'''; jeśli <math>\tau = \{\emptyset, X\}</math>, to <math>\tau</math> nazywamy '''topologią trywialną}.
 
Jeśli <math>\tau = \mathcal{P}(X)</math>, to <math>\tau</math> nazywamy '''topologią dyskretną'''; jeśli <math>\tau = \{\emptyset, X\}</math>, to <math>\tau</math> nazywamy '''topologią trywialną}.
  
Niech <math>(X,\tau)</math> będzie przestrzenią topologiczną. '''Otoczeniem'''punktu <math>x\in X</math> nazywamy dowolny zbiór <math>A</math> taki, że <math>x\in U\subseteq A</math> dla pewnego <math>U\in \tau</math>. Można łatwo pokazać, że dowolny podzbiór <math>B</math> zbioru <math>X</math> jest otwarty (to znaczy <math>B\in \tau</math>) wtedy i tylko wtedy, gdy <math>B</math> jest otoczeniem każdego swojego elementu. Zbiór otoczeń <math>x\in X</math> oznaczymy <math>\mathcal{N}(x)</math>. Jak łatwo zauważyć, zbiór <math>\mathcal{N}(x)</math> jest filtrem w kracie <math>(\mathcal{P}(X), \subseteq)</math> i dlatego nazywamy go  często '''filtrem otoczeń punktu <math>x</math>'''. Zauważmy też,  że dla dowolnego <math>x\in X</math>, filtr otoczeń <math>\mathcal{N}(x)</math> jest wyznaczony jednoznacznie, a wiec  w rzeczywistości odwzorowanie <math>\mathcal{N}\colon X\to  \mathcal{P}(\mathcal{P}(X))</math> dane przez
+
Niech <math>(X,\tau)</math> będzie przestrzenią topologiczną. '''Otoczeniem'''punktu <math>x\in X</math> nazywamy dowolny zbiór <math>A</math> taki, że <math>x\in U\subseteq A</math> dla pewnego <math>U\in \tau</math>. Można łatwo pokazać, że dowolny podzbiór <math>B</math> zbioru <math>X</math> jest otwarty (to znaczy <math>B\in \tau</math>) wtedy i tylko wtedy, gdy <math>B</math> jest otoczeniem każdego swojego elementu. Zbiór otoczeń <math>x\in X</math> oznaczymy <math>\mathcal{N}(x)</math>. Jak łatwo zauważyć, zbiór <math>\mathcal{N}(x)</math> jest filtrem w kracie <math>(\mathcal{P}(X), \subseteq)</math> i dlatego nazywamy go  często '''filtrem otoczeń punktu <math>x</math>'''. Zauważmy też,  że dla dowolnego <math>x\in X</math>, filtr otoczeń <math>\mathcal{N}(x)</math> jest wyznaczony jednoznacznie, a więc w rzeczywistości odwzorowanie <math>\mathcal{N}\colon X\to  \mathcal{P}(\mathcal{P}(X))</math> dane przez
  
 
<center><math>x\mapsto \{A\subseteq X \mid (\exists U\in  \tau)(x\in U\subseteq A)\}</math></center>
 
<center><math>x\mapsto \{A\subseteq X \mid (\exists U\in  \tau)(x\in U\subseteq A)\}</math></center>
Linia 185: Linia 185:
 
jest dobrze określoną funkcją. Ponadto, zbiór <math>O\subseteq  X</math> jest otwarty wtedy i tylko wtedy, gdy <math>O=\mathbf{int}(O)</math>, to znaczy, gdy <math>O</math>  jest punktem stałym odwzorowania <math>\mathbf{int}\colon \mathcal{P}(X)\to \mathcal{P}(X)</math>. Co więcej, <math>\tau = \{\mathbf{int}(A)\mid A\subseteq X\}</math>.
 
jest dobrze określoną funkcją. Ponadto, zbiór <math>O\subseteq  X</math> jest otwarty wtedy i tylko wtedy, gdy <math>O=\mathbf{int}(O)</math>, to znaczy, gdy <math>O</math>  jest punktem stałym odwzorowania <math>\mathbf{int}\colon \mathcal{P}(X)\to \mathcal{P}(X)</math>. Co więcej, <math>\tau = \{\mathbf{int}(A)\mid A\subseteq X\}</math>.
  
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 <math>\Gamma(X)</math>. Ponieważ <math>\Gamma(X)</math> jest podzbiorem <math>\mathcal{P}(X)</math> zamkniętym ze względu na  dowolne infima, więc dla dowolnego <math>A\subseteq X</math>  istnieje najmniejszy zbiór domknięty zawierający <math>A</math>,  który jest niczym innym, jak tylko infimum zbioru ograniczeń  górnych <math>A</math> w <math>\Gamma(X)</math> (czyli przecięciem wszystkich domkniętych nadzbiorów <math>A</math>).  Zbiór ten oznaczamy <math>\mathbf{cl}_{\tau}(A)</math> albo po  prostu <math>\mathbf{cl}(A)</math> jeśli <math>\tau</math> jest  ustalona. Podobnie, jak w przypadku operacji wnętrza,  odwzorowanie <math>\mathbf{cl} \colon \mathcal{P}(X)\to  \mathcal{P}(X)</math> jest dobrze określoną funkcją, a zbiór  <math>C\subseteq X</math> jest domknięty wtedy i tylko wtedy, gdy  jest punktem stałym odwzorowania <math>\mathbf{cl}</math>, to  jest gdy <math>C = \mathbf{cl}(C)</math>.
+
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 <math>\Gamma(X)</math>. Ponieważ <math>\Gamma(X)</math> jest podzbiorem <math>\mathcal{P}(X)</math> zamkniętym ze względu na  dowolne infima, więc dla dowolnego <math>A\subseteq X</math>  istnieje najmniejszy zbiór domknięty zawierający <math>A</math>,  który jest niczym innym, jak tylko infimum zbioru ograniczeń  górnych <math>A</math> w <math>\Gamma(X)</math> (czyli przecięciem wszystkich domkniętych nadzbiorów <math>A</math>).  Zbiór ten oznaczamy <math>\mathbf{cl}_{\tau}(A)</math> albo po  prostu <math>\mathbf{cl}(A)</math>, jeśli <math>\tau</math> jest  ustalona. Podobnie, jak w przypadku operacji wnętrza,  odwzorowanie <math>\mathbf{cl} \colon \mathcal{P}(X)\to  \mathcal{P}(X)</math> jest dobrze określoną funkcją, a zbiór  <math>C\subseteq X</math> jest domknięty wtedy i tylko wtedy, gdy  jest punktem stałym odwzorowania <math>\mathbf{cl}</math>, to  jest, gdy <math>C = \mathbf{cl}(C)</math>.
  
  
Linia 193: Linia 193:
 
Niech <math>(X,\tau)</math> będzie przestrzenią topologiczną. '''Bazą'''topologii <math>\tau</math> nazywamy każdą podrodzinę <math>\beta\subseteq \tau</math> taką, że dla każdego otoczenia <math>A</math> punktu <math>x</math> istnieje <math>B\in\beta</math> taki, że <math>x\in B\subseteq A</math>. W szczególności, cała rodzina <math>\tau</math> jest bazą topologii <math>\tau</math>.
 
Niech <math>(X,\tau)</math> będzie przestrzenią topologiczną. '''Bazą'''topologii <math>\tau</math> nazywamy każdą podrodzinę <math>\beta\subseteq \tau</math> taką, że dla każdego otoczenia <math>A</math> punktu <math>x</math> istnieje <math>B\in\beta</math> taki, że <math>x\in B\subseteq A</math>. W szczególności, cała rodzina <math>\tau</math> jest bazą topologii <math>\tau</math>.
  
Przypomnijmy, że jeśli <math>P</math> jest częściowym porządkiem, to jego podzbiory <math>A,B</math> są '''współkońcowe''' jeśli <math>\downarrow A = \downarrow B</math>. Ponadto, jeśli <math>A\subseteq B</math> oraz <math>\downarrow A = \downarrow  B</math> to mówimy, że '''<math>A</math> jest współkońcowy w  <math>B</math>'''. Rozważmy więc kratę <math>(\mathcal{P}(X), \supseteq)</math> dla przestrzeni topologicznej  <math>(X,\tau)</math>. W tej kracie rodzina <math>\mathcal{N}(x)</math> dla dowolnego <math>x\in X</math> jest zbiorem skierowanych. Zauważmy, że podrodzina  <math>\beta</math> topologii <math>\tau</math> na <math>X</math>  jest bazą wtedy i tylko wtedy, gdy dla każdego <math>x\in  X</math>, zbiór <math>\beta(x)</math> jest współkońcowy w  <math>\mathcal{N}(X)</math>, gdzie <math>\beta(x) = \{B\in  \beta\mid x\in B\}</math>.
+
Przypomnijmy, że jeśli <math>P</math> jest częściowym porządkiem, to jego podzbiory <math>A,B</math> są '''współkońcowe''', jeśli <math>\downarrow A = \downarrow B</math>. Ponadto, jeśli <math>A\subseteq B</math> oraz <math>\downarrow A = \downarrow  B</math>, to mówimy, że '''<math>A</math> jest współkońcowy w  <math>B</math>'''. Rozważmy więc kratę <math>(\mathcal{P}(X), \supseteq)</math> dla przestrzeni topologicznej  <math>(X,\tau)</math>. W tej kracie rodzina <math>\mathcal{N}(x)</math> dla dowolnego <math>x\in X</math> jest zbiorem skierowanym. Zauważmy, że podrodzina  <math>\beta</math> topologii <math>\tau</math> na <math>X</math>  jest bazą wtedy i tylko wtedy, gdy dla każdego <math>x\in  X</math>, zbiór <math>\beta(x)</math> jest współkońcowy w  <math>\mathcal{N}(X)</math>, gdzie <math>\beta(x) = \{B\in  \beta\mid x\in B\}</math>.
  
 
==Zbiory zwarte==
 
==Zbiory zwarte==
Linia 204: Linia 204:
 
W dowolnej przestrzeni topologicznej <math>(X,\tau)</math> możemy zdefiniować relację przechodnią i zwrotną między elementami <math>x,y\in X</math> w następujący sposób: {{wzor|spec||<math>x\sqsubseteq_{\tau} y \iff (\forall U\in \tau)(x\in U\Rightarrow  y\in U),</math>}} którą nazywamy '''preporządkiem specjalizacji'''. Mówimy, że przestrzeń topologiczna <math>X</math> spełnia '''aksjomat oddzielania'''<math>T_0</math> (lub: jest przestrzenią <math>T_0</math>) jeśli <math>\sqsubseteq_{\tau}</math> jest  częściowym porządkiem, to znaczy wtedy i tylko wtedy, gdy  <math>\sqsubseteq_{\tau}</math> jest relacją antysymetryczną.  Dalej, mówimy, że przestrzeń topologiczna <math>X</math> spełnia  '''aksjomat oddzielania <math>T_1</math>''' (jest przestrzenią  <math>T_1</math>) wtedy i tylko wtedy, gdy  <math>\sqsubseteq_{\tau}</math> redukuje się do równości.  Oczywiście definicje powyższe implikują, że każda przestrzeń  <math>T_1</math> jest <math>T_0</math>, ale nie jest odwrotnie,  jak pokazuje przykład topologii <math>\{\emptyset, \{1\}, \{0,1\}  \}</math> na zbiorze dwuelementowym <math>\{0,1\}</math>.
 
W dowolnej przestrzeni topologicznej <math>(X,\tau)</math> możemy zdefiniować relację przechodnią i zwrotną między elementami <math>x,y\in X</math> w następujący sposób: {{wzor|spec||<math>x\sqsubseteq_{\tau} y \iff (\forall U\in \tau)(x\in U\Rightarrow  y\in U),</math>}} którą nazywamy '''preporządkiem specjalizacji'''. Mówimy, że przestrzeń topologiczna <math>X</math> spełnia '''aksjomat oddzielania'''<math>T_0</math> (lub: jest przestrzenią <math>T_0</math>) jeśli <math>\sqsubseteq_{\tau}</math> jest  częściowym porządkiem, to znaczy wtedy i tylko wtedy, gdy  <math>\sqsubseteq_{\tau}</math> jest relacją antysymetryczną.  Dalej, mówimy, że przestrzeń topologiczna <math>X</math> spełnia  '''aksjomat oddzielania <math>T_1</math>''' (jest przestrzenią  <math>T_1</math>) wtedy i tylko wtedy, gdy  <math>\sqsubseteq_{\tau}</math> redukuje się do równości.  Oczywiście definicje powyższe implikują, że każda przestrzeń  <math>T_1</math> jest <math>T_0</math>, ale nie jest odwrotnie,  jak pokazuje przykład topologii <math>\{\emptyset, \{1\}, \{0,1\}  \}</math> na zbiorze dwuelementowym <math>\{0,1\}</math>.
  
Nazwy ''aksjomaty oddzielania'' pochodzą stąd, że w  przestrzeniach topologicznych o własnościach <math>T_0</math> czy  <math>T_1</math> zbiory otwarte ''oddzielają punkty'' w  odpowiedni sposób. W dalszej części wykładu będziemy mówić  głównie o przestrzeniach <math>T_0</math>, które nie są  przestrzeniami <math>T_1</math> (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ż <math>T_1</math>. Nasz  wykład będzie więc różnił się znacznie od standardowego wykładu  topologii ogólnej.
+
Nazwy ''aksjomaty oddzielania'' pochodzą stąd, że w  przestrzeniach topologicznych o własnościach <math>T_0</math> czy  <math>T_1</math> zbiory otwarte ''oddzielają punkty'' w  odpowiedni sposób. W dalszej części wykładu będziemy mówić  głównie o przestrzeniach <math>T_0</math>, które nie są  przestrzeniami <math>T_1</math> (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ż <math>T_1</math>. Nasz  wykład będzie więc różnił się znacznie od standardowego wykładu  topologii ogólnej.
  
  
Linia 223: Linia 223:
  
  
{{definicja |12.14|| Niech <math>P</math> będzie częściowym porządkiem. Zbiór <math>U</math> nazywamy '''otwartym w sensie Scotta''' jeśli spełnia dwa warunki:
+
{{definicja |12.14|| Niech <math>P</math> będzie częściowym porządkiem. Zbiór <math>U</math> nazywamy '''otwartym w sensie Scotta''', jeśli spełnia dwa warunki:
  
 
* <math>U = \uparrow U</math> (<math>U</math> jest zbiorem górnym),
 
* <math>U = \uparrow U</math> (<math>U</math> jest zbiorem górnym),

Aktualna wersja na dzień 12:29, 27 lis 2006

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 -rachunku. Aby stworzyć semantykę tego języka, należy zaproponować pewną kategorię składającą się z obiektów typu w taki sposób, aby termy -rachunku były interpretowane jako elementy , zaś aplikacja funkcji do argumentu była rozumiana jako aplikacja strzałki do argumentu typu . Jeśli teraz rozważymy -term , widzimy, że pierwsze wolne wystąpienie musi być typu , zaś drugie typu . A zatem musimy wymagać, by . 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ę , która jest zwrotna, przechodnia i antysymetryczna.

Niech będzie częściowym porządkiem. Element jest ograniczeniem górnym zbioru , jeśli dla każdego (co zapisujemy również ). Podobnie, element jest ograniczeniem dolnym zbioru , jeśli dla każdego (czyli ). Jeśli dwa dowolne elementy posiadają w ograniczenie górne, to oznaczamy to jako . W przeciwnym wypadku piszemy . Najmniejsze ograniczenie górne zbioru (jeśli istnieje) nazywamy supremum i oznaczamy . Największe ograniczenie dolne zbioru (jeśli istnieje) nazywamy infimum i oznaczamy . Jeśli jest dwuelementowy, np. , i posiada supremum (infimum), to piszemy () i mówimy o supremum (infimum) binarnym.

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 porządku nazywamy skierowanym, co oznaczamy , jeśli jest niepusty i każde dwa elementy z posiadają ograniczenie górne w (tzn. i dla pewnego ). Łańcuchem nazywamy każdy zbiór skierowany, który jest liniowy. Supremum zbioru skierowanego oznaczamy , kiedykolwiek istnieje. Podzbiór porządku nazywamy filtrowanym, jeśli jest niepusty i każde dwa elementy z posiadają ograniczenie dolne w (tzn. i dla pewnego ). Infimum zbioru filtrowanego (jeśli istnieje) oznaczamy .

Poset nazywamy -zupełnym, jeśli posiada element najmniejszy oraz każde dwa elementy takie, że , posiadają supremum .

Oznaczamy:





jest zbiorem dolnym, jeśli . jest zbiorem górnym, jeśli . jest ideałem, jeśli jest skierowany i dolny. jest filtrem, jeśli jest filtrowany i górny. Ideałem głównym nazywamy każdy ideał postaci dla . Filtrem głównym jest każdy filtr postaci dla pewnego .

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

W każdym zbiorze częściowo uporządkowanym możemy zdefiniować relację aproksymacji (ang. way-below relation) w następujący sposób: dla mamy (czytamy: aproksymuje lub jest skończony względem ) wtedy i tylko wtedy, gdy dla każdego zbioru skierowanego takiego, że mamy dla pewnego . W jednym zdaniu:

Element nazywamy zwartym lub skończonym, gdy . Zbiór wszystkich elementów zwartych posetu oznaczamy zwykle . Dla relacji przyjmujemy podobne oznaczenia, jak dla porządku:





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

  • ,
  • ,
  • .


Bazą posetu nazywamy każdy podzbiór taki, że dla każdego zbiór jest skierowany i posiada supremum .

Definicja 12.1

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


Twierdzenie 12.2

Poset jest ciągły wtedy i tylko wtedy, gdy dla każdego , zbiór jest skierowany i mamy .

Dowód

Niech będzie ciągły i będzie bazą dla . Niech będzie dowolnym elementem . Pokażemy, że jest zbiorem skierowanym i jego supremum to . Niech . Skoro z założenia zbiór jest skierowany z supremum , to z definicji relacji aproksymacji istnieją dwa elementy takie, że oraz . Ale ze skierowania zbioru wynika istnienie elementu takiego, że oraz . A zatem z własności (w2) mamy , czyli wykazaliśmy, że zbiór jest skierowany. Zauważmy, że jest ograniczeniem górnym zbioru . Jeśli jest dowolnym innym ograniczeniem górnym, to skoro , to . A zatem . Z drugiej strony, jeśli jest dowolnym posetem takim, że , to jest bazą, a więc jest ciągły. End of proof.gif

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

Twierdzenie 12.3 [interpolatywność aproksymacji]

Jeśli poset jest ciągły, to relacja aproksymacji posiada własność interpolacji:
  • .


Definicja 12.4 [dziedzina]

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

Dziedziną algebraiczną nazywamy każdy dcpo algebraiczny . Poset jest dziedziną -ciągłą, jeśli posiada przeliczalną bazę. Dziedzina algebraiczna z przeliczalną bazą jest nazywana dziedziną -algebraiczną lub dziedziną Scotta. (Zauważmy, że na to, by dziedzina algebraiczna była -algebraiczna potrzeba i wystarcza, by baza była przeliczalna. Dowód tego stwierdzenia jest bardzo prosty i wynika z dwóch faktów: z tego, że dla każdej bazy dziedziny 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 jest dcpo, ponieważ każdy jego podzbiór skierowany posiada element największy. Co więcej, każdy element jest zwarty, a więc jest dziedziną Scotta.

Przykład 12.6 [liczby naturalne]

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


Przykład 12.7 [odcinek]

Odcinek z naturalnym porządkiem jest ciągły, co łatwo wynika z faktu, że wtedy i tylko wtedy, gdy lub . Jest to również krata zupełna, a więc w szczególności dziedzina ciągła i poset -zupełny.
Tk-12.2.png


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

Niech będzie dowolnym zbiorem. Zbiór potęgowy jest kratą zupełną i dla każdego mamy i . jest więc w szczególności dcpo i -zupełny. Najmniejszym elementem jest , a największym .
Tk-12.3.png

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

i tenże zbiór jest skierowany, istnieje taki, że . Zbiór jest więc skończony, jako podzbiór zbioru skończonego .

Załóżmy, że . Przypuśćmy, że dla pewnego zbioru skierowanego w . Mamy więc , co oznacza, że dla każdego istnieje taki, że . Ponieważ jest skierowany, istnieje , który zawiera wszystkie zbiory . To oznacza, że , co należało pokazać.


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

Niech oznacza zbiór wszystkich podprzedziałów domkniętych, niepustych przedziału uporządkowany względem odwrotnej inkluzji, to znaczy:

dla . Poset jest dcpo, -zupełny, -ciągły i nie jest algebraiczny. Elementem najmniejszym jest , a element największy nie istnieje. Elementami maksymalnymi są wszystkie przedziały postaci dla , które utożsamiamy w sposób naturalny z liczbami rzeczywistymi z odcinka . Relacja aproksymacji jest dana jako:

Bazą przeliczalną w jest rodzina wszystkich podprzedziałów odcinka o końcach wymiernych.

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 . Poset jest izomorficzny z , więc posiada dokładnie te same cechy co .


Przykład 12.11 [dziedzina kul]

Niech będzie przestrzenią metryczną. Rozważmy rodzinę wszystkich par postaci , gdzie i i zdefiniujmy relację w następujący sposób:

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

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

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

Tk-12.5.png


Przykład 12.12 [model zbioru Cantora]

Zbiór wszystkich skończonych i nieskończonych ciągów zerojedynkowych (oczywiście ) w porządku prefiksowym jest dziedziną Scotta. Każdy zbiór skierowany jest łańcuchem. Elementem najmniejszym jest ciąg pusty . 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 , który nie jest maksymalny, jest zwarty.
Tk-12.6.png

Funkcje monotoniczne

Funkcję między posetami nazywamy monotoniczną, jeśli zachowuje porządek, tj. jeśli w , to w . Funkcja jest ciągła, jeśli zachowuje suprema zbiorów skierowanych, to znaczy: jeśli jest skierowany i posiada supremum , to posiada supremum . Zauważmy, że każda funkcja ciągła jest monotoniczna. Rzeczywiście, jeśli w , to zbiór jest skierowany i ma supremum . Tak więc . Z kolei, monotoniczność implikuje, że dla skierowanego, zbiór jest również skierowany. Wnioskujemy więc, że funkcja jest ciągła wtedy i tylko wtedy, gdy dla dowolnego zbioru skierowanego posiadającego supremum, zbiór jest skierowany oraz zachodzi .

Uwaga
Jeśli funkcja monotoniczna jest traktowana kategoryjnie, jako funktor między kategoriami i , 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 nazywamy dowolną rodzinę podzbiorów zbioru zamkniętą zewzględu na skończone przecięcia i dowolne sumy, a parę 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 porządku zamknięty ze względu na dowolne suprema i skończone infima. O elementach 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 jest kratą, w której istnieją wszystkie suprema. To znaczy, że jest w rzeczywistości kratą zupełną, ponieważ infimum dowolnego podzbioru zbioru jest równe supremum zbioru wszystkich ograniczeń dolnych . W szczególności, każda topologia na zbiorze zawiera zbiór pusty (który jest równy dla ) i całą przestrzeń ().

Jeśli , to nazywamy topologią dyskretną; jeśli , to nazywamy topologią trywialną}.

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

jest dobrze określoną funkcją.

Niech będzie przestrzenią topologiczną i niech . Wnętrzem zbioru nazywamy największy zbiór otwarty zawarty w , który będziemy oznaczać dalej jako lub po prostu , jeśli jest jasne o jakiej topologii jest właśnie mowa. Zauważmy, że odwzorowanie dane przez

jest dobrze określoną funkcją. Ponadto, zbiór jest otwarty wtedy i tylko wtedy, gdy , to znaczy, gdy jest punktem stałym odwzorowania . Co więcej, .

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 . Ponieważ jest podzbiorem zamkniętym ze względu na dowolne infima, więc dla dowolnego istnieje najmniejszy zbiór domknięty zawierający , który jest niczym innym, jak tylko infimum zbioru ograniczeń górnych w (czyli przecięciem wszystkich domkniętych nadzbiorów ). Zbiór ten oznaczamy albo po prostu , jeśli jest ustalona. Podobnie, jak w przypadku operacji wnętrza, odwzorowanie jest dobrze określoną funkcją, a zbiór jest domknięty wtedy i tylko wtedy, gdy jest punktem stałym odwzorowania , to jest, gdy .


Bazy w przestrzeniach topologicznych

Niech będzie przestrzenią topologiczną. Bazątopologii nazywamy każdą podrodzinę taką, że dla każdego otoczenia punktu istnieje taki, że . W szczególności, cała rodzina jest bazą topologii .

Przypomnijmy, że jeśli jest częściowym porządkiem, to jego podzbiory współkońcowe, jeśli . Ponadto, jeśli oraz , to mówimy, że jest współkońcowy w . Rozważmy więc kratę dla przestrzeni topologicznej . W tej kracie rodzina dla dowolnego jest zbiorem skierowanym. Zauważmy, że podrodzina topologii na jest bazą wtedy i tylko wtedy, gdy dla każdego , zbiór jest współkońcowy w , gdzie .

Zbiory zwarte

Podzbiór przestrzeni topologicznej nazywamy zwartym, jeśli dowolne pokrycie zbiorami otwartymi zawiera podpokrycie skończone, to jest: jeśli dla dowolnej rodziny , to istnieje podrodzina taka, że . W praktyce będziemy mieli bardzo często do czynienia z rodzinami indeksowanymi, więc definicja zwartości upraszcza się do następującej: jest zwarty wtedy i tylko wtedy, gdy dla implikuje dla , gdzie .


Porządek specjalizacji i aksjomaty oddzielania

W dowolnej przestrzeni topologicznej możemy zdefiniować relację przechodnią i zwrotną między elementami w następujący sposób:

     ()

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

Nazwy aksjomaty oddzielania pochodzą stąd, że w przestrzeniach topologicznych o własnościach czy zbiory otwarte oddzielają punkty w odpowiedni sposób. W dalszej części wykładu będziemy mówić głównie o przestrzeniach , które nie są przestrzeniami (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ż . 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 będą przestrzeniami topologicznymi. Mówimy, że funkcja jest ciągła wtedy i tylko wtedy, gdy dla każdego zbioru otwartego w , przeciwobraz jest otwarty w (tj. )).


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 będzie częściowym porządkiem. Zbiór nazywamy otwartym w sensie Scotta, jeśli spełnia dwa warunki:
  • ( jest zbiorem górnym),
  • Jeśli dla zbioru skierowanego mamy , to istnieje element taki, że .
O zbiorze mającym własność (S2) mówimy, że jest nieosiągalny przez suprema zbiorów skierowanych. Rodzinę zbiorów otwartych w sensie Scotta oznaczamy lub po prostu .


Twierdzenie 12.15

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

Dowód

Niech . Pokażemy, że . Jest oczywiste, że jest zbiorem górnym, więc pokażemy tylko własność (S2). Niech będzie dowolnym zbiorem skierowanym w , który posiada supremum . Jeśli , to i , a więc istnieją elementy i . Ale jest skierowany, więc istnieje taki, że . Ponieważ i są zbiorami górnymi, , co należało pokazać. Niech będzie dowolną rodziną zbiorów otwartych. Jest jasne, że jest zbiorem górnym. Następnie, jeśli dla , to dla pewnego . A zatem istnieje taki, że . Element należy więc do , a więc , czego należało dowieść. End of proof.gif

Można pokazać, że zbiór 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 dla .

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


Twierdzenie 12.16

Niech będzie częściowym porządkiem. Dla dowolnych elementów następujące warunki są równoważne:
  • ,
  • ,
  • .

Co więcej, topologia Scotta jest .


Dowód

(1)(2) wynika z tego, że zbiory otwarte są górne. (2)(3): przypuśćmy, że . Wówczas istnieje domknięty w sensie Scotta, taki, że i . A zatem dla zbioru otwartego mamy i . To znaczy, że Parser nie mógł rozpoznać (nieznana funkcja „\nepod”): {\displaystyle x\nepod_{\sigma} y} , co należało pokazać (3)(1): ponieważ ideał jest domknięty w sensie Scotta i zawiera , więc , a zatem . Własność wynika z równoważności (1) i (2) powyżej. End of proof.gif

Topologia Scotta na dziedzinach

Niech będzie porządkiem ciągłym. Łatwo pokazać, że w topologii Scotta na mamy dla każdego . Lecz o tej sytuacji możemy powiedzieć nawet więcej:


Twierdzenie 12.17

Niech będzie porządkiem ciągłym, a jego bazą. Wówczas rodzina jest bazą dla topologii Scotta.

Dowód

Wiemy już, że elementy są zbiorami otwartymi w sensie Scotta. Niech dla dowolnego i . Skoro jest skierowany z supremum , to z otwartości wynika, że istnieje . A zatem dla pewnego , co należało pokazać. 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 będą posetami. Dla funkcji następujące warunki są równoważne:
  • jest ciągła,
  • jest funkcją ciągłą między topologiami i .

Dowód

Niech będzie ciągła i . Ponieważ funkcje ciągłe są monotoniczne, jest zbiorem górnym. Jeśli dla pewnego zbioru skierowanego , to , to istnieje taki, że . To oznacza, że , co należało pokazać. Z drugiej strony, załóżmy, że jest ciągła w sensie Scotta. Niech w . Wtedy jest zbiorem domkniętym w sensie Scotta zawierającym , a więc zbiór ten musi zawierać również . To daje . Funkcja jest więc monotoniczna. Niech będzie skierowany. Rozważmy przeciwobraz zbioru domkniętego . Jest on domknięty w i zawiera , a więc musi też zawierać . Pokazaliśmy, że , czyli . Ale monotoniczność implikuje, że , co należało pokazać. End of proof.gif