Praporządek

Praporzą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ę $\leqslant ^{*}$ na $\mathbb {N} ^{\mathbb {N} }$ przez

$f\leqslant ^{*}g$ wtedy i tylko wtedy, gdy ${\big (}\exists N\in \mathbb {N} {\big )}{\big (}\forall n\geqslant N{\big )}(f(n)\leqslant g(n){\big )}$

(gdzie $\leqslant$ oznacza naturalny porządek na $\mathbb {N}$). Wówczas $\leqslant ^{*}$ 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ę $\leqslant$ na $M$ przez

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

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

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

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

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

• Jeżeli $K$ jest klinem w rzeczywistej przestrzeni unormowanej $X,$ to relacja dana warunkiem $x\leqslant y\iff 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,\sqsubseteq )$ jest praporządkiem, tzn. $\sqsubseteq$ jest zwrotną i przechodnią relacją na zbiorze $P.$ Zdefiniujmy relacje binarną $\equiv$ na $P$ przez

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

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

jeśli $p\equiv p',$ $q\equiv q'$ oraz $p\sqsubseteq q,$ to także $p'\sqsubseteq q'.$

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

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

Można sprawdzić, że $\leqslant$ 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,\sqsubseteq )$ przypisuje porządek częściowy określony wyżej. Niech $(X,\sqsubseteq )$ i $(Y,\sqsubseteq ')$ będą praporządkami. Wówczas funkcji monotonicznej $f\colon X\to Y$ można przypisać funkcję $g\colon 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\colon 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\colon \mathbf {Pos} \to \mathbf {Pre} .$

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