7 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í - buď na 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, 2020 1/25 Fl: IB000: Ekvivalence, Uspořádané množiny Vlastnosti binárních relací, zopakování Nechť RCM x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) £ R; ireflexivní, právě když pro každé a G M platí (a, a) 0 iž; □ symetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6) G R, pak také (6, a) G iž; antisymetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6), (6, a) G iž, pak a — b\ tranzitivní, právě když pro každé a,b,c £ M platí, že jestliže (a, 6), (6, c) G iž, pak také (a,c) Gi?. a & c Petr Hliněný, Fl MU Brno, 2020 2/25 Fl: IB000: Ekvivalence, Uspořádané množiny 7.1 Relace ekvivalence a rozklady • Podle Definice 6.2 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 R je ekvivalencím • Jak vypadá graf relace ekvivalence?c • Neformálně řečeno; ekvivalence je relace R C MxM, taková, že G i? 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) £ R se pak píše x ~ y. Petr Hliněný, Fl MU Brno, 2020 3/25 Fl: IB000: Ekvivalence, Uspořádané množiny Další ukázkové binární relace Příklad 7.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\\: • (x, y) G R právě když x má stejnou barvu vlasů jako y\L • (x, y) G R právě když x, y mají stejnou výšku a stejnou barvu vlasů;c • (x, y) G iž právě když x, y mají stejnou výšku nebo stejnou barvu vlasůx U kterého body se nejedná o relaci ekvivalence a proč? Je to poslední případ, kdy není splněna tranzitivita! □ Tvrzení 7.2. Necht iž, 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, 2020 4/25 Fl: IB000: Ekvivalence, Uspořádané množiny ■r Příklad 7.3. Necht Ä C N x N je binární relace definovaná takto: (x, y) G R právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a y „stejné"? í Platí (x, y) G R právě když x, y dávají stejný zbytek po dělení třemi. Je to opět relace ekvivalence. □ Příklad 7.4. Buď R binární relace mezi všemi studenty na přednášce Fl: IB000 definovaná takto: (x,y) £ R právě když x i y sedí v první lavici. Už na první pohled jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? i 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.) □ Petr Hliněný, Fl MU Brno, 2020 5/25 Fl: IB000: Ekvivalence, Uspořádané množiny ■r Rozklady a jejich vztah k ekvivalencím Definice 7.5. Rozklad množiny. Nechť M je množina. Rozklad (na) M je množina podmnožin Af C 2M splňující násl. tři podmínky: • 0 ^ Af (tj. každý prvek Af je neprázdna podmnožina M); • pokud A,B(EJ\Í, pak buď A = B nebo AnB = ft Prvkům Af se také říká ŕr/c/y rozkladu. • Buď M = {a, 6, c, d}. Pak Af = {{a}, {6, c}, {d}} je rozklad na M.n • Nechť A0 = {k G N | fc mod 3 = 0}, Ax = {k G N | fc mod 3 = 1}, A2 = {k G N | k mod 3 = 2}. Pak Af = {Aq, Ai, A2} je rozklad všech přirozených čísel N podle zbytkových tříd.n Každý rozklad Af na M jednoznačně určuje jistou ekvivalenci Rjsj na M: Petr Hliněný, Fl MU Brno, 2020 6/25 Fl: IB000: Ekvivalence, Uspořádané množiny "'"věta 7.6. Necht M je množina a J\í 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 ÁÍ taková, že x, y G A. Pak Rj\f je ekvivalence na M.c Důkaz: Dokážeme, že Rjsj je reflexivní, symetrická a tranzitivní (Def. 6.2). • Reflexivita: Buď x G M libovolné. Jelikož Aí je rozklad na M, musí existovat A G ÁÍ takové, že x G A (jinak spor se třetí podmínkou z Definice 7.5). Proto (x, x) G Rj\f, tedy R^f je reflexivní.c • Symetrie: Nechť (x, y) G Äyv-- Podle definice ižyv" pak existuje A G TV taková, že x, y G A. To ale znamená, že také (y, x) G Rj\f podle definice ižyv". tedy Rj\f je symetrická.c • Tranzitivita: Nechť (x1y)1(y1z) G Äyv-- Podle definice R^f existují A, B G A/- takové, že x, y G A a y, z G B. Jelikož AdB ^ 0, podle druhé podmínky z Definice 7.5 platí A — B. Tedy x, z G A = B, proto (x, z) G Äyv" podle definice Rj\f. n Petr Hliněný, Fl MU Brno, 2020 7/25 Fl: IB000: Ekvivalence, Uspořádané množiny r Každá ekvivalence R na M naopak jednoznačně určuje jistý rozklad M/R na M: Věta 7.7. Necht M je množina a R ekvivalence na M. Pro každé x G M definujeme množinu x = {yeM| (x, y) E R}. Pak {[x] x G M} je rozklad na M, který značíme M/R.c M Důkaz: Dokážeme, že M/R splňuje podmínky Definice 7.5. Petr Hliněný, Fl MU Brno, 2020 8/25 Fl: IB000: Ekvivalence, Uspořádané množiny Pro každé Nechť Jestliže x x □ x x n [y] ŕ 0, pak x y □ x E M/R platí [x] ^ 0, neboť x E y] E M/R. Ukážeme, že pokud H [y] ^ 0, existuje z E M takové, ze z E [x] a z E [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G Ä, platí (z, y) G Ä. Jelikož (x, z), (z, y) E Ra R je tranzitivní, platí (x,y) E R. Proto také (y,x) E R (opět ze symetrie R). Nyní dokážeme, že [y] [x]: * ,,[x] C [ž/]": Nechť v E [x]. Pak (x,v) G i? podle definice [x]. Dále (y,x) E R (viz výše), tedy (y, v) E R neboť R je tranzitivní. To podle definice [y] znamená, že v E [y]x * ,,[y] C [#]": Nechť v E [y]. Pak (y,v) E R podle definice [y]. Dále (x,y) G R (viz výše), tedy (x, v) E R neboť i? je tranzitivní. To podle definice [x] znamená, že v E [x]x Platí U [x]eM/R x = M, neboť x E [x] pro každé x E M □ Petr Hliněný, Fl MU Brno, 2020 9/25 Fl: IB000: Ekvivalence, Uspořádané množiny ■r 7.2 Uspořádané množiny • Podle Definice 6.2 je relace R C M x M (částečné) uspořádání práve 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 R je uspořádáním. • Neformálně řečeno: uspořádání je taková relace R C MxM, kde G i? právě když x je v nějakém smyslu „menší nebo rovno" než y. Mohou ovšem existovat taková x,y G M, kde neplatí G iž ani (y, x) G Ä. (Pak říkáme, ze x a y jsou nesrovnáte!né.)c • 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, 2020 10/25 Fl: IB000: Ekvivalence, Uspořádané množiny Značení. Pro větší přehlednost se relace uspořádání často značí symboly jako □ či ^ místo prostého R. I my budeme psát třeba x ^ y místo (x,y) £ 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. □ Petr Hliněný, Fl MU Brno, 2020 11/25 Fl: IB000: Ekvivalence, Uspořádané množiny Uspořádaná množina Definice 7.8. Uspořádaná množina je dvojice (M, kde M je množina a ^ je (částečné) uspořádání na M.c 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, 2020 12/25 Fl: IB000: Ekvivalence, Uspořádané množiny Příklady uspořádaných množin Příklad 7.9. Necht M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M definované následovně (jedná se úplně 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.c Všimněte si dobře možného problému - pokud by dva studenti měli přesně stejnou výšku, nebyla by splněna podmínka antisymetrie. Prakticky však můžeme uvažovat, že toto nenastane (matematicky bychom řekli, že pravděpodobnost výskytu dvou studentů přesně stejné výšky bez omezení přesnosti měření je nula) a bude se jednat o uspořádání. □ Příklad 7.10. Necht M je množina všech českých studentů 1. ročníku Fl. Uvažme relaci R C M x M definovanou tak, že (x, y) G R právě když x a y mají stejné rodné číslo, u Je možné, aby R byla uspořádáním na M? Ano, za zákonného předpokladu jedinečnosti rodného čísla. Zajímavé, že? □ Petr Hliněný, Fl MU Brno, 2020 13/25 Fl: IB000: Ekvivalence, Uspořádané množiny Příklad 7.11. 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, I), kde a|6 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í.c • Buď 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} {o, b, c} {0,0} íbc} {o} {bř {c} {} □ Petr Hliněný, Fl MU Brno, 2020 14/25 Fl: IB000: Ekvivalence, Uspořádané množiny Multikriteriální uspořádání Co třeba znamená požadavek na „nejlepší počítač"? • 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. • Takže jak lze objekty podle více kritérií seřadit? • Pro numerická kritéria lze řadit podle jejich váženého průměru (či součtu). • 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. • 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, 2020 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 i E I nechť hodnoty nabývané i-tým kritériem tvoří uspořádanou množinu (Aí,<í). Definice 7.12. Uspořádání podle více kritérií. Pro ICN mějme systém uspořádaných množin (A^, <^) kde i E I. Na množině M := y(ieIAi definujeme binární relace Ľ a ^ takto; pro í,m E M kde í — [í{ : i E I) a m — {mi : i E I) platí * (po složkách) í □ m právě když í{