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$.