Częściowy porządek

Ten artykuł od 2020-12 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

W matematyce dyskretnej, para ${\displaystyle (X,\leqslant ),}$ gdzie ${\displaystyle X}$ jest zbiorem, a ${\displaystyle \leqslant }$ relacją częściowego porządku określoną na ${\displaystyle 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 asymetryczna). 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 ${\displaystyle \preccurlyeq }$ jest (słabym) porządkiem częściowym na zbiorze ${\displaystyle X.}$ Wówczas relacja ${\displaystyle \prec }$ na ${\displaystyle X}$ zdefiniowana przez

${\displaystyle x\prec y\iff x\preccurlyeq y\land x\neq y}$

jest ostrym porządkiem częściowym.

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

${\displaystyle x\preccurlyeq y\iff x\prec y\lor x=y}$

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. ${\displaystyle \leqslant ,\sqsubseteq ,\subseteq ,\preccurlyeq }$), a wersja silna była oznaczona symbolem bez tego znaku (np. ${\displaystyle <,\sqsubset ,\subset ,\prec }$).

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

Przykłady

• 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 ${\displaystyle \preccurlyeq }$ określona w zbiorze liczb zespolonych:

  ${\displaystyle a+bi\preccurlyeq c+di\iff a\leqslant c\land 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 ${\displaystyle R}$ wyznacza porządek częściowy po utożsamieniu elementów ${\displaystyle x,y}$ takich że ${\displaystyle x\;R\;y}$ i ${\displaystyle y\;R\;x;}$ proces ten można nazwać redukcją praporządku do porządku.

Zobacz też

• antyłańcuch
• dobry porządek
• funkcja monotoniczna
• łańcuch
• pojęcie forsingu
• porządek liniowy

Przypisy