Praporządek

Praporządek (ang. pre-order), zwany także quasi-porządkiem (ang. quasi-order) to 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\leq 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 : Pos → Pre.

Liczba praporządków

Liczbę praporządków na zbiorze $n$-elementowym opisuje ciąg A000798 w On-Line Encyclopedia of Integer Sequences.

Zobacz też

• częściowy porządek
• antyłańcuch
• łańcuch
• pojęcie forsingu