Uspořádaná množina

Technology

12 hours ago

Author

Albert Flores

Uspořádaná množina je množina, na které je definováno uspořádání. Uspořádání je binární relace, která je reflexivní, tranzitivní a (slabě) antisymetrická. Definice nevyžaduje, aby každé dva prvky množiny byly porovnatelné, proto se také používá název částečně uspořádaná množina. Uspořádání použité v definici je neostré (podmínka reflexivity říká, že pro každý prvek x množiny je xRx). Relaci uspořádání často značíme ≤, ⩽, případně (pokud chceme zdůraznit, že se nejedná o relaci „menší nebo rovno“ na číslech) ⪯ nebo ⪳.

Úplně uspořádaná množina je uspořádaná množina, jejíž každé dva prvky jsou porovnatelné, tj. xRy nebo yRx.

Definice

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 \land 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 \land yRx) \implies x = y) - slabá antisymetrie (neexistují cykly v uspořádání)

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

Ostré uspořádání má definici shodnou s neostrým, ale podmínka reflexivity je nahrazena podmínkou ireflexivity: * ( \forall x \isin A)( \neg(xRx)) - antireflexivita (žádný prvek není v relaci sám se sebou).

Úplné uspořádání (též lineární uspořádání) na množině A, je takové uspořádání, že \forall x,y \isin A je xRy nebo yRx (v případě ostrého uspořádání je to přirozeně vyžadováno pouze pro dvojice různých prvků). Uspořádání, které není úplné, se nazývá částečné uspořádání.

(Částečně) uspořádaná množina je množina, na které je definováno neostré částečné uspořádání.

Úplně uspořádaná množina je množina, na které je definováno neostré úplné uspořádání.

Příklady

# Relace \leq je neostré uspořádání na přirozených číslech i reálných číslech. # Relace \subseteq je neostré uspořádání na potenční množině (množině všech podmnožin) libovolné množiny. +more # 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á relace (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