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