Teoria kategorii dla informatyków/Ćwiczenia 12: Teoria dziedzin I

From Studia Informatyczne

==Zadanie 12.1==

Niech (P,\leq) będzie częściowym porządkiem i niech A,B\subseteq P. Pokaż, że jeśli \downarrow A = \downarrow B to \bigvee A istnieje wtedy i tylko wtedy, gdy \bigvee B istnieje i w obu przypadkach te suprema są sobie równe.

Wskazówka:

Wystarczy pokazać, że dowolne ograniczenie górne zbioru A jest ograniczeniem górnym zbioru B.

Rozwiązanie:

Niech A\leq u dla pewnego u\in P. Wówczas dla x\in \downarrow A mamy x\leq a dla a\in A<ath> i co za tym idzie <math>x\leq u. Pokazaliśmy, że \downarrow A\leq u. A zatem B\subseteq \downarrow B=\downarrow A\leq u. Udowodniliśmy więc, że dowolne ograniczenie górne u zbioru A jest ograniczeniem górnym zbioru B. A zatem najmniejsze ograniczenie górne (jeśli istnieje) zbioru A jest najmniejszym ograniczeniem górnym zbioru B, co kończy dowód.


==Zadanie 12.2==

Niech \mathcal{D} będzie skierowaną przez inkluzję rodziną skierowanych podzbiorów posetu (P,\leq). Udowodnij, że \bigcup \mathcal{D} jest skierowanym podzbiorem P.

Wskazówka:

Nie zapomnijmy o wykazaniu niepustości \bigcup \mathcal{D}.

Rozwiązanie:

Jeśli D\in \mathcal{D}, to istnieje x\in D, bo D niepusty. A zatem x\in \bigcup \mathcal{D}, co świadczy o niepustości tego zbioru.

Niech teraz a,b\in \bigcup \mathcal{D}. Wówczas istnieją D_a, D_b\in \mathcal{D} takie, że odpowiednio a\in D_a oraz b\in D_b. Skoro rodzina \mathcal{D} jest skierowana przez inkluzję, to istnieje D\in \mathcal{D} taki, że D_a, D_b\subseteq D, co daje nam a,b\in D. Ponieważ D jest skierowanym podzbiorem P, istnieje z\in D\subseteq \bigcup \mathcal{D} taki, że a,b\leq z. A to świadczy o tym, że zbiór \bigcup \mathcal{D} jest skierowany.


==Zadanie 12.3==

Niech (A_i)_{i\in I} będzie dowolną indeksowaną rodziną podzbiorów częściowego porządku (P,\leq) posiadających suprema w P. Pokaż, że zbiory \{\bigvee A_i\mid i\in I\} oraz \bigcup_{i\in I} A_i mają te same ograniczenia górne (a co za tym suprema, o ile chociaż jedno z nich istnieje).

Wskazówka:

Zauważmy, że dowolne ograniczenie górne pierwszego ze zbiorów jest ograniczeniem górnym dla każdego ze zbiorów A_i.

Rozwiązanie:

Niech \{\bigvee A_i\mid i\in I\}\leq u dla pewnego u\in P. Wówczas dla każdego i\in I mamy A_i\leq u, co daje \bigcup A_i\leq u. Rozumowanie powyższe daje się odwrócić, więc tak naprawdę pokazaliśmy, że \{\bigvee A_i\mid i\in I\}\leq u wtedy i tylko wtedy, gdy \bigcup A_i\leq u, co kończy dowód.


==Zadanie 12.4==

Niech (P,\leq) będzie częściowym porządkiem, A,B\subseteq P oraz \downarrow A = \downarrow B. Udowodnij, że A jest skierowany wtedy i tylko wtedy, gdy B jest skierowany. Wyciągnij wniosek, że dowolny podzbiór X posetu P jest skierowany wtedy i tylko wtedy, gdy jego domknięcie dolne \downarrow X jest skierowany.

Rozwiązanie:

Przypuśćmy, że A jest skierowany. Wówczas istnieje a\in A. Oczywiście a\in A\subseteq \downarrow A = \downarrow B, co oznacza, że a\in \downarrow B. A zatem istnieje b\in B taki, że a\leq b. W szczególności, B jest zbiorem niepustym.

Podobnie wnioskując, zauważamy, że jeśli b_1, a_2\in A, to istnieją a_1, a_2\in A takie, że b_1\leq a_1 oraz b_2\leq a_2. Ponieważ A jest skierowany, istnieje a\in A taki, że a_1, a_2\leq a. W szczególności b_1, b_2\leq a i a\in \downarrow A = \downarrow B. To znaczy, że istnieje b \in B taki, że a\leq b, a co za tym idzie b_1, b_2\leq b. Zbiór B jest więc skierowany. Z symetrii założeń wynika pierwsza z tez zadania.

Druga z tez wynika natychmiast z obserwacji \downarrow X = \downarrow \downarrow X.


==Zadanie 12.5==

Niech (P,\leq) będzie częściowym porządkiem. Pokaż, że jeśli D jest podzbiorem skierowanym P, który posiada supremum, zaś A pewnym podzbiorem P oraz \downarrow A = \downarrow D, to A jest skierowany i jego supremum jest równe supremum D.

Wskazówka:

Wykorzystaj Zadania 12.2 i 12.3.

Rozwiązanie:

Skoro \downarrow A = \downarrow D i \downarrow D jest skierowany, to z Zadania 12.3 wynika, że A jest skierowany, a z Zadania 12.2 wynika, że supremum A istnieje i jest równe \bigvee D.


==Zadanie 12.6==

Niech (P,\leq) będzie częściowym porządkiem. Udowodnij, że dwa poniższe warunki są równoważne: (i) każdy podzbiór P ograniczony z góry posiada supremum; (ii) każdy niepusty podzbiór P posiada infimum.

Rozwiązanie:

Załóżmy (i). Niech \emptyset \neq A\subseteq P. Niech B będzie zbiorem ograniczeń dolnych A. Oczywiście B jest ograniczony z góry przez dowolny element zbioru A. Z założenia, B osiada supremum, które jest największym ograniczeniem dolnym A, czyli jego infimum.

Podobnie, dla dowolnego zbioru C ograniczonego z góry, jego supremum jest dane jako infimum zbioru ograniczeń górnych C.

W końcu zauważmy, że poset P, w którym jeden z równoważnych warunków (i) lub (ii) jest spełniony, posiada element najmniejszy \bot, który - zgodnie z tym, co udowodniliśmy powyżej - powstaje jako supremum zbioru pustego (równoważnie: jako infimum P).


==Zadanie 12.7==

Wskaż taki częściowy porządek P, że:

  1. jest dcpo, ale nie jest bc-zupełny,
  2. jest ciągły, ale nie jest algebraiczny,
  3. jest nieciągły i jest dcpo,
  4. nie jest dcpo, ale jest ciągły,
  5. jego relacja aproksymacji jest pusta.


Wskazówka:

Warto rozważać niewielkie przykłady.

Rozwiązanie:


1. Niech P=\{\bot, x, y, z, w\} oraz niech \leq będzie przechodnim domknięciem relacji \{(\bot, x), (\bot,y), (x,z), (y,z),(x,w),(y,w)\}. Tutaj oczywiście podzbiór \{x,y\} posiada ograniczenia górne, ale nie posiada supremum.

Grafika:tk-12.7.png

2. Niech P = \omega\cup \{\top, x\}. Porządek definiujemy tak, że \top jest elementem największym, liczby z \omega są uporządkowane w sposób naturalny, zaś x jest powyżej 0, poniżej \top i nieporównywalny z żadną inną liczbą naturalną. W takim posecie nie zachodzi x = \bigvee \ll x, co już łatwo pokazać.

Grafika:tk-12.8.png

3. Poprzedni przykład wystarcza.

4. Liczby naturalne \omega.

Grafika:tk-12.1.png


5. Wystarczy wziąć dwie kopie liczb naturalnych i dołączyć element największy.

Grafika:tk-12.9.png


==Zadanie 12.8==

Pokazać, że w przestrzeni topologicznej (X,\tau), która jest T_0 zachodzi \mathbf{cl}\{x\} = \downarrow_\tau x, gdzie \leq_{\tau} jest porządkiem specjalizacji.

Wskazówka:

Topologia Scotta na dowolnym częściowym porządku jest tutaj dobrym przykładem.

Rozwiązanie:

Wystarczy zauważyć, że y\notin \mathbf{cl}\{x\} wtedy i tylko wtedy, gdy istnieje zbiór domknięty C zawierający x i taki, że y\notin C. Ale to jest równoważne stwierdzeniu, że istnieje zbiór otwarty U := X\setminus C taki, że y\in U i x\notin U lub po prostu y\notin \downarrow_{\tau} x, co należało pokazać.


==Zadanie 12.9==

Niech \sigma oznacza topologię Scotta na posecie ciągłym (P,\leq). Pokaż, że \mathbf{int}_{\sigma}(\uparrowarrow x) = \Uparrow x dla dowolnego x\in P.

Wskazówka:

Istotnym założeniem jest ciągłość posetu, która gwarantuje nam, że relacja aproksymacji jest interpolatywna (por. Twierdzenie 12.3).

Rozwiązanie:

Po pierwsze pokażmy, że \Uparrow x jest zbiorem otwartym w sensie Scotta. Z własności (w2) relacji aproksymacji łatwo wynika, że \Uparrow x jest zbiorem górnym. Jeśli teraz \bigvee D = z\in \Uparrow x dla pewnego zbioru skierowanego D\subseteq {}^{\uparrowarrow} P, to z własności interpolacji (Twierdzenie 12.3) znajdujemy x\ll w\ll z i dalej z definicji relacji aproksymacji dostajemy d\in D taki, że w\leq d. Mamy więc albo x\ll w\leq d, czyli z (w2) x\ll d, albo d\in \Uparrow x, co dowodzi, że \Uparrow x jest otwarty w sensie Scotta.

Jeśli teraz \sigma\ni U\subseteq \uparrowarrow x, to weźmy dowolny element u\in U. Ponieważ P jest ciągły, u = \bigvee  {}^{\uparrowarrow}\ll u. A zatem z otwartości U wynika, że istnieje z\in \ll u taki, że z\in U. Pokazaliśmy więc, że x\leq z\ll  u, czyli u\in \Uparrow x. Z dowolności wyboru u dostajemy U\subseteq \Uparrow x; innymi słowy, \Uparrow x jest największym zbiorem otwartym zawartym w \uparrowarrow x, czyli wnętrzem zbioru \uparrowarrow x, co należało pokazać.


==Zadanie 12.10==

Pokazać, że topologia Scotta na dowolnym posecie ciągłym ma bazę złożoną z filtrów.

Wskazówka:

Należy pamiętać (Zadanie 12.7), że w posecie ciągłym zbiory typu \Uparrow x są otwarte w topologii Scotta, ale w ogólności nie są filtrami, co pokazuje poniższy rysunek:

Grafika:tk-12.10.png

Rozwiązanie:

Niech P będzie posetem ciągłym. Weźmy zbiór otwarty U\subseteq P oraz element x\in U. Trzeba teraz pokazać, że istnieje filtr F\in \sigma(P) taki, że x\in F\subseteq U. Zbiór F konstruujemy, jak następuje: połóżmy x_0 = x. Ponieważ U jest otwarty, to istnieje x_1\ll x_0 taki, że x_1\in U. Podobnie dla dowolnego x_n\in U znajdziemy x_{n+1}\in U tak, że x_{n+1}\ll x_n. Wystarczy teraz położyć F = \bigcup_{n\in \omega}\Uparrow x_n. Jest oczywiste, że F jest zarówno zbiorem otwartym, jak i to, że jest filtrem!

Grafika:tk-12.11.png