Relace uspořádání

Relace uspořádání je binární relace na množině, která je reflexivní, antisymetrická a transitivní.

Motivace

Uspořádání je běžný pojem, se kterým pracujeme i v běžném životě. Spoustu věcí můžeme nějakým způsobem uspořádat — slova podle abecedy, žáky ve škole podle výšky, zboží podle ceny. Toto všechno popisuje relace uspořádání, kterou obvykle značíme pomocí symbolu ≤. Související symboly jsou: <, >, ≥. Jejich význam je zřejmý.

Co bychom od takové relace očekávali? Už ze symbolu je jasné, že v relaci uspořádání budou prvky, které jsou stejné — jde nám tedy o to nadefinovat vlastnosti relace menší nebo rovno. Taková relace by tak měla být reflexivní. Musí platit, že a ≤ a.

Co dále? Určitě nebude platit symetrie — pokud máme uspořádání podle ceny, tak pokud je auto levnější než chleba, tak určitě nebude zároveň chleba levnější než auto. Co bychom obecně očekávali, pokud by se stalo, že a ≤ b a zároveň b ≤ a? Dávalo by to někdy smysl? Ano, pokud by platilo a = b. Jediný případ, kdy nezáleží na pořadí prvků vložených do relace je, když jsou ty prvky stejné — uspořádání je tak antisymetrické.

Nakonec pokud víme, že auto je dražší než chleba a letadlo je ještě dražší než auto, tak očekáváme, že letadlo bude určitě dražší než chleba. To popisuje transitivita.

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

To, co jsme si před chvílí nadefinovali, je ve skutečnosti pouze částečné uspořádání, není úplné. Proč není úplné? Zkusme si definovat uspořádání na množinách. Jakým způsobem bychom mohli porovnat dvě množiny?

Řekneme, že množina A je menší nebo rovna než množina B, pokud A ⊆ B, tedy pokud je A podmnožinou B. Dává to smysl, protože pokud máme A = {1, 2} a B = {1, 2, 3}, tak o A bychom mohli říci, že je menší — B obsahuje tytéž prvky jako A a ještě k tomu obsahuje navíc číslo tři. Takže například bude platit:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Potíž je ale v tom, když chceme porovnat tyto množiny: A = {a, b} a B = {a, c}. Která z nich je menší nebo větší? Potíž je v tom, že sice obě množiny obsahují prvek a, ale druhý prvek mají vždy různý. Ani jedna množina není podmnožinou druhé, takže neplatí A ≤ B ani B ≤ A. Takové množiny jsou pomocí našeho uspořádání neporovnatelné.

Proto definujeme úplně uspořádanou množinu nebo též řetězec, pokud jsou každé dva prvky z množiny porovnatelné. Takovými množinami jsou například číselné množiny s klasickým uspořádáním. Pro každá dvě reálná čísla a, b jste schopni rozhodnout, jestli a ≤ b nebo b ≤ a.

Příklady ze života

Příkladem, kdy se vyplatí neporovnávat, by mohlo být uspořádání podle krásy, relace < by tak znamenala "být škaredější". Možná bychom to měli spíše definovat obráceně > jako „být hezčí“, abychom byli korektnější :-). Asi má smysl porovnávat mezi sebou dvě ženy, například „Helenka Vondráčková“ < "Agáta Hanychová" ve smyslu Agáta je hezčí než Helenka. Nebo dva chlapy: "Jirka Paroubek" < "Vojta Kotek" ve smyslu Kotek je hezčí než Paroubek.

Problém je v tom, že asi jen těžko můžeme porovnávat krásu muže a ženy. Je hezčí Agáta nebo Vojta? Je škaredější náš národní poklad, Helenka, nebo sexy mozek Jirka? Radši nezkoumat...

Pokud se v posledním příkladu omezíme například jen na ženy, můžeme říci, že máme úplně uspořádanou množinu, protože dokážeme porovnat krásu všech žen.

Minimální a maximální prvek, nejmenší a největší prvek

Máme-li uspořádanaou množinu M, pak prvek min ∈ M nazveme minimální, pokud neexistuje x ∈ M takové, že x < m. Tedy nejsme schopni nalézt prvek, který by byl menší než prvek min.

Prvek max ∈ M nazveme maximální, pokud neexistuje x ∈ M takové, že x > max. Tedy nejsme schopni nalézt prvek, který by byl větší.

Předchozí dva pojmy se liší od pojmů nejmenší a největší.

Prvek a ∈ M nazveme nejmenší, pokud pro všechny x ∈ M platí, že a ≤ x. Tedy nejmenší prvek a je menší nebo roven než všechny ostatní prvky z množiny M.

Prvek b ∈ M nazveme největší, pokud pro všechna x ∈ M platí, že b ≥ x. Největší prvek b je větší nebo roven než všechny ostatní prvky z množiny M.

Jaký je rozdíl mezi největším prvkem a maximálním prvkem? Maximálních prvků může být více, protože množina nemusí být nutně úplně seřazená. Pokud se vrátíme k příkladu porovnávání lidí na základě vzhledu, pak můžeme říci, že Carmen Electra je nejhezčí žena a Johny Depp je nejhezčí muž. Ale tyto dvě osoby už mezi sebou nejsme schopni porovnat, nevíme, jestli je hezčí Carmen Electra nebo Johny Depp.

Oba prvky tak jsou maximální. Nejsme schopni nalézt osobu, která by byla hezčí než Johny Depp — Johny je hezčí než všichni ostatní muži a se ženami ho porovnávat nemůžeme. Podobně pro Carmen Electru — ta je hezčí než všechny ženy a s muži ji porovnávat nemůžeme.

Ale ani jeden z nich není největší, v tomto smyslu nejhezčí. Protože aby byl Johny Depp nejhezčí/největší, musel by být hezčí než všechny osoby, včetně všech žen. Ale už jsme si řekli, že s ženami ho porovnávat nemůžeme, proto nemůže být nejhezčí člověk, je jen, v terminologii teorie uspořádání, maximální.

Je asi snadno vidět, že pokud má množina největší prvek, pak tento prvek je zároveň i maximální. Pokud je prvek a větší než všechny ostatní prvky z množiny (definice největšího prvku), pak jistě nenajdeme prvek, který by byl ještě větší (definice maximálního prvku).

Příkladem množiny, která má největší a nejmenší prvek je například uzavřený interval <0, 1>. Pokud zvolíme stejný interval, ale otevřený, tak by neměl ani největší, ani nejmenší prvek: (0, 1).

Pokud bychom chtěli nekonečně mnoho minimálních prvků, mohli bychom zadefinovat uspořádání R takto. Nejprve definujeme pomocné množiny M_x. Množiny budou mít tento tvar: pro všechna x z intervalu (0, 1) definujeme množinu M_x = {y | y = x + n}, kde n celé nezáporné číslo. Tím dostaneme například takovéto množiny:

$$\begin{eqnarray} M_{0{,}5}&=&\left\{0{,}5;, 1{,}5;, 2{,}5;, 3{,}5; \ldots\right\}\\ M_{0{,}7}&=&\left\{0{,}7;, 1{,}7;, 2{,}7;, 3{,}7; \ldots\right\}\\ M_{0{,}8}&=&\left\{0{,}8;, 1{,}8;, 2{,}8;, 3{,}8; \ldots\right\} \end{eqnarray}$$

Na každé množině M_x definujeme klasické uspořádání, které označíme R_x. Na konci už jen tato uspořádání sjednotíme: R = ∪ R_x. V tomto uspořádání tak můžeme vždy porovnávat jen v rámci původních řetězců. Můžeme tak zjistit, jestli 0,5 ≤ 2,5, ale už nemůžeme zjistit, jestli 0,5 ≤ 2,7 protože tato čísla se nenacházela ve stejné M_x množině a tak jejich vztah nemáme definovaný.

V této relaci uspořádání pak platí, že každý prvek z intervalu (0, 1) je minimálním prvkem.

Hasseovy diagramy

Uspořádané množiny můžeme zakreslit pomocí Hasseova diagramu. Jedná se o graf, ve kterém vrcholy představují prvky množiny a hrana mezi vrcholy (a, b) nám říká, že a < b a zároveň neexistuje c takové, že a < c < b. Tedy mezi prvky a a b už žádný jiný prvek není. Přitom musí platit, že v grafu je vrchol a níže než vrchol b. Příklad Hasseova diagramu:

Tento Hasseův diagram znázorňuje uspořádanou množinu {A, B, C, D, E, F}. Přitom platí: A < B, B < E, dále samozřejmě platí A < E, ale mezi temito vrcholy hrana není, protože existuje vrchol B, pro který platí A < B < E. Prvky E a D jsou neporovnatelné, protože ani jeden není nad druhým nebo pod druhým.

Přestože se Hasseovy diagramy obykle zakreslují takto hezky zarovnaně, tak to není bezpodmínečně nutné. Předchozí Hasseův diagram může vypadat i takto:

Dalším příklad může být množina: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Jsou to přirození dělitelé čísla 60. Uspořádání podle dělitelnosti může být zobrazeno takhle:

Uspořádání dle dělitelnosti znamená, že [a, b] ∈ R právě když a dělí b. Z diagramu si můžeme všimnout, že každé číslo má nad sebou čísla, která dělí. Například nad číslem 6 jsou čísla 12, 30 a 60. Nad číslem 4 jsou čísla 12, 20 a 60. Atd. Naopak číslo 3 nad sebou nemá číslo 10, protože ho nedělí — pozor, číslo 10 je vizuálně nad číslem 3, ale nevede k němu „zdola nahoru“ žádná čára. Pokud se od čísla 3 budeme pohybovat pouze nahoru, můžeme jít k číslům 15 a 6 a od nich k číslu 30. K číslu 10 už bychom se dostali jen tak, že bychom slezli dolů, což nesmíme.