Praporządek

Praporządek, quasi-porządekrelacja, 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

  • 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

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)

Zobacz też

Przypisy

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

Linki zewnętrzne