TKI Moduł 12

Dziedziny jako częściowe porządki

Pojęcia podstawowe

Niech $(P,⊑)$ będzie częściowym porządkiem. Element $a\in P$ jest ograniczeniem górnym zbioru $X\subseteq P$, jeśli $x⊑a$ dla każdego $x\in X$ (co zapisujemy również $X⊑a$). Podobnie, element $b\in P$ jest ograniczeniem dolnym zbioru $X⊑P$, jeśli $b⊑x$ dla każdego $x\in X$ (czyli $b⊑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\mathrm{\#}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) bianarnym.

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\ne \mathrm{\varnothing }$ i $x,y\in D\Rightarrow x,y⊑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\ne \mathrm{\varnothing }$ i $x,y\in F\Rightarrow z⊑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 $\mathrm{\perp }$ 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 \mathrm{\exists }x\in X\mid z⊑x\}$

$\uparrow X=\{w\in P\mid \mathrm{\exists }x\in X\mid x⊑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 zupełnym (mówimy też: $P$ jest dcpo), 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$) wtw, gdy dla każdego zbioru skierowanego $D{\subseteq }^{\uparrow }P$ takiego, że $y⊑\bigvee {}^{\uparrow }D$ mamy $x⊑d$ dla pewnego $d\in D$. W jednym zdaniu:

$x\ll y⟺\mathrm{\forall }D{\subseteq }^{\uparrow }P(y⊑\bigvee {}^{\uparrow }D\Rightarrow (\mathrm{\exists }d\in D(x⊑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 \mathrm{\exists }x\in X\mid z\ll x\}$

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

$\Downarrow x=\Downarrow \{x\}$

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

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

(w1) $(\mathrm{\forall }x,y\in P)(x\ll y\Rightarrow x⊑y)$,

(w2) $(\mathrm{\forall }x,y,z,w\in P)(x⊑y\ll z⊑w\Rightarrow x\ll w)$,

(w3) $(\mathrm{\perp }\in P\Rightarrow (\mathrm{\forall }x\in P(\mathrm{\perp }\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. Poset $P$ jest ciągły jeśli posiada bazę. Jeśli $K(P)$ jest bazą, to mówimy, że $P$ jest algebraiczny.

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

Dowód: Niech $P$ będzie ciągły i $B$ będzie bazą dla $P$. Niech $x\in P$ bedzie 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^{\prime },b^{\prime }\in B$ takie, że $a⊑a^{\prime }\ll x$ oraz $b⊑b^{\prime }\ll x$. Ale ze skierowania zbioru $\Downarrow x\cap B$ wynika istnienie elementu $c\in B$ takiego, że $a^{\prime }⊑c\ll x$ oraz $b^{\prime }⊑c\ll x$. A zatem z własności (w2) mamy $a,b⊑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 {}^{\uparrow }(\Downarrow x\cap B)⊑z$. A zatem $x=\bigvee {}^{\uparrow }\Downarrow x$. Z drugiej strony, jeśli $P$ jest dowolnym posetem takim, że $x=\bigvee {}^{\uparrow }\Downarrow x$, to $P$ jest bazą, a więc $P$ jest ciągły. QED.

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. Jeśli poset jest ciągły, to relacja aproksymacji posiada własność interpolacji:

(w4) $(\mathrm{\forall }M{\subseteq }_{fin}P)(\mathrm{\forall }x\in P)(M\ll x\Rightarrow (\mathrm{\exists }y\in P(M\ll y\ll x)))$.

Definicja. Poset $P$ nazywamy dziedziną} lub dziedziną ciągłą jeśli jest ciągły i zupełny.

Dziedziną algebraiczną nazywamy każdy zupełny poset 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 faktow: 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ą.)

Przykłady

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

Przykład [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 [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 zupełny, ponieważ łańcuch $\omega$ nie ma supremum.

Przykład [odcinek] Odcinek $[0,1]$ z naturalnym porządkiem jest ciągły, co łatwo wynika z faktu, że $x\ll y$ wtw, 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.

Przykład [zbiór potęgowy] Niech $X$ będzie dowolnym zbiorem. Zbiór potęgowy ${𝒫}(X)$ jest kratą zupełną i dla każdego $Y\subseteq X$ mamy $\bigvee Y=\bigcup Y$ i $\bigwedge Y=\bigcap Y$. ${𝒫}(X)$ jest więc w szczególności zupełny i $bc$-zupełny. Najmniejszym elementem ${𝒫}(X)$ jest $\mathrm{\varnothing }$, a największym $X$. Pokażemy, że dla $A,B\subseteq X$ mamy $A\ll B$ wtw, 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 {𝒟}$ dla pewnego zbioru skierowanego ${𝒟}$ w ${𝒫}(X)$. Mamy więc $A\subseteq \bigcup {𝒟}$, co oznacza, że dla każdego $a\in A$ istnieje $D_a\in {𝒟}$ taki, że $a\in D_a$. Ponieważ ${𝒟}$ jest skierowany, istnieje $D\in {𝒟}$, który zawiera wszystkie zbiory $D_a$. To oznacza, że $A\subseteq D\in {𝒟}$, co należało pokazać.

Przykład [dziedzina podprzedziałów odcinka] Niech $\mathrm{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]⊑[c,d]⟺[a,b]\supseteq [c,d]$ dla $a,b,c,d\in [0,1]$. Poset $\mathrm{I}[0,1]$ jest zupełny, $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]⟺[a,b]\supseteq (c,d).$. Bazą przeliczalną w $\mathrm{I}[0,1]$ jest rodzina wszystkich podprzedziałów odcinka $[0,1]$ o końcach wymiernych.

Przykład [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 $\mathrm{I}[0,1]\mathbb{ℝ}$. Poset $\mathrm{I}[0,1]\mathbb{ℝ}$ jest izomorficzny z $\mathrm{I}[0,1]$, więc posiada dokładnie te same cechy co $\mathrm{I}[0,1]$.

Przykład [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ę $⊑$ w następujący sposób:

$(x,r)⊑(y,s)⟺d(x,y)\le r-s.$

Można pokazać, że relacja $⊑$ jest częściowym porządkiem. Poset $\mathrm{B}\mathrm{X}=(\{(x,r)\mid x\in X,r>0\},⊑)$ jest ciągły, a relacja aproksymacji może być opisana jako: $(x,r)\ll (y,s)⟺d(x,y)<r-s.$ Poset $\mathrm{B}\mathrm{X}$ jest dziedziną (tj. jest dcpo) wtw, gdy $X$ jest przestrzenią metryczną zupełną. Poset $\mathrm{B}\mathrm{X}$ jest $\omega$-ciągły wtw, gdy przestrzeń metryczna $X$ jest ośrodkowa.

Przykład [model zbioru Cantora] Zbiór wszystkich skończonych i nieskończonych ciągów zerojedynkowych ${\mathrm{\Sigma }}^{\mathrm{\infty }}$ (oczywiście $\mathrm{\Sigma }=\{0,1\}$) 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 ${\mathrm{\Sigma }}^{\mathrm{\infty }}$, który nie jest maksymalny, jest zwarty.

Funkcje między posetami

Funkcję $f:P\to Q$ między posetami nazywamy monotoniczną, jeśli zachowuje porządek, tj. jeśli $x⊑y$ w $P$, to $f(x)⊑f(y)$ w $Q$. Funkcja $f$ jest ciągła, jeśli zachowuje suprema zbiorów skierowanych, to znaczy: jeśl $D\subseteq P$ jest skierowany i posiada supremum $\bigvee {}^{\uparrow }D\in P$, to $f[D]$ posiada supremum $\bigvee f[D]=f(\bigvee {}^{\uparrow }D)$. Zauważmy, że każda funkcja ciągła jest monotoniczna. Rzeczywiście, jeśli $x⊑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)⊒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 {}^{\uparrow }f[D]=f(\bigvee {}^{\uparrow }D)$.