Praporzą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ą.
- 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 ![{\displaystyle {\big (}\exists N\in \mathbb {N} {\big )}{\big (}\forall n\geqslant N{\big )}(f(n)\leqslant g(n){\big )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9db88cd29e1fb867db3135161ac03c739a8d6f9f)
- (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 ![{\displaystyle {\big (}\exists z\in M{\big )}{\big (}xz=y{\big )}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9d1403939079e24280082b561bbd61289378b10)
- 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 ![{\displaystyle y.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83f72471aff7c6fbb27df0f971283a068efe091f)
- 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 ![{\displaystyle X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ba76c5a460c4a0bb1639a193bc1830f0a773e03)
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 ![{\displaystyle q\sqsubseteq p.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dd72562bf90986b12421f0c8e99c7c8bfc2d21a)
Wówczas
jest równoważnością na
Ponadto
- jeśli
oraz
to także ![{\displaystyle p'\sqsubseteq q'.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14bab9b8b6b544e42accd3941cd9e877d9eeb4db)
Dlatego możemy określić relację binarną
na przestrzeni ilorazowej
przez
wtedy i tylko wtedy, gdy ![{\displaystyle p\sqsubseteq q.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95f655bcc7cff50402cd651fa2f2931735e9350b)
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
![{\displaystyle g([a])=[f(a)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a21894b78c34e41a83a6072a68df2688ffa9a00)
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)
- ↑ K. Kuratowski, A. Mostowski: Set Theory. Warszawa: PWN, 1976.brak strony w książce
pojęcia podstawowe |
|
---|
własności i typy | według liczby argumentów |
|
---|
konkretne przykłady |
|
---|
własności relacji binarnych |
|
---|
praporządki |
|
---|
inne zestawy własności |
|
---|
|
---|
działania na relacjach | |
---|
powiązane struktury | |
---|
pozostałe pojęcia |
|
---|