Praporządek

Praporządek, kwaziporządek, quasi-porządek – relacja, która jest zwrotna i przechodnia. Praporządkiem określa się również relację przeciwzwrotną i przechodnią, tak zdefiniowana relacja jest ostrym porządkiem częściowym. Dalsza część artykułu omawia wersję zwrotną.

Przykłady praporządków

• Szczególnym przypadkiem praporządku jest częściowy porządek.
• Każda relacja równoważności jest praporządkiem.
• Niech $X=\{a,b,c,d\}$ i niech relacja $R\subseteq X\times X,$ będzie zadana następująco: $R=\{(a,b),(a,c),(a,d),(b,d),(c,d),(b,c),(c,b)\}.$ Wówczas $R$ jest praporządkiem na $X,$ który nie jest porządkiem częściowym.

• Rozważmy zbiór ${\mathbb{N}}^{\mathbb{N}}$ wszystkich funkcji ze zbioru liczb naturalnych $\mathbb{N}$ w $\mathbb{N}.$ Określmy relację ${⩽}^{*}$ na ${\mathbb{N}}^{\mathbb{N}}$ przez

$f{⩽}^{*}g$ wtedy i tylko wtedy, gdy $(\mathrm{\exists }N\in \mathbb{N})(\mathrm{\forall }n⩾N)(f(n)⩽g(n))$

(gdzie $⩽$ oznacza naturalny porządek na $\mathbb{N}$). Wówczas ${⩽}^{*}$ jest praporządkiem, ale nie porządkiem częściowym.

• Rozważmy zbiór $[\mathbb{N}{]}^{\omega }$ wszystkich nieskończonych podzbiorów zbioru liczb naturalnych $\mathbb{N}.$ Określmy relację ${\subseteq }^{*}$ na $[\mathbb{N}{]}^{\omega }$ przez

$A{\subseteq }^{*}B$ wtedy i tylko wtedy, gdy różnica zbiorów $A\setminus B$ jest skończona.

Wówczas ${\subseteq }^{*}$ jest praporządkiem, ale nie porządkiem częściowym.

• Niech $M$ będzie monoidem. Określmy relację $⩽$ na $M$ przez

$x⩽y$ wtedy i tylko wtedy, gdy $(\mathrm{\exists }z\in M)(xz=y).$

Wówczas $⩽$ jest praporządkiem. Dla monoidu wolnego $(A^{*},\cdot )$ jest to porządek częściowy zwany porządkiem prefiksowym (mamy $x⩽y,$ gdy $x$ jest prefiksem $y$).

• Niech $G=(V,E)$ będzie grafem skierowanym. Określamy relację $⩽$ na $V$ przez

$x⩽y$ wtedy i tylko wtedy, gdy w $G$ istnieje droga z $x$ do $y.$

Innymi słowy, relacja $⩽$ jest wyznaczona przez krawędzie domknięcia zwrotnego i przechodniego grafu $G.$ Wówczas $⩽$ jest praporządkiem.

• Jeżeli $K$ jest klinem w rzeczywistej przestrzeni unormowanej $X,$ to relacja dana warunkiem $x⩽y⟺y-x\in K$ jest praporządkiem w zbiorze $X.$

Redukcja do porządków

W niektórych rozważaniach w matematyce (np. w teorii forsingu) traktujemy praporządki tak jakby były one porządkami częściowymi przez utożsamienie elementów które powinny być równe. Formalnie postępuje się w następujący sposób.

Przypuśćmy, że $(P,⊑)$ jest praporządkiem, tzn. $⊑$ jest zwrotną i przechodnią relacją na zbiorze $P.$ Zdefiniujmy relacje binarną $\equiv$ na $P$ przez

$p\equiv q$ wtedy i tylko wtedy, gdy $p⊑q$ oraz $q⊑p.$

Wówczas $\equiv$ jest równoważnością na $P.$ Ponadto

jeśli $p\equiv p^{\prime },$ $q\equiv q^{\prime }$ oraz $p⊑q,$ to także $p^{\prime }⊑q^{\prime }.$

Dlatego możemy określić relację binarną $⩽$ na przestrzeni ilorazowej $P/\equiv$ przez

$[p{]}_{\equiv }⩽[q{]}_{\equiv }$ wtedy i tylko wtedy, gdy $p⊑q.$

Można sprawdzić, że $⩽$ jest relacją zwrotną, przechodnią i (słabo) antysymetryczną, czyli jest to częściowy porządek.

Oznaczmy przez $F$ przyporządkowanie, które praporządkowi $(X,⊑)$ przypisuje porządek częściowy określony wyżej. Niech $(X,⊑)$ i $(Y,{⊑}^{\prime })$ będą praporządkami. Wówczas funkcji monotonicznej $f:X\to Y$ można przypisać funkcję $g:FX\to FY$ określoną wzorem

$g([a])=[f(a)].$

Można sprawdzić, że tak określona funkcja jest dobrze określona i jest funkcją monotoniczną $g:FX\to FY.$

Przyporządkowanie $F$ określmy także dla funkcji (tj. przypisując funkcji $f$ między praporządkami odpowiadającą funkcję $g$ między porządkami częściowymi). Wtedy $F$ jest funktorem z kategorii Pre praporządków w kategorię Pos posetów. Jest to funktor lewy sprzężony do funktora zapominania (włożenia) $G:𝐏𝐨𝐬\to 𝐏𝐫𝐞.$

Zobacz też

• antyłańcuch
• łańcuch
• pojęcie forsingu

Linki zewnętrzne

• Ciąg zawierający liczby praporządków na zbiorze n-elementowym