Praporządek

Z Wikipedii

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

[edytuj] 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 $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ę $\leq^*$ na ${}^{\mathbb N}{\mathbb N}$ przez

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

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

[edytuj] 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