Częściowy porządek

Z Wikipedii

Częściowy porządek (ang. partial order) – relacja zwrotna, przechodnia i antysymetryczna albo równoważnie antysymetryczny praporządek.

W matematyce dyskretnej, para $(X, \leq)$ , gdzie $X$ jest zbiorem, a $\leq$ relacją częściowego porządku określoną na $X$ bywa nazywana posetem (z ang. partially ordered set – zbiór częściowo uporządkowany).

[edytuj] 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 $\preceq$ jest (słabym) porządkiem częściowym na zbiorze $X$ . Wówczas relacja $\preceq$ na $X$ zdefiniowana przez

$x \prec y \iff x \preceq y \and x \neq y$

jest ostrym porządkiem częściowym.

I na odwrót, jeśli $\prec$ jest ostrym porządkiem częściowym na zbiorze $X$ , to relacja $\preceq$ na $X$ zdefiniowana przez

$x \preceq y \iff x \prec y \or x = y$

jest (słabym) porządkiem częściowym.

[edytuj] 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. $\leq, \sqsubseteq, \subseteq, \preccurlyeq$ ), a wersja silna była oznaczona symbolem bez tego znaku (np. $<, \sqsubset, \subset, \prec$ ).

Należy mieć jednak na uwadze, że zwyczaj taki nie wykształcił się względem inkluzji zbiorów, gdzie symbol $\subset$ 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 $\subseteq$ oraz $\varsubsetneq$ odpowiednio dla relacji słabej i silnej.

[edytuj] 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 $\preccurlyeq$ określona w zbiorze liczb zespolonych:
$a+bi \preccurlyeq c+di \iff a\leq c \and b \leq d$
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 $x\; R\; y$ i $y\; R\; x$ ; proces ten można nazwać redukcją praporządku do porządku.