Praporządek
Praporządek, kwaziporządek, quasi-porządek – 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
edytujW 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ż
edytujPrzypisy
edytuj- ↑ K. Kuratowski, A. Mostowski: Set Theory. Warszawa: PWN, 1976.