5   Uspořádané množiny, Uzávěry
V této lekci dále pokračujeme probíráním binárních relací na množinách jako nástrojů vyjadřujících vztahy mezi objekty. Zaměřujeme se nyní především na relace „srovnávající" objekty podle jejich vlastností. Takto vágně opsané relace mívají jasné společné znaky, které se objevují ve formální definici relace uspořádání.
Stručný přehled lekce
* Uspořádané množiny a relevantní pojmy k uspořádání.
* Hasseovské diagramy uspořádaných množin.
* Uzávěry relací-jak danou relaci „obohatit" o zvolenou vlastnost.
c
Petr Hliněný, Fl MU Brno, 2012
1/33
Fl: IB000: Uspořádané množiny, Uzávěry
Vlastnosti binárních relací, zopakování
Nechť R C M x M. Binární relace i? je
• reflexivní, právě když pro každé a G M platí (a, a) G R;
•Ô -ô
• ireflexivní, právě když pro každé a G M platí (a, a) 0 i?;
• symetrická, právě když pro každé a, b G M platí, že jestliže (a, 6) G i?, pak také (b, a) G R;
• antisymetrická,  právě  když  pro  každé a,b   G   M  platí,  že jestliže
(a, 6), (b, a) G i?, pak a = b\
• tranzitivní, právě když pro každé a, 6, c G M platí, že jestliže (a, 6), (6, c) G fí, pak také (a, c) G i?. a        6 c
Petr Hliněný, Fl MU Brno, 2012
2/33
Fl: IB000: Uspořádané množiny, Uzávěry
5.1   Uspořádání a uspořádané množiny
• Podle Definice 4.4 je relace R C M x M (částečné) uspořádání právě když R je reflexivní, antisymetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je uspořádáním.
• Neformálně řečeno: uspořádání je taková relace i? C MxM, kde(x,y) G R právě když x je v nějakém smyslu „menší nebo rovno" než y. c
Mohou ovšem existovat taková x,y G M, kde neplatí (x,y) G R ani (y, x) G R. (Pak říkáme, že x a y jsou nesrovnatelné.)^
• Jak názorně zobrazit (částečné) uspořádání? Zjednodušeně takto:
8
12
dělitelnost:
2
3
5
7
11
1
Petr Hliněný, Fl MU Brno, 2012
3/33
Fl: IB000: Uspořádané množiny, Uzávěry
Značení. Pro větší přehlednost se relace uspořádání často značí symboly jako C či ^ místo prostého R. I my budeme psát třeba x < y místo (x,y) G R.
Poznámka: Zajisté jste se již setkali s „neostrým" uspořádáním čísel < a „ostrým" uspořádáním < .   Všimněte si dobře, že námi definované uspořádání je vždy „neostré".
Pokud byste naopak chtěli definovat „ostré" uspořádání, mělo by vlastnosti ireflexivní, antisymetrické a tranzitivní. (Příliš se však tato varianta nepoužívá.)
Nadále budeme pracovat pouze s neostrým uspořádáním, ale smyčky vyplývající z reflexivity budeme pro větší přehlednost v obrázcích vynechávat.
c
Petr Hliněný, Fl MU Brno, 2012
4/33
Fl: IB000: Uspořádané množiny, Uzávěry
^Uspořádaná množina
Definice 5.1. Uspořádaná množina je dvojice {M,<), kde M je množina a < je (částečné) uspořádání na M.u
Definice: Uspořádání ^ na M je lineární (nebo také úplné), pokud každé dva prvky M jsou v ^ srovnatelné.
Petr Hliněný, Fl MU Brno, 2012
5/33
Fl: IB000: Uspořádané množiny. Uzávěry
Příklady uspořádaných množin
Příklad 5.2. Necht M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace uspořádání R C M x M definované následovně (jedná se vždy o uspořádání?):
• (x,y) G R právě když x má alespoň takovou výšku jako y;c
• (x,y) G R právě když y má alespoň takovou výšku jako x;
• (x, y) G R právě když x a y mají stejné rodné číslo, c
Ano, i v posledním bodě se jedná o uspořádání! Zajímavé, že? c
Petr Hliněný, Fl MU Brno, 2012
6/33
Fl: IB000: Uspořádané množiny, Uzávěry
Příklad 5.3. Další ukázky uspořádaných množin následují zde:
• (N, <) je lineárně uspořádaná množina, kde < má „obvyklý" význam.c
• (N, j), kde a\b je relace dělitelnosti „a dělí b" na přirozených číslech, je uspořádaná množina. Toto uspořádání není lineární.
• Bud' M množina. Pak (2M,C) je uspořádaná množina (říkáme inkluzí). Které dvojice jsou v uspořádání inkluzí nesrovnatelné?
{a, b, c}
{a b}       {a c}     {t>, c}
{}
z
Petr Hliněný, Fl MU Brno, 2012
7/33
Fl: IB000: Uspořádané množiny, Uzávěry
Jak rozšířit uspořádání na větší množiny Příklad 5.4. Uspořádání „po složkách".
Nechť (A,<a) a (B,<b) jsou uspořádané množiny. Definujme binární relaci c na A x B předpisem
(a, b) c (a', b')    právě když    a <a a' a 6 6'. Pak (A x £?, c) je uspořádaná množina. Toto usp. se nazývá „po složkách". c
Příklad 5.5. Lexikografické uspořádání.
Nechť (A,<a) a (B,<b) jsou uspořádané množiny. Definujme binární relaci ^ na A x B předpisem
(a, b) ^ (a', 6')    právě když    bud' a <a »'a« / a', nebo a — a' a b <b b'.
Pak (A x £?, ^) je uspořádaná množina. Navíc pokud <a i <b jsou lineární, je i lineární. Toto uspořádání se nazývá lexikografické.□ c
Fakt: Jsou-li (Ai, <i), ■ ■ ■ ,(An,<n) uspořádané množiny, kde n > 2, pak množinu A\ x • • • x An lze uspořádat třeba po složkách nebo lexikograficky.
Všimněte si, že lexikograficky se například řadí slova ve slovníku. ..
Petr Hliněný, Fl MU Brno, 2012
8/33
Fl: IB000: Uspořádané množiny, Uzávěry
5.2   Další pojmy uspořádaných množin
Definice 5.6.   Nechť (M, ^) je uspořádaná množina. Prvek x £ M je
• minimální právě když pro každé y G M platí, že jestliže y ^ x, pak x <y. (Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
• maximální právě když pro každé y G M platí, že jestliže x <y, pak y ^ x. (Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.)c
• nejmenší právě když pro každé y G M platí, že x ^ y.
c
c
• největší právě když pro každé y G M platí, že y ^ x.
Petr Hliněný, Fl MU Brno, 2012
9/33
Fl: IB000: Uspořádané množiny, Uzávěry
Prvek x e M
» pokrývá y G M právě když x ^ y, y ^ x a neexistuje žádné z G M takové, zex^z^ya,y<z<x.
je dolní závora (mez) množiny ACM právě když x < y pro každé y G A.
je horní závora (mez) množiny ACM právě když y < x pro každé y G A.
Petr Hliněný,  Fl MU Brno, 2012
10/33
Fl: IB000: Uspořádané množiny, Uzávěry
• x G M je infimum množiny ACM právě když x je největší dolní závora množiny A.
• x G M je supremum množiny A C M, právě když x je nejmenší horní závora množiny A.c
• A  C  M je řetězec v uspořádání ^ právě když (A, ^) je lineárně uspořádaná množina.
Pozor! Některé uvedené definice mají dosti „netriviální chování" na nekonečných množinách. Proto je budeme obvykle uvažovat jen nad konečnými množinami...
Petr Hliněný,  Fl MU Brno, 2012 11/33 Fl: IB000: Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R C M x M je předuspořádání [také kvaziuspořádání, nebo polouspořádání) právě když i? je reflexivní a tranzitivní.c
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u předuspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné. V předuspořádání takto mohou vznikat „balíky" (třídy) se stejnou hodnotou kritéria, což schematicky ilustrujeme na následujícím obrázku.
Petr Hliněný,  Fl MU Brno, 2012
12/33
Fl: IB000: Uspořádané množiny, Uzávěry
Věta 5.8. Je-li □ před uspořádá ní na M, můžeme definovat relaci ~ na M předpisem
x ~ y    právě když    x □ y a y □ x.
Pak ~ _/'e ekvivalence na M, která se nazývá jádro předuspořádání A/a rozkladu Mj ~ pa/c /ze zavesř re/ac/    definovanou takto
[x] ^ [y]    právě když x □ y.
Pa/c (M/ ~, ^) _/e uspořádaná množina indukovaná c
Pro ukázku si vezměme relaci dělitelnosti na Z. Pak třeba —2 ~ 2. Jádrem zde jsou dvojice čísel stejné absolutní hodnoty.
Petr Hliněný,  Fl MU Brno, 2012
13/33
Fl: IB000: Uspořádané množiny, Uzávěry
Věta 5.8. Je-li □ před uspořádá ní na M, můžeme definovat relaci ~ na M předpisem
x ~ y    právě když    x □ y a y □ x. Pak ~ je ekvivalence na M, která se nazývá jádro předuspořádání A/a rozkladu M j ~ pa/c /ze zavesř re/ac/ ^ definovanou takto
[x] ^ [y]    právě když x □ y.
Pa/c (M/ ~, ^) _/e uspořádaná množina.
Důkaz (náznak): nTranzitivita a reflexivita relace ~ vyplývá z tranzitivity a reflexivity relace Symetrie ~ pak je přímým důsledkem její definice. Tudíž ~ skutečně je relací ekvivalence a Mj ~ je platný rozklad, c
Tranzitivita a reflexivita relace < se opět dědí z relace Její antisymetrie vyplývá následující úvahou: Pokud [x] ^ [y] a [y] ^ [x], pak podle naší definice £ E y a y □ x, neboli x ~ y a [x] = [y] podle definice tříd rozkladu, c
Pozor, nejdůležitější částí této větve důkazu je však ještě zdůvodnění, že naše podaná definice vztahu [x] ^ [y] je korektní, což znamená, že její platnost nezávisí na konkrétní volbě reprezentantů x z [x] a y z [y]. □
Petr Hliněný,  Fl MU Brno, 2012
14/33
Fl: IB000: Uspořádané množiny, Uzávěry
5.3   Hasseovské diagramy
Motivací zavedení tzv. Hasseovských diagramů uspořádaných množin jsou přehlednější „obrázky" než u grafů relací. Například si srovnejte následující:
Petr Hliněný,  Fl MU Brno, 2012
15/33
Fl: IB000: Uspořádané množiny, Uzávěry
Definice: Hasseovský diagram konečné uspořádané množiny (M,<) je jeho (jednoznačné) grafické znázornění získané takto:
• Do první „horizontální vrstvy" zakreslíme body odpovídající mininálním prvkům (M,<). (Tj. které nepokrývají nic.)c
• Máme-li již zakreslenu vrstvu i, pak do vrstvy i + 1 (která je „nad" vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze prvky vrstev < i. Pokud prvek x vrstvy i + 1 pokrývá prvek y vrstvy < i, spojíme x a y neorientovanou hranou (tj. „čárou").
Petr Hliněný,  Fl MU Brno, 2012
16/33
Fl: IB000: Uspořádané množiny, Uzávěry
:F
Příklad 5.9. Relaci inkluze na čtyfprvkové množině {a, b, c, d} zakreslíme Hasseovským diagramem takto:
Jak vidíme, v Hasseovském diagramu „vynecháváme" ty hrany relace ■<, které vyplývají z reflexivity či tranzitivity. To celý obrázek výrazně zpřehlední, a přitom nedochází ke ztrátě informace, c
Lze vynechat i šipky na hranách, neboť dle definice všechny míří „vzhůru", c
Také pojem „vrstvy" v definici je jen velmi neformální, důležité je, že větší (pokrývající) prvky jsou nad menšími (pokrývanými).
c
Z
Petr Hliněný,  Fl MU Brno, 2012
17/33
Fl: IB000: Uspořádané množiny, Uzávěry
5.4   Uzávěry relací
Definice: Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud splňuje následující podmínky:
• Pro každou množinu M a každou relaci R C M x M existuje alespoň jedna relace S Q M x M, která má vlastnost V a pro kterou platí R C S.
• Nechť / je množina a nechť Ri C M x M je relace mající vlastnost V pro každé i g /. Pak relace f]ieI Rí má vlastnost V.c
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uzavíratelná vlastnost.
Antisymetrie není uzavíratelná vlastnost, c
Věta 5.10. Necht V je uzavíratelná vlastnost binárních relací. Buď M množina a R libovolná binární relace na M. Pak pro množinu všech relací S 5 R na M majících vlastnost V existuje infimum Ry (vzhledem k množinové inkluzi), které samo má vlastnost V.
Tuto „nejmenší" relaci Ry s vlastností V nazýváme V-uzávěr relace R.
Petr Hliněný,  Fl MU Brno, 2012
18/33
Fl: IB000: Uspořádané množiny, Uzávěry
Tvrzení 5.11. Nechť i? je binární relace na M. Pak platí následující poznatky.
• Reflexivní uzávěr i? je přesně relace R U {(x,x) | x £ M}x
• Symetrický uzávěr R je přesně relace
i?= {(x,y) | (x,y) G i? nebo (y,x) G
• Tranzitivní uzávěr R je přesně relace i?+ = U£i Tl{R), kde Tje funkce, která pro každou binární relaci S vrátí relaci
T(5) = S U {(x,z) | existuje y takové, že (x, y), (y, z) £ 5}
a 71 = 7~ ° ' • • ° Tje *-krát iterovaná aplikace funkce T. c
i
• Reflexivní a tranzitivní uzávěr R je přesně relace R* = Q+, kde Q je reflexivní uzávěr
• Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence ob-sáhující i?) je přesně relace kde Q je reflexivní uzávěr R.
• Na pořadí aplikování uzávěrů vlastností záleží!
Petr Hliněný,  Fl MU Brno, 2012
19/33
Fl: IB000: Uspořádané množiny, Uzávěry
Neformálně:
• Význam reflexivních a symetrických uzávěrů je z předchozího zřejmý, c
• Význam tranzitivního uzávěru R+ je následovný:
Do R+ přidáme všechny ty dvojice (x,z) takové, že v i? se lze „dostat po šipkách" z x do z. Nakreslete si to na papír pro nějakou jednoduchou relaci, abyste význam tranzitivního uzávěru lépe pochopili, c
• A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl.
• Například buď R C N x N definovaná takto: R = {(i,i + 1) | i e N}. Pak R* je běžné lineární uspořádání < přirozených čísel.
c
c
Petr Hliněný,  Fl MU Brno, 2012
20/33
Fl: IB000: Uspořádané množiny, Uzávěry