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 $\underset{\downarrow }{\bigwedge }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\}.$