Praporządek

relacja zwrotna i przechodnia

Praporządek, kwaziporzą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

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)  

Zobacz też

edytuj

Przypisy

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

Linki zewnętrzne

edytuj