Praporządek

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Praporządek (ang. pre-order), zwany także quasi-porządkiem (ang. quasi-order) to 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[edytuj | edytuj kod]

  • 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.
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[edytuj | edytuj kod]

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 : PosPre.

Liczba praporządków[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. K. Kuratowski, A. Mostowski: Set Theory. Warszawa: PWN, 1976.