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.
- 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ż