Uspořádaná množina

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Definice[editovat | editovat zdroj]

Uspořádaná množina je množina na které je definováno uspořádání.

Hlavní článek: Uspořádání

Uspořádání na množině a je binární relace R, která je na a reflexivní, tranzitivní a slabě antisymetrická, tj. pro kterou platí následující podmínky:

  • ( \forall x \isin a)(xRx) - reflexivita (každý prvek je v relaci R sám se sebou)
  • ( \forall x,y,z \isin a)((xRy \and yRz) \implies xRz) - tranzitivita (pokud je prvek množiny v uspořádání mezi jinými dvěma prvky, jsou tyto dva rovněž srovnatelné)
  • ( \forall x,y \isin a)((xRy \and yRx) \implies x = y) - slabá antisymetrie (neexistují cykly v uspořádání)

Toto uspořádání nazýváme také někdy neostré uspořádání.

Ostré uspořádání má definici shodnou s neostrým, ale podmínka reflexivity je nahrazena podmínkou antireflexivity:

  • ( \forall x \isin a)( \neg(xRx)) - antireflexivita (žádný prvek není v relaci sám se sebou)

Příklady[editovat | editovat zdroj]

  1. Relace  \leq je neostré uspořádání na přirozených číslech i reálných číslech.
  2. Relace < je ostré uspořádání na přirozených číslech i reálných číslech.
  3. Relace  \subseteq je neostré uspořádání na potenční množině (množině všech podmnožin) libovolné množiny.
  4. Relace „být předkem“ na množině všech lidí je ostré uspořádání.

Všimněte si, že na rozdíl od prvního příkladu nejsou ve třetím a čtvrtém případě každé dva prvky množiny srovnatelné - neplatí  ( \forall x,y \isin a)(xRy \vee yRx). V takovém případě hovoříme o částečném uspořádání. Pokud jsou každé dva různé prvky množiny porovnatelné, hovoříme o úplném uspořádání.

To jsou příklady smysluplných a intuitivně „správných“ uspořádání. Do definice uspořádání se ale vejdou i podivnější případy:

  • prázdná množina (tj. relace, která neobsahuje žádnou dvojici) je ostré uspořádání nad libovolnou množinou
  • relace „existuje cesta z A do B“ je neostrým uspořádáním na množině vrcholů orientovaného acyklického grafu

Související články[editovat | editovat zdroj]