Praporządek

Praporządek (ang. pre-order), zwany także quasi-porządkiem (ang. quasi-order) to relacja, która jest zwrotna i przechodnia.

• 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\leq y\iff y-x\in K}$ jest praporządkiem w zbiorze ${\displaystyle X}$.

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) G : Pos → Pre.

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

• przegląd zagadnień z zakresu matematyki,
• częściowy porządek,
• antyłańcuch,
• łańcuch,
• pojęcie forsingu.