Porządek częściowy


Częściowy porządek w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z Porządek częściowy) Przejdź do nawigacji Przejdź do wyszukiwania

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

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

Spis treści

Ostre i słabe porządki | 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 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 X . {\displaystyle X.} Wówczas relacja {\displaystyle \prec } na X {\displaystyle X} zdefiniowana przez

x y x y x y {\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 X , {\displaystyle X,} to relacja {\displaystyle \preccurlyeq } na X {\displaystyle X} zdefiniowana przez

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

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

Oznaczenia | 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. , , , {\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 | 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 {\displaystyle \preccurlyeq } określona w zbiorze liczb zespolonych: a + b i c + d i a c b d {\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 R {\displaystyle R} wyznacza porządek częściowy po utożsamieniu elementów x , y {\displaystyle x,y} takich że x R y {\displaystyle x\;R\;y} i y R x ; {\displaystyle y\;R\;x;} proces ten można nazwać redukcją praporządku do porządku.

Zobacz też | edytuj kod

Na podstawie artykułu: "Porządek częściowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy