Praporządek

Praporządek, kwaziporządek, quasi-porządek – relacja, która jest zwrotna i przechodnia^[1]. 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 ${\displaystyle X=\{a,b,c,d\}}$ i niech relacja ${\displaystyle R\subseteq X\times X,}$ będzie zadana następująco: ${\displaystyle R=\{(a,b),(a,c),(a,d),(b,d),(c,d),(b,c),(c,b)\}.}$ Wówczas ${\displaystyle R}$ jest praporządkiem na ${\displaystyle X,}$ który nie jest porządkiem częściowym.

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

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

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

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

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

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

• Niech ${\displaystyle M}$ będzie monoidem. Określmy relację ${\displaystyle \leqslant }$ na ${\displaystyle M}$ przez

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle g([a])=[f(a)].}$

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

Przyporządkowanie ${\displaystyle F}$ określmy także dla funkcji (tj. przypisując funkcji ${\displaystyle f}$ między praporządkami odpowiadającą funkcję ${\displaystyle g}$ między porządkami częściowymi). Wtedy ${\displaystyle 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) ${\displaystyle G\colon \mathbf {Pos} \to \mathbf {Pre} .}$

Zobacz też

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

Przypisy

1. K. Kuratowski, A. Mostowski: Set Theory. Warszawa: PWN, 1976. Brak numerów stron w książce

Linki zewnętrzne

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