Částečné spořádání

Částečné spořádání můžeme zadefinovat u prvků v jakékoliv množině, kterou se snažíme nějak uspořádat. Toto je odlišné od úplného uspořádání, kde můžeme s jistotou porovnat každý prvek s každým jiným prvkem. Úplné úspořádání známe z číselných množin, kde čísla zpravidla srovnáváme podle pořadí na číselní ose.

U některých prvků můžeme říci, že jeden je menší než druhý, zatímco pro jiné prvky nemůžeme takové porovnání provést.

Výhodou částečného uspořádání je snadná vizualizaci pomocí Hasseova diagramu. Jedná se o grafické znázornění, které pomáhá ilustrovat vztahy mezi prvky.

Definice relace uspořádání

Máme množinu $X$ a na ní relaci $R$. Pak o $R$ řekneme, že je částečným uspořádáním množiny $M$, pokud má následující vlastnosti:

• Reflexivita. Pro všechna $x ∈ X$ platí $R(x,x)$.
• Tranzitivita. Pokud pro nějaké tři prvky $x, y, z ∈ X$ a platí $R(x,y)$ a $R(y,z)$, pak pro ně platí i $R(x,z)$.
• Slabá antisymetrie. Pokud pro nějaké dva prvky $x, y ∈ X$ platí $R(x,y)$ a $R(y,x)$, pak $x=y$.

Největší/Nejmenší prvek

Často je potřeba identifikovat nejmenší a největší prvek.

DEFINICE: Mějme množinu A s uspořádáním $≤_A$. Prvek a ∈ A se nazývá největší (nejmenší) prvek množiny A, jestliže pro všechna b ∈ A platí, že b $≤_A$ a, $≤_A$ b).

Příklady

Třeba když máme hierarchii tříd, můžeme definovat částečné uspořádání podle toho, zda je jedna třída podmnožinou druhé.

• Relace ≤, ≥ na množině N je uspořádání.
• Důležitý typ uspořádání je tzv. lexikografické uspořádání.