* 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. 2013 1/24 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, 2013 2/24 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 ekvivalence.c • 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é". Značení. V případě relace ekvivalence se někdy lze setkat s pojmenováním jako ~ či místo R. Místo (x,y) £ i? se pak píše x y. Petr Hliněný, Fl MU Brno, 2013 3/24 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, 2013 4/24 Fl: IB000: Ekvivalence, Uspořádané množiny Příklad 5.3. Nechi i? 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é"? Dávají stejný zbytek po dělení třemi, □ 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. Už na „první pohled" jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? 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, 2013 5/24 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/" = {Ao,Ai,A2J 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, 2013 6/24 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 A/" taková, že x,y G A. To ale znamená, že také (y, x) G -R/v" podle definice .R/V, tedy -R/V je symetrická.c • Tranzitivita: Nechť (x, y), (y, z) G i?/V- Podle definice Rj\f existují A, B G M takové, že x, y G A a y, z G -B. Jelikož Ani? 7^ 0, podle druhé podmínky z Definice 5.5 platí A = B. Tedy x, 2; G A = B, proto (x, z) G Rj\f podle definice i?^-. Petr Hliněný, Fl MU Brno, 2013 7/24 Fl: IB000: Ekvivalence, Uspořádané množiny Každá ekvivalence R na M naopak jednoznačně určuje jistý rozklad M/R na M: Věta 5.7. Necht M je množina a R ekvivalence na M. Pro každé x G M definujeme množinu [x] = {y G M | {x,y) G 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 5.5. Petr Hliněný, Fl MU Brno, 2013 8/24 Fl: IB000: Ekvivalence, Uspořádané množiny • Pro každé [x] g M/R platí [x] ^ 0, neboť x g [x].ľ • Nechť [x], [y] g M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y}. c Jestliže [x] n [y] ^ 0, existuje z g M takové, že z g [x] a z g [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) g R. Jelikož i? je symetrická a (y, z) g i?, platí (z, y) g i?. Jelikož (x, z), (z, y) g i? a i? je tranzitivní, platí (x,y) g R. Proto také (y, x) g R (opět ze symetrie i?). nNyní dokážeme, že [y] = [x]: * C [y]": Nechť f e [x]. Pak (x, v) G i? podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) e R neboť i? je tranzitivní. To podle definice [y] znamená, že f e [y].c * «[y] C [x]": Nechť v e [y]. Pak (y,v) e i? podle definice [y]. Dále (x,y) G R (viz výše), tedy (x,t>) G R neboť i? 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, 2013 9/24 Fl: IB000: Ekvivalence, Uspořádané množiny 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, 2013 10/24 Fl: IB000: Ekvivalence, Uspořádané množiny 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, 2013 11/24 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, 2013 12/24 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, 2013 13/24 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, 2013 14/24 Fl: IB000: Ekvivalence, Uspořádané množiny Jak rozšířit uspořádání na větší množiny Příklad 5.11. 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, 2013 15/24 Fl: IB000: Ekvivalence, Uspořádané množiny 5.4 Další pojmy uspořádaných množin Definice 5.13. 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 x • největší právě když pro každé y G M platí, že y ^ x. Petr Hliněný, Fl MU Brno, 2013 16/24 Fl: IB000: Ekvivalence, Uspořádané množiny 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^ya,y