Praporządek ( ang. pre-order), zwany także quasi-porządkiem (ang. quasi-order) to relacja , która jest zwrotna i przechodnia .

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 X 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 M będzie monoidem . Określmy relację na M 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 x jest prefiksem y)

• Niech G = (V,E) będzie grafem skierowanym. Określamy relację na V przez

wtedy i tylko wtedy, gdy w G istnieje droga z x do y.

Innymi słowy, relacja jest wyznaczona przez krawędzie domknięcia zwrotnego i przechodniego grafu G. Wówczas jest praporządkiem.

• Jeżeli K jest klinem w rzeczywistej przestrzeni unormowanej X, to relacja dana warunkiem jest praporządkiem w zbiorze X.

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 P. Zdefiniujmy relacje binarną na P przez

wtedy i tylko wtedy gdy oraz

Wówczas jest równoważnością na P. 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 F 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

g([a]) = [f(a)]

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

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 : Pos → Pre.

Liczba praporządków

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

Zobacz też

• ,
• częściowy porządek ,
• antyłańcuch ,
• łańcuch ,
• pojęcie forsingu .