^5 Ekvivalence, Uspořádané množiny 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í - bud' na formy shodnosti nebo uspořádání. Stručný přehled lekce * Relace ekvivalence, jím odpovídající rozklady množin. * Uspořádané množiny a relevantní pojmy k uspořádání. * Hasseovské diagramy uspořádaných množin. Petr Hliněný. Fl MU Brno. 2015 1/25 Fl: IB000: Ekvivalence, Uspořádané množiny 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, 2015 2/25 Fl: IB000: Ekvivalence, Uspořádané množiny 5.1 Relace ekvivalence • Podle Definice 4.4 je relace R C M x M ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je ekvivalencí, ľ • Jak vypadá graf relace ekvivalence?:: • Neformálně řečeno; ekvivalence je relace R C MxM, taková, že (x,y) 6 R právě když x a y jsou v nějakém smyslu „stejné" (leží na stejné hromádce). Značení. V případě relace ekvivalence se poměrně často lze setkat s označením jako ~ či místo R. Místo (x,y) £ i? se pak píše x y. Petr Hliněný, Fl MU Brno, 2015 3/25 Fl: IB000: Ekvivalence, Uspořádané množiny Další ukázkové binární relace Příklad 5.1. Necht M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M a zkoumejme, zda se jedná o ekvivalence: • (x,y) G R právě když x má stejnou výšku jako y;n • (x,y) G R právě když x má stejnou barvu vlasů jako y;c • (x,y) G R právě když x,y mají stejnou výšku a stejnou barvu vlasů;c • (x,y) G R právě když x,y mají stejnou výšku nebo stejnou barvu vlasů.c U kterého body se nejedná o relaci ekvivalence a proč? c Je to poslední případ, kdy není splněna tranzitivita! c Tvrzení 5.2. Nechť R,S jsou dvě relace ekvivalence na stejné množině M. Pak jejich průnik R n S je opět relací ekvivalence. Petr Hliněný, Fl MU Brno, 2015 4/25 Fl: IB000: Ekvivalence, Uspořádané množiny r Příklad 5.3. Necht i? C N x N je binární relace definovaná takto: (x, y) e R právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a y „stejné"? c Platí (x, y) E R právě když x, y dávají stejný zbytek po dělení třemi. Je to opět relace ekvivalence, c C Příklad 5.4. Bud' R binární relace mezi všemi studenty na přednášce FhlBOOO definovaná takto: (x, y) e R právě když x i y sedí v první lavici, c Už na první pohled jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? c Protože není reflexivní pro studenty sedící v dalších lavicích. (Takže si dávejte dobrý pozor na správné pochopení definic.) C Petr Hliněný, Fl MU Brno, 2015 5/25 Fl: IB000: Ekvivalence, Uspořádané množiny 5.2 Rozklady a jejich vztah k ekvivalencím Definice 5.5. Rozklad množiny. Nechť M je množina. Rozklad (na) M je množina podmnožin M C 2M splňující násl. tři podmínky: • 0 0 M (tj. každý prvek M je neprázdná podmnožina M); • pokud A,B&J\Í, pak buď A = B nebo A n B = 0; Prvkům A/" se také říká třídy rozkladu. • Buď M = {a, b, c, d}. Pak N = {{a}, {b, c}, {d}} je rozklad na Mx • Nechť A0 = {k G N | k mod 3 = 0}, Ax = {k G N | mod 3 = 1}, A2 = {k G N j mod 3 = 2}. Pak A/" = {^0,^1,^2} je rozklad všech přirozených čísel N podle zbytkových tříd.c Každý rozklad M na M jednoznačně určuje jistou ekvivalenci Rj\f na M: Petr Hliněný, Fl MU Brno, 2015 6/25 Fl: IB000: Ekvivalence, Uspořádané množiny ^Věta 5.6. Necht M je množina a M rozklad na M. Necht C M x M je relace na M definovaná takto (x, y) G Rj\f právě když existuje A G M taková, že x, y G A. Pak Rj\f je ekvivalence na M.c Důkaz: Dokážeme, že Rj\f je reflexivní, symetrická a tranzitivní (Def. 4.4).c • Reflexivita: Buď x G M libovolné. Jelikož M je rozklad na M, musí existovat A G M takové, že x G A (jinak spor se třetí podmínkou z Definice 5.5). Proto (x, x) G Rj\f, tedy Rj\f je reflexivní. • Symetrie: Nechť (x,y) G Rj\f. Podle definice Rj\f pak existuje A G M taková, že x,y G A. To ale znamená, že také (y,x) G Rj\f podle definice .R/V, tedy Rj\f je symetrická.c • Tranzitivita: Nechť (x, y), (y, z) G -R/v"- Podle definice Rj\f existují A, B G M takové, že x, y G A a y, z G B. Jelikož AnB ^ 0, podle druhé podmínky z Definice 5.5 platí A = B. Tedy x,z ) e R podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) e i? neboť R je tranzitivní. To podle definice [y] znamená, že f e [y].c * «[y] C [x]": Nechť v e [y]. Pak (y,f) G i? podle definice [y]. Dále (x,y) G i? (viz výše), tedy (x, v) G i? neboť R je tranzitivní. To podle definice [x] znamená, že f G [x].c • Platí U^Jgm/äN = M, neboť x g [x] pro každé x g M. □ Petr Hliněný, Fl MU Brno, 2015 9/25 Fl: IB000: Ekvivalence, Uspořádané množiny r 5.3 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, 2015 10/25 Fl: IB000: Ekvivalence, Uspořádané množiny r 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 < . nVš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 a případně i šipky z tranzitivity budeme pro větší přehlednost v obrázcích vynechávat. c Petr Hliněný, Fl MU Brno, 2015 11/25 Fl: IB000: Ekvivalence, Uspořádané množiny Uspořádaná množina Definice 5.8. Uspořádaná množina je dvojice (M, ^), kde M je množina a ^ je (částečné) uspořádání na M.r 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, 2015 12/25 Fl: IB000: Ekvivalence, Uspořádané množin; Příklady uspořádaných množin Příklad 5.9. 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, 2015 13/25 Fl: IB000: Ekvivalence, Uspořádané množiny Příklad 5.10. 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, 2015 14/25 Fl: IB000: Ekvivalence, Uspořádané množiny Multikriteriální uspořádání Co třeba znamená požadavek na „nejlepší počítač"? c • I pokud se soustředíme jen na užitné/ výkonové charakteristiky počítače, můžeme porovnávat nejen podle rychlosti procesoru, ale také třeba podle výkonu grafiky, velikosti paměti a disku, nebo i počtu nakouslých jablek, c • Takže jak lze objekty podle více kritérií seřadit? c • Pro numerická kritéria lze řadit podle jejich váženého průměru (či součtu).c • Nebo uspořádat podle průniku seřazení jednotlivých kritérií (po složkách). Pokud P je lepší než Q, tak P v žádném kritériu nemůže zaostávat za Q. Avšak výsledkem bude typicky existence několika „nejlepších" objektů, které nebudeme umět vzájemně porovnat, i • Nakonec slovníkovým uspořádáním: Kritéria seřadíme od nejdůležitějšího a první odlišná hodnota kritéria rozhoduje. Například nás v prvé řadě zajímá rychlost procesoru, poté velikost paměti a až nakonec výkon grafiky či velikost disku... (nejsme hráči her) Petr Hliněný, Fl MU Brno, 2015 15/25 Fl: IB000: Ekvivalence, Uspořádané množiny Formalizace multikriteriálního uspořádání Formálně mějme několik kritérií označených indexovou množinou I. Pro í E I nechť hodnoty nabývané í-tým kritériem tvoří uspořádanou množinu {Ai,