Częściowy porządek (
ang.
partial order) –
relacja
zwrotna
,
przechodnia
i
antysymetryczna
albo równoważnie antysymetryczny
praporządek
.
W
matematyce dyskretnej
, para
, gdzie X jest
zbiorem
, a
relacją częściowego porządku określoną na X bywa nazywana posetem (z ang. partially ordered set – zbiór częściowo uporządkowany).
Ostre i słabe porządki
Słabymi porządkami częściowymi nazywane są relacje
zwrotne
,
przechodnie
i
antysymetryczne
, z kolei ostre porządki częściowe to relacje
przeciwzwrotne
i
przechodnie
(relacja przeciwzwrotna i przechodnia jest zarazem antysymetryczna). Porządki ostre i słabe są blisko związane w tym sensie, że łatwo jest zamienić relację jednego typu na relację drugiego typu.
Przypuścmy, że
jest (słabym) porządkiem częściowym na zbiorze X. Wówczas relacja
na X zdefiniowana przez
![x \prec y \iff x \preceq y \and x \neq y](http://upload.wikimedia.org/math/0/8/6/08692f49e5350cd2c09fd5059995decb.png)
jest ostrym porządkiem częściowym.
I na odwrót, jeśli
jest ostrym porządkiem częściowym na zbiorze X, to relacja
na X zdefiniowana przez
![x \preceq y \iff x \prec y \or x = y](http://upload.wikimedia.org/math/6/1/d/61d81dad3b44d3ff6d642b6ea0bc6963.png)
jest (słabym) porządkiem częściowym.
Oznaczenia
Często w tekstach matematycznych używamy zarówno słabej, jak i silnej wersji porządku, którym się interesujemy. Zwyczajowo używamy wtedy oznaczeń takich, aby wersja słaba była oznaczana symbolem zawierającym znak równości (np.
), a wersja silna była oznaczona symbolem bez tego znaku (np.
).
Należy mieć jednak na uwadze, że zwyczaj taki nie wykształcił się względem
inkluzji
zbiorów, gdzie symbol
oznaczać może zawieranie właściwe lub niewłaściwe (relację silną lub słabą). W celu uniknięcia nieporozumień stosuje się więc często symbole
oraz
odpowiednio dla relacji słabej i silnej.
Przykłady
Zbiór podzbiorów {x,y,z}, uporządkowany przez inkluzję
- Szczególnym przypadkiem częściowego porządku jest
porządek liniowy
, w szczególności: naturalny porządek na
liczbach rzeczywistych
jest porządkiem częściowym.
- Relacja
określona w zbiorze
liczb zespolonych
:
![a+bi \preccurlyeq c+di \iff a\leqslant c \and b \leqslant d](http://upload.wikimedia.org/math/7/8/3/7834c69a2527df99566a8a81d51664ea.png)
jest częściowym porządkiem. Nie jest to jednak porządek liniowy. - Relacja
zawierania
zbiorów określona na dowolnej
rodzinie
podzbiorów ustalonego zbioru jest częściowym porządkiem.
- Każdy praporządek R wyznacza porządek częściowy po utożsamieniu elementów x,y takich że
i
; proces ten można nazwać
redukcją praporządku do porządku
.
Zobacz też