Algebra 1 poznámky ke studiu předmětu verze 2016-2017 Břetislav Fajmon OBSAH 1 Obsah 1 Definice grupy 4 2 Grupa permutací 8 3 Grupa Zn zbytkových tříd, dělitelnost v množině Z 12 4 Okruh, obor integrity a těleso 16 5 Základní vlastnosti grup 19 6 Podgrupy, cyklické grupy 20 7 Izomorfismy, homomorfismy a součiny grup 21 8 Relace, rozklady, uspořádané množiny 23 9 Význačné prvky v uspořádaných množinách 31 10 Polosvazy a svazy 43 11 Další vlastnosti svazů 52 12 Výsledky některých příkladů 62 12.1 Výsledky ke kapitole 8 – relace, uspořádané množiny . . . . . . . . . . . . 62 12.2 Výsledky ke kapitole 9 – význačné prvky v uspořádaných množinách . . . . 63 12.3 Výsledky ke kapitole 10 – polosvazy, svazy . . . . . . . . . . . . . . . . . . 63 12.4 Výsledky ke kapitole 11 – další vlastnosti svazů . . . . . . . . . . . . . . . 64 2 OBSAH Úvod Vážení studenti, tento text je podkladem pro zkoušku Algebra 1 a obsahuje materiál k 11 teoretickým otázkám, jež budou předmětem ústní zkoušky. Přednášky 5,6,7 nejsou zpracovány, ale podle odkazů do textu Rosický, jenž najdete v IS, lze potřebný obsah dohledat ve skriptech nebo v zápiscích z přednášky. Pokud odečteme pojmy, které jsou pokryty v jiném předmětu (kartézský součin, relace, zobrazení, bijekce, surjekce, injekce) nebo které nejsou v této fázi až zas tak důležité (jádro homomorfismu, horní a dolní jádro izotonního zobrazení), zůstává asi třicet devět pojmů, které musíte v tomto předmětu zvládnout. Pro jistotu uvádím jejich stručný přehled: • Vlastnosti operací (1), (2), (3), (4), (5), (6), (7), (18), (19), (20). • Struktury související s operacemi: grupoid, pologrupa, monoid, grupa, okruh, obor integrity, těleso, homomorfismus grup, izomorfismus grup, součin grup. • Vlastnosti relací (11), (12), (13), úplná relace (nemá své číslo), operace průseku, operace spojení. • Pojmy související s relací ekvivalence: ekvivalence, rozklad, faktormnožina, faktor- grupa. • Pojmy související s uspořádanými množinami: poset (= částeně uspořádaná množina), coset (= řetězec = úplně uspořádaná množina), woset (= dobře uspořádaná množina), izotonní zobrazení posetů, izomorfismus posetů, −polosvaz, −polosvaz, svaz, úplný svaz. Přeji Vám, abyste při studiu Algebry 1 našli něco, co Vás bude bavit, nebo aspoň viděli důležitost daných pojmů. Pomocí je také přemýšlet o konkrétních příkladech těchto pojmů v situacích známých číselných množin, operací průniku a sjednocení množin či vlastností dělitelnosti na množině celých nebo přirozených čísel. Břeťa Fajmon, prosinec 2016 OBSAH 3 Zdroje, ze kterých bylo čerpáno: • Horák: Algebra a teoretická aritmetika, 1987 (jen mírně renovovaného v roce 2013, ovšem vydaného pod jiným názvem Základy matematiky); • Rosický: Algebra – grupy a okruhy 2000, reprint textu z roku 1985, který obsahuje učivo v potřebné hloubce a rozsahu (a dobře podává přehled pojmů i pro předmět Algebra 3 ve druhém ročníku); • Pinter: A book of Abstract Algebra, 2010. Není o moc novější než dvě předchozí knihy, je pouze reprintem druhého vydání z roku 1990 – dlužno říci, že tam, kde mi v předchozích dvou knihách chyběla motivace ke studiu či vysvětlení, mi je Pinter poskytl (vřele doporučuji); • Ve druhé části (přenášky 8 až 11) jsem se držel především textu Kopka: Svazy a Booleovy algebry (Ústí nad Labem 1991, zejména str. 19-82). 4 1 DEFINICE GRUPY 1 Definice grupy Struktura grupy, a vlastně vlasnosti očíslované (1) až (6), představuje axiomy běžně používané při práci s operacemi v aritmetice. Studovat tedy grupy a spol. znamená studovat axiomy, na kterých je založena celá aritmetika, věda počítání s čísly. Tato kapitolka předkládá pouze definici vlastností (1) až (5), společně se základními příklady. Tyto vlastnosti budou podrobněji studovány v dalších kapitolách. Definice 1.1. Axiom = fakt, jehož platnost se v dané matematické teorii předpokládá a nedokazuje (chceme jeho platnost předpokládat, protože se nám to jeví jako rozumné, ve shodě s realitou). Definice 1.2. Operace ∗ na množině M ... zobrazení M × M → M, které přiřadí uspořádané dvojici [a, b] (ve které záleží na pořadí) prvek a ∗ b ∈ M. Pojem operace je základní definicí prvních sedmi přednášek tohoto textu. Budeme si všímat vlastnosti několika základních, ale též několika z různých důvodů zajímavých operací na konečných i nekonečných množinách. Dříve, než začneme studovat konkrétní operace a struktury, několik označení pro stručný matematický zápis, která jsou bezpodmínečně nutná: • označení: ∀ ... pro každé, pro každou; • označení: ∃ ... existuje; • označení: ∃! ... existuje právě jedno • označení: : (dvojtečka) ... tak, že; platí • označení: ⇒ ... z toho plyne, odtud plyne; potom platí; • označení: ∈ ... patří do, je prvkem; • označení: N = {1, 2, 3, . . .} ... množina přirozených čísel; • označení: N0 = {0, 1, 2, 3, . . .} ... množina přirozených čísel včetně nuly; • označení: Z = {. . . , −2, −1, 0, 1, 2, 3, . . .} ... množina celých čísel; • označení: množinu racionálních čísel označujeme a definujeme: Q := m n : m ∈ Z, n ∈ N . • označení: ∃ ... neexistuje, neexistují; • označení: ∩ ... průnik množin; • označení: ∪ ... sjednocení množin; • označení: R ... množina reálných čísel; • označení: I ... množina iracionálních čísel, tj. R = Q ∪ I; 5 Axiomy pro počítání s čísly (které student zná ze střední školy) možná daly základ pro definice následujících vlastností, jež budou hrát klíčovou roli: Definice 1.3. Vlastnost (1) ... uzavřenost množiny M vzhledem k operaci ∗: ∀x, y ∈ M : x ∗ y ∈ M. (1) Vlastnost (1) je přirozená – chceme, aby operace na množině byly definované takovým způsobem, aby výsledek operace zase byl prvkem dané množiny. Definice 1.4. Vlastnost (2) ... asociativita operace ∗: ∀x, y, z ∈ M : (x ∗ y) ∗ z = x ∗ (y ∗ z). (2) Vlastnost (2) platí pro většinu operací, o kterých bude za chvíli řeč – jednoduše řečeno, několikanásobné použití jedné operace nezávisí na uzávorkování. Snad jen operace − a : nejsou asociativní. Definice 1.5. Vlastnost (3) ... existence jednotkového prvku vzhledem k operaci ∗: ∃e ∈ M : x ∗ e = e ∗ x = x ∀x ∈ M. (3) Příklad pro vlastnost (3): jednotkový prvek vzhledem k operaci sčítání je 0 (někdy nazýván též nulový prvek, aby nedošlo k záměně s prvkem 1), jednotkový prvek vzhledem k operaci násobení je 1. Definice 1.6. Vlastnost (4) ... existence inverzních prvků vzhledem k operaci ∗: ∀x ∈ M ∃ x−1 ∈ M : x ∗ x−1 = x−1 ∗ x = e. (4) Příklad pro vlastnost (4): Pro číslo 2 je inverzním prvkem vzhledem k operaci sčítání číslo −2, vzhledem k operaci násobení číslo 1 2 . Uveďme nyní základní definice některých struktur, které splňují dané vlastnosti: Definice 1.7. • Grupoid (M, ∗) ... množina M, na které operace ∗ splňuje vlastnost (1); • Pologrupa (M, ∗) ... množina M, na které operace ∗ splňuje vlastnosti (1),(2); • Monoid (M, ∗) ... množina M, na které operace ∗ splňuje vlastnosti (1),(2),(3) (někdy též: pologrupa s jednotkou, pologrupa s jednotkovým prvkem); • Grupa (M, ∗)... množina M s operací ∗, která splňuje na množině M vlastnosti (1), (2), (3), (4). Kromě těchto čtyř základních struktur, které byly právě definovány, ještě řada operací splňuje vlastnost (5) – viz následující definice. Tato vlastnost (5) už do samotné definice stěžejního pojmu grupy není zahrnuta, protože jak uvidíme v následujících dvou kapitolách, existují význačné příklady grup, které ji nesplňují. Proto slovo „komutativní musíme k právě definovaným strukturám zvlášť dodat jako novou vlastnost. 6 1 DEFINICE GRUPY Definice 1.8. • Operace ∗ se nazývá komutativní na množině M, pokud platí vlastnost (5): ∀x, y ∈ M : x ∗ y = y ∗ x. (5) • (M, ∗) se nazývá komutativní grupoid, pokud je grupoid a operace ∗ splňuje vlastnost (5), tj. je komutativní na množině M. • (M, ∗) se nazývá komutativní pologrupa, pokud je pologrupa a operace ∗ splňuje vlastnost (5), tj. je komutativní na množině M. • (M, ∗) se nazývá komutativní monoid, pokud je monoid (tj. pokud je pologrupa s jednotkou) a operace ∗ splňuje vlastnost (5), tj. je komutativní na množině M. • definice: (M, ∗) se nazývá komutativní grupa, pokud je grupa a operace ∗ splňuje vlastnost (5), tj. je komutativní na množině M. Podle předchozích pojmů platí tyto základní věty pro nám známé množiny: Věta 1.9. (N, +) je komutativní pologrupa. Důkaz: Opravdu, operace sčítání je komutativní – platí (5). Sečtením dvou přirozených čísel je zase přirozené číslo – platí (1). Sečtení tří čísel z N nezáleží na uzávorkování – platí (2). Vlastnosti (1),(2) platí na struktuře, která se nazývá pologrupa. Vlastnost (3) neplatí, protože 0 = jednotkový prvek vzhledem ke sčítání, není přirozené číslo (eventuálně bychom mohli tvrdit, že (N0, +) je monoid). Vlastnost (4) na (N, +) neplatí, protože např. inverzní prvek k 2 je −2, ale −2 /∈ N. P Doplněním množiny N o nulový prvek a inverzní prvky vzhledem ke sčítání dostaneme: Věta 1.10. (Z, +) je komutativní grupa. Dále se podívejme na některé základní množiny vzhledem k násobení: Věta 1.11. (Z, ·) je komutativní monoid. Důkaz: Opravdu, násobení je komutativní – platí (5). Vynásobením dvou celých čísel je zase celé číslo – platí (1). Násobení tří čísel nezávisí na uzávorkování – platí (2). Jednotkovým prvkem vzhledem k násobení je číslo 1, což je celé číslo – platí tedy (3), tedy (Z, ·) je monoid. Ovšem inverzní prvky vzhledem k násobení nejsou celá čísla: např. inverzí k číslu 2 vzhledem k násobení je 1 2 , ale to není celé číslo, inverzí k 3 je 1 3 , ale 1 3 /∈ Z, atd. P Doplněním množiny Z o inverzní prvky vzhledem k násobení by se zdálo, že se situace vylepší, ale pozor: Věta 1.12. (Q, ·), (R, ·) jsou komutativní monoidy. Důkaz: Opravdu, přece jen chybí ještě jeden inverzní prvek, a sice pro nulu: rovnice 0·x = 1 nemá řešení na množině Q nebo R, tj. neplatí vlastnost (4), dané množiny nejsou grupami vzhledem k násobení. P 7 Čili vyloučením nuly z množin v předchozí větě dostaneme: Věta 1.13. (Q − {0}, ·), (R − {0}, ·) jsou komutativní grupy. Někdy též značíme Q∗ := Q − {0}, R∗ := R − {0}, tj. (Q∗ , ·), (R∗ , ·) jsou komutativní grupy. Tím, jak se axiomaticky zkonstruuje či popíše množina R pomocí množiny Q, se zde nebudeme zabývat, jen si nyní připomeňme, že existují jistá čísla, která nelze vyjádřit pomocí zlomku p q ∈ Q; důkaz takového tvrzení je dobrou ilustrací dokazování sporem, takže by jej studenti mohli umět: Věta 1.14. √ 2 není racionální číslo. Důkaz: je např. ve skriptech Rosický, str. 15, za důkazem věty 3.6. P 8 2 GRUPA PERMUTACÍ 2 Grupa permutací Kromě nekonečných množin, na kterých se definuje operace, se budeme občas zabývat i konečnými množinami. Například: • označení: 2A ... množina všech podmnožin množiny A; to je totéž jako množina všech zobrazení množiny A do dvouprvkové množiny {0, 1}. Opravdu, např. pro A = {a, b, c, d, e}, když si vezmeme jakoukoli podmnožinu množiny A, například množinu {a, c, d}, tak ta je ekvivalentní tomu zobrazení f množiny A do {0, 1}, které zobrazí a, c, d na jedničku a b, e na nulu. Naopak, pokud si vezmeme jakékoli zobrazení g : A → {0, 1}, například to, pro které g(a) = 0, g(b) = 0, g(c) = 0, g(d) = 1, g(e) = 1, to je ekvivalentní podmnožině {d, e} množiny A. Pro všechny volby zobrazení dostáváme právě všechny různé podmnožiny množiny A. Věta 2.1. a) Množina (2A , ∪) je komutativní monoid. b) Množina (2A , ∩) je komutativní monoid. Důkaz: Opravdu, sjednocením či průnikem dvou podmnožin dané množiny A je zase nějaká podmnožina množiny A – platí (1). Operace ∪ a ∩ nezáleží na uzávorkování – platí (2). Jednotkovým prvkem vzhledem ke sjednocení je ∅, jednotkovým prvkem vzhledem k průniku je celá množina A ... platí (3) vzhledem k oběma operacím. Inverze ke mnoha prvkům této struktury neexistují – například pro operaci sjednocení a podmnožinu {a} množiny A = {a, b, c, d, e} by musela existovat podmnožina X množiny A, aby {a}∪X = ∅, a to neexistuje. Důležitým příkladem (většinou konečné, ale i nekonečné, to závisí na počtu prvků dané množiny) je grupa permutací n-prvkové množiny, kde operací je skládání zobrazení. Na permutaci např. 5-prvkové množiny se na SŠ pohlíželo jako na pořadí pěti jejích prvků, např. 51324. Na VŠ budeme na permutace pohlížet jako na: Definice 2.2. Permutace n−prvkové množiny je bijektivní1 zobrazení množiny {1, 2, . . . , n} do sebe. Sn je množina všech permutací tohoto typu. Například permutace f : M → M pro M = {1, 2, 3, 4, 5} definovaná    1 2 3 4 5 ↓ ↓ ↓ ↓ ↓ 5 1 3 2 4    je bijektivní, takže existuje permutace f−1 k ní inverzní    1 2 3 4 5 ↑ ↑ ↑ ↑ ↑ 5 1 3 2 4    1 Definice bijekce viz kapitola 6, nyní se spokojíme s intuitivní představou o bijekci, a sice že v bijekci M → M z každého prvku množiny M vychází právě jedna šipka, a do každého prvku množiny M směřuje právě jedna šipka daného zobrazení. 9 Protože permutace je zvláštní případ zobrazení a zobrazení M → M lze skládat za sebou, můžeme mluvit o operaci „skládání zobrazení , respektive „skládání permutací • označení: ◦ ... (čti „po ) operace skládání zobrazení; Uvažme nyní například množinu permutací tříprvkové množiny {1, 2, 3} do sebe – označme ji S3 (písmeno S pravděpodobně pochází z toho faktu, že tyto permutace představují jakési jistým způsobem symetrické útvary, nebo modelují struktury, kterým se říká symetrie). Věta 2.3. (S3, ◦) je grupa, která není komutativní. Množina S3 má šest prvků: e =    1 2 3 ↓ ↓ ↓ 1 2 3    , s =    1 2 3 ↓ ↓ ↓ 2 3 1    , t =    1 2 3 ↓ ↓ ↓ 3 1 2    , u =    1 2 3 ↓ ↓ ↓ 1 3 2    , v =    1 2 3 ↓ ↓ ↓ 3 2 1    , w =    1 2 3 ↓ ↓ ↓ 2 1 3    . Prvek e je jednotkový, neprovede žádnou změnu v pořadí, například s ◦ e =    1 2 3 ↓ ↓ ↓ 2 3 1    ◦    1 2 3 ↓ ↓ ↓ 1 2 3    =         1 2 3 ↓ ↓ ↓ 1 2 3 ↓ ↓ ↓ 2 3 1         =    1 2 3 ↓ ↓ ↓ 2 3 1    = s. Všimněme si, že nejprve je prováděno přiřazení e, a až poté (◦ = „po ) je provedeno přiřazení s. Dále například u ◦ v =    1 2 3 ↓ ↓ ↓ 1 3 2    ◦    1 2 3 ↓ ↓ ↓ 3 2 1    =         1 2 3 ↓ ↓ ↓ 3 2 1 ↓ ↓ ↓ 2 3 1         =    1 2 3 ↓ ↓ ↓ 2 3 1    = s, v ◦ u =    1 2 3 ↓ ↓ ↓ 3 2 1    ◦    1 2 3 ↓ ↓ ↓ 1 3 2    =         1 2 3 ↓ ↓ ↓ 1 3 2 ↓ ↓ ↓ 3 1 2         =    1 2 3 ↓ ↓ ↓ 3 1 2    = t. Čili je vidět, že v ◦ u = u ◦ v, tj. operace ◦ je nekomutativní! Propočítáním všech možných 36 kombinací dostaneme přehlednou tabulku výsledků operace ◦. Nejprve je potřeba říci, že u každé tabulky operace ∗ na konečné množině prvků je levý prvek x vybrán z levého sloupce záhlaví a pravý prvek y z horního řádku záhlaví; výsledek operace pak je znázorněn na průsečíku „řádku x a „sloupce y : ∗ . . . y . . . ... ... x ... x ∗ y ... ... ... 10 2 GRUPA PERMUTACÍ Tedy konkrétně u operace ◦ na množině S3 dostaneme tabulku operace: ◦ e s t u v w e e s t u v w s s t e w u v t t e s v w u u u v w e s t v v w u t e s w w u v s t e Uveďme nyní některé další vlastnosti této grupy, které vyplývají z kapitol 5 a 6, ale po jejich nastudování pak tyto vlastnosti přirozeně náleží do této kapitolky: Existuje šest podgrup2 grupy (S3, ◦): tzv. triviální podgrupa, která obsahuje pouze jednotkový prvek e, s tabulkou operace ◦ e e e , další podgrupou je celá šestiprvková grupa (S3, ◦) samotná. Kromě těchto dvou extrémně malých nebo velkých podgrup existují též tři dvouprvkové podgrupy ◦ e u e e u u u e , ◦ e v e e v v v e , ◦ e w e e w w w e a jedna tříprvková podgrupa s tabulkou operace ◦ e s t e e s t s s t e t t e s . Co se týká řádu3 jednotlivých prvků grupy (S3, ◦), platí: • e1 = e, tj. e je prvek řádu 1; • u2 = v2 = w2 = e, tj. prvky u, v, w jsou řádu 2; • s3 = t3 = e, tj. prvky s, t jsou řádu 3. Z řádů jednotlivých prvků také vidíme, že existuje k = 6 (nejmenší společný násobek řádů jednotlivých prvků) tak, že libovolný z prvků umocněný na šestou se rovná jednotce e: e6 = e, u6 = (u2 )3 = e3 = e, v6 = e, w6 = e, s6 = (s3 )2 = e2 = e, t6 = e. Dále, ohledně generátorů grupy S3 lze říci, že (S3, ◦) je generována dvěma svými prvky, a sice v a w, protože všechny dalšíé čtyři prvky grupy lze vyjádřit pomocí operace ◦ a prvků v, w: e = v ◦ v; s = v ◦ w; t = s ◦ s = (v ◦ w)2 = (v ◦ w) ◦ (v ◦ w); u = w ◦ s = w ◦ (v ◦ w). 2 Kapitola 6. 3 Kapitola 5. 11 Podle označení množiny generátorů lze psát (S3, ◦) =< v, w > . Příklad 2.4. (reparát příkladu, který díky nesprávné definici skládání zobrazení na přednášce zaslouží také opravu) Jsou dány permutace P =    1 2 3 4 5 6 7 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 5 3 1 4 6 2 7    , R =    1 2 3 4 5 6 7 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 7 1 6 3 4 2 5    . Vypočtěte P ◦ R2 . Řešení: Podle definice skládání zobrazení platí P ◦ R2 = P ◦ R ◦ R =              1 2 3 4 5 6 7 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 7 1 6 3 4 2 5 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 5 7 2 6 3 1 4 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 6 7 3 2 1 5 4              =    1 2 3 4 5 6 7 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 6 7 3 2 1 5 4    . 12 3 GRUPA ZN ZBYTKOVÝCH TŘÍD, DĚLITELNOST V MNOŽINĚ Z 3 Grupa Zn zbytkových tříd, dělitelnost v množině Z • definice: nesoudělná čísla a, b jsou taková celá čísla, která nemají žádného společného dělitele mezi přirozenými čísly, kromě jedničky; • definice: dělitel čísla b (pro b ∈ Z); • definice: největší společný dělitel dvou celých čísel b, c; • označení: a|b (a dělí b, nebo též: a je dělitelem čísla b); • důkaz věty 3.2 (Euklidova algoritmu) ze skript Rosický, str. 14. • označení: ∧ ... a současně; • označení: ∨ ... nebo; • definice: prvočíslo ... takové přirozené číslo větší než 1, které je mezi přirozenými čísly dělitelné jen jedničkou a sebou samým; • definice: celá čísla a, b jsou kongruentní podle modulu n, pokud n|(b − a); • označení: a ≡ b(mod n); • označení: := ... definiční rovnítko – neznamená rovnici, ale definiční přiřazení, kdy levé straně přiřazujeme např. funkční předpis, označujeme nějakou množinu, a po- dobně. Klíčovou strukturu představuje následující definice: • definice: množina zbytkových tříd modulo n ... je zde pomocí popsat celou konstrukci této množiny například pro n = 6: Rozdělíme všechna celá čísla do šesti podmnožin podle toho, jak daleko je dané číslo na číselné ose vpravo od nejbližšího násobku čísla 6 (viz obrázek 1). Pak v každé třídě jsou právě ta celá čísla, která jsou mezi sebou kongruentní modulo 6, tj. a ≡ b, když 6|(a − b). – Třída [1] obsahuje čísla 1, 7, 13, atd. ale také záporná čísla −5, −11, −17, atd., protože nejbliží násobek čísla 6 je od nich vzdálený o jednu jednotku vlevo. – Třída [2] obsahuje čísla 2, 8, 14, atd. ale také záporná čísla −4, −10, −16, atd. a jsou to právě ta čísla, od nichž je vzdálen násobek šesti o dvě jednotky vlevo. – Třída [3] obsahuje čísla 3, 9, 15, atd. ale také záporná čísla −3, −9, −15, atd. – Třída [4] obsahuje čísla 4, 10, 16, atd. ale také záporná čísla −2, −8, −14, atd. – Třída [5] obsahuje čísla 5, 11, 17, atd. ale také záporná čísla −1, −7, −13, atd. – A konečně třída [0] obsahuje všechna celá čísla dělitelná šesti, tj. 0, 6, 12, atd. ale také záporná čísla −6, −12, −18, atd. 13 Obrázek 1: Rozdělení celých čísel do šesti podmnožin. V každé třídě takto vytvořené jsou právě ta celá čísla, která jsou mezi sebou kongruentní modulo 6. Každá z těchto šesti podmnožin je nekonečná, odtud tedy honosný název „třída . Nyní se budeme dále dívat na tyto třídy jako na prvky množiny Z6 (tj. množina Z6 je konečná a má jen šest prvků!!!) a definujeme na této množině operace ⊕, následovně: [a] ⊕ [b] := [a + b]; tj. součet tříd je třída, která obsahuje celé číslo a + b, [a] [b] := [a · b]; tj. součin tříd je třída obsahující celé číslo a · b. Lze ukázat, že tyto dvě operace nezávisí na výběru celých čísel a, b z daných nekonečných množin. Pro takto definovanou šestiprvkovou množinu a operace na ní nyní platí, že (Z6, ⊕) je grupa, (Z6, ) je monoid (= pologrupa s jednotkou [1]). Tato grupa (resp. monoid) se nazývá grupa zbytkových tříd modulo 6 (resp. monoid zbytkových tříd modulo 6). Příklad 3.1. a) Pomocí tabulky operace ⊕ dokažte, že (Z6, ⊕) je grupa: b) Pomocí tabulky operace dokažte, že(Z6, ) je monoid: 14 3 GRUPA ZN ZBYTKOVÝCH TŘÍD, DĚLITELNOST V MNOŽINĚ Z Tabulka 1: Tabulka operace ⊕ na množině Z6. ⊕ [0] [1] [2] [3] [4] [5] [0] [0] [1] [2] [3] [4] [5] [1] [1] [2] [3] [4] [5] [0] [2] [2] [3] [4] [5] [0] [1] [3] [3] [4] [5] [0] [1] [2] [4] [4] [5] [0] [1] [2] [3] [5] [5] [0] [1] [2] [3] [4] Tabulka 2: Tabulka operace na množině Z6. [0] [1] [2] [3] [4] [5] [0] [0] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [4] [5] [2] [0] [2] [4] [0] [2] [4] [3] [0] [3] [0] [3] [0] [3] [4] [0] [4] [2] [0] [4] [2] [5] [0] [5] [4] [3] [2] [1] • označení: Zn ... množina zbytkových tříd modulo n; • označení: Z∗ n ... množina zbytkových tříd modulo n mimo prvek [0], tj. Z∗ n := Zn − {[0]}. Toto označení používáme i pro klasické množiny Q∗ (racionální čísla mimo nuly), R∗ (reálná čísla mimo nuly), protože se nám hodí, že (Q∗ , ·), (R∗ , ·) jsou grupy (nulu z těchto množin musíme vyloučit, protože pro ni neexistuje inverzní prvek vzhledem k operaci násobení). Zbytkové třídy lze sestavit nejen pro n = 6, ale pro jakékoli přirozené n > 1. Následující dvě věty studenti nemusí umět dokázat (ale je dobré si zapamatovat, co říkají): Věta 3.2. Ve struktuře (Z∗ n, ) existuje k prvku [k] inverzní prvek vzhledem k násobení právě tehdy, když k, n jsou nesoudělná. Například v (Z6, ) neexistují k prvkům [2], [3], [4] inverzní prvky, protože čísla 2, 3, 4 jsou soudělná s číslem 6. 15 Věta 3.3. Důsledek předchozí věty: Pokud n je prvočíslo, tak k, n jsou nesoudělná čísla pro k = 1, 2, . . . , (n − 1), tj. ke všem prvkům (kromě [0], kterou jsme vyloučili) existují inverzní prvky vzhledem k násobení , a tedy (Z∗ n, ) je grupa. Například (Z∗ 7 , ) je grupa. Čtenář by se o tom mohl snadno přesvědčit z tabulky operace na množině Z∗ 7 . 16 4 OKRUH, OBOR INTEGRITY A TĚLESO 4 Okruh, obor integrity a těleso Okruh je po grupě druhou základní definicí struktury v kursech moderní algebry. A je to definice naprosto přirozená. Když totiž zkoumáme množinu Z, nikdy o ní ne přemýšlíme jako o množině s jedinou operací, ale máme současně na mysli sčítání (odčítání je skryto v inverzních prvcích) a násobení (dělení je skryto v inverzních prvcích). Matematik se tedy snaží formulovat, jaké zákonitosti platí pro interakci operací + a ·. Tato interakce je popsána v definici algebraické struktury zvané okruh: Definice 4.1. okruh (anglicky: ring) je množina (M, +, ·) s operacemi + a ·, které splňují vlastnosti: a) Operace + splňuje vlastnosti (1), (2), (3), (4), (5), tj. (M, +) je komutativní grupa; b) operace · splňuje vlastnosti (1), (2), (3), tj. množina (M, ·) je monoid (= pologrupa s jednotkou); c) interakce operací + a · splňuje tzv. distributivní zákon = vlastnost (6): ∀ x, y, z ∈ M : x · (y + z) = x · y + x · z, (y + z) · x = y · x + z · x (6) (rovnice jsou dvě díky tomu, že operace · není obecně komutativní). Název „distributivní odpovídá tomu, že po odstranění závorek se prvek x rozdělí = distribuuje k oběma členům součtu. Na vlastnost (6), pokud se na ni díváme zprava doleva, lze také pohlížet jako na pravidlo vytýkání – je možné vytknout před (nebo za) závorku prvek x, pokud jím násobíme ze stejné strany dva členy součtu. Nejrozumnější pohled na vlastnost (6) je ten, že se jedná o pravidlo, které určuje větší prioritu operace násobení před sčítáním – násobení je tak agresivní, že po odstranění závorek se vrhne na oba členy součtu, které byly uvnitř. Podobně též platí např. 8 + 2 · 3 = 14, tj. operace · váže jednotlivá celá čísla s větší prioritou než je tomu u sčítání a odčítání. Příklad 4.2. • Příkladem konečného okruhu je struktura zbytkových tříd z předchozího oddílu 3, tj. množina (Zn, ⊕, ). • Příkladem nekonečného okruhu je (Z, +, ·), tedy množina celých čísel s tradičními operacemi sčítání a násobení. Ovšem struktura (Zn, ·) z minulé kapitoly vykazuje určité defekty, tj. obsahuje tzv, netriviální dělitele nuly: Definice 4.3. netriviální dělitelé nuly jsou takové prvky a, b množiny M, které se nerovnají nule (0 = jednotkový prvek4 v grupě (M, +)), ale jejich součin (= výsledek operace násobení v pologrupě (M, ·)) je roven nule: a · b = 0; 4 Někdy se mu též říká nulový prvek, protože označení „jednotka či „jednotkový prvek je vyhrazeno jednotce 1 v pologrupě (M, ·) vzhledem k násobení. 17 Příklad 4.4. Příkladem struktury s netriviálními dělitely nuly je množina Z6 zbytkových tříd modulo 6: její prvky [2], [3] nebo [3], [4] jsou netriviální dělitelé nuly, protože platí [2] [3] = [0], [3] [4] = [0]. Tito netriviální dělitelé nuly jsou dosti překvapivým jevem, který například u celých čísel nenastane – a také nežádoucím jevem. Okamžitá otázka pro matematický popis vyvstává, kdy se taková situace vyskytne a jak zaručit, že k ní nedojde. Z tohoto důvodu definujeme obor integrity: Definice 4.5. obor integrity5 (anglicky: integral domain) je množina6 (M, +, ·) s operacemi + a ·, která je okruhem a navíc jsou splněny vlastnosti: ad a) Operace + nesplňuje nic navíc; ad b) operace · splňuje navíc: • M neobsahuje netrivální dělitele nuly (vzhledem k operaci ·); • vlastnost (5), tj. operace · je komutativní na M; ad c) díky komutativitě operace · lze distributivní zákon psát v jediné rovnici: ∀ x, y, z ∈ M : x · (y + z) = x · y + x · z = y · x + z · x = (y + z) · x. Příklad 4.6. • (Z7, ⊕, ) je konečný obor integrity, protože 7 je prvočíslo, tj. (Z∗ 7 , ) neobsahuje netriviální dělitele nuly. • (Z, +, ·) je nejen nekonečný okruh, ale i nekonečný obor integrity, protože neobsahuje netriviální dělitele nuly a násobení je komutativní, a tedy distributivní zákon lze psát v jedné rovnici. V klasické teorii operací se definuje ještě jeden pojem, který je dokonce ještě silnější než obor integrity, a sice těleso: Definice 4.7. Těleso (anglicky: field ... proto některé české učebnice používají též název „pole ) je množina (M, +, ·), která je oborem integrity a navíc operace · splňuje vlastnost (4), tj. 5 Význam slova integrita: celistvost. Ve stejné rodině významů je i slovo integer = celek, celé číslo. Podobně i slovo „integrál vlastně znamená součet, spojení, sečtení. A fráze „is an integral part of ... = je nedílnou součástí, je zakomponovanou součástí. V Bibli je hebrejský výraz „:íš támím překládán do angličtiny jako „the man of integrity , do češtiny jako „muž bezúhonný , ale lepší by byl překlad „celistvý člověk ... to neznamená člověk naprosto dokonalý, ale člověk, který je ochoten pracovat na všech třech hlavních oblastech života: na svém vztahu k Bohu, na vztahu k lidem i na svém vztahu k práci. Tedy integrita je něco pozitivního, velmi žádoucího a charakterního. Podobně tomu bude i v matematice: obor integrity neobsahuje patologický jev výskytu netriviálních dělitelů nuly. 6 Aby byla definice naprosto čistá, měli bychom dodat, že množina je minimálně dvouprvková, obsahuje totiž nulu jako jednotkový prvek vzhledem ke sčítání a jedničku jako jednotkový prvek vzhledem k násobení a 0 = 1. 18 4 OKRUH, OBOR INTEGRITY A TĚLESO ad a) Operace + nesplňuje nic nového, ad b) operace · splňuje navíc vlastnost (4), tedy (M − {0}, ·) je grupa7 ; ad c) zde nic nového. Příklad 4.8. • (Z7, ⊕, ) je konečný obor integrity, ale též i konečné těleso, protože v případě konečné množiny M pojmy obor integrity a těleso splývají. • (Q, +, ·) je nekonečné těleso, protože (Q − {0}, ·) je grupa ... je splněna i vlastnost (4), že množina M obsahuje i inverzní prvky vzhledem k operaci násobení. (Z, +, ·) je nekonečný obor integrity, který není tělesem, protože množina Z neobsahuje většinu inverzních prvků vzhledem k operaci násobení. Tedy pojmy okruh, obor integrity a těleso představují struktury stále silnějších vlastností: Každé těleso je oborem integrity, každý obor integrity je i okruh (a z tranzitivity Obrázek 2: Vztah mezi pojmy okruh, obor integrity, těleso. pojmů plyne, že i každé těleso je okruh). Ale naopak to neplatí: existují okruhy, které nejsou oborem integrity, např. (Z6, ⊕, ); a existují obory integrity, které nejsou tělesem, např. (Z, +, ·). 7 Vlastnost (4) je silnější než vlastnost „neobsahuje netriviální dělitele nuly , tj. u bodu b) je dostatečné uvést, že operace · u tělesa splňuje (1),(2),(3),(4),(5). Lze dokázat tvrzení, že každé těleso je i oborem integrity, tj. těleso „neobsahuje netriviální dělitele nuly . 19 5 Základní vlastnosti grup • důkaz věty 1.6 ... Rosický, str.6; • důkaz věty 1.8 ... Rosický, str.6; • důkaz věty 4.1 indukcí ... Rosický, str. 22; • definice: invertibilní prvek ... takový prvek, ke kterému v dané množině existuje prvek inverzní vezhledem ke studované operaci. • definice: záporná mocnina prvku grupy se definuje jako příslušná kladná mocnina jeho inverzního prvku; • definice: řád prvku grupy; • znalost věty 4.17 = zákony o krácení ... vlastnost číslo (7): pokud (G, ·) je grupa a a, b, c ∈ G, pak platí implikace a · b = a · c ⇒ b = c, b · a = c · a ⇒ b = c. (7) Zde je dobré podotknout, že předpoklad, že G je grupa, je důležitý, protože například v problémové pologrupě (Z6, ) zákony o krácení neplatí: například [2] [2] = [2] [5], ale po zkrácení prvku [2] zleva bychom dostali [2] = [5], což není pravda. • důkaz věty 4.17 ... Rosický, str.26; Pojmy záporná mocnina prvku a řád prvku doplňte prosím příklady. 20 6 PODGRUPY, CYKLICKÉ GRUPY 6 Podgrupy, cyklické grupy • definice: podgrupa H grupy G; • definice: vlastní podgrupy grupy G ... takové podgrupy, které „mají méně prvků než původní grupa G, tj. všechny možné podgrupy mimo samotnou grupu G. • důkaz věty 5.5 ... Rosický, str.28. • definice: podgrupa generovaná množinou M ... nejmenší možná podgrupa grupy G, která obsahuje množinu M. • definice: cyklická grupa = grupa generovaná některým svým jediným prvkem • označení: < M > ... podgrupa grupy G generovaná množinou M; Definice pojmů doplňte prosím příklady. 21 7 Izomorfismy, homomorfismy a součiny grup • věta 4.18 a vlastnost (8): Pro grupu G a prvek a ∈ G je následující zobrazení ra bijekce: ra : G → G je definované předpisem ra(x) := a · x ∀x ∈ G. (8) Tato věta ilustruje jeden důležitý fakt, že když vynásobíme jedním pevným prvkem a (to je pevné) po řadě všechny prvky x (to se mění), dostaneme jako výsledek těchto součinů zase všechny prvky grupy G, tj. daný řádek tabulky grupové operace obsahuje všechny prvky právě jednou (tj. když se v řádku operace opakují některé prvky a nejsou všechny navzájem různé, tak víme, že množina G vzhledem k této operaci není grupa). Tohoto zobrazení se dále využívá v důkazu Caleyho věty (Rosický, str. 42, věta 8.14): Každá grupa je izomorfní nějaké podgrupě grupy permutací ... to plyne z toho, když si uvědomíme, že zobrazení ra je permutace všech prvků grupy G, tj. přiřazení a → ra je hledaný izomorfismus. Proto je ra důležité a má své číslo8 . • vlastnost (9) ... Kdy zobrazení f : (G1, ·) → (G2, ∗) mezi grupami zachovává výsledky operace? Tehdy, když platí f(a · b) = f(a) ∗ f(b) ∀a, b ∈ G1. (9) • definice: izomorfismus (součástí je vlastnost (9)); • definice: homomorfismus injektivní nebo surjektivní (součástí je vlastnost (9)); • definice: injekce9 = prosté zobrazení; • definice: surjekce = zobrazení NA; • definice: bijekce = vzájemně jednoznačné zobrazení; • označení: ∼= ... je izomorfní s; • důkaz věty 4.18 ... Rosický, str.26; • definice: jádro homomorfismu; • označení: ⇔ ... právě tehdy, když; • důkaz věty 6.4 ... Rosický, str.32; 8 V roce 2016/17 studenti nemusí důkaz Caleyho věty umět ke zkoušce, ale v roce 2017/18 už ano. 9 Lepší příklad injektivního homomorfismu než na přednášce: f : R → R je reálná funkce definovaná vztahem f(x) = exp x ... definiční obor je celé R, obor hodnot je pouze R+ , tedy vlastní podmnožina množiny R. 22 7 IZOMORFISMY, HOMOMORFISMY A SOUČINY GRUP • definice: součin grup ... Pokud G1, G2 jsou grupy, lze provést jejich kartézský součin G1 ×G2 a na tomto kartézském součinu definovat operaci · vztahem (vlastnost (10)) [a, b] · [c, d] := [a · c, b · d]. (10) Tato definice operace by se dala označit za přirozenou definici po složkách, a · c je totiž operace definovaná v grupě G1, a podobně b · d je operace definovaná v grupě G2 – tedy nově definovaná operace těží z vlastností operací definovaných v jednotlivých grupách. Důležitým příkladem součinu grup je množina R×R, kde (R, +) představuje množinu reálných čísel – pak grupa R×R s operací sčítání po složkách je množinou vektorů v rovině, grupa R×R×R s operací sčítání po složkách je množinou vektorů v prostoru. Studiu těchto důležitých grup se studenti budou věnovat v následujícím semestru v předmětu Algebra 2. Definice pojmů doplňte prosím příklady. 23 8 Relace, rozklady, uspořádané množiny V prvních sedmi přednáškách tohoto textu jsme se zabývali studiem pojmu „operace na množině M , tj. zobrazení M × M → M. Sledovali jsme operace • +, − (odčítání bylo schováno v inverzích prvků u operace +), • ·, : (dělení bylo schováno u inverzí v grupě vzhledem k násobení), • ∪, ∩, • ◦ (= skládání zobrazení), • ⊕, (operace sčítání a násobení na množině zbytkových tříd). Definice 8.1. V následujících zhruba čtyřech týdnech se budeme zabývat pojmem relace na množině M, což je obecně nějaká podmnožina kartézského součinu M × M. Prvky relace jsou tedy uspořádané dvojice [x, y], ve kterých záleží na pořadí. Budeme studovat vlastnosti relací například • ≤, ≥; • | (dělí = je dělitelem); • ⊆, ⊇; • ≡ (relace kongruence). Hlavní rozdíl mezi relacemi a operacemi: výsledkem operace ∗ mezi dvěma prvky a, b byl obecně nějaký třetí prvek a ∗ b, kdežto relace např. ≤ jen uvádí do vztahu dané dva prvky a, b, když a ≤ b (odtud i název, který vychází z anglického relation = vztah). (Horák, str. 24) Relaci lze podle definice zadat jako množinu uspořádaných dvojic (ve kterých záleží na pořadí prvků), například R = {[a, b], [b, a], [b, c], [b, b]}; ve shodě s učebním textem10 Kopka, Svazy a Booleovy algebry, str.17, budeme též relaci vypisovat takovým stylem, že označení relace bude umístěno v zápise mezi danými prvky (podobně jako ≤ je napsáno mezi prvky a a b, tj. v našem příkladu tatáž relace bude zapsaná i vztahy aRb, bRa, bRc, bRb. Každou relaci na konečné množině můžeme též reprezentovat grafem, kde prvek [a, b] znázorníme šipkou vycházející z a a směřující do b, prvek [b, b] znázorníme smyčkou z b do b, atd. (viz obrázek Horák, str. 24): 10 Zde náleží upozornění na kolizi značení: R v prvních sedmi kapitolách označovalo množinu reálných čísel, v kapitolách 8 až 11 to bude označovat relaci – obojí značení je tak tradiční a v literatuře zaužívané, že jej použiji i já navzdory tomu, že občas může dojít k nedorozumění. 24 8 RELACE, ROZKLADY, USPOŘÁDANÉ MNOŽINY Obrázek 3: Grafová reprezentace relace R – příklad. Další způsob, jak lze reprezentovat relaci R, je matice relace (pro tentýž příklad): a b c d a b c d      0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0      (na průsečíku prvního řádku (= řádku prvku a) a druhého sloupce (= sloupce prvku b) matice je hodnota 1, protože uspořádaná dvojice [a, b] je prvkem relace R; dále na průsečíku druhého řádku a druhého sloupce matice je 1, protože smyčka [b, b] je prvkem relace R; na třetím a čtvrtém řádku matice jsou samé nuly, protože c ani d není první souřadnicí žádné uspořádané dvojice z R, atd. Čtyřem šipkám v grafové reprezentaci odpovídají čtyři hodnoty 1 v matici relace. Příklad 8.2. (vyučující – studenti) V následující definici řekněte, (i) jak lze danou vlastnost poznat z grafové reprezentace relace (a z reprezentace maticí); (ii) jak musíme změnit výše obrázkem zadanou relaci, aby splňovala danou vlastnost (11), anti-(11), (12), anti-(12). Definice 8.3. Podobně jako u operací jsme studovali různé vlastnosti, i u relací budeme studovat určité vlastnosti a rysy. Nyní si uvedeme první z nich. Relace R na množině M se nazývá reflexivní, když ∀x ∈ M : xRx; (11) antireflexivní, když ∀x ∈ M : ¬(xRx); (anti-11), symetrická, když ∀x, y ∈ M : xRy ⇒ yRx; (12) 25 antisymetrická, když ∀x, y ∈ M : (xRy ∧ yRx ⇒ x = y); (anti-12) tranzitivní, když ∀x, y, z ∈ M : xRy ∧ yRz ⇒ xRz; (13) V dalším budeme většinou uvažovat jen definici a grafovou reprezentaci relace, maticovou reprezentaci nemusíte příliš znát. Příklad 8.4. (v trojicích, jen studenti) Vezměte si stránku A4 a rozdělte na osm částí. V každé části nakreslete pět bodů znázorňujících pětiprvkovou množinu, označte je a, b, c, d, e. Do množiny šipkami znázorněte relaci, která 1. je reflexivní, 2. je antireflexivní, 3. není ani reflexivní, ani antireflexivní, 4. je symetrická, 5. je antisymetrická, 6. není ani symetrická, ani antisymetrická, 7. je tranzitivní, 8. není tranzitivní. Příklad 8.5. (v trojicích, jen studenti) Jaké vlastnosti splňuje relace | (dělí, je dělitelem) na množině (Z, ·)? Relaci | definujeme normálně, jak bychom u dělitelnosti čekali: ∀x, y ∈ Z : x|y ⇔ (∃p ∈ Z : y = x · p) Definice 8.6. Relace R reflexivní a tranzitivní na M se nazývá kvaziuspořádání11 (a splňuje tedy vlastnosti (11),(13)). Pokud R je navíc a) symetrická, nazývá se ekvivalence na M (tj. ekvivalence splňuje vlastnosti (11),(12),(13); b) antisymetrická, nazývá se uspořádání na M (tj. uspořádání splňuje vlastnosti (11),anti-(12),(13)). Příklad 8.7. (vyučující – studenti) Jen dvě otázky, než pokročíme k vážnějším příkla- dům: • Může být některá relace symetrická a antisymetrická současně? • Může být některá relace ekvivalence a uspořádání současně? 11 Další, název v novější literatuře: Předuspořádání ... tj. pokud přidáme dobrou třetí vlastnost této relace, stane se z ní uspořádání. 26 8 RELACE, ROZKLADY, USPOŘÁDANÉ MNOŽINY A nyní už zajímavější příklady: Příklad 8.8. (v trojicích, jen studenti) U následujících příkladů rozhodněte, jaké vlastnosti splňují zadané relace: a) Relace ≤ na množině N = {1, 2, 3, . . .}; b) relace (být rovnoběžný) na množině přímek v rovině; c) Relace je zadána grafovou reprezentací12 na obrázku 4: Obrázek 4: d) Zadání opět grafem13 , obrázek 5: Obrázek 5: V další definici a následném příkladu se podíváme na vztah mezi relací ekvivalence a rozkladem množiny. Tuto strukturu jsme zde už měli, ale nyní se na ni zaměříme ještě jednou spíše z pohledu relací než operací: 12 Kopka, str.20, obr. 2a 13 Kopka, str.20, obr. 2b. 27 Definice 8.9. Řekneme, že systém pomnožin Mi množiny M tvoří rozklad množiny M, když a) i=1,...,n Mi = M; b) Mi ∩ Mj = ∅ pro i = j. Tj. ad a) sjednocením množin Mi je celá množina M, a ad b) množiny Mi jsou po dvou disjunktní, tj. každé dvě z nich mají prázdný průnik. Definujeme-li nyní relaci R vztahem xRy ⇔ x, y ∈ Mi pro nějaké i, (14) (prvky x, y jsou v relaci, když leží ve stejné třídě rozkladu), pak tato relace je ekvivalence a nazývá se relace určená (= indukovaná) rozkladem množiny M. Značíme M/R := {M1, M2, . . . , Mn} a množina M/R se nazývá faktorová množina množiny M podle ekvivalence R, nebo krátce faktormnožina14 . Příklad 8.10. Množina Z5: z kapitoly 3 už víme o relaci kongruence: a ≡ b (mod 5), když 5|(b − a). Podle této relace lze množinu celých čísel rozdělit do pěti podmnožin: Obrázek 6: Množina zbytkových tříd Z5. V této situaci lze nyní říci: a) Označíme-li M0 := [0], M1 := [1], M2 := [2], M3 := [3], M4 := [4], tak systém podmnožin {M0, M1, M2, M3, M4} tvoří rozklad množiny Z. b) Označíme-li znakem R danou relaci kongruence, můžeme psát xRy, když x, y náleží do stejné podmnožiny rozkladu ... tato relace je relací ekvivalence na Z (je to relace reflexivní (např. 5 ≡ 5), symetrická (např. 5 ≡ 10 implikuje15 , že 10 ≡ 5), tranzitivní (5 ≡ 10, 10 ≡ 30 ⇒ 5 ≡ 30). 14 Česky: rozkladová množina (ale vžil se anglický název, FACTOR (jako sloveso) znamená ROZLOŽIT). 15 Česky: z toho plyne, že ... 28 8 RELACE, ROZKLADY, USPOŘÁDANÉ MNOŽINY c) Když se na Mi přestaneme dívat jako na množiny a začneme se na ně dívat jako na prvky, dostaneme pětiprvkovou množinu Z/R := {M1, M2, M3, M4, M5}, kde všechna čísla v každé množině Mi jsme ztotožnili v jedno a označili za jediný prvek. Je to faktorová množina množiny Z podle ekvivalence R, nebo krátce faktor- množina. d) (Z/R, ⊕) je tzv. faktorgrupa, pokud definujeme sčítání ⊕ pro nové prvky Mi, jak jsme to udělali v kapitole 3. Čili studenti se nemusí slova faktorgrupa bát – definujeme-li na faktormnožině operaci, která na ní splňuje vlastnosti (1),(2),(3),(4), mluvíme o faktorgrupě16 . Příklad 8.11. (ve trojicích, jen studenti) i) Relace = na M := {p q : p ∈ Z, q ∈ N} definovaná vztahem a b = c d ⇔ ad = bc je ekvivalence. a) Jaké zlomky leží v jedné třídě rozkladu indukované touto relací? b) co je to množina M/ = ? ii) Jaké vlastnosti splňuje relace na obrázku17 číslo 5? Obrázek 7: Definice 8.12. Množina M, na které je definovaná relace uspořádání, se nazývá (částečně) uspořádaná množina – v textu Kopka18 je označována poněkud nezvyklým termínem poset (z anglického partially ordered set)19 . 16 Vlastně probráno v kapitole 3, jen slovo faktorgrupa jsme tam nepoužili. 17 Kopka 4b, str.24. 18 Str.23, definice 1.6. 19 Je to skutetečně neobvyklý termín pro češtinu, až extrémní – ale navrhuji jej panu Kopkovi odpustit, určitě jej použil s dobrým záměrem, aby studenti a vyučující nemuseli stále vypisovat dlouhý termín částečně uspořádaná množina. 29 Ikdyž relace uspořádání je blízká relaci ≤ (respektive ≤ je čtenáři známým příkladem uspořádání), budeme ji označovat (v souladu s textem Kopka) obecnějším symbolem ¢, který zaručuje, že se ne vždy bude jednat o relaci zcela totožnou s klasickou relací ≤ na množině celých či reálných čísel. Příklad 8.13. Je (Z, |) (s relací dělitelnosti) částečně uspořádaná množina (= poset)? Definice 8.14. Pro relaci uspořádání zavádíme kromě grafové reprezentace přehlednější strukturu, a sice tzv. Hasseovy diagramy, ve kterých 1. reflexivitu (= smyčky) nevyznačujeme, protože ji automaticky předpokládáme u všech prvků uspořádané množiny; 2. šipky odstraníme tak, že Hasseův diagram jednoznačně orientujeme zdola nahoru – jestliže prvek je spojen s jiným prvkem výš v diagramu, tak je s ním v relaci; 3. hranami vyznačíme jen bezprostředně následující prvky – ostatní šipky vyplývající z tranzitivity nevykreslujeme; pak pokud x ¢ y, tak je mezi prvky x a y „řetězec spojů mezi bezprostředními předchůdci a následovníky; 4. antisymetrie bude z nákresů patrna též – ta ovšem spočívá spíše v neexistenci oboustranných šipek mezi různými prvky. Jako příklad zkusíme nakreslit Hasseův diagram pro pětiprvkovou množinu M = {a, b, c, d, e} a relaci R na M definovanou výčtem uspořádaných dvojic (výsledek viz obrázek 8): R = {[a, a], [b, b], [c, c], [d, d], [e, e], [a, d], [d, e], [a, e], [b, d], [b, e], [d, e]}. Obrázek 8: Hasseův diagram relace uspořádání. Příklad 8.15. (ve trojicích, jen studenti) Vypište podle Hasseova diagramu relaci R výčtem uspořádaných dvojic na obrázku 9: a) poset a; b) poset b20 : 20 Kopka, str.28, obrázky 5a,5b. 30 8 RELACE, ROZKLADY, USPOŘÁDANÉ MNOŽINY Obrázek 9: Dvě uspořádané množiny. Pojmy, označení a důkazy, které studenti musí znát z této kapitoly: studenti musí vysvětlit definice následujících patnácti pojmů a uvést vždy nějaký příklad: 1) relace, 2) reflexivní relace, 3) antireflexivní relace, 4) symetrická relace, 5) antisymetrická relace, 6) tranzitivní relace, 7) kvaziuspořádání, 8) ekvivalence, 9) uspořádání, 10) rozklad množiny, 11) třídy rozkladu, 12) ekvivalence indukovaná rozkladem, 13) faktorová množina množiny M podle ekvivalence R, 14) uspořádaná množina (= poset), 15) Hasseův diagram. 31 9 Význačné prvky v uspořádaných množinách V této kapitole začneme studovat vlastnosti částečně uspořádaných množin (tzv. posetů, nečesky řečeno), tj. množin, na kterých je definována relace uspořádání, kterou lze reprezentovat Hasseovým diagramem. Definice 9.1. Pokud (P, ¢) je poset, označme či definujme • relace ¡ se nazývá ostré uspořádání v množině P, když ∀x, y ∈ P: x ¡ y ⇔ (x ¢ y ∧ x = y); • relace se nazývá pokrytí v množině P, když ∀x, y ∈ P: x y ⇔ x ¡ y ∧ (∀a ∈ P : x ¡ a ¢ y ⇒ a = y) (jinými slovy, pokrytí je relace nejbližšího následovníka, tj. pokud x je pokryto prvkem y (tj. x y), tak mezi x, y už nelze vložit další prvek a různý od y). Říkáme, že y „bezprostředně následuje za x , nebo že „y pokrývá x . • dodejme zde ještě definici úplně uspořádané množiny neboli řetězce: (P, ¢) je úplně uspořádaná množina = řetězec, pokud ¢ je uspořádání a současně úplná relace, tj. pokud platí x ¢ y nebo y ¢ x pro každé dva x, y ∈ P. (anglicky: coset = completely ordered set) Poznámka: pomocí ostrého uspořádání a pokrytí lze lépe popsat konstrukci Hasseových diagramů: vyznačujeme v nich hranami pouze relaci bezprostředního následovníka21 . Příklad 9.2. (ilustrační příklad) Na obrázku 10 vidíte příklad jednoho cosetu = řetězce – je jím nekonečná množina Z. Obrázek 10: Množina Z je coset = řetězec. 21 Kopka, str.30, lemma 4. Platí tedy pro konečný poset (P, ¢) a a, b ∈ P toto: a ¡ b (ostře menší než) znamená, že v množině P existuje řetězec bezprostředních následovníků a = x0 x1 x2 . . . xn = b. 32 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Definice 9.3. (Význačné prvky posetu) Pokud (P, ¢) je poset, M = ∅ je podmnožina množiny P, tak prvek a ∈ M nazveme22 a) nejmenší prvek množiny M, když ∀x ∈ M : a ¢ x; b) minimální prvek množiny M, když ∃ x ∈ M : x ¡ a; c) největší prvek množiny M, když ∀x ∈ M : a ¤ x; d) maximální prvek množiny M, když ∃ x ∈ M : x £ a; Příklad 9.4. (ilustrační příklad) Ad obrázek 11: V tříprvkové množině M s uspořádáním zadaným na Hasseovském diagramu je 1 prvek minimální a nejmenší současně, a dále 3 je prvek maximální a největší současně. V množině N s klasickým uspořádáním ≤ je nejmenší prvek 1 a je to též minimální prvek. Největší prvek množiny N neexistuje. Obrázek 11: Dvě dobře uspořádané množiny = wosety. Dále na obrázku 12 je množina M, ve které a je minimální i nejmenší prvek současně. Na druhé straně, největší prvek tato množina nemá – má pouze dva maximální prvky c, d. Obrázek 12: Rozdíl mezi maximálním a největším prvkem. Tj. maximální prvek množiny M je takový, „nad kterým už není v této množině žádný prvek. Na druhé straně největší prvek musí být srovnatelný se všemi prvky množiny M a musí být větší nebo roven než libovolný z nich. 22 Tyto definice nebudu zkoušet v Algebře 1, protože patří do předmětu Základy matematiky. 33 V úvodních definicích ještě budeme potřebovat zmínit definici dobře uspořádané mno- žiny: Definice 9.5. Poset (P, ¢) se nazývá dobře uspořádaná množina (woset ... z anglického well ordered set), když ∀M = ∅, M ⊆ P: M má nejmenší prvek. V dobře uspořádané množině musí tedy i každá dvouprvková podmnožina mít nejmenší prvek, tedy každé dva prvky jsou srovnatelné. Tedy každá dobře uspořádaná množina je řetězec (= každý woset je coset). Jaký je tedy rozdíl mezi wosetem a cosetem? V cosetu nemusí mít některé podmnožiny (ani celá daná množina samotná) nejmenší prvek, kdežto we wosetu ano. Tedy M a N z obrázku 11 jsou dobře uspořádané množiny, kdežto Z z obrázku 10 ne, protože samotná množina Z nemá nejmenší prvek. Obrázek 13: Vztah mezi danými pojmy. Na obr. 13 vidíme vztah mezi danými třemi pojmy: jen některé velmi hezké řetězce jsou wosety, všechny řetězce jsou cosety (to je ekvivalentní označení), a nejvíce je posetů, protože to jsou mnohem obecnější struktury, které mohou obsahovat i dvojice navzájem nesrovnatelných prvků. Poté, co jsme si odbyli nezajímavé definice (ony tedy jsou důležité, ale dostane se na ně až v předmětu „teorie množin ), vraťme se k posetům a uvedeme si některé klíčové příklady posetů, které nejsou řetězce (tj. posety, které nejsou cosety). Příklad 9.6. (ilustrační) a) Vraťme se k označení 2P (viz kapitola 2) a nakreslíme strukturu posetu (2P , ⊆) pro P = {1, 2, 3} (tj. nezajímá nás v této chvíli operace průniku nebo sjednocení, ale relace ⊆): b) Na množině N definujme uspořádání pomocí dělitelnosti, tj. a ¢ b ⇔ a|b. Pak (N, ¢) je poset, který má nekonečně mnoho prvků. Na obrazku 6 je nakreslena jen jeho dolní část: 34 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Obrázek 14: 2P pro P = {1, 2, 3}. Ze struktury dělitelů vidíme, že např. číslo 24 má vlastní dělitele 1, 2, 4, 8, 3, 6, 12 (a sebe sama jako nevlastního dělitele). Příklad 9.7. (studenti ve trojicích) Nakreslete Hasseovský diagram posetu 2P pro P = {1, 2, 3, 4} – pro zjednodušení k uzlům diagramu nevpisujte závorky a čárky, tj. množiny budou označeny jen znaky prvků: např ∅, 12, 124 jsou označení různých množin. Podívejme se nyní na další význačné prvky v posetech: Definice 9.8. Když (P, ¢) je poset a M je nějaká neprázdná podmnožina množiny P, nazýváme prvek a ∈ P (pokud takový prvek existuje): • dolní závora množiny M, pokud a ¢ x ∀x ∈ M; • infimum množiny M (označujeme inf M), pokud je největším prvkem na množině všech dolních závor množiny M; tj. a je infimum, pokud pro všechny další dolní závory d platí d ¢ x ∀x ∈ M ⇒ d ¢ a; 35 • horní závora množiny M, pokud a ¤ x ∀x ∈ M; • supremum množiny M (označujeme sup M), pokud je nejmenším prvkem na množině všech horních závor množiny M. Tj. a je supremum, pokud pro všechny další holní závory h platí h ¤ x ∀x ∈ M ⇒ h ¢ a; Nejdůležitějším postřehem k předchozím definicím je asi to, že závory nebo infimasuprema množiny M nemusí samy být prvky množiny M!! Obecně závora, infimum či supremum je prvek množiny P, který může a nemusí ležet v dané množině M. Příklad 9.9. (ilustrační) a) Například v posetu přirozených čísel s uspořádáním zadaným dělitelností těchto čísel (obr. 6) uvažujme množinu M = {12, 8, 20}. Dolní závorou množiny M jsou čísla 1, 2, 4 (společní dělitelé prvků v množině M), a tedy infimem je číslo 4 jako největší z těchto prvků (tj. infimem v (N, |) je největší společný dělitel prvků v množině M. Analogicky horní závorou množiny M jsou společné násobky čísel 12, 8, 20, tj. čísla 120, 240, 360, atd., a tedy supremem je nejmenší horní závora, tedy číslo 120. b) V posetu podmnožin tříprvkové množiny (obr. 14) například platí inf{{1, 2}, {1, 3}} = {1, 2} ∩ {1, 3} = {1}, inf{{1, 2}, {2}, {2, 3}} = {2}, tedy infimem několika množin je jejich vzájemný průnik, sup{{1, 2}, {1}} = {1, 2} ∪ {1} = {1, 2} (supremem několika množin v dané struktuře je jejich sjednocení). Příklad 9.10. Najděte suprema množin na obrázku, pokud existují: 36 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Pojďme se nyní věnovat zobrazování mezi posety – to je už poslední částí této kapitoly a do velké míry to bude obsahovat podobné otázky jako homomorfismus grup. V případě posetů zde ovšem vystupuje pojem analogický, který budeme označovat jako izotonní zobrazení23 . Definice 9.11. (Kopka, str.41) (P, ¢), (A, ¢1) jsou posety (index 1 u uspořádání posetu A naznačuje, že se jedná obecně o jinou relaci uspořádání, než je relace ¢ v posetu P). Zobrazení F : P → A se nazývá izotonní zobrazení, když ∀ x, y ∈ P : x ¢ y ⇒ F(x) ¢1 F(y). (15) 23 Medicína: tonus = napětí (svalů), tj. špatný tonus znamená nachlazená, tvrdá a bolestivá záda nebo nohy (křeč ve svalech při zranění, podchlazení nebo s rostoucím věkem a nedostatkem pohybu). Izotonní roztok je takový roztok, který má stejné pH (= stejnou kyselost) jako tkáň, do které se má tento roztok při lékařském zákroku injekcí dostat (no a v matematice bude izotonní zobrazení asi zobrazení, které bude zachovávat určitou vlastnost). 37 Poznámka: izotonní zobrazení tedy zachovává uspořádání – každé dva prvky uspořádané v množině P se zobrazí na dva prvky, které jsou uspořádané v množině A. Příklad 9.12. (ilustrační) Obrázek 15: Příklad izotonního posetového zobrazení F. Obrázek 16: Zobrazení F není izotonní. Z obrázku 15 je vidět, že izotonní zobrazení nemusí být injekce ani surjekce, a dokonce může zobrazit dva srovnatelné, ale různé prvky v množině P na jeden a tentýž prvek množiny A. Celkem přirozeně tedy vyvstává definice izomorfismu posetů, který, podobně jako u izomorfismu grup, bude naprosto zachovávat celou strukturu a vlastnosti: 38 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Definice 9.13. (P, ¢), (A, ¢1) jsou posety. Zobrazení F : P → A se nazývá posetový izomorfismus, když je izotonní bijekce a F−1 je také izotonní. Dané posety označujema v takovém případě jako navzájem izomorfní. Jinými slovy, jsou-li dva posety izomorfní, jsou v podstatě totožné, se všemi svými vlastnostmi, až na přeznačení prvků. To je vidět z následující věty, která vypisuje základní vlastnosti izomorfismu posetů: Věta 9.14. F : P → A je posetový izomorfismus, (P, ¢), (A, ¢1) jsou posety. Pak platí: (i) Ostře srovnatelné prvky se zobrazí na ostře srovnatelné prvky: ∀ x, y ∈ P : x ¡ y ⇒ F(x) ¡1 F(y); (ii) F zachovává nesrovnatelné24 prvky: ∀ x, y ∈ P : x ‡ y ⇒ F(x) ‡1 F(y); (iii) F zachovává nejmenší prvek: obrazem nejmenšího prvku 0 (pokud existuje) posetu P je nejmenší prvek 0 posetu A; (iv) F zachovává minimální prvek: obrazem minimálního prvku (pokud existuje) posetu P je minimální prvek posetu A; (v) F zachovává infima konečných množin: Pro neprázdnou konečnou množinu M ⊆ P je obrazem inf M (pokud toto existuje) v množině P prvek inf(F(M)) množiny A, kde F(M) ⊆ A je množina obrazů prvků z M, tj. F(M) := {F(x) : x ∈ M}: F(inf M) = inf(F(M)); (vi) F zachovává největší prvek: obrazem největšího prvku 1 (pokud ten existuje) posetu P je největší prvek 1 posetu A; (vii) F zachovává maximální prvek: obrazem maximálního prvku (pokud ten existuje) posetu P je maximální prvek posetu A; (viii) F zachovává suprema konečných množin, pokud tato existují pro M ⊆ P: F(sup M) = sup(F(M)); Důkaz: Podívejme se jen na platnost vlastností (i), (ii), ostatní vlastosti je možné dokázat analogicky. Ad (i): Chceme dokázat, že posetový izomorfismus zachovává ostré uspořádání ¡, které odpovídá danému neostrému uspořádání ¢. Tak tedy: uvažujme, že platí x ¡ y, tedy platí také x ¢ y (to si připravujeme půdu pro použití vlastnosti (15), která platí pro neostré uspořádání). Protože izomorfismus F splňuje vlastnost (15), platí F(x) ¢1 F(y). 24 Označení: x ‡ y znamená, že prvky x, y jsou navzájem nesrovnatelné v relaci ¢. 39 Mohou nastat dvě situace, a sice F(x)¡1 F(y) (a to máme dokázat, takže to je příznivá situace), nebo F(x) = F(y) (to je nepříznivá situace). Prozkoumejme nepříznivou situaci: F(x) = F(y) nemůže nastat, protože pak by platilo (protože inverzní zobrazení F−1 je též izotonní) x = F−1 (F(x)) = F−1 (F(y)) = y, ale to je spor s předpokladem, že x ¡ y. Tedy musí nastat příznivá situace, a sice F(x) ¡1 F(y). Ad (ii): Dokazujeme sporem, a sice předpokládáme platnost negace, a z toho dospějeme ke sporu: Předpokládejme platnost negace A ⇒ B, a tedy platnost A ∧ ¬B: x ‡ y ∧ F(x), F(y) jsou srovnatelné. Pak protože F−1 je izotonní, musí být srovnatelné i prvky F−1 (F(x)), F−1 (F(y)), a protože F−1 (F(x)) = x a F−1 (F(y)) = y, je to spor s předpokladem, že x, y jsou nesrovnatelné. P Příklad 9.15. Uspořádejme si tedy informace o izotonních zobrazeních mezi posety z hlediska analogického pojmu homomorfismus z teorie grup: 1. Stejně jako u izomorfismu grup, i izomorfismus uspořádaných množin (= posetů) zachovává celou strukturu mezi danými dvěma množinami, všechny jejich vlastnosti. Například pro relaci dělitelnosti na množině přirozených čísel, uvažujme dva podposety posetu (N, |), které vidíme na obrázku 17 – poset dělitelů čísla 12 a poset dělitelů čísla 45. Z obrázku vidíme, že tyto posety jsou izomorfní. Obrázek 17: Izomorfní posety. 2. Podobně jako u injektivního homomorfismu grup se jednalo vlastně o izomorfismus první grupy s nějakou vlastní podmnožinou druhé grupy, i u injektivního izotonního zobrazení se jedná o izomorfismus prvního posetu s nějakou vlastní podmnožinou druhého posetu. Tj. všechny vlastnosti prvního posetu jsou zachovány jako součást vlastností druhého posetu. 40 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Obrázek 18: Injektivní izotonní zobrazení = izomorfní vnoření jednoho posetu do druhého. Na obrázku 18 vidíme injektivní izotonní zobrazení F – říkáme též, že poset P je izomorfně vnořen do druhého posetu A. 3. Do třetice, podobně jako u surjektivního homomorfismu grup (projekce, která zachovává jistou vlastnost, ale jiné ztrácí), i surjektivní izotonní zobrazení sice zachovává vlastnost (15), ale některé charakteristiky prvního posetu ztrácí: Například prvky 1, 2 na obrázku 19 v posetu P nesrovnatelné jsou surjektivním homomorfismem zobrazeny na tentýž prvek a ∈ A. 4. A konečně je teoreticky možná i čtvrtá situace, že totiž F je izotonní, ale není bijekce, ani injekce, ani surjekce – touto situací jsme se u grup ani nezabývali, i když určitě může nastat25 . Takové izotonní zobrazení vidíme na obr. 15 – vypuštěním prvku f z posetu A bychom ovšem dostali surjektivní izotonní zobrazení, tj. předchozí případ (tj. podobně jako případ 2 je ukryt v případu 1 – izotonní injekce je izomorfismem s nějakou vlastní podmnožinou posetu A – i případ 4 je ukryt v případu 3, a sice izotonní neinjektivní zobrazení je izotonní surjekcí na nějakou vlastní podmnožinu posetu A). Lze tedy mluvit o tom, že případ 4 znamená surjektivní projekci posetu P na nějaký vlastní podposet posetu A. Příklad 9.16. Nakreslete Hasseovské diagramy všech neizomorfních posetů pro tříprv- kovou26 množinu. Příklad 9.17. Nakreslete Hasseovské diagramy všech neizomorfních posetů pro čtyřprvkovou množinu. 25 Například projekce grupy (Z, +) do grupy permutací (S3, ◦) definovaná f(l) = e pro l liché, f(s) = u pro s sudé ... f je jistě homomorfismus grup, protože {e, u} je podgrupa grupy S3, ale není to injekce (jedná se o projekci všech sudých čísel na jeden prvek a všech lichých čísel na druhý prvek), ani surjekce, protože grupa S3 má ještě další čtyři prvky – ovšem tuto situaci lze vypuštěním těchto čtyř prvků převést na situaci surjektivního homomorfismu. V ROCE 2017/18 DOPLNIT DO KAPITOLY 7. 26 Jednoprvkový poset existuje jediný, dvouprvkové posety existují dva neizomorfní. 41 Obrázek 19: Surjektivní izotonní zobrazení. Stejně jako u homomorfismu grup byl význačným pojmem jádro homomorfismu, bude existovat i zde pojem „jádro izotonního zobrazení . Ovšem na rozdíl od grupy (kde sledujeme, jaké prvky se zobrazí v homomorfismu na jednotku), v posetu máme teoreticky i dva význačné prvky – nejmenší prvek a největší prvek celého posetu (pokud tyto prvky existují). Definice jádra tedy budou dvě: horní jádro a dolní jádro. Definice 9.18. F : P → A je izotonní zobrazení27 mezi posety. Dolní jádro tohoto izotonního zobrazení se nazývá množina všech prvků posetu P, které se zobrazí na nejmenší prvek 0 ∈ A, KerdF := {x ∈ P : F(x) = 0 .} Horní jádro izotonního zobrazení se nazývá množina všech prvků posetu P, které se zobrazí na největší prvek 1 ∈ A, Kerh F := {x ∈ P : F(x) = 1 .} Pokud nejmenší (největší) prvek cílové množiny A neexistuje, říkáme, že KerdF = ∅ (KerhF = ∅). A příkladem předchozího pojmu zakončíme tuto kapitolu: Příklad 9.19. (ilustrační) Obrázek ilustruje různá horní a dolní jádra izotonní surjekce ve dvou situacích: 27 Kopka definuje horní jádro jen pro izotonní surjekci – to je jen malý rozdíl; obecně jádro má cenu sledovat jen u surjekce, protože u injekce je jádro buď jednoprvková, nebo prázdná množina, což není moc zajímavé. 42 9 VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH Pojmy, označení a důkazy, které studenti musí znát z této kapitoly: studenti musí vysvětlit definice následujících pojmů a uvést jejich příklady a dokázat dvě drobné vlastnosti izomorfismu posetů: 1) ostré uspořádání, 2) relace pokrytí příslušná ostrému uspořádání, 3) coset = řetězec, 4) woset = dobře uspořádaná množina, 5) dolní závora, 6) infimum, 7) horní závora, 8) supremum, 9) izomorfismus posetů, 10) izotonní injekce, 11) izotonní surjekce, 12) důkaz věty 9.14.i), 13) dk. věty 9.14.ii), 14) dolní jádro izotonní surjekce, 15) horní jádro izotonní surjekce. 43 10 Polosvazy a svazy V předešlé kapitole jsme zavedli pojmy infimum (= největší dolní závora) a supremum (= nejmenší horní závora). Pomocí těchto pojmů nyní definujeme na posetu P dvě operace28 : průsek a spojení . Definice 10.1. Pokud v posetu (P, ¢) má každá dvouprvková podmnožina své infimum, lze definovat operaci průsek x y := inf{x, y} (16) a poset (P, ¢) se nazývá průsekový polosvaz; to tedy znamená, že • x y je dolní závorou, tj. x y ¢ x, x y ¢ y; (16a) • x y je největší dolní závorou, tj. ∀d ∈ P : (d ¢ x ∧ d ¢ y ⇒ d ¢ x y). (16b) Pokud v posetu (P¢) má každá dvouprvková podmnožina své supremum, lze definovat operaci spojení x y := sup{x, y} (17) a poset (P, ¢) se nazývá spojový polosvaz; to tedy znamená, že • x y je horní závorou, tj. x ¢ x y, y ¢ x y; (17a) • x y je nejmenší horní závorou, tj. ∀h ∈ P : (x ¢ h, y ¢ h ⇒ x y ¢ h). (17b) Poznámka: Lidové vysvětlení pojmů průsek a spojení (a tedy potažmo i vysvětlení pojmů infimum, supremum): a) Pokud poset (P, ¢) je průsekový polosvaz, v jeho Hasseově diagramu ∀x, y ∈ P ∃! z ∈ P, • do něhož se po hranách dostanete z x i y cestou stále dolů (z je dolní závora množiny {x, y}), • přičemž z je ze všech takových uzlů nejvýše (je největší dolní závora množiny {x, y}). b) Pokud poset (P, ¢) je spojový polosvaz, v jeho Hasseově diagramu ∀x, y ∈ P ∃! z ∈ P, • do něhož se po hranách dostanete z x i y cestou stále vzhůru (z je horní závora množiny {x, y}), • přičemž z je ze všech takových uzlů nejníže (je nejmenší horní závora množiny {x, y}). Příklad 10.2. Rozhodněte, zda je daný poset také průsekový polosvaz nebo spojový polosvaz, vypočtěte dané operace průseku nebo spojení: 28 Pozor: prvních sedm přednášek bylo věnováno operacím, přednáška 8 a 9 relacím – nyní v kapitolách 10 a 11 na struktuře zvané poset dochází k souhře těchto pojmů: pomocí relace uspořádání budeme definovat dvě operace. Studium této souhry relací a operací je svým způsobem zlatým hřebem tohoto předmětu. 44 10 POLOSVAZY A SVAZY (i) (ii) (iii) (iv) 45 Poznámka: Jak si studenti dobře zapamatují operace , ? • operace na množině29 (2A , ⊆) je totéž jako operace ∩; • operace na množině (2A , ⊆) je totéž jako operace ∪. Tj. (2A , ⊆) je důležitým příkladem posetu, který je současně průsekovým i spojovým polosvazem. , jsou operace – lze tedy studovat bližší vlastnosti těchto operací!!!!!!!!!!! Jsou pro ně splněny vlastosti (1) až (7) definované v první polovině tohoto textu? Podívejme se pro začátek alespoň na vlastnosti (1) až (5), a pak zmíníme jednu novou, kteoru označíme číslem (18): (1) Uzavřenost operace na dané množině platí z podstaty věci: z definice −polosvazu nebo −polosvazu už je zaručeno, že na daném nosiči (= v množině P) existuje příslušné infimum či supremum ... tj. tato vlastnost platí: operace je uzavřená na daném −polosvazu, operace je uzavřená na každém −polosvazu. (2) Asociativita operací , je splněna a je velmi zajímavé a instruktivní důkaz provést, využívá se při něm totiž základních vlastností operací průsek a spojení, které jsou obsaženy přímo v definici (tedy vlastnosti (16a),(16b), respektive (17a),(17b)). Dokažme30 například asociativitu operace průsek: ∀x, y, z ∈ P : (x y) z = x (y z). 29 Označení 2A vysvětleno v kapitole 2. 30 Při odvozování důkazu je nad implikacemi nebo nerovnostmi vždy číslo vlastnosti, na základě které příslušná implikace nebo nerovnost platí. Vysvětlivky těchto vlastností: (16a) ... průsek dvou prvků je menší nebo roven než každý z nich; (16b) ... pokud nějaký prvek je menší nebo roven než jiné dva, pak z definice je též menší nebo roven než jejich průsek; (17a) ... spojení dvou prvků je větší nebo rovno než každý z nich; (17b) ... pokud nějaký prvek je větší nebo roven než jiné dva, pak z definice je též větší nebo roven než jejich spojení. 46 10 POLOSVAZY A SVAZY No a v této fázi důkazu zbývá už jen malý kousek, stačí si uvědomit, že relace ¢ je antisymetrická, tj. platí a ¢ b ∧ b ¢ a ⇒ a = b. Tedy z obou nerovností, ke kterým jsem při odvozování dospěli, plyne nakonec rovnost, což je vlastnost (anti-12). Asociativita pro druhou operaci, , je dokazatelná analogicky. Pokud by stále ještě daný důkaz byl příliš náročný, lze si jednotlivé jeho části i nakreslit. První tři řádky předchozího odvozování lze znázornit v levé části následujícího obrázku, další tři řádky v pravé části: Z obrázku je vidět, že antisymetrie (anti-12) zaručuje, že oba prvky, mezi kterými by existovaly oboustranné šipky, se musí rovnat. (3) Existuje v polosvazech jednotkový prvek vzhledem k operaci průsek či spojení? Jen někdy: Jednotkou vzhledem k operaci je největší prvek −polosvazu, pokud ten existuje (on existovat nemusí pro tento typ polosvazu – například obrázek (ii) za definicí polosvazu). Podobně jednotkou vzhledem k operaci je nejmenší prvek −polosvazu, pokud tento existuje (existovat totiž nemusí pro −polosvaz – například obrázek (iii) za definicí polosvazu). (4) Vzhledem k analogii s operací průniku ve struktuře (2A , ⊆) – viz úvodní označení a věta 1 v kapitole 2 – a faktu, že (2A , ⊆) je průsekový polosvaz, neexistuje v této struktuře většina inverzních prvků, i když existuje jednotka vzhledem k dané operaci. Podobné platí o operaci , když uvážíme, že (2A , ⊆) je i spojový polosvaz. To jsou tedy protipříklady, které ukazují, že obecně neplatí vlastnost (4). (5) Komutativita platí!!! To plyne z faktu, že existence infima či suprema dvouprvkové množiny nezávisí na pořadí prvků v této množině. 47 (18) A konečně slibovaná nová vlastnost, kterou nazveme idempotence (z latinského idem = totéž, stejné): Operace , jsou idempotentní na příslušných polosvazech, na kterých je lze definovat, a sice ∀x ∈ P : x x = x, x x = x. (18) Idempotence je zajímavá vlastnost, protože vylučuje existenci mocnin – x2 vzhledem k operaci je totiž x x, a to je rovno x, podobně x3 = x x x = x, atd., zkrátka práce s mocninami je touto vlastostí eliminována. Alespoň někdy nemusíme počítat žádné mocniny!! Analogicky platí pro operaci spojení x3 := x x x = x, x4 = x, atd. Poznámka: Idempotentní prvek v grupě je jediný, a to jednotka této grupy – jen jednotka grupy splňuje vlastnost e · e = e (a více jednotek v grupě být nemůže, jak jsme dokázali o vlastnostech grupy). Ovšem pozor, idempotentní prvky (což jsou v polosvazech všechny prvky) nejsou vzhledem k polosvazové operaci průseku či spojení jednotky, protože vlastnost (18) platí vždy jen pro prvek samotný, nikoli pro různé prvky x, y. Polosvazy jsou (pokud splňují vlastnost (3)) většinou pologrupy, ale jejich operace , jsou jiného charakteru než operace v grupách. Lze tedy uzavřít, že pologrupy nám jsou zdrojem řady zvláštních vlastností – existence dělitelů nuly v Zn, vlastnost idempotence ve struktuře všech podmnožin, apod. Co nás tady ještě čeká? Analogií operace s průnikem a operace se sjednocením na struktuře (2A , ⊆) jsme si připravili půdu k následující definici, která je tedy celkem přirozená. V dalším se teď budeme zabývat otázkou: Jaké vlastnosti má poset, který je současně polosvazem obou typů? Definice 10.3. Poset (P, ¢), který je současně průsekový i spojový polosvaz, se nazývá svaz31 . Analogicky lze říci, že protože svaz je spojením vlastností průsekového polosvazu a spojového polosvazu, tak pro svaz je charakteristické, že s každou svou dvouprvkovou podmnožinou obsahuje i její infimum a supremum32 . Pod svazem tedy chápeme strukturu (P, ¢, , ), kde a) relace ¢ splňuje vlastnosti (11), (anti-12), (13); b) operace splňuje vlastnost (16) (tedy prakticky obě z vlastností (16a),(16b)); c) operace splňuje vlastnost (17), tedy prakticky v řeči nerovností to jsou vlastnosti (17a),(17b). Příklad 10.4. Několik příkladů svazů: 31 Anglicky: lattice. Pozor, neplést s hlávkovým salátem: lettuce. Anglicky polosvaz: semilattice. 32 Které ovšem nemusí ležet přímo v dané dvouprvkové podmnožině, jak jsme už na několika příkladech viděli. 48 10 POLOSVAZY A SVAZY Př. 1 Po struktuře (2A , ⊆) je i druhý hlavní příklad předchozí kapitoly (6 b)), množina N s relací definovanou na základě dělitelnosti, svaz. Průsekem dvou přirozených čísel je jejich největší společný dělitel, spojením dvou čísel je jejich nejmenší společný násobek – tyto dvě charakteristiky vždy existují pro každá dvě přirozená čísla. Př. 2 I některé podposety svazu (N, |) jsou svazy, například podsvaz33 všech dělitelů čísla 24 nebo podsvaz všech dělitelů čísla 30 Naopak řada podposetů posetu (N, |) svazem není, protože nejsou uzavřené na operace průseku a spojení. Například podposet prvních devíti přirozených čísel není svazem, protože v něm neexistuje například supremum dvouprvkové množiny {4, 6}: 33 Z příkladů je vidět, že aby podmnožina svazu byla též svazem, musí být uzavřená vzhledem k operacím průsek a spojení. 49 Př. 3 Každý řetězec (= coset) je svaz ... například N s klasickým uspořádáním ≤ je svaz, (Z, ≤) je svaz. Př. 4 Vybrané podmnožiny trojrozměrného prostoru R3 s přirozeným uspořádáním ⊆ tvoří svaz: prázdná množina, všechny jednoprvkové množiny (= všechny body trojrozměrného prostoru), všechny přímky, všechny roviny, a nakonec celý prostor R3 samotný. Pak na této struktuře lze definovat průsek zcela normálně množinově (pro přímky p, q je p jejich průsečík, nebo prázdná množina v případě rovnoběžných různých nebo mimoběžných přímek; pro přímku a rovinu je jejich průsekem též průsečík, nebo prázdná množina, pokud průsečík neexistuje, nebo celá daná přímka, pokud v dané rovině leží; průsekem dvou rovin je jejich průnik, atd.). Operaci spojení nelze definovat přímo množinově jako sjednocení, protože mnohá sjednocení nejsou mezi vybranými prvky struktury – ovšem definujeme-li např. spojení dvou různoběžných či rovnoběžných přímek jako rovinu, která obě přímky obsahuje, spojení bodu a přímky jako buď tuto přímku, pokud na ní bod leží, nebo celou rovinu, ve které leží od i přímka, spojení dvou mimoběžek jako celý prostor R3 , protože to je jediný mezi prvky struktury, který obě mimoběžky obsahuje, atd., tak je opět zaručeno, že pro každé dva prvky struktury existuje v ní i jejich supremum34 . Př. 5 A abychom zavzpomínali na témata 1 až 7, tak i množina všech podgrup dané grupy, s uspořádáním množinovým ⊆ tvoří svaz. Průsek na této struktuře lze definovat jako množinový průnik, spojení opět nefunguje jako sjednocení, ale musíme je definovat G1 G2 :=< G1 ∪ G2 > , což je podgrupa generovaná sjednocením množin G1, G2, tj. „nejbližší větší podgrupa, která obě množiny obsahuje. Například vezmeme-li naši starou známou grupu permutací (S3, ◦), svaz jejích podgrup lze znázornit v Hasseově diagramu: 34 Tedy operaci spojení dvou prvků musíme definovat jako průnik těch množin, které oba prvky obsahují. Intuitivně řečeno je to „nejbližší větší prvek v dané struktuře. 50 10 POLOSVAZY A SVAZY Každé dvě z podrup na prostřední vrstvě vygenerují vzájemným skládáním prvků už všech šest prvků, tedy celou grupu S3, tj. např. {e, v} {e, w} = {e, v} ∪ {e, w} = S3, jak jsme viděli v kapitole 2. Dříve než přistoupíme ke studiu dalších vlastností svazu, všimneme si ještě jedné věci, která platí i v každém polosvazu – každý polosvaz definuje tzv. duální polosvaz, jehož Hasseovský diagram je obrácen vzhůru nohama o 180 stupňů: Definice 10.5. Pokud například (P, ¢) je průsekový polosvaz, tak duální uspořádání ¤ definujeme jako relaci, ve které obrátíme směr všech šipek. Struktura (P, ¤) se pak nazývá duální polosvaz a jedná se o spojový polosvaz. Příklad 10.6. Na obrázku vidíme −polosvaz (P, ¢) a vedle něj nakreslený −polosvaz (P, ¤) zadaný toutéž množinou, pouze všechny šipky mají opačný směr, tj. Hasseovský diagram je oproti původnímu polosvazu „hlavou dolů . 51 Z příkladu je vidět i duální vztah mezi příslušnými pojmy v daném duálním polosvazu: • K dolní závoře v −polosvazu je jednoznačně přiřazena horní závora v duálním −polosvazu. • K infimu a b v −polosvazu je jednoznačně přiřazena supremum a b v duálním −polosvazu; Tedy ve vztahu duality nejsou jen relace ¢ a ¤, ale i operace a . Například vztahy (16a), (16b) jsou duálními ke vztahům (17a),(17b). Pokud jsme podrobně dokázali asociativitu (2) pro operaci , tak analogický vztah asociativity pro operaci bychom dokázali přesně stejným postupem, pouze • znak bychom zaměnili za znak ; • znak ¢ bychom zaměnili za znak ¤; • vlastnost (16a), pojem dolní závory, bychom zaměnili za vlastnost (17a), pojem horní závory; • vlastnost (16b), pojem infima, bychom zaměnili za vlastnost (17b), pojem suprema. Ve svazech, kde jsou definovány obě operace současně, tj. existují současně infima i suprema dvouprvkových podmnožin, lze někdy využívat těchto duálních vztahů mezi pojmy a z platnosti určité vlastnosti jednoduše dokázat příslušnou duální vlastnost pouze záměnou za , ¤ za ¢, horních závor za dolní závory, suprem za infima. To je pro matematiky velmi pomocný poznatek, protože jim usnadňuje práci s dokazováním vlastností ve svazech na polovinu. Pojmy, označení a důkazy, které studenti musí znát z této kapitoly: 1) průsek a spojení, 2) průsekový polosvaz, spojový polosvaz, 3) dk. asociativity (2) pro průsek, 4) příklad polosvazu, kde platí vlastnost (3) pro spojení (průsek), 5) příklad polosvazu, kde neplatí vlastnost (4) pro spojení (průsek), 6) definice a význam idempotence, 7) definice a příklady svazu, 8) duální uspořádání a duální polosvaz, 9) vytvoření duálního vztahu (17a) ze vztahu (16a), 10) vytvoření duálního vztahu (16b) ze vztahu (17b). 52 11 DALŠÍ VLASTNOSTI SVAZŮ 11 Další vlastnosti svazů Z předchozí kapitoly víme, že ve svazu platí pro operace , vlastnosti (1), (2), (5), (16a), (16b), (17a), (17b), (18), protože to jsou vlastnosti, které si tyto operace přinesly z příslušných polosvazů (tj. platí i v každém polosvazu). V této kapitole se podíváme ještě na několik vlastností, které platí v každém polosvazu, nebo které platí speciálně pouze ve svazech. Pak můžeme spokojeně uzavřít tento semestr s pocitem, že o vlastnostech svazů víme řadu věcí. Následující vlastnost snad ještě patří do předešlé kapitoly, protože formálně dokazuje základní fakt, který jsme už vypozorovali při hledání výsledků operace průseku a spojení pro srovnatelné prvky. Věta 11.1. (Kopka, str. 66) V každém svazu (S, ¢, , ) platí: a) x ¢ y ⇔ x y = x (platí i v −polosvazu); b) x ¢ y ⇔ x y = y (platí i v −polosvazu). Důkaz: ad a) Viz sken: Příklad 11.2. Dokažte část (b) předchozího tvrzení, když víte, že je duálním ke tvrzení (a). Protože (2A , ⊆, ∩, ∪) je svaz, budeme studovat vlastnosti této celkem přijatelné struktury v následujícím příkladu. Příklad 11.3. Už víte, že struktura 2A je pologrupa vzhledem k operacím sjednocení a průniku (viz začátek kapitoly 2, první věta v té kapitole) – zkuste ještě operace průniku a sjednocení více prozkoumat a najděte nějakou jejich další vlastnost: buď vlastnost odděleně jedné z těchto operací, nebo vlastnost vzájemné interakce obou z nich. Projděme tedy ještě jednou jednotlivé vlastnosti průniku a sjednocení, a přidáme si i vlastnosti, které jsmeještě neměli: Množiny (1),(2),(3) Tyto vlastnosti platí. Množiny (4) Neplatí, inverzní prvky vzhledem k operacím ∪, ∩ většinou neexistují. 53 Množiny (5) Platí ... sjednocení a průnik nezáleží na pořadí vstupujících množin. Množiny (6) Platí oboustranně tj. operace ∩, ∪ lze v distributivním zákonu zaměnit: pro podmnožiny X, Y , Z množiny A: Z ∩ (X ∪ Y ) = (Z ∩ X) ∪ (Z ∩ Y ) (6a), Z ∪ (X ∩ Y ) = (Z ∪ X) ∩ (Z ∪ Y ) (6b). Důkaz těchto rovností jsme provedli jen schematicky pomocí tzv. Vennových diagramů, ve kterých šrafujeme danou množinu na lévé straně rovnosti, pak na pravé straně rovnosti a výsledek porovnáme – viz obrázky pod jednotlivými tvrzeními. No to je teda bomba, to je ultravlastnost!! Operace průniku a sjednocení jsou navzájem distributivní v obou směrech!! Ta množina všech podmnožin je skutečně zvláštní struktura!! 54 11 DALŠÍ VLASTNOSTI SVAZŮ Množiny (anti-7) (rozšíření rovnosti) Pro každé dvě podmnožiny platí X = Y ⇒ X ∩ Z = Y ∩ Z, X ∪ Z = Y ∪ Z. Toto platí vždy pro podmnožiny dané množiny, podobně jako (anti-7) platí v každém grupoidu ... stačí, aby struktura byla uzavřená na danou operaci a výsledek operace existoval (vlastnost (1)). Množiny (7) (krácení v rovnosti průniku) Platí následující vztah? X ∩ Z = Y ∩ Z ⇒ X = Y. (7a) Jak ukazuje následující sken, i kdyby některé části diagramu byly bez prvků (vyznačeno ve skenu) a platilo X ∩ Z = Y ∩ Z, tak obecně, pokud množiny X, Y obsahují další prvky mimo svůj společný průnik, neplatí žádaná rovnost X = Y , ani neplatí dílčí nerovnosti X ⊆ Y , X ⊇ Y : (7b) Analogicky existují takové množiny, že X ∪ Z = Y ∪ Z ⇒ X = Y ; Viz sken: 55 Množiny (18) Idempotence35 X ∩ X = X, X ∪ X = X platí téměř zřejmě, tím jsme se už zabývali v předchozí kapitole, str. 45. Množiny (19) (absorbce) Jednoduše pomocí množinových Vennových diagramů pro obě strany rovnosti lze ověřit, že platí pro každé dvě podmnožiny dané množiny (X ∩ Y ) ∪ Y = Y, (X ∪ Y ) ∩ Y = Y. (19) První rovnost vyjadřuje, že průnik dvou množin je pohlcen (= absorbován) sjednocením s libovolnou z nich (tedy platí též (X ∩ Y ) ∪ X = X), druhá rovnost praví, že sjednocení dvou množin je pohlceno (absorbováno) průnikem s libovolnou z nich (tj. přeznačením X za Y lze psát také (X ∪ Y ) ∩ X = X. Množiny (20) (modularita) Zabývejme se chvíli otázkou, zda platí pro každé dvě podmnožiny dané množiny vztah X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ Z. (20) Tato rovnost připomíná asociativitu (2), ale nyní jsou v ní zahrnuty dvě operace. A kdyby platila, byla by to tedy supervlastnost, protože interakce dvou operací by nezáležela na uzávorkování, to by byl teda gól. Z Vennových diagramů vidíme, že vlastnost neplatí: Ovšem je vidět, že platí inkluze ∀X, Y, Z : X ∪ (Y ∩ Z) ⊇ (X ∪ Y ) ∩ Z. Tuto inkluzi (česky: vlastnost „být podmnožinou ) bychom mohli nazvat jako polo- modularitu36 nebo cizím slovem semimodularitu, přičemž rovnost nastane jen tehdy, když X − Z = ∅. 35 Příští rok, pokud budu přednášet, tato vlastnost bude mít číslo 8, vlastnost (19) číslo 9 a vlastnost (20) číslo 10 – v letnošním školním roce už to asi není rozumné přečíslovat. Tak budou vlastnosti (1) až (10) představovat různé možné vlastnosti operací. Při letošním označení (1) až (7), (18), (19), (20), I am sorry. 36 Pomůcka k zapamatování této přirozené polomodularity: vnější sjednocení (= sjednocení před závorkou) je nadmnožinou, podobně jako spojení dvou prvků je větší nebo rovno jednotlivým prvkům. 56 11 DALŠÍ VLASTNOSTI SVAZŮ Množiny modif-(20) (modifikovaná modularita) Z jistých důvodů se při studiu množin a svazů používá vlastnost tzv. modifikované modularity – do předpokladů modularity přidáváme podmínku X ⊆ Z. Je to pravděpodobně proto, že situace srovnatelných prvků X, Z je většinou ta, která nás zajímá. U mnoha vlastností je jedno, zda množiny X, Y , Z mají nějaké další prvky mimo své vzájemné průniky, ale zde u vlastnosti (20) je snad zajímavější sledovat situaci za podmínky X ⊆ Z. Tak tedy: • ∀X, Y, Z : X ⊆ Z ⇒ X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ Z. (modif-10) A u množin platí modifikovaná modularita jako rovnost! Lze snadno odtušit kreslením Vennových diagramů: Přechod: Svaz (2A , ⊆, ∩, ∪) je tedy velmi zajímavá struktura, protože splňuje vlastnosti (1),(2),(3), (5),(6), (18),(19),(20) (není splněno pouze (4) a (7) ze všech deseti vlastností operací, kterými jsme se v tomto semestru zabývali). Nesplňuje ovšem tato superstruktura něco navíc než každý svaz s operací průseku a spojení? Které z těchto vlastností platí v každém svazu (S, ¢, , )37 ? Svazy (6) Platí v každém svazu distributivita? To by pro interakci průseku a spojení muselo platit z (x y) = (z x) (z y), z (x y) = (z x) (z y). Obecně zde neplatí rovnost, jak ukazuje následující příklad svazu, který se nazývá pentagon: Příklad 11.4. V pentagonu (viz následující sken) obecně neplatí žádná z distributivních rovností, platí jen jednostranné nerovnosti: 37 Vlastnosti (1) až (5) byly u svazů vlastně prověřeny v předchozí kapitole v rámci studia polosvazů – totéž lze říci i ve svazech, tj. svazy (respektive operace průsek a spojení v nich) nesplňují (3),(4). 57 Příklad 11.5. V diamantu (viz následující sken) obecně neplatí žádná z distributivních rovností, platí jen jednostranné nerovnosti: Zdá se ovšem, že jednostranné nerovnosti platí, tedy vzhledem k (6) jsou svazy polodistributivní = semidistributivní! Věta 11.6. V každém svazu (S, ¢, , ) platí ∀x, y, z ∈ S: • z (x y) ¤ (z x) (z y), (6a) • z (x y) ¢ (z x) (z y). (6b) Pomůcka k zapamatování (6a),(6b): překvapivě platí ty nepřirozené části, ty, které bychom neodvodili z operace průseku či spojení z definice. (6a) ... vnější průsek je nad spojením závorek, (6b) ... vnější spojení je pod průsekem závorek. Tj platí jen jednostranné nerovnosti, ale „zrovna ty silné, ty, které bychom nehádali či nečekali, že budou platit . Důkaz: Dokažme (6a), pak duální vztah (6b) je ke cvičení pro studenty: 58 11 DALŠÍ VLASTNOSTI SVAZŮ Příklad 11.7. Dokažte vztah (6b) pro svazy. Svazy =-anti-(7) (rozšíření rovnosti) Z rovnosti x = y plyne v každém svazu, že x z = y z, x z = y z. Svazy ¢-anti-(7) (rozšíření nerovnosti) Platí též, tj. pro x¢y platí v každém svazu, že • a) x z ¢ y z; • b) x z ¢ y z. Tyto vztahy je ovšem potřeba dokázat, protože nevíme přesně, co vše lze od obecného uspořádání čekat: Svazy (7) Krácení platilo jen v grupě, a neplatí v množinách – dá se tedy čekat, že nebude platit ani ve svazech, které jsou pologrupy vhledem ke operaci průseku a spojení. A opravdu, následující příklad ukazuje, že krácení neplatí ani pro rovnost, ani pro nerovnost, ani pro průsek, ani pro spojení. Využijem přitom svaz zvaný pentagon ještě jednou: 59 Svazy (18) (idempotence) Už bylo probráno v předchozí kapitole, idempotence operací průsek a spojení platí v každém příslušném polosvazu, tedy i ve svazech. Svazy (19) (absorbční zákony pro svazy) Věta 11.8. Pro svaz (S, ¢, , ) platí tzv. absorbční zákony (19) ∀x, y ∈ S : 19a) (x y) y = y, 19b) (x y) y = y. Absorbce = pohlcení. Vlastnost a): průsek dvou prvků je pohlcen (= absorbován) spojením s kterýmkoli z nich; Vlastnost b): spojení dvou prvků je pohlceno (= absorbováno) průsekem s kterýmkoli z nich. Důkaz: Dokážeme jen tvrzení a), a pak totiž tvrzení b) plyne z tvrzení a), protože je k němu duální: 60 11 DALŠÍ VLASTNOSTI SVAZŮ Příklad 11.9. (ve dvojici či trojici) Dokažte vztah (b) z předchozí věty podrob- něji!! Svazy modif-(20) U množin platila v modif-(20) rovnost, nyní platí u svazů pouze nerovnost, jak je vidět opět z příkladu pentagonu: Pomůcka k zapamatování modifikované semimodularity: vnější průsek je nepřirozeně nad (= větší nebo roven), vnější spojení je nepřirozeně pod (= menší nebo rovno). Vztah je tzv. autoduální, tj. duální k sobě samému, neexistuje žádný jiný vztah modifikované semimodularity. Věta 11.10. V každém svazu platí vlastnost modif-semi-(20), tj. ∀x, y, z : x ¢ z ⇒ x (y z) ¢ (x y) z. Důkaz: Vztah je nyní jediný, jeho důkaz je opět v kategorii standardních důkazů, které využívají definice průseku jako infima (16a),(16b) a spojení jako suprema (17a),(17b) dvouprvkových množin: Zdá se tedy, že struktura (2A , ⊆, ∩, ∪) vykazuje ještě lepší vlastnosti než obecný svaz (S, ¢, , ). Proto, abychom ve svazech zajistili přesně to, co se odehrává v množinách, tj. například vlastnosti modif-(20) a (6) a nikoli jen polovlastnosti, musíme ještě k definici svazu přidat další podmínky. Které? Směřujeme ke struktuře, které se říká Booleova algebra, kde 2A je příkladem Booleovy algebry. Ale na to už nebudeme mít nyní čas – možná až v algebře 3. Poslední poznámka na závěr studia svazů: lze definovat pojem podsvazu jako podmnožinu svazu, která je uzavřená vzhledem k operacím průseku a spojení. To je ovšem pojem přirozený a lze jej očekávat. V každém svazu existuje průsek (či spojení) dvou prvků, a tedy existuje též průsek (spojení) k prvků x1 x2 . . . xk. Dalším směrem matematického zkoumání je rozšíření operace spojení a průseku na nekonečně mnoho prvků38 : 38 Kopka, str.72-73. 61 Definice 11.11. Pokud v daném posetu S existují infima a suprema všech jeho nekonečných podmnožin M, označujeme operace zobecněný průsek z M := inf M i pro M nekonečnou, (21) zobecněné spojení z M := inf M i pro M nekonečnou. (22) Struktura (S, ⊆, z, z) se nazývá úplný svaz39 . Příklad 11.12. Množina přirozených čísel s klasickým uspořádáním ≤ je svaz, ale není to úplný svaz, protože neexistuje supremum celé nekonečné množiny N. Podobně množina Z je svaz, ale není úplný svaz, protože v ní neexistuje např. supremum podmnožiny všech kladných celých čísel, nebo infimum podmnožiny všech záporných celých čísel. Na studium úplných svazů zde nyní už není prostor (více viz Kopka, str.72-82). Poznamenejme zde jen, že pojem má smysl u nekonečných množin, protože každý konečný svaz je současně i úplný svaz. Proto by více detailů mohlo následovat v předmětu Algebra 3 nebo v magisterském předmětu Teorie množin, který se zevrubněji zabývá množinami nekonečnými. Každopádně pojem úplného svazu směřuje k zajímavému hlavnímu výsledku, že každý poset lze izomorfně vnořit do úplného svazu (Mac Neillova věta), jehož vedlejším produktem je popis konstrukce množiny reálných čísel jako úplného svazu, do kterého lze izomorfně vnořit svaz Q racionálních čísel40 . Z této kapitoly by studenti měli znát: 1) Definici úplného svazu a příklad svazu, který není úplný; 2) dk. věty 11.1; 3) vyslovit a dokázat (pomocí Venových diagramů) některé z vlastností průniku a sjednocení množin, zejména vlastnosti (6), (19) a modif-(20); 4) vyslovit a dokázat některé vlastnosti svazů, zejména semi-(6), (19) a semi-modif-(20). 39 Pozor, slovo „úplný nyní není vzato z terminologie úplné relace – v úplném svazu nadále mohou existovat nesrovnatelné prvky. Spíše se zde míní úplnost vzhledem k supremům a infimům – úplný svaz obsahuje i infima a suprema svých nekonečných podmnožin, což v obyčejném svazu platit nemuselo. 40 Množina Q totiž neobsahuje suprema a infima některých svých nekonečných podmnožin – když množinu Q o tato infima a suprema doplníme, dostaneme množinu R. 62 12 VÝSLEDKY NĚKTERÝCH PŘÍKLADŮ 12 Výsledky některých příkladů 12.1 Výsledky ke kapitole 8 – relace, uspořádané množiny Viz příklad 2: reflexivní relace je reprezentována smyčkami u všech prvků (jedničkami na celé hlavní diagonále), antireflexivní relace nepřítomností smyček (nepřítomností jedniček na hlavní diagonále), symetrická relace má pro každou šipku též šipku v opačném směru, antisymetrická relace nemůže mít oboustranné šípky mezi dvěma různými prvky, tranzitivní relace musí pro např. šipku od a do b a od b do c obsahovat i šipku od a do c. Viz příklad 4: Studentům by mělo být jasné, že např. antireflexivní relace není negací relace reflexivní, ale úplným protipólem reflexivní relace – tj. že existují relace s nějakou smyčkou, které nejsou ani reflexivní, ani antireflexivní. Podobně u tranzitivní relace nemusí být všechny možné tranzitivní spoje prvky relace, ale jen ty, které jsou vynuceny šipkami v posloupnosti tří prvků (tj. xRy a yRz vynucují šipku xRz). Viz příklad 5: R je reflexivní a tranzitivní, tedy kvaziuspořádání. Je důležité si všimnout, že relace R není antisymetrická, protože například 3|(−3) a (−3)|3, ale odtud neplyne 3 = −3. Není ani symetrická, protože pokud 3|6, neplyne odtud, že 6|3. Viz příklad 7: ad a) může ale jen podmnožina reflexivní relace, bez šipek mezi různými prvky; ad b) jediná relace je současně ekvivalence i uspořádání, a sice samotná reflexivní relace xRx ∀x ∈ M. To není zajímavý příklad ani ekvivalence (každý prvek je v relaci jen se sebou samým), ani uspořádání (všechny prvky jsou navzájem mezi sebou nesrovnatelné – k jejich „vzájemnému uspořádání vlastně nedošlo). Viz příklad 8: ad a) R je reflexivní, antisymetrická a tranzitivní, tedy uspořádání. ad b) R je reflexivní, symetrická a tranzitivní, tedy ekvivalence. ad c) R je reflexivní, antisymetrická a tranzitivní, tedy uspořádání. ad d) R je pouze reflexivní, jinak nic rozumného nelze říci. Viz příklad 11: ad i) a) v jedné třídě rozkladu leží zlomky, které lze zkrátit na stejný základní tvar; b) množina M/ = je množina všech racionálních čísel (všechny zlomky upravitelné na tentýž základní tvar jsme ztotožnili v jedno racionální číslo). ii) Relace je reflexivní, antisymetrická a tranzitivní, takže je to uspořádání!! Viz příklad 13: Ne, protože není antisymetrická. Ale (Z/E) už je poset, pokud relace E ztotožňuje 3, −3 do jednoho prvku [3], dále 4, −4 do jednoho prvku [4], atd. a uprostřed nulu nechává nulou a označuje ji jako [0]. Tím pádem jsme dostali strukturu N0, kde relace dělitelnosti je už antisymetrická (pro žádné různé prvky (x = y) neplatí x|y ∧y|x). Viz příklad 15: ad a) [1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [1, 3], [1, 4], [4, 3], [1, 3]. ad b) [1, 1], [2, 2], [3, 3], [4, 4], [3, 4], [4, 1], [3, 1], [4, 2], [3, 2]. 12.2 VÝSLEDKY KE KAPITOLE ?? – VÝZNAČNÉ PRVKY V USPOŘÁDANÝCH MNOŽINÁCH 63 12.2 Výsledky ke kapitole 9 – význačné prvky v uspořádaných množinách Viz příklad 7: Jedná se o poset zobrazený na titulní straně textu Kopka: obrázek 20. Obrázek 20: 2P pro P = {1, 2, 3, 4}. Viz příklad 10: ad a) sup{a, d} = c, sup{e, f} = e. ad b) sup M neexistuje, protože množina horních závor {b, c, d} nemá nejmenší prvek. Viz příklad 16: Neizomorfních posetů na tříprvkové množině je pět – viz obrázek: Viz příklad 17: Neizomorfních posetů na čtyřprvkové množině je šestnáct – viz obrázek 21. 12.3 Výsledky ke kapitole 10 – polosvazy, svazy Viz příklad 2: ad i) 4 7 = 2, 6 2 = 2, 7 7 = 7, 3 7 = 6, 6 8 = 6; jedná se o průsekový i spojový polosvaz; ad ii) 6 3 = 7, 6 3 neexistuje. Jedná se o průsekový polosvaz, který není spojovým polosvazem. 64 12 VÝSLEDKY NĚKTERÝCH PŘÍKLADŮ Obrázek 21: Všechny navzájem neizomorfní čtyřprvkové posety. ad iii) 5 7 = 10, 2 3 neexistuje, 2 7 neexistuje. Jedná se o spojový polosvaz, který není průsekovým polosvazem. ad iv) 4 5 neexistuje, 2 3 neexistuje. Tedy daný poset není ani průsekovým, ani spojovým polosvazem. 12.4 Výsledky ke kapitole 11 – další vlastnosti svazů Viz příklad 2: Důkaz věty x ¢ y ⇔ x y = y: 12.4 VÝSLEDKY KE KAPITOLE ?? – DALŠÍ VLASTNOSTI SVAZŮ 65 Viz příklad 7: Důkaz distributivity (6b) s vnějším spojením: Viz příklad 9: Důkaz absorbce spojení průsekem: