Praporządek

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

  • Szczególnym przypadkiem praporządku jest częściowy porządek.
  • Każda relacja równoważności jest praporządkiem.
  • Niech i niech relacja , będzie zadana następująco: . Wówczas jest praporządkiem na który nie jest porządkiem częściowym.
  • Rozważmy zbiór wszystkich funkcji ze zbioru liczb naturalnych w . Określmy relację na przez
wtedy i tylko wtedy, gdy
(gdzie oznacza naturalny porządek na ). Wówczas jest praporządkiem ale nie porządkiem częściowym.
  • Rozważmy zbiór wszystkich nieskończonych podzbiorów zbioru liczb naturalnych . Określmy relację na przez
wtedy i tylko wtedy, gdy różnica zbiorów jest skończona.
Wówczas jest praporządkiem ale nie porządkiem częściowym.
  • Niech będzie monoidem. Określmy relację na przez
wtedy i tylko wtedy, gdy .
Wówczas jest praporządkiem. Dla monoidu wolnego jest to porządek częściowy zwany porządkiem prefiksowym (mamy gdy jest prefiksem )
  • Niech będzie grafem skierowanym. Określamy relację na przez
wtedy i tylko wtedy, gdy w istnieje droga z do .
Innymi słowy, relacja jest wyznaczona przez krawędzie domknięcia zwrotnego i przechodniego grafu . Wówczas jest praporządkiem.
  • Jeżeli jest klinem w rzeczywistej przestrzeni unormowanej , to relacja dana warunkiem jest praporządkiem w zbiorze .

Redukcja do porządków[edytuj]

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 jest praporządkiem, tzn. jest zwrotną i przechodnią relacją na zbiorze . Zdefiniujmy relacje binarną na przez

wtedy i tylko wtedy, gdy oraz

Wówczas jest równoważnością na . Ponadto

jeśli , oraz , to także

Dlatego możemy określić relację binarną na przestrzeni ilorazowej przez

wtedy i tylko wtedy, gdy

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

Oznaczmy przez przyporządkowanie, które praporządkowi przypisuje porządek częściowy określony wyżej. Niech i będą praporządkami. Wówczas funkcji monotonicznej można przypisać funkcję określoną wzorem

Można sprawdzić, że tak określona funkcja jest dobrze określona i jest funkcją monotoniczną .

Przyporządkowanie określmy także dla funkcji (tj. przypisując funkcji między praporządkami odpowiadającą funkcję między porządkami częściowymi). Wtedy 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]

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

Zobacz też[edytuj]

Przypisy

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