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, 2011 1/20 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, 2011 2/20 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, 2011 3/20 Fl: IB000: Uspořádané množiny, Uzávěry 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á.) c 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. Petr Hliněný, Fl MU Brno, 2011 4/20 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 c je (částečné) uspořádání na M.c Definice: Uspořádání i? na M je lineární (nebo také úplné), pokud každé dva prvky M jsou v R srovnatelné. Petr Hliněný, Fl MU Brno, 2011 5/20 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, 2011 6/20 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, 2011 7/20 Fl: IB000: Uspořádané množiny, Uzávěry Jak rozšířit uspořádání Příklad 5.4. Uspořádání „po složkách". Nechť (A, 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, 2011 8/20 Fl: IB000: Uspořádané množiny, Uzávěry 5.2 Další pojmy uspořádaných množin Definice 5.6. Buď (M, □) uspořádaná množina. Prvek x £ M je • minimální právě když pro každé y G M platí, že jestliže y Qx, 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 iCj, pak i/Ci. (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 Q y. c c • největší právě když pro každé y G M platí, že y C x. Petr Hliněný, Fl MU Brno, 2011 9/20 Fl: IB000: Uspořádané množiny, Uzávěry Prvek x e M • pokrýva y G M právě když x ^ y, y □ x a neexistuje žádné z G M takové, zex^z^yayQzQx. je dolní závora (mez) množiny ACM právě když x Q y pro každé y G A. je horní závora (mez) množiny ACM právě když y Q x pro každé y G A. Petr Hliněný, Fl MU Brno, 2011 10/20 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, C) 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, 2011 11/20 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. Petr Hliněný, Fl MU Brno, 2011 12/20 Fl: IB000: Uspořádané množiny, Uzávěry Tvrzení 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, 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, 2011 13/20 Fl: IB000: Uspořádané množiny, Uzávěry Tvrzení 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 Mj ~ 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. 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 x Q 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, 2011 14/20 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, 2011 15/20 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, 2011 16/20 Fl: IB000: Uspořádané množiny, Uzávěry 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, 2011 17/20 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, 2011 18/20 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, 2011 19/20 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, 2011 20/20 Fl: IB000: Uspořádané množiny, Uzávěry