Częściowy porządek

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

W matematyce dyskretnej, para (X, \leqslant), gdzie X jest zbiorem, a \leqslant 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[edytuj | edytuj kod]

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

 x \prec y \iff x \preccurlyeq 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 \preccurlyeq na X zdefiniowana przez

x \preccurlyeq y \iff x \prec y \or x = y

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

Oznaczenia[edytuj | edytuj kod]

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. \leqslant, \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.

Przykłady[edytuj | edytuj kod]

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\leqslant c \and b \leqslant d
    jest częściowym porządkiem. Nie jest to jednak porządek liniowy.
  • Relacja podzbioró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.

Zobacz też[edytuj | edytuj kod]