Algebra 1 (MA 0003) RNDr. Břetislav Fajmon, Ph.D. Katedra matematiky Pedagogické fakulty Masarykovy univerzity v Brně — verze 2021 Algebra 1 (MA 0003) 1 Obsah 1 Týden 01: Základní vlastnosti operace na množině M 4 1.1 Cvičení 1: Vlastnosti číselných operací.................... 4 1.2 Cvičení 2: Určovaní vlastností různých operací................ 7 1.3 Přednáška 1................................... 8 1.4 Dodatky 1.................................... 16 2 Týden 02 - další vlastnosti operace na množině 20 2.1 Přednáška 2................................... 20 3 Týden 03 24 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy ......... 24 3.2 Přednáška 3: Izomorfismus, Calyeho věta................... 27 4 Týden 04 33 4.1 Cvičení 04: Nekomutativní grupy....................... 33 4.2 Přednáška 04: Lagrangeova věta, homomorfismus grup, faktorgrupa .... 36 5 Týden 05 46 5.1 Cvičení 05: Rád prvku, cyklické grupy, grupy zbytkových tříd ....... 46 5.2 Přednáška 05.................................. 56 6 Týden 06 60 6.1 Cvičení 06: Rezerva, resty z minulých hodin, odpovědi na otázky...... 60 6.2 Přednáška 06: struktury se dvěma operacemi................. 60 7 Týden 07 65 7.1 Cvičení 07: Polynomy 01............................ 65 7.2 Přednáška 07: Struktury se dvěma operacemi II............... 66 8 Týden 08 67 8.1 Cvičení 08: Polynomy 02............................ 67 8.2 Přednáška 08: Přehled algebraických metod hledání kořene polynomu ... 68 9 Týden 09 69 9.1 Cvičení 09: Polynomy 03............................ 69 9.2 Přednáška 09: Přehled numerických metod hledání kořene polynomu .... 70 10 Týden 10 74 10.1 Cvičení 10: Komplexní čísla 01......................... 74 10.2 Přednáška 10: Konstrukce číselných oborů.................. 74 11 Týden 11 74 11.1 Cvičení 11: Komplexní čísla 02......................... 74 11.2 Přednáška 11: Konstrukce oboru C, o komplexních číslech.......... 74 2 Katedra matematiky PedF MUNI v Brně 12 Týden 12 74 12.1 Cvičení 12: Prověřka-b na polynomy a komplexní čísla ........... 74 12.2 Přednáška 12: Příprava a otázky ke zkoušce ................. 75 13 Výsledky některých příkladů 82 13.1 Výsledky ke cvičení 1.1 - zatím žádné nejsou uvedeny............ 82 13.2 Výsledky ke cvičení 1.2 - Určování vlastností různých operací....... 82 13.3 Výsledky ke cvičení 3.1 - Vlastnosti grup, podgrupy a generátory grupy . . 83 13.4 Výsledky ke cvičení 4.1 - nekomutativní grupy................ 84 13.5 Výsledky ke cvičení 5.1 - řád prvku, cyklické grupy, grupy zbytkových tříd 85 Algebra 1 (MA 0003) 3 Úvod Tato skripta jsou napsána jako doplňující text do předmětu Algebra 1 pro 2. semestr bakalářského studia budoucích učitelů matematiky na 2.stupni ZS. Předmět svým charakterem navazuje na témata předmětu MA0001 (Základy matematiky) a předpokládá, že studenti si budou pamatovat pojmy: množina, kartézský součin, relace, uspořádání, ekvivalence, zobrazení, operace, posloupnost, reálná funkce, a některé základní vlastnosti relace, viz cvičení 1 tohoto textu. V předmětu Základy matematiky jsme studovali zejména relace a jejich vlastnosti. Nyní v předmětu Algebra 1 budeme studovat zejména pojem operace. Tento text by nemohl vzniknout bez knihy (Pinter 2010), ze které jsem podstatně čerpal jak pro přednášku, tak pro cvičení. I když tento předmět se studentům nutně bude zdát teoretický, Charles Pinter napsal svou knihu s přesvědčením, že algebra je pro matematiku potřebná - stejně potřebná jako geometrie. V roce 2020 proběhla rekonstrukce osnovy, pro kterou budou v průběhu roku 2021 skripta průběžně doplňována. Pravděpodobně bude ve výuce použit i text kolegyně dr. Budínové o polynomech, pro část „komplexní čísla" bude obohacením i středoškolská učebnice (Robova, Hála, Calda 2013). Břetislav Fajmon, verze textu leden 2021 4 Katedra matematiky PedF MUNI v Brně 1 Týden 01: Základní vlastnosti operace na množině M 1.1 Cvičení 1: Vlastnosti číselných operací Podívejme se na tzv. Axiomy euklidovské geometrie: 1. Každé dva různé body lze spojit úsečkou. 2. Úsečku lze libovolně daleko prodloužit v přímku. 3. Pro dva různé body S, A lze sestrojit kružnici se středem v S, která prochází bodem A . 4. Přímý úhel lze kolmicí rozdělit na dva pravé úhly. 5. Bodem A, který neleží na přímce p, lze vést právě jednu přímku q rovnoběžnou s přímkou p. Tyto axiomy si budete ještě procházet v předmětu geometrie. Nyní si pouze všimněme toho, že axiomy udávají vztahy mezi jednotlivými geometrickými pojmy (ty jsou podtrženy), nebo vlastnosti některých pojmů (např. přímý úhel je speciální úhel, který lze rozdělit kolmicí na dva shodné pravé úhly ... vlastnost 4). Úkol cca na 10 min ve dvojicích. Přemýšlejte nad vlastnostmi známých operací sčítání, odčítání, násobení a dělení reálných čísel a pokuste se sestavit pět axiomů, které tyto operace splňují. Máte na to deset minut a poraďte se se sousedem (ve skupinkách o třech lidech). Axiomy pro počítání s čísly (které studenti znají ze střední školy) zhruba daly základ pro definice následujících vlastností, jež budou hrát klíčovou roli: Vlastnost (1) Uzavřenost množiny M vzhledem k operaci *: Vx, y G M : x * y G M. 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. Vlastnost (2) Asociativita operace *: Vx, y, z G M : (x * y) * z = x * (y * z). 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í. Algebra 1 (MA 0003) 5 Vlastnost (3) Existence jednotkového prvku vzhledem k operaci *: 3eGM:x*e = e*x = x Vx G M. 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. Vlastnost (4) Existence inverzních prvků vzhledem k operaci *: Vx G M 3 x-1 G M : x * x-1 = x-1 * x = e. 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 |. Uveďme nyní základní definice některých struktur, které splňují dané vlastnosti: Definice 1 Grupoid (M, *) ... množina M, na které operace * splňuje vlastnost (1); Definice 2 Pologrupa (M, *) ... množina M, na které operace * splňuje vlastnosti (1),(2); Definice 3 Monoid (M, *) ... množina M, na které operace * splňuje vlastnosti (1),(2),(3) (někdy též podle starší terminologie: pologrupa s jednotkou, pologrupa s jednotkovým prvkem); Definice 4 Grupa (M, *)... množina M s operací*, která splňuje na množině M vlast-nosti (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. Vlastnost (5) Operace * se nazývá komutativní na množině M, pokud platí vlastnost (5): Vx, y E M : x * y = y * x. Definice 5 (M, *) se nazýva komutativní grupoid, pokud je grupoid a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Definice 6 (M, *) se nazývá komutativní pologrupa, pokud je pologrupa a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Definice 7 (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. 6 Katedra matematiky PedF MUNI v Brně Definice 8 (M, *) se nazýva komutativní grupa, pokud je grupa a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Při přemýšlení nad základními vlastnostmi operací sčítání a násobení lze ještě najít často axiom, který si všímá „interakce" = vzájemného vztahu mezi těmito dvěma operacemi: interakce operací + a • splňuje tzv. distributivní zákon = vlastnost (6) : V x,y, z 6 M : x ■ (y + z) = x ■ y + x ■ z, (y + z) ■ x = y ■ x + z ■ x. Název „distributivní" lingvisticky odpovídá tomu, že po odstranění závorek se prvek x rozdělí = distribuuje k oběma členům součtu. Matematicky se jedná o pravidlo násobení závorky, ve které se nachází „součet" prvků, kde „součet" je operace s nižší prioritou než násobení. Například známá operace sčítání reálných čísel má nižší prioritu než násobení reálných čísel: 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í (a pokud bychom chtěli nejprve sečíst čísla 8 a 2, a teprve pak výsledek vynásobit třemi, musíme díky větší prioritě násobení užít pro sčítání závorky). Axiom (6) lze formulovat pro různé dvojice operací, tj. obecně bychom měli psát, že distributivní zákon mezi operacemi * a y je V x, y, z £ M : x * (y X/ z) = (x * y) X/ (x * z), (y v z) * x = (y * x) V (z * x)- To, že rovnice distributivity jsou dvě, musíme mít na mysli tam, kde operace * není komutativní, tj. nesplňuje vlastnost (5). Určitě si zopakujte ty nej důležitější pojmy předmětu Základy matematiky: Úloha 1.1 Uvedte definice následujících základních pojmů z předmětu Základy matematiky a u každé uveďte příklad: a) množina; b) kartézský součin; c) relace d) ekvivalence; e) uspořádání; f) zobrazení; g) operace; h) (reálná) posloupnost; Algebra 1 (MA 0003) 7 i) (reálna) funkce. Úloha 1.2 Uveďte následující definice vlastností relací a u každé z nich uveďte príklad: • Relace p na množině M je reflexivní , když ... • Relace p na množině M je symetrická, když ... • Relace p na množině M je tranzitivní, když ... • Relace p na množině M je úplná, když ... • Zobrazení f z X do Y je taková relace na X x Y, že platí ... Definice z obou úloh najdete v textu Základy matematiky. 1.2 Cvičení 2: Určování vlastností různých operací Úloha 1.3 Zjistěte, jaké struktury vzhledem k uvedené známé operaci (běžné označení) jsou následující množiny: a) (N,+). b) (Z,+). c) (Z,-). d) (Q,-), (R,-). e) (Q-{0},-), (i?-{O},-)- f) (2A, U), kde A = {a, b, c, d, e) je pětiprvková množina. g) (2A, n), kde A = {a, b, c, d, e} je pětiprvková množina. h) (Z,-), (Z,:). i) (M, +), kde M = {-100, -99, -98,..., -1, 0,1, 2,..., 99,100}. Úloha 1.4 Opakování definic a práce s nimi a) Nadiktujte sousedovi v lavici definici grupy a on ji zapíše zkráceným matematickým zápisem, ve kterém se nevyskytuje ani jedno české slovo, kromě slova „grupa". b) Co to znamená, že (M, *) není grupoid, tj. není splněna vlastnost (1)? Negujte vlast- nost (1). c) Co to znamená že není splněna vlastnost (4) z definice grupy? Negujte vlastnost (4). Úloha 1.5 a) Uveďte definici vlastnosti (4) pro operaci v na množině M ve stručném matematickém zápisu. 8 Katedra matematiky PedF MUNI v Brně b) Uveďte príklad struktury (M,xj), která splňuje vlastnost (4). c) Uveďte príklad struktury (M,xj), která NEsplňuje vlastnost (4). Úloha 1.6 Dokážte, že množina všech podmnožin tříprvkové množiny s operací symetrického rozdílu 4- je grupa (viz Pinter 2010, str. 30, oddíl C). Výsledky některých cvičení najdete v závěru textu v oddílu 13.2. 1.3 Přednáška 1 Algebra je nauka o řešení rovnic1. Proto bychom mohli zmínit, co je to rovnice s neznámou x na množině M, na níž je definována operace v: • Rovnost je relace ekvivalence na množině výrazů, ve kterých vystupují prvky množiny M a operace V- Příklad: běžně rovnost na množině reálných čísel chápeme jako relaci ekvivalence na množině výrazů, v nichž vystupují reálná čísla, reálné funkce a známé operace s reálnými čísly. • Rovnítko je symbol relace rovnosti. • Rovnice s neznámou x na množině M je výroková funkce, ve které vystupuje neznámý prvek x, symbol rovnosti (rovnítko), prvky množiny M nebo výrazy na množině M. Jak víme, výroková funkce není výrokem, protože bychom museli dosadit za x, abychom dostali výrok pravdivý či nepravdivý. • Řešit rovnici s neznámou x na množině M znamená najít obor pravdivosti3 K všech prvků z množiny M, pro které se stává daná rovnice pravdivým výrokem. Podívejme se na některé jednoduché příklady: a) Specifikace množiny M je také pro řešení rovnice důležitá. Například rovnice 7 + x = 2 nemá řešení na množině přirozených čísel (tedy tato rovnice nemá řešení na monoidu (No, +))!! Nebo rovnice 7-x = 2 nemá řešení na množině celých čísel (tj. na monoidu (Z,-)). Tj. vidíme, že už na monoidech (strukturách s jednou operací) některé rovnice nemají řešení!! Nebo rovnice x2 - 2 = 0 nemá řešení na množině racionálních čísel (v této rovnici uvažujeme současně výrazy s operací sčítání (odčítání) i násobení, hledáme tedy řešení na tělese (Q, +, •)). arabské ,,'al gebr" znamenalo „složit" rovnici, tj. vyřešit ji = nalézt její řešení2. Zejména se jedná o polynomické rovnice, kterými se budeme zabývat ve druhé polovině semestru. 3K označuje tzv. množinu kořenů dané rovnice na množině M. Algebra 1 (MA 0003) 9 b) Ve většině tohoto textu se budeme zabývat rovnicemi s výrazy, ve kterých vystupuje jediná operace, a množina, na které budeme řešení rovnice hledat, bude zpravidla grupa nebo monoid vzhledem k této operaci. Oběma operacemi současně (tedy algebraickými strukturami se dvěma operacemi) se budeme zabývat až v kapitole 5. Až dosud (v prvním týdnu) byly uvedeny různé axiomy operací, se kterými se v matematice setkáváme (operací sčítání, násobení čísel, operace průniku a sjednocení množin). Zkusme se nyní odpoutat od konkrétních operací, které známe. Podobně jako v předmětu Základu matematiky jsme se odpoutali od relací „menší nebo rovno", „je dělitelem" a „je podmnožinou" a studovali obecně vlastnosti uspořádaných množin, tj. množin, na nichž je definována relace reflexivní, antisymetrická a tranzitivní, nyní se na chvíli odpoutáme od konkrétních operací a budeme studovat obecně vlastnosti grupy - tj. vlastnosti množiny, na níž je definována operace *, jež splňuje vlastnosti (1), (2), (3), (4). Začněme ovšem jedním příkladem konečné, šestiprvkové grupy: Příklad 1 Grupa pootočení hodinové ručičky. Uvažujme čísla 0 až 5 rozmístěna po obvodu kružnice (např. obvodu ciferníku hodin) tímto způsobem (viz obrázek): Číslo 0 se nachází tam, kde se obyčejně na hodinách vyskytuje číslo 12. Dále čísla 1 až 5 jsou společně s nulou rozmístěna rovnoměrně po obvodu kružnice tak, že úhel určený středem kružnice a rameny procházejícími dvěma sousedními čísly je 60° neboli |. Dále se budeme zabývat množinou pootočení jedné ručičky s osou otáčení ve středu kružnice: • prvek 0 představuje nulové pootočení ručičky - s ručičkou se nic nestane; • prvek 1 představuje pootočení o jednu jednotku, tj. o 60°; • prvek 2 představuje pootočení ručičky o dvě jednotky, tj. o 120°; • prvek 3 přestavuje pootočení o 180°; • prvek 4 přestavuje pootočení o 240°; 10 Katedra matematiky PedF MUNI v Brně • prvek 5 přestavuje pootočení o 300°. Pokud ručička začíná svůj pohyb nasměrována na nulu, tak otáčením o uvedené uhly ji dostaneme opět do polohy nasměrované na některý z prvků - tj. množina otočení splňuje vlastnost (1), protože složením dvou otočení ručičky dostaneme zase nějaký ze základních šesti prvků. Dále operace skládání otáčení je asociativní (splňuje (2)), když totiž při počátečním nastavení ručičky do nulové polohy složíme otočení (1 + 2) +44, dostaneme prvek 1 stejně jako při postupu 1 + (2 + 4) - složením těchto tří pootočení dostaneme vždy úhel 420°, po jehož aplikaci ručička ukazuje na prvek 1. Tedy skládání pootočení nezávisí na jejich uzávorkování5. Pootočení 0 je neutrálním prvkem vzhledem ke skládání pootočení (platí vlastnost (3)) - když např. ručičku namířenou na prvek 4 pootočíme o 0, ručička je stále namířena na prvek 4. A konečně, každý prvek má svůj inverzní prvek v této šestiprvkové množině (platí vlastnost (4)), se který když jej složíme, dostaneme ručičku zase do polohy 0: • inverzí k 0 je opět 0; • inverzí k 1 je 5 - a naopak, inverzí k 5 je 1; • inverzí k 2 je 4 - a naopak, inverzí k 4 je 2; • inverzí k 3 je opět 3. Tedy celkem naše množina pootočení (označme ji Hq = {0,1,2,3,4,5}) vzhledem k operaci skládání pootočení je grupa = operace + na ní definovaná splňuje vlastnosti (1) až (4). Protože Hq je konečná množina, lze si výsledky operace + napsat do tabulky: Danou tabulku operace * konstruujeme tak, že na průsečíku řádku prvku x a sloupce prvku y se vyskytuje výsledek operace x * y (a této logiky konstrukce tabulek operací se budeme držet v celém textu): * y X x * y Máme-li k dispozici úplnou tabulku operace * na množině m, máme při zjišťování vlastností operace vyhráno. Jak lze nahlédnout v tabulce 1.1, vlastnosti (1), (2), (3), (4) operace + na Množině Hq lze všechny z této )tabulky vyčíst (viz výklad ... elicit from 4Operaci označíme jako H— i když se nejedná o klasické sčítání čísel, toto skládání otočení má velmi příbuzné vlastnosti se sčítáním. 5Dokonce skládání tří pootočení nezávisí na jejich pořadí, protože operace skládání pootočení splňuje i vlastnost (5) = komutativitu; tou se ovšem nyní nechceme příliš zabývat. Algebra 1 (MA 0003) 11 Tabulka 1.1: Tabulka operace + na množině Hq. + 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 the students).* (tento znak znamená konec daného příkladu) Je jasné, že lze obecně definovat grupu (Hn, +) pootočení hodinové ručičky o násobky úhlu ^ s operací skládání pootočení - tato grupa má n prvků. - při přepisu doplňte: všechny možné podmnožiny, na kterých je operace skládání pootočení uzavřená (tabulka pro operaci na podmnožině {0, 2, 4, }, ostatní jen zmiňte); - poslední řádek příkladu zakončete takovou velkou tečkou za tečkou ve větě, která naznačuje konec příkladu. □. Příklad 2 Prozkoumejte vlastnosti operace sčítání na množině celých čísel. - při přepisu doplňte ... tabulku operace sčítání na množině Z - při přepisu doplňte ... 0 je neutrální prvek vzhledem ke sčítání - při přepisu doplňte ... inverze - při přepisu doplňte ... podmnožiny uzavřené na operaci Definice 9 Triviální podgrupy (= nevlastní podgrupy) grupy (G, v) se nazývají dvě podgrupy: a) S± = {n} je podgrupou vzhledem k \/, která obsahuje pouze neutrální prvek (je neprázdná a splňuje (1) a (4)), b) S2 = G (samotná celá grupa je též podgrupou sama sebe). Každou jinou podgrupu nazveme vlastní podgrupou grupy (G, v)- Příklad 3 Označme (F(R), +) množinu všech funkcí (= zobrazení R —> R, viz předmět Základy matematiky) s operací sčítání funkcí. 12 Katedra matematiky PedF MUNI v Brně - při přepisu doplňte ... náznak tabulky operace, nějaké ukázky skládání funkcí, skutečnost, že skládání funkcí není komutativní, stručný důkaz, že skládání funkcí je asociativní (je vlastně vložen, jen ho okomentujte), co je neutrálním prvkem. Skládání funkcí, potažmo jakýchkoli zobrazení, je asociativní operace: (/ o g) o h(x) = (/ o g)(h(x)) = f{g{h{x))) = f o (g(h(x))) = f o (g o h){x). Příklad 4 Důležitým příkladem grupy, na kterou se nyní zaměříme blíže, je grupa bijekcí n-prvkové množiny na sebe sama, kde operací je skládání zobrazenŕ. Často se jí též říká grupa permutací - označení opravdu má blízko ke středoškolskému pojmu permutace, kdy např. permutace 5-prvkové množiny {1,2,3,4,5} byla chápána jako určité pořadí všech jejích prvků, např. pořadí 51324. Nyní budeme na tyto permutace pohlížet jako na zobrazení, které základní vzestupné pořadí 12345 přemění na pořadí např. 51324. Permutace n—prvkové množiny je bijekce množiny {1,2,..., n} na sebe sama. Sn je množina všech permutací tohoto typu. Například permutace / : M —> M pro M = {1, 2, 3,4, 5} definovaná 1 2 3 4 5 \ \~ 4' 4' 4' 4' I 5 1 3 2 4 / je bijektivní, takže existuje permutace /_1 k ní inverzní 1 2 3 4 5 \ t t t t t 5 1 3 2 4 / Důležité úsporné označení permutace V dalším textu budeme permutace zadávat úspornějším způsobem, který napíše každé číslo jen jednou, nikoli dvakrát. V tomto úsporném označení budeme permutaci / 1 2 3 4 5 \ /= li i i i i \ označovat jako / = (1,5,4,2) \ 5 1 3 2 4 / (v tomto označení se jedná o uzavřený cyklus zobrazení: 1 se zobrazí na následující zapsané číslo, tj. 5, číslo 5 se zobrazí na 4, číslo 4 na 2 a poslední zapsané číslo v závorce se zobrazí na první číslo 1, a tím se cyklus uzavře!!). Číslo 3 není v zápise uvedeno, protože se zobrazením / nemění, tj. /(3) = 3. Podobně permutaci / 1 2 3 4 5 \ /_1 = [ t t t t t J budeme vyjadřovat jako f'1 = (1,2,4,5) \ 5 1 3 2 4 / 6Až do konce této přednášky se všechny informace týkají tohoto příkladu. Algebra 1 (MA 0003) 13 (tj. změnil se změr cyklu, veškeré zobrazování otočilo směr; mohli bychom zapsat i /_1 = (2,4,5,1), protože nezáleží na tom, které číslo je v uzavřeném cyklu jako první; stále se jedná o stejný prvek: f'1 = (1, 2,4, 5) = (2,4, 5,1) = (4, 5,1, 2) = (5,1, 2, 4); a protože nezáleží na pořadí prvků v cyklu, zavedeme další úmluvu, a sice první prvek každého cyklu napíšeme to nej menší možné číslo). Operace skládání permutací 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í: o ... (čti „po") operace skládání zobrazení, ve které je nejdříve aplikováno druhé zobrazení v pořadí, a pak první - proto i čtení tohoto symbolu pomocí předložky „po" je zcela instruktivní; Ilustrujeme situaci pro n = 3: Uvažujme množinu permutací tříprvkové množiny {1, 2, 3} do sebe - označme ji S3. Množina S3 má šest prvků: e := id (tímto symbolem budeme označovat identické zobrazení, jež zobrazí všechny prvky na sebe sama, tj. 1 na 1, 2 na 2 a 3 na 3), s := (1, 2, 3) (pozor, neplést s identitou, u této permutace v souladu s úsporným označením platí s(l) = 2, s(2) = 3, s(3) = 1), t := (1, 3, 2) (pozor, (3, 2,1) a (2,1, 3) je pořád stejný prvek t, ve kterém r(l) = 3, r(3) = 2, í(2) = 1), u := (2,3) (u(2) = 3, u(3) = 2, u(l = 1)), a nakonec v := (1,3), w := (1,2). Permutací tříprvkové množiny je tedy šest. Tyto permutace lze skládat, výsledkem složení je zase permutace tříprvkové množiny: například soe = (l,2,3)oid= (1,2,3) = s nebo uov = (2,3) o (1,3) = (1,2,3) = s (všimněte si, že zobrazování skládáme ZPRAVA DOLEVA, tj. 1 se zobrazí na 3, pak v levé permutaci 3 na 2, tj. celkem 1 na 2; dvojka v permutaci psané napravo není, tj. zobrazí se na sebe sama, složením s permutací vlevo se zobrazí na 3, celkem tedy 2 se zobrazí na 3; a konečně 3 se v permutaci napravo zobrazí na 1, v levé permutaci se 1 zobrazí na sebe sama, tj. celkem 3 na 1) nebo v o u = (1,3) o (2,3) = (1,3, 2) = t. Cili z posledních dvou příkladů je vidět, že v o u ^ u o v, tj. operace o je nekomutativní (neplatí vlastnost (5))! Propočítáním všech možných 36 kombinací dostaneme přehlednou tabulku výsledků operace o: Nejprve je potřeba říci, že u každé tabulky operace * na konečné množině prvků je prvek x v levém sloupcovém záhlaví vybrán jako první a prvek y v horním řádkovém záhlaví jako druhý7. 14 Katedra matematiky PedF MUNI v Brně Tabulka 1.2: Tabulka operace o na množině 63. 0 id (1,2,3) (1,3,2) (2,3) (1,3) (1,2) id id (1,2,3) (1,3,2) (2,3) (1,3) (1,2) (1,2,3) (1,2,3) (1,3,2) id (1,2) (2,3) (1,3) (1,3,2) (1,3,2) id (1,2,3) (1,3) (1,2) (2,3) (2,3) (2,3) (1,3) (1,2) id (1,2,3) (1,3,2) (1,3) (1,3) (1,2) (2,3) (1,3,2) id (1,2,3) (1,2) (1,2) (2,3) (1,3) (1,2,3) (1,32,) id Tedy konkrétně u operace o na množině 63 dostaneme tabulku operace: Z tabulky je vidět, že operace je uzavřená na množině 63, tj. platí vlastnost (1). Asociativita (2) platí pro skládání jakýchkoli zobrazení, viz příklad 3. A nakonec, je splněna i vlastnost (4), protože: jednotkový prvek id je (jako každý jednotkový prvek v grupě) inverzní sám k sobě; z tabulky dále vidíme, že (1,2,3)_1 = (1,3,2), (1, 3, 2)_1 = (1, 2, 3), a prvky (2, 3), (1, 3), (1, 2) jsou inverzemi sebe sama! Dále existuje šest podgrup grupy (63, o): tzv. triviální podgrupa, která obsahuje pouze jednotkový prvek id, s tabulkou operace 0 id id id další podgrupou je celá šestiprvková grupa (63, o) samotná. Kromě těchto dvou extrémně malých nebo velkých podgrup existují též tři dvouprvkové podgrupy 0 id (2,3) 0 id (1,3) 0 id (1,2) id id (2,3) , id id (1,3) , id id (1,2) (2,3) (2,3) id (1,3) (1,3) id (1,2) (1,2) id a jedna tříprvková podgrupa s tabulkou operace 0 id (1,2,3) (1,3,2) id id (1,2,3) (1,3,2) (1,2,3) (1,3,2) (1,2,3) id (1,3,2) (1,3,2) id (1,2,3) K čemu je dobrá grupa permutací 63? Má i svůj geometrický význam, tj. lze ji použít při popisu některých základních geometrických zobrazení, například bijektivních zobrazení 7Toto je klíčově důležitá domluva, řečená už výše. Pořadí hraje roli právě u tohoto příkladu, kdy se jedná o operaci nekomutativní, tj. na pořadí prvků do operace vstupujících záleží. Algebra 1 (MA 0003) 15 trojúhelníku na sebe sama (tzv. symetrií trojúhelníku, odtud i původ písmene S v označení množiny), kterých je také šest, stejně jako prvků množiny S3 - jedná se o tři otočení a tři osové souměrnosti. Každé z těchto geometrických proměn (= transformací) trojúhelníku lze přiřadit jednu permutaci jeho tří vrcholů. - zde by se hodil obrázek s přiřazením permutací v krátkém zápisu jednotlivým transformacím trojúhelníku, s mírným vysvětlením, zkuste použít tento obrázek (vlastně jej můžete překreslit stejně, jen v posledním sloupečku bude to zjednodušené označení permutací pomocí cyklů = označení uvedené v té tabulce grupy 63): Obrázek 1.1: Množina D3 permutací odpovídajících symetriím trojúhelníku. 16 Katedra matematiky PedF MUNI v Brně 1.4 Dodatky 1 V této části jsou uloženy součásti textu, které možná nebudou probrány - některé obecné důkazy, některé teoretické věci jsou zde „matematicky přesněji vyloženy". Studenti by měli z těchto dodatkových částí vědět definice, a pak jen to, co jim speciálně zdůrazní vyučující, respektive co se probere na přednášce. Základní vlastnosti grup Studujme nyní tedy obecně vlastnosti grupy (G, y). Co v této obecné poloze lze říci o množině G a operaci y? Pokud abstrahujeme od konkrétních situací a budeme studovat pouze vlastnosti (1) až (4) na množině G, dojdeme k poznatkům, které platí pro každou strukturu, která je vzhledem k nějaké operaci grupa. První otázku si položme ohledně axiomu (3): pokud existuje neutrální prvek grupy, musí být jeden, nebo v jedné grupě může existovat více neutrálních prvků?8 Věta 1 (o jednoznačnosti neutrálního prvku) V každé grupě (G, y) existuje jediný neutrální prvek. Důkaz: Sporem: předpokládejme, že v grupě existují dva různé neutrální prvky n\ a ni takové, že n\ ^ ni. Jaké z toho plynou vlastnosti těchto dvou prvků? Klíčová myšlenka: pokud je prvek neutrální, tak nemění výsledek operace v vůči jakémukoli dalšímu prvku, tj. např. g y ni = 9- Mohlo by tedy být zajímavé, co se stane, když aplikujeme operaci na dané dva neutrální prvky ni, ni9: (3)2 (3)! což je spor s tím, že oba neutrální prvky jsou navzájem různé10. □ Tak to je zajímavé, neutrální prvek grupy může být pouze jeden jediný. A jak je to s inverzními prvky grupy? Víme, že v grupě existuje inverze ke každému prvku vzhledem k operaci v ~~ musí také ke každému prvku existovat jediná inverze? Mohli bychom najít v grupě nějaký prvek, ke kterému existují inverze dvě? Věta 2 (o jednoznačnosti inverzních prvků) V každé grupě (G, y) existuje ke každému prvku x jediný inverzní prvek x_1 vzhledem k operaci y. 8Víme, že např. na množině Q — {0} existuje vzhledem k násobení jediný neutrální prvek 1 - ale musí tomu tak být v každé grupě? Co když existují grupy se dvěma nebo třemi neutrálními prvky? 9Vlastnost (3)i znamená, že využíváme vlastnosti (3) pro prvek n\, vlastnost (3)2 platí pro neutrální prvek U'2- 10Celý důkaz je možné formulovat i jako přímý důkaz typu 2: předpokládáme, že prvky n\, ri2 oba se chovají jako neutrální, tj. uvedené odvození by o nich dokázalo, že se musí nutně rovnat - tj. z toho plyne přímo, že prvek neutrální je pouze jeden. Algebra 1 (MA 0003) 17 Důkaz: Předpokládejme opět, že k nějakému prvku a E G vykazují dva prvky a1 , a2x vlastnost inverze, tj. platí a y o-i1 = n, A aX1 xj a = n (musí platit oba vztahy, protože o operaci v zatím nevíme, zdaje komutativní) a současně a xj a-21 = ni A a2x XJ a = n. Klíčová myšlenka: vynásobením11 aX1 xj a2ľ pravděpodobně nic nezískáme. Prvky aX1, aX1 vystupují ve vlastnosti (4), tj. měli bychom studovat něco jako rovnice ve vlastnosti (4). VYUŽIJEME TOHO, ŽE VE VLASTNOSTI (4) SE VYSKYTUJÍ DVĚ ROVNOSTI, A JEDNU APLIKUJEME NA PRVEK a ZLEVA, DRUHOU ZPRAVA: -1 (3) _ -1 (4)i / -i \ _ -1 (2) -i / „ -U (4)2 _i _ (3) _! a2 = = nxj a2 == {a1 xja)xja2 = a1 XJ [a XJ a2 j = a1 xj n = a1 . Využili jsme platnosti asociativního zákona (2) pro kaskádu tří prvků uprostřed spojených operací V- Z uvedené kaskády rovností je vidět, že prvky aT1 a a2x musí nutně být stejné. Důkaz je hotov - inverzní prvek k prvku a existuje v grupě právě jeden. □ Věta 3 (můžeme „krátit"12 v rovnostech, ve kterých se vyskytují prvky grupy G a operace XJ?) V každé grupě (G, Xj) platí zákony o krácení (7), tj. Va, b,c G G : (axjb = axjc^-b = c) A (bxja = cxja^-b = c). Důkaz: Provedeme například pro první z implikací: Vztah axj b = axj c rozšíříme zleva aplikací inverzního prvku na obě strany rovnice (to je vlastně vlastnost anti-(7), která ovšem plyne z vlastnosti (1): „vynásobením" téhož prvku grupy G (který je na obou stranách rovnice) dostaneme opět prvek grupy G: a-1 XJ axj b = a-1 • a xj c, a s využitím asociativity (2) (v grupě nezáleží na uzávorkování „součinu" tří prvků vzhledem k operaci xj), vlastnosti inverzí (4) a vlastnosti neutrálního prvku (3) dostaneme b = c. Důkaz druhé nerovnosti bychom museli provádět vynásobením obou stran rovnice zprava, abychom mohli aplikovat vlastnost inverzí (4). □ Všimněte si, že říkám „vynásobením", ikdyž nyní nestudujeme operaci násobení, ale operaci v ... tak moc jsou operace sčítání a násobení v nás zakódovány, že používáme terminologii, která odpovídá těmto operacím - správně bychom měli říci: aplikací operace v na dané prvky v daném pořadí, tj. na uspořádanou dvojici prvků ... 12Opět terminologie: i když mluvíme obecně o operaci y, pro vlastnost (7) se vžil termín „zákony o krácení", třebaže krácení je termín vzatý z rovností, ve kterých se vyskytuje běžná operace násobení. 18 Katedra matematiky PedF MUNI v Brně Věta 4 (o vzájemně inverzních prvích) V každé grupě (G, v) z rovnosti axj b = n (kde n je neutrální prvek) plyne, že platí a-1 = b, a současně b-1 = a (tedy prvek b je inverzní k prvku a, a současně prvek a je inverzním prvkem k prvku b). Důkaz: je prostý, neboť plyne z věty 2: pokud b vykazuje vlastnosti inverze (4), tak musí být inverzní k prvku a, protože více inverzních prvků k danému prvku v grupě být nemůže. Další možnost důkazu: pokud rozšíříme rovnost a XJ b = n prvkem a-1 zleva, dostaneme -1 r, -1 (3) -1 a y a y o = a y n = a , po aplikaci vlastnosti (4) na první výraz dostaneme b = a-1. □ Věta 5 (o výpočtech inverzních prvků) V každé grupě (G, v) platí: i) (a y = V a_1 (inverze součinu dvou prvků je součin jejich inverzí, ale v opačném pořadí!!!); ii) (a-1)-1 = a (inverzí k inverzi je původní prvek). Důkaz: ad i) Přímo ověřením vlastnosti (4) pro prvky a y b a v a_1; a V b V V a_1) — a V (b V b~v) V a_1 — a V n V a_1 — a V a_1 — n- Protože nevíme, zda operace v Je komutativní, měli bychom ověřit i druhý za zákonů (4), tj. upravovat výraz (V1 y a"1) V a V b analogickým způsobem se v něm „vyruší" nejprve a-1 XJ a, a pakfo-1 y b a dostaneme opět pouze n. ad ii) Z rovnosti a XJ a-1 = n a věty 4 o vzájemné inverzi máme (a-1)-1 = a. □ Definice 10 Rád konečné grupy se nazývá počet jejích prvků, označujeme \G\. Označení počtu prvků je standardní, nazývat tento počet prvků řádem je poněkud bizarní, ale má jakési opodstatnění u cyklických grup. Rozšíření vlastnosti (2) na k prvků Ve větě 5 se vyskytuje „součin" čtyř prvků za sebou - přesně pracující matematik by měl prozkoumat, zda se nedopouští při důkazu něčeho, co není definováno. Pokud Algebra 1 (MA 0003) 19 definujeme součin čtyř prvků vzhledem k operaci yjako součin prvního prvku se součinem následujících tří prvků, tj. a y 0 Vc Vá), postupným užitím vlastnosti (2) pro tři prvky dostaneme a y 0 V c) V d = a y b y (c V d) = {a y b) y (c V d) = {a y b) y c v d a jedná se stále o týž výsledek. „Součin" čtyř prvků je tedy definován korektně a platí pro něj vlastnost (2)' ... v sekvenci třikrát za sebou použité operaci y nezáleží na uzávorkování. S takto rozšířeným zákonem asociativity můžeme pak vyslovit a dokázat některé věty pro větší počet operací y v řetězci za sebou, například analogii části (a) věty 5: («i V fl2 V " " V afc)_1 == ak1 V ak-i V • • • V a-21 V a-i1-Dále pro nás bude užitečná například definici n-té mocniny vzhledem k operaci y: Definice 11 n-tá mocnina prvku a grupy (G, y) se definuje jako prvek získaný v řetězci operací an := a\j a\j ■ ■ ■ xj a . "-v-' n-krát A pokud už máme definovanou mocninu, má smysl ptát se, zda existují odmocniny, a sice v následujícím smyslu: Definice 12 n-tá odmocnina prvku a grupy (G, y) je takový prvek x G G (pokud tedy existuje), že a = xn. Definice 13 zápornou odmocninu a-5 grupy (G, y) definujeme jako pátou mocninu jejího inverzního prvku, tj. a-5 := (a-1)5. 20 Katedra matematiky PedF MUNI v Brně 2 Týden 02 — další vlastnosti operace na množině 2.1 Přednáška 2 Podgrupa (S, y) grupy (G, y) Zabývejme se nyní otázkou: kdy je neprázdná podmnožina S grupy (G, y) také grupou? Definice 14 Podgrupa (S, y) grupy (G, y) je taková neprázdná podmnožina S množiny G, která je uzavřená vzhledem k operaci y (vlastnost 1) a s každým prvkem a obsahuje i jeho inverzi a-1 (vlastnost 4)- Kupodivu se ukazuje, že dané dvě vlastnosti (1), (4) neprázdné13 podmnožině S grupy (G, y) stačí na to, aby byla grupou vzhledem k téže operaci y: Věta 6 (co stačí podmnožině grupy, aby byla sama grupou) Pokud neprázdná podmnožina S grupy (G, y) splňuje vlastnosti (í), (4), už je sama grupou vzhledem k téže operaci y. Důkaz: (S, y) splňuje asociativitu (2) díky tomu, že je podmnožinou grupy, kde vlastnost (2) platí. Vlastnost (3), = existence neutrálního prvku, plyne z vlastnosti (4): Díky tomu, že S je neprázdná, obsahuje aspoň jeden prvek, označme jej a. a (4) _i c (i) _i c tedy neutrální prvek n patří i do množiny S a pro (S, y) platí (3). □ Označení 01 ... hvězdička znamená, že z dané množiny Z, Q, R vyloučíme nulu, značíme tedy symbolem Z*, Q*, R*. Příklad 5 Podmnožina Q* všech zlomků kromě nuly je podgrupou grupy (R*,-): vynásobením dvou nenulových zlomků dostaneme nenulový zlomek (platí (1)), inverzí k nenulovému zlomku vzhledem k násobení je jeho převrácená hodnota (platí (4)) a Q* je neprázdná. 13Ve skutečnosti podmínka neprázdnosti je třetí podmínkou, která musí platit - uvidíme v důkazu, že z neprázdnosti a vlastnosti (4) už plyne vlastnost (3) o neutrálním prvku. Algebra 1 (MA 0003) 21 Generátory podgrupy Uvažujme množinu S = {a, b, c}, která je podmnožinou grupy (G, y). Na to, abychom našli nejmenší možnou podgrupu, která obsahuje prvky a, b, c, musíme vyrobit všechny možné součiny těchto tří prvků a jejich inverzí14, a nejen to: musíme brát všechny možné konečné sekvence prvků spojených operací y, ve kterých se vyskytují (i opakovaně) prvky a, b, c a jejich inverze. Typickými takto vytvářenými prvky jsou například a V b V a V c_1 nebo c-1 y a-1 y b\y b\y c. Je jasné že součinem dvou prvků tohoto typu je zase prvek tohoto typu (tj. platí (1)): Například „součinem" prvku a y b y a a prvku c y y a y c je prvek a\j b\j a\j cxj b'1 xj a\j c. Dále jsou prvky tohoto typu uzavřené vzhledem k inverzi, tj. k prvku a y y c-1 y a je inverzí (podle věty 5.a bereme součin dílčích inverzních prvků v opačném pořadí) prvek a"1 y c y bxj a"1 (tedy platí i (4)). Dokázali jsme celkem, že množina prvků tohoto typu tvoří podgrupu grupy (G, y). Nazývá se Definice 15 podgrupa grupy G generovaná množinou S, prvky množiny S nazýváme generátory podgrupy < S >. Podgrupu generovanou podmnožinou S označujeme jako ( označení 02 ) < S >. A ještě jedna definice, která s tím souvisí: Definice 16 Pokud podgrupa < S > je celá generována některým svým prvkem a, nazývá se cyklická podgrupa grupy G. Cyklickou podgrupu generovanou prvkem a někdy označujeme ( označení 03 ) < a > a je jasné, že obsahuje prvky a, a2 := a y a, a3 := a y a y a,..., a také prvky a-1, a-1 y a-1, a-1 y a-1 y a-1,..., a také prvek n = a y a-1. Ad Příklad 1: Grupa (Hq, +) s operací pootočení hodinové ručičky je příkladem cyklické grupy, generované jediným prvkem - kterým? □ V této chvíli už se v daných součinech vyskytuje neutrální prvek n G G, protože a\/ a = n. 22 Katedra matematiky PedF MUNI v Brně Ad příklad 4: Ohledně generátorů grupy S3 lze říci, že (63, o) je generována dvěma svými prvky, a sice (1,3) a (1,2), protože všechny další čtyři prvky grupy lze vyjádřit pomocí operace o a prvků (1, 3), (1, 2): id = (l,3)o(l,3); (1,2,3) = (l,3)o(l,2); (1, 3, 2) = (1, 2, 3) o (1, 2, 3) = ((1, 3) o (1, 2))2 = ((1, 3) o (1, 2)) o ((1, 3) o (1, 2)); (2,3) = (1,2) o (1,2,3) = (1,2) o ((1,3) o (1,2)). Podle označení množiny generátorů lze psát (53,0) =< (1,3),(1,2)>. Tato grupa tedy není cyklická, protože naše množina generátorů je dvouprvková a žádnou jednoprvkovou množinu generátorů v ní nelze najít. □ Věta 7 (5„, o), množina permutacŕ5 M —>■ M pro M = {1, 2,... , n} vzhledem k operaci skládání permutací je pro n > 3 nekomutativní grupa. Důkaz pro obecné n: Operace o je na množine Sn uzavřená, tj. platí vlastnost (1), protože složení dvou permutací je opět permutace. Asociativita (2) platí pro skládání jakýchkoli zobrazení, viz příklad 3. Identické zobrazení id definované Va £ {1,2,... ,n} vztahem íd(a) = a je neutrálním prvkem na množině permutací, tj. platí (3): Pro obecnou permutaci p : {1, 2,... , n} —> {1, 2,... , n} totiž máme pro každné a 6 {1, 2,... , n}: p o íd(a) = p(a) A id o p(a) = íd(p(a)) = p(a). Zbývá důkaz vlastnosti (4): V obecném případě (5„, o) permutací na n-prvkové množině M = {1,. .. ,n} najdeme pro libovolnou permutaci p £ Sn její inverzní prvek p~x následujícím způsobem. Jelikož p : M —> M je bijektivní zobrazení, podle věty 17 ze základů matematiky (inverzní relace k prostému zobrazení je také zobrazení) víme, že inverzní relace p~x je zobrazením. Dále p je surjekce, tj. p~x je definováno pro každé a 6 {1,2,... ,n}. Tedy pro bijekci p je p~x také bijekce (v grafické reprezentaci relace pouze zaměníme směr všech šipek), a tedy permutace {1, 2, ..., n} —> {1, 2, ..., n}. A konečně pro n > 4 stačí najít jednu dvojici, pro kterou operace o nekomutuje, a to je např. cyklus (1, 2) a cyklus (1,2,... ,n): (1, 2) o (1, 2, ..., n) = (2, 3, n - 1, n) ^ (1, 2,... , n) o (1, 2) = (1, 3, 4, n - 1, n). Důkaz je hotov. □ Operace na cyklické podgrupě je vždy komutativní 15Pozor, prvky množiny Sn nejsou podmnožiny či jednotlivé prvky množiny M, ale zobrazení množiny M do sebe!! Jedná se už o složitější strukturu. Algebra 1 (MA 0003) 23 Navzdory patáliím nekomutativních operací existuje i v tabulkách nekomutativních operací jedna jistota a elegantní věc: Operace na cyklické podgrupě (= podgrupě generované jediným prvkem) H grupy G je komutativní, třebaže na celé grupě G tato operace komutativní být nemusí. Například podgrupa {id, (1, 2, 3), (1, 3, 2)} grupy (63, o) je generovaná prvkem (1, 2, 3), a tedy je to cyklická podgrupa, tj. cyklická grupa. Je vidět, že tabulka operace na {íd, (1, 2, 3), (1, 3, 2)} je symetrická, tj. operace je na ní komutativní. Důkaz faktu, že operace na každé cyklické grupě je komutativní, je lehký - pokuste se o něj v rámci cvičení. Názvy a vla stnosti algebraických struktur - příklady Příklad 6 Zopakujte vlastnosti (1) až (5) a přiřaďte názvy algebraických struktur k příkladům z minulé přednášky podle definic 1 až 8. Zmíněna vlastnost (6) = distributivita souhry dvou operací, na kterou se lze odkazovat jako na stranu 6. Příklad 7 Určete algebraické vlastnosti struktury (Zq, •). - ještě před tímto příkladem uveďte větu o krácení v grupě, a pak upozorněte na neplatnost této věty o krácení v tomto příkladu (může k tomu dojít, protože se nejedná o grupu); - ten systém rovnic x na druhou =b, x na pátou = é raději neopisujte, tuto část z přednášky vyřadím 24 Katedra matematiky PedF MUNI v Brně 3 Týden 03 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy Úloha 3.1 Príklady z Pinter 2010, str. 39, oddíl B: Například B.í: Dokažte, že v každé grupě platí následující implikace (e je neutrálni prvek grupy), nebo uveďte protipříklad, že neplatí: x2 = e => x = e. Například B.2: Dokažte, že v každé grupě platí následující implikace, nebo uveďte protipříklad, že neplatí: 9 9 x = a. 2 2 x = a Například B.4: Dokažte, že v grupě platí následující implikace, nebo uveďte protipříklad, že neplatí (e je neutrální prvek grupy): T*^ - T* \ nf - (D Například B. 5: Dokažte, že v grupě platí následující fakt, nebo uveďte protipříklad, že neplatí: Vi e G 3 i/ £ G : x = y2 (tj. každý prvek x má v grupě svou „odmocninu" y). Úloha 3.2 Příklady z Pinter 2010, str. 40, oddíl E: počet prvků a jejich inverzí - výborné příklady. Úloha 3.3 Příklady z Pinter 2010, str. 41, oddíl F: vytváření tabulky operace pro grupy s malým počtem prvků - např.: Například F.2: Může v grupě (G,*) nastat situace, že v tabulce její operace se dvakrát opakuje stejný prvek na jednom řádku? Xi . x2 ... a ... y . ■ y ■■■ Zdůvodněte, proč ano - proč ne. Například F.3: M = {e, a, b}. Doplňte tabulku operace * tak, aby (M, *) byla grupa. e a b e e a b a a b b Algebra 1 (MA 0003) 25 Například F.4: Čtyřprvková grupa G = {e, a, b, c, } splňuje Vx G G : x2 = e (kde e je její neutrální prvek). Sestavte tabulku operace * této grupy: * e a b c e a b c Například F.5: Čtyřprvková grupa G = {e, a, b, c, } splňuje a2 = e, b2 ^ e (kde e je její neutrální prvek). Sestavte tabulku operace * této grupy: * e a b c e a b c Úloha 3.4 (text Pinter 2010, str. 42, oddíl G): Dokážte, že kartézský součin grup (G, v) a (H, *) je grupa (G x H, □) - jak definovat operaci □? Úloha 3.5 Príklady z Pinter 2010, str. 43, oddíl H: mocniny a odmocniny v grupě -výborné příklady. Například H.0: a) zopakujte si definici n-té mocniny a n-té odmocniny v grupě, b) Jak byste definovali v grupě zápornou mocninu a-5 pro nějaký prvek a? Úloha 3.6 Příklady z Pinter 2010, str. 48, oddíl A: rozeznání podgrupy - výborné příklady. Například A.l: G = (R,+) je grupa vzhledem k běžné operaci sčítání. Je H = {loga; a E Q, a > 0} podgrupou grupy G vzhledem ke stejné operaci? Zdůvodněte. Například A.5: G = (R x R, +) je grupa vzhledem k běžné operaci sčítání vektorů. Je H = {(x, y); y = 2x} podgrupou grupy G vzhledem ke stejné operaci? Zdůvodněte. Například D.5 na str. 50: (G, *) je konečná grupa, H její neprázdná podmnožina uzavřená vzhledem k operaci *, a navíc e G H, kde e je jednotkový prvek grupy G. Dokažte, že pro a G H také a-1 G H (tj. H je uzavřená vzhledem k inverzím). Nápověda k důkazu : H = {a±, a2, ..., an} a vyberme si libovolné at G H. Uvažujme nyní navzájem RUZNE prvky at * a±, (Zj * a2, ■ ■ ■, Oj * an: atd. Úloha 3.7 Příklady z Pinter 2010, str. 50, oddíl E: generátory grupy - výborné příklady. 26 Katedra matematiky PedF MUNI v Brně Například N.l (není v textu Pinter 2010): Vypište všechny prvky podgrupy < 6 > grupy (Hie, +) = grupy všech pootočení ručičky o jednu šestnáctinu plného úhlu. Například E.l: Vypište všechny cyklické podgrupy grupy (i/io,+) skládání otáčení hodinové ručičky o násobky desetiny plného úhlu. Například E.3: Vypište všechny prvky podgrupy < 6, 9 > grupy (i/12, +)• Například E.7 - modifikace16: V grupě H2 x i/4 je operace sčítání po složkách zadaná tabulkou Tabulka 3.3: Tabulka operace + na množině H2 x i/4. + [0 0] [0 1] [0 2] [0 CO [1 0] [1 1] [1 2] [1 CO [0 0] [0 0] [0 1] [0 2] [0 3] [1 0] [1 1] [1 2] [1 3] [0 1] [0 1] [0 2] [0 3] [0 0] [1 1] [1 2] [1 3] [1 0] [0 2] [0 2] [0 3] [0 0] [0 1] [1 2] [1 3] [1 0] [1 1] [0 3] [0 3] [0 0] [0 1] [0 2] [1 3] [1 0] [1 1] [1 2] [1 0] [1 0] [1 1] [1 2] [1 3] [0 0] [0 1] [0 2] [0 3] [1 1] [1 1] [1 2] [1 3] [1 0] [0 1] [0 2] [0 3] [0 0] [1 2] [1 2] [1 3] [1 0] [1 1] [0 2] [0 3] [0 0] [0 1] [1 3] [1 3] [1 0] [1 1] [1 2] [0 3] [0 0] [0 1] [0 2] Určete, jakou podgrupu generuje prvek [1; 1]. Například E.6: Sestavte tabulku operace grupy (i/2 x i/3) vzhledem k operaci sčítání po složkách. A druhý úkol: dokažte o této grupě, že je cyklická. Například N.3: Zjistěte, zda je grupa z příkladu E.7 cyklická, a pokud ne, tak najděte nějakou minimální množinu jejích generátorů (existuje nějaké dva prvky, které už generují celou tuto grupu?). Výsledky některých cvičení najdete v závěru textu v oddílu 13.3. 16 Jediný důvod, proč je příklad E.7 před příkladem E.6 je historický - E.7 byl nejprve podrobně napsán na písemce. U příkladu E.6 se pak očekává, že si čtenář sestaví při řešení tabulku operace na součinu grup sám. Algebra 1 (MA 0003) 27 3.2 Přednáška 3: Izomorfismus, Calyeho věta V 18. a 19. století, když se formovaly termíny českého překladu předmětu algebra, byl jedním z návrhů českého překladu slova algebra termín „stejnostka" neboli nauka o stejnostech17. I když se tento český překlad neujal, vystihuje snahy moderní algebry všímat si shodných či podobných vlastností různých objektů. Ve shodě s navrhovaným starým překladem názvu tohoto předmětu nyní budeme zkoumat pojem izomorfismu. Lapidárně řečeno, dva objekty jsou izomorfní, když mají tutéž strukturu. I řecké slovo izomorfismus je podobného obsahu (isos = stejný, morfé = tvar, tj. izomorfní budou objekty, které mají možná jinou podstatu, ale v jistém smyslu stejný tvar). v o A 2_ Z, h 0 o A X h 4 A Q_ O CL G2, která splňuje vlastnost Va,6GGi: f(aVb) = f(a)*f(b). Obrázek 3.3: Podmínka zachování výsledků operace při zobrazení /. Jinými slovy (viz obrázek 3.3, izomorfismus mezi grupami je taková bijekce / : G\ G2, při které jsou f(a v b) a f(a) * fib) tytéž prvky, pro jakoukoli dvojici prvků a, b. úl V b r Obrázek 3.4: Komutativní diagram pro podmínku zachování výsledků operace. A nebo ještě jinak, říkáme, že izomorfismus / mezi grupami je bijekce, pro kterou diagram na obrázku 3.4 komutuje, neboli když vypustíme na prvky a, b z „ohrady" G\ operaci v, a pak výsledek přeneseme (zobrazením /) do „ohrady" G2, dosáhneme stejného výsledku, jako když bychom nejprve přenesli oddělené prvky a, b zobrazením / do „ohrady" G2 a tam na ně vypustili operaci * . Příklad 8 (R,+) a (R+,-) jsou izomorfní grupy, pokud definujeme zobrazení R —> R+ vztahem fix) = ex. Snadno se vidí, že zobrazení f je injekce, protože nenabývá dvou 19Diagram komutuje = nezáleží na pořadí: operace následovaná zobrazením dává tentýž výsledek jako zobrazení následované operací, pokud vždy mluvíme o binární operaci na té množině, ve které se dané dva prvky vyskytují. Algebra 1 (MA 0003) 29 stejných hodnot pro dvě různá x±,X2 E R. Dále je f surjekce R na R+ - pro každé y E R+ existuje x E R tak, že ex = y. Celkem tedy f je bijekce. Dále podmínka zachování výsledků operace nyní má vzhledem k zadaným operacím tvar f(a + b) = f(a)-f(b). Tato podmínka také platí, protože ea+h = ea ■ eh. Celkem f je grupovým izomorfismem.* Při hledání odpovědi na otázku, zda jsou dvě různé grupy izomorfní, musíme tedy projít tři kroky: a) definovat zobrazení / : G\ —> G2', b) dokázat o tomto zobrazení, že je injektivní a surjektivní, a tedy bijekce; c) dokázat, že platí vlastnost zachování výsledků operace. Pokud jsou dvě grupy izomorfní, tak chování operace na té druhé je přesnou kopií chování operace na první grupě. Tedy pokud první grupa (Gi, v) má vlastnost, kterou grupa (G2, *) nemá, nemohou být tyto grupy izomorfní. Například • G\ je komutativní, ale G2 ne. • G\ má nějaký prvek, který je inverzí sebe sama, ale G2 takový prvek nemá. • G\ je generována dvěma svými prvky, ale G2 není generována žádnou dvojicí svých prvků. • Atd., možná více viz cvičení. Před více než 100 lety dokázal Arhur Cayley větu, kterou se nyní budeme zabývat: Každá grupa (libovolná, konečná i nekonečná, komutativní i nekomutativní) je izomorfní nějaké podgrupě grupy permutací (ty byly představeny v minulé kapitole). Tento výsledek je revolučním ve studiu grup, protože vlastně tvrdí, že žádné jiné grupy (až na přeznačení prvků) než grupy permutací vlastně neexistují!!! A o to více je tento výsledek revoluční ve studiu operací - tvrdí totiž, že na grupách neexistuje žádná jiná operace než operace skládání permutací!!!! Jinými slovy, pomocí operace SKLÁDÁNÍ PERMUTACÍ lze reprezentovat jakékoli další operace na grupách, tj. sčítání, násobení, atd. Věta 8 (Cayley) Každá grupa (G, v) je izomorfní nějaké grupě permutací. Důkaz: dokážeme ve třech krocích: 1. Ke každému prvku a E G vytvoříme permutaci ira : G —> G (a dokážeme, že se jedná o permutaci G, tedy o bijekci). 30 Katedra matematiky PedF MUNI v Brně 2. O množině těchto permutací G* := K; a G G} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekcí G —>■ G). 3. Definujeme zobrazení / : G —> G* a dokážeme o něm, že je izomorfismus mezi grupami. Tak pojďme na to!! Důkaz podrobněji: 1. Ke každému prvku a E G vytvoříme permutaci ira : G —> G (a dokážeme, že se jedná o permutaci G, tedy o bijekci). Definujme pro libovolný prvek a E G zobrazení 7ra definované vztahem Vx E G : 7ra(x) := axj x (zobrazení Tľa zobrazí každé x E G na prvek axj x E G). Dokažme o 7ra, že se jedná o bijekci: • 7ra je injekce G —> G: Předpokládejme, že 7ra(xi) = 7ra(x2) - to by znamenalo podle definice zobrazení ira, že axj xx = axj X2, a protože v grupě platí vlastnost (7), můžeme vykrátit po vynásobení rovnosti prvkem a-1 zleva a dostaneme x\ = X2 ... tedy rovnost hodnot zobrazení 7ra může nastat jen pro tentýž prvek tedy / je injekce. • 7ra je surjekce G na G: Pro libovolný prvek y E G musíme najít jeho vzor vzhledem k zobrazení 7ra - jakmile najdeme aspoň jeden vzor, budeme vědět, že jedná se o surjekci, protože všechny prvky y E G hy pak byly pokryty nějakými vzory vzhledem k zobrazení /. Odpověď: hledaný vzor z G je prvek a-1 y Ví Pak totiž TTafa"1 XJ y) = axj a-1 XJ y = y. • Celkem ira je bijekce. 2. O množině těchto permutací G* := K; a EG} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekci G —» G). G* je podmnožinou grupy Sq všech permutací na G —> G. Dokážeme o G*, že je podgrupa: Algebra 1 (MA 0003) 31 • G* je neprázdná, nejmenší možná grupa G je totiž minimálně jednoprvková (obsahuje neutrální prvek e), a tedy minimálně 7re(x) := e y x Je identická permutace, která náleží do G*. • (G*, o) splňuje vlastnost (1), tedy pro dvě různé permutace 7Ta, 717, musíme najít prvek c G G, že ttc = pía o 717,. Skutečně to platí - pokud vezmeme c := a xj b, potom Podrobněji rozepsáno, Vx G G : 7rav6(x) = (ay^V^ = aV^V^) = ay^^) = ^a{^b{x)) = (7rao7r6)(x). Tedy složením dvou prvků 7ra a 717, z G* je zase prvek z G*, tj. množina G* je uzavřená vzhledem k operaci o. • (G*,o) splňuje vlastnost (4): Stačí dokázat, že ke každému ira G G* existuje inverzní permutace vzhledem ke skládání permutací: A to opravdu existuje, je to totiž permutace 7Ta-i odpovídající prvku a-1 G G - pak platí (podle vlastnosti (1) je složením permutací permutace odpovídající „násobku" obou dílčích prvků) • Tedy celkem G* je neprázdná a splňuje vlastnosti (1) a (4) - podle věty 6 je G* podgrupa grupy Sq, a tedy hlavně sama (G*, o) je grupou. 3. Definujeme zobrazení / : G —» G* a dokážeme o něm, že je izomorfismus mezi grupami. • Jako zobrazení / se nabízí přiřazení, o kterém už dlouho mluvíme: prvku a E G přiřadíme jím definovanou permutaci 7ra E G*, neboli f (a) = ttq. • / je injekce: Pokud f (a) = f(b), znamená to, že 7ra = 717,, tedy Vx G G : 7ra(x) = 7i7,(x); a tak i speciálně pro jednotku e E G platí 7ra(e) = 717,(e), což znamená a y e = b y e, to ale znamená, že a = b. Rovnost obrazů si vynucuje rovnost vzorů, tedy / je injekce. • / je surjekce: Tato vlastnost je zaručena už tím, jak je množina G* vytvořena: jsou do ní vybírány jen ty permutace 7ra, které odpovídají prvku a E G, tj. každá permutace 7ra má svůj vzor a E G vzhledem k zobrazení /. 32 Katedra matematiky PedF MUNI v Brně • / zachovává výsledky operace: chceme dokázat podmínku Va,foGG: f(avb) = f(a)of(b), a tu snadno dokážeme rozepsáním podle definice zobrazení / a vlastnosti (1) pro skládání permutací: f (a V b) = 7Tav& = 7Ta O 7T6 = f (a) o f (b). • Celkem / je izomorfismus grupy (G, v) na grupu (G*, o). Příklad 9 Kniha Pinter 2010, str. 97-102, opět poskytuje řadu cvičení na pojem izomor-fismu: Například C. 3: Zjistěte, zda je grupa 2^a'h^ s operací symetrického rozdílu 4- (stejná operace jako v úloze 1.6) izomorfní s grupou (V, ■), kde V = {1, —í} a ■ je operace násobení komplexních čísel. Své zjištění zdůvodněte. Například D.l: Prozkoumejte grupy a) (i/4,4-); b) (H2 X H2,+) (sčítání definováno po složkách po složkách); c) grupu komplexních jednotek (V, ■), kde V = {1, —1, í, —í} a ■ je operace násobení komplexních čísel. Které dvě z nich jsou izomorfní, a proč ta třetí s nimi není izomorfní? Například D.2: Viz cvičení 05, kde budou zhruba probrány grupy zbytkových tříd. (cvičení sady G): Izomorfní grupy na množině reálných čísel. (cvičení sady J): Regulární reprezentace grupy - rychlá konstrukce podgrupy grupy Sn, která je s grupou G izomorfní!! Algebra 1 (MA 0003) 33 4 Týden 04 4.1 Cvičení 04: Nekomutativní grupy Úloha 4.1 Jsou dány permutace P = (1, 5, 6, 2, 3), R= (1, 7, 5,4, 3, 6, 2). Vypočtěte P o R2 (výsledek najdete na konci tohoto textu). Úloha 4.2 Kniha Pinter 2010, str. 75, oddíl B, príklady na grupy permutací. Například B.2: Vypište prvky cyklické podgrupy grupy (5*6, o) generované prvkem f = (1,2, 3,4) o (5, 6). Například B.3: Najděte čtyřprvkovou komutativnípodgrupu grupy (6*5,0) a napište její tabulku operace. Například B.4: Podgrupa grupy (S5, o) generovaná prvky f = (1,2), g = (3,4,5) má šest prvků. Vypište tyto prvky, označte je e, f, g, h, í, j a sestavte tabulku operace o. Například N.l: Podgrupa grupy (S4, o) generovaná prvky f = (1,3) o (2,4), í7 = (3,4) má osm prvků. Najděte je všechny. Může vám pomoci vytváření tabulky operace o, ale nemusíte ji dělat celou. Například N.2: Vypište všechny prvky cyklické podgrupy grupy (67, o) generované prvkem f = (1,3) o (4, 5, 7). Například N.3: Grupa (6*4,0) má 24 prvků. Najděte nějakou její osmiprvkovou podgrupu - vypište podrobně zbylých sedm prvků kromě neutrálního prvku. Může vám pomoci vytváření tabulky operace o, ale nemusíte ji dělat celou. Úloha 4.3 (ad Pinter 2010, str. 77, sada F) na grupu symetrií pravidelného n-úhelníka: Grupa symetrií čtverce (příklad je zde podrobně rozebrán, ale možná, že bude třeba se studenty projít ještě příklad na symetrie trojúhelníka z přednášky 1 a připomenout celou problematiku). Uvažujme čtverec a takové jeho transformace, že po jejich provedení dostaneme zase čtverec se stranami rovnoběžnými s vertikálním a horizontálním směrem. Mám na mysli pootočení čtverce (se středem otáčení ve středu čtverce) o násobky 90° (ty jsou čtyři, a sice pootočení o 0°, o 90°, o 180° a o 270°), a ještě překlopení čtverce v osové souměrnosti 34 Katedra matematiky PedF MUNI v Brně podle navzájem symetrických os (ty jsou též čtyři pro osy otáčení v obou úhlopříčkách čtverce a ve dvou osách procházejících středy protějších stran čtverce). Použitím některé z těchto osmi transformací na čtverec dostaneme zase nějakou pozici čterce, která vznikne ze základní polohy uplatněním jedné dílčí transformace, tj. množina těchto osmi transformací (= přeměn ve smyslu osového překlopení či ve smyslu pootočení čtverce) tvoří grupu. Jak nyní dojdeme k permutaci přirozených čísel? Například tak, že do rohů základní polohy čtverce umístíme čísla 1,2,3,4. A po provedení dané transformace zapíšeme permutaci těchto čtyř čísel vzhledem k základní poloze. Pak identické transformaci (při které se neděje nic) odpovídá permutace R0 = id, pootočení o 90° odpovídá permutace Ri = (1,2,3,4) (v tom smyslu, že číslo 1 se pootočením dostalo na pozici čísla 2, číslo 2 se na pozici čísla 3, číslo 3 na 4 a číslo 4 na pozici 1). Podobně pootočení o 180° odpovídá permutace R% = (1, 3) o (2, 4)20 a pootočení o 270° permutace R3 = (1,4, 3, 2)21. (podrobněji viz obrázek 4.5). i h 3 i 0 ^ H -i 2. D -/4 * 1 l o W -----• z t 3 i ■2. H 1 U1 H Ki l5 h 1 i- •i , \ Z "i- A ■1 í Obrázek 4.5: Permutace odpovídající pootočení čtverce. 20Pozor, tuto permutaci nelze lépe označit než spojením dvou disjunktních cyklů délky 2, protože dochází ke dvěma nezávislým prohozením během jedné permutace. 21Což je totéž jako (4, 3, 2,1), ale začínáme při zápisu nejmenším možným číslem, abychom se vyznali ve výsledcích operací a podle pozice nejmenšího čísla poznali jednoznačně daný prvek. Algebra 1 (MA 0003) 35 Z \ \ \ H A H '1 A 'L h 3 lze sestrojit grupu symetrií pravidelného n-úhelníku a označit ji Dn vzhledem k operaci skládání zobrazení. Například D5 označuje grupu symetrií pětiúhelníku, atd. Každému rovinnému útvaru, který je pravidelný vzhledem k otáčení nebo osové souměrnosti, lze přiřadit jistou grupu symetrií. Grupy symetrií se široce používají v teorii elektronové struktury a molekulárních vibrací. V elementární časticové fyzice byly tyto grupy symetrii využity k předpovězení existence částic, které ještě ani nebyly experimentálně zjištěny! Proto i studium nekomutativních grup má svoje 36 Katedra matematiky PedF MUNI v Brně místo v algebře. Tabulka 4.4: Tabulka operace o na množině D4 symetrií čtverce. 0 Rq Ri R2 R3 R4 R5 Rq R7 Rq Rq Ri R2 R3 R4 R5 Rq R7 Ri Ri R2 R3 id Rq Ri R5 R4 R2 R2 R3 Ro Ri R5 R4 R7 Rq R3 R3 Ro Ri R2 R7 Rq R4 R5 R4 R4 R7 R5 Rq Ro R2 R3 Ri R5 R5 Rq R4 Ri R2 Ro Ri R3 Rq Rq R4 R7 R5 Ri R3 Ro R2 R? R? R5 Rq R4 R3 Ri R2 Ro Úkol: Najděte všechny inverzní prvky a všechny podgrupy v grupě D4. Úloha 4.4 Dva úkoly pro grupu permutací (63, o) (použijte prosím označení prvků a tabulku operace o v příkladu 4)' cl) dokažte, že (6*3,0) není cyklická grupa; b) najděte dvouprvkovou podmnožinu grupy, která generuje celou grupu (6*3,0). Úloha 4.5 Pokud bude čas, je možné se zabývat některými dalšími vlastnostmi permutací (ad Pinter 2010, kapitola 8): Každou permutaci lze rozložit na součin cyklů, každý cyklus lze rozložit na součin transpozic. Sudá a lichá permutace podle počtu transpozic. Ale to spíše až do předmětu Algebra 2 (lineární algebra). Výsledky některých cvičení najdete v závěru textu v oddílu 13.4. 4.2 Přednáška 04: Lagrangeova věta, homomorfismus grup, fak-torgrupa V dnešním oddílu budeme potřebovat znalosti o pojmu ekvivalence (relace reflexivní, symetrická a tranzitivní) a pojmu rozklad určený ekvivalencí (v jedné třídě rozkladu jsou právě ty prvky množiny M, které jsou navzájem v relaci příslušné ekvivalence) - viz předmět Základy matematiky. Jen zde připomeňme, že rozklad množiny M na systém podmnožin M±, M2, ■ ■ ■, Mk je takový systém podmnožin, které jsou a) neprázdné, b) po dvou disjunktní (každé dvě různé množiny mají prázdný průnik) a c) jejich sjednocením je celá množina M - někdy se takovému systému podmnožin říká též disjunktní pokrytí, Algebra 1 (MA 0003) 37 tj. je to systém po dvou disjunktních podmnožin, který pokrývá celou množinu M v tom smyslu, že [J Mj = M. Přidejme nyní navíc k předmětu Základy matematiky: • Pro důkaz jednoho zajímavého tvrzení (věty 17) nám bude stačit si uvědomit, že pokud dvě třídy rozkladu Mj, Mj mají neprázdný průnik, pak se musí rovnat, čili Mj = M j a jedná se o tutéž třídu. Lze tedy rozklad množiny M na podmnožiny Mj definovat i následovně: - Vie {1,2,...,*;}: M^0; - a E Mil) Mj Mi = Mj] - každý prvek a E M leží v jedné třídě rozkladu. • Označení 04: Znak ~ bude značit relaci ekvivalence určenou daným rozkladem, tj. a ~ b právě tehdy, když a, b E Mj pro nějaké i. • Označení 05: Označme dále [a] tu třídu rozkladu, která obsahuje prvek a, tedy podmínku z označení 07 budeme psát ve tvaru a ~ b <ř» [a] = [b]. Někdy se matematické výsledky dostavují zajímavým a překvapujícím způsobem. Při studiu pojmu grupa, tj. pojmu binární operace xj, která na množině M splňuje čtyři axiomy známé z operací sčítání a násobení racionálních čísel, jsme se zatím dostali ke Cayleyho větě, která je svým způsobem šokující: každou operaci v grupě lze reprezentovat operací skládání permutací na nějaké grupě permutací. K dalšímu zajímavému, a snad i nečekanému výsledku dojdeme nyní, když budeme přemýšlet o pojmu tzv. třídy prvku vzhledem k podgrupě. Definice 18 Va z grupy (G, v) a její podgrupu (H,xj) lze definovat: levá třída prvku a E G vzhledem k podgrupě H je množina axj H := {axj h E G : h E H} (množina výsledku operace axj h, kde prvek a E G je pevné a prvek h probíhá podgrupu H); podobně pravá třída prvku a E G vzhledem k podgrupě H je množina H y a := {hxj a E G : h E H} (množina výsledku operace hxja, kde prvek a E G je pevné a prvek h probíhá podgrupu H). 38 Katedra matematiky PedF MUNI v Brně Pojmy levá a pravá třída prvku splývají jen tehdy, pokud v Je komutativní operace, jinak ne. Dříve, než půjdeme dále, musíme se podívat na nějaký příklad tříd prvku vzhledem k podgrupě: Příklad 10 Pro grupu G = (H4,+) = (Z4,+) = ({0,1,2,3,},+) a podgrupu H = ({0, 2}) dostáváme následující levé třídy prvků podle podgrupy: • levá třída prvku 0 vzhledem k H je 0 + H = {0, 2} = H = H + 0 (tedy levá třída prvku 0 je rovná pravé třídě prvku 0); • levá třída prvku 2 vzhledem k H je 2 + H = {0, 2} = H = H + 2 (tedy levá třída prvku 2 je rovná pravé třídě prvku 2); • levá třída prvku 1 vzhledem k H je 1 + H = {1, 3} = H + 1 (tedy levá třída prvku 1 je rovná pravé třídě prvku 1); • levá třída prvku 3 vzhledem k H je 3 + H = {1, 3} = H + 3 (tedy levá třída prvku 3 je rovná pravé třídě prvku 3); Příklad 11 Pro grupu G = OS3, °) permutací z příkladu 4 a podgrupu H = ({id, (1,2,3), (1,3,2)}) dostáváme následující levé třídy prvků podle podgrupy (viz tabulka operace o u příkladu 4)' • levá třída prvku id vzhledem k H je id o H = {id, (1, 2, 3), (1, 3, 2)} = H = H o id (tedy levá třída prvku id je rovná pravé třídě prvku id vzhledem k operaci o); • levá třída prvku (1, 2, 3) vzhledem k H je (1, 2, 3)oH = {id, (1, 2, 3), (1, 3, 2)} = H = H o (1, 2, 3) (tedy levá třída prvku (1, 2, 3) je rovná pravé třídě prvku (1, 2, 3)); • levá třída prvku (1,3,2) vzhledem k H je (1,3,2) o H = {id, (1, 2, 3), (1, 3, 2)} = H o (1, 3, 2) (tedy levá třída prvku (1, 3, 2) je rovná pravé třídě prvku (1, 3, 2)); • levá třída prvku (2, 3) vzhledem k H je (2, 3) o H = {(2, 3), (1, 3), (1, 2)} = H o (2, 3) (tedy levá třída prvku (2, 3) je rovná pravé třídě prvku (2, 3)); • levá třída prvku (1, 3) vzhledem k H je (1, 3) o H = {(2, 3), (1, 3), (1, 2)} = H o (1, 3) (tedy levá třída prvku (1, 3) je rovná pravé třídě prvku (1, 3)); • levá třída prvku (1, 2) vzhledem k H je (1, 2) o H = {(2, 3), (1, 3), (1, 2)} = H o (1, 2) (tedy levá třída prvku (1, 2) je rovná pravé třídě prvku (1, 2)); Na příkladu 11 je vidět, že například množina (2,3) o H nemusí obsahovat žádný z původních prvků podgrupy H, a taky nemusí být podgrupa, protože neobsahuje neutrální prvek id, i když H podgrupa grupy G je (ze všech navzájem disjunktních tříd = podmnožin je podgrupou právě jedna - ta, která obsahuje neutrální prvek, a tedy třída H o id neboli třída H). Algebra 1 (MA 0003) 39 Zabývejme se dále pouze pravými třídami prvků - všechny následující věty se budou týkat pravých tříd prvku vzhledem k podgrupě H, ikdyž bychom je mohli analogicky (či duálně?) formulovat i pro levé třídy prvku. Věta 9 je pouze pomocnou větou, která bude potřeba v důkazu věty 10 (věty 9 až 12 jsou řečeny za předpokladu označení z definice 18, tj. (H, v) je podgrupa grupy (G, Xj)). Věta 9 a E H xj b právě tehdy, když H xj a = H xj b. Důkaz: „<=": tato část důkazu je triviální: protože a = e xj a E H XJ a a také b = exjbEHxjb,z rovnosti množin plyne i a E H XJ b. „=>": předpokládejme, že a E Hxjb, a tedy existuje h E H tak, že a = hxjb. Za tohoto předpokladu dokážeme množinovou rovnost z platnosti dvou inkluzí: H XJ a C H xj b: Pokud x E H xj a, tak x = h\ xj a pro nějaké h\ E H. Z předpokladu věty dosaďme za a a dostaneme i = /iiVa='iiV('lVř') = ('íiV'í)Vř') a protože součin v poslední závorce je prvkem H, dostáváme celkem, že x E H xj b. H xj b C H xj a: Pokud x E H xj b, tak x = h2 xj b pro nějaké h2 E H. Z předpokladu věty (a = h Xjb) si vyjádřeme b, konkrétně (protože jsme v grupě G, všechny inverze existují) a = hxj b => h-1 XJ a = b, a po dosazení za b dostaneme x = h2Xjb= h2XJ (h'1 XJ a) = (h2 XJ h'1) XJ a, a protože součin v poslední závorce je prvkem množiny H, dostáváme celkem, že x E H xj a. Věta 9 netvrdí nic světoborného, v podstatě jen to, že pokud prvky a, b jsou spojeny v operaci xj „přes podgrupu H", tak jejich pravé třídy jsou totožné. Následující věta 10 je prvním významným výsledkem této kapitoly. Věta 10 Pravé22 třídy H XJ a pro všechny možné prvky a grupy (G, Xj) tvoří rozklad množiny G. Důkaz: Dokážeme ve dvou krocích: a) Hxj a, Hxjb jsou buď disjunktní, nebo totožné; b) každý prvek grupy G leží v nějaké třídě takto vytvořeného rozkladu. 22Platí i analogická věta: Všechny levé třídy a y H ... 40 Katedra matematiky PedF MUNI v Brně a) Pokud množiny H XJ a, H XJ b mají prázdny společný průnik, neděláme nic, protože to je pozitivní situace, kterou jsme si přáli; zbývá projít situaci, kdy průnik obou těchto množin je neprázdný a obsahuje nějaký prvek x: x E (H y a) íl (H y b) => (x = hxXJ a) A (x = h2XJb) => hiXj a = h2XJb; vyjádřeme například prvek a z rovnosti, ke které jsme dospěli (jsme v grupě, tedy všechny inverze existují): a = hx1 y ^2 V ^ To tedy znamená, že a = (hX1 XJ h2) XJ b E H XJ b, a to podle věty 9 (tady právě ji potřebujeme!!) znamená, že H XJ a = H XJ b. b) Zbývá ukázat, že libovolný prvek c E G leží v některé z pravých tříd vzhledem k podgrupě H: to je už celkem snadné, protože c = exj c (kde e je neutrální prvek), a tedy c G H xj c. Našli jsme třídu rozkladu, ve které prvek c leží. Než se dostaneme k větě 12 vedoucí k Lagrangeově větě, ještě jedno označení a jeden výsledek, věta 11: Označení 06. Označme množinu tříd G/h rozkladu grupy G podle její komutativní podgrupy H ... vzhledem k operaci v definované pomocí vztahu (H V a)xj(H X7b):=Hx7(axjb) jako tzv. rozkladovou grupu nebo též při doslovném překladu faktorgrupu23. Věta 11 Struktura G/h vytvořená z tříd podle nějaké své komutativní podgrupy H s operací XJ je grupa. Důkaz věty 11 je technický a nebudeme ho uvádět. Raději zde zmíníme, že G/h v příkladech 10 a 11 jsou tedy grupy, jejímiž prvky jsou podmnožiny původní množiny G, a operace sčítání či skládání zobrazení je tak definována mezi množinami! Základním často použitým příkladem v tomto textu je právě příklad 10, kde Z4 je tzv. množina zbytkových tříd. Zbytkovým třídám se budeme věnovat v příští kapitole, v této kapitole jsme pouze zmínili větu, v níž je klíčové zejména to, že operace „sčítání množin" je definována korektně, tj. bez ohledu na to, jaký prvek vybereme z první množiny a ze druhé množiny, výsledek jejich operace stále padne též do stejné množiny jako všechny ostatní takto zkonstruované výsledky. Věta 12 Existuje bijekce mezi podgrupou (H, xj) a každou pravou třídou H XJ a. Důkaz: Bijekcí bude to nejpřirozenější zobrazení / : H —» H XJ a, které bychom asi vytvořili: f(h) = hxja. Takto definované / je injekce: f(h1) = f(h2)^ h1xja = h2xja^ hx = h2 23Anglicky FACTOR znamená, „rozložit". Algebra 1 (MA 0003) 41 (a podmínka injekce o rovnosti vzorů při rovnosti obrazů je dokázána). Dále / je surjekce: každý prvek množiny H xj a Je tvaru h xj a pro nějaké h E H, a toto h je hledaným vzorem vzhledem k zobrazení /. Celkem / je tedy injekce i surjekce, a tedy bijekce. Důkaz je hotov. □ Důsledkem věty 12 pro konečné grupy G je: Všechny pravé třídy Hxj a mají tentýž počet prvků!!!!! Čtenář si určitě říká, kdy už přijde ta slavná Lagrangeova věta z názvu této kapitoly - už se blíží, je to věta následující!!! Ale ty nej důležitější věty, věta 10 a věta 12, už byly řečeny. Ta následující je pouze jejich důsledkem, tj. pan Lagrange je autorem souvislostí všech těchto vět. Podívejme se ovšem předtím na příklad ilustrující celou situaci: Obrázek 4.7: Rozklad konečné grupy G na pět pravých tříd vzhledem k podgrupě H. Všechny třídy rozkladu mají stejný počet prvků. Příklad 12 Uvažujme situaci na obrázku 4-7: všech pravých tříd vzhledem k podgrupě H konečné grupy G je pět - jedna z nich je H xj e = H a další čtyři jsou H XJ a, H XJ b, Hxjc, Hxjd. Existuje bijekce (podle věty 12) mezi těmito čtyřmi množinami a grupou H, tj. všech pět množin má stejný počet prvků. Při konečném počtu prvků grupy G by platil vztah \G\ =5 - \H\. Věta 13 Lagrangeova věta pro konečné grupy. Počet prvků libovolné podgrupy H je dělitelem počtu prvků konečné grupy G (připomeneme-li si definici řádu grupy, tak: řád podgrupy H je dělitelem řádu grupy G). Důkaz Lagrangeovy věty je dalším důsledkem věty 12: pokud všechny pravé třídy mají stejný počet prvků, tak počet všech prvků je pouze nějakým násobkem počtu \H\. Příklad 13 Pokud G má 15 prvků, tak kromě nevlastních podgrup (jednoprvkové obsahující pouze neutrální prvek a celé grupy G) mohou mít jakékoli vlastní podgrupy jen tři prvky nebo pět prvků (což jsou vlastní dělitelé čísla 15). 42 Katedra matematiky PedF MUNI v Brně Příklad 14 Pokud \G\ je prvočíslo, tak grupa G má pouze nevlastní podgrupy (sebe samotnou a jednoprvkovou triviální podgrupu). Věta 14 Pokud \G\ = p je prvočíslo, tak grupa (G, v) je cyklická grupa a jakékoli a E G různé od neutrálního prvku e je jejím generátorem. Důkaz: Uvažujme a E G, a dále platí a ^ e (kde e je neutrální prvek). Rád prvku a je roven m > 1 (protože řádu 1 je pouze neutrální prvek grupy). Pak < a > je cyklická podgrupa, která má m prvků (a současně z předchozího platí m > 1), tj. celkem m\p A m > 1 => m = p (z neexistence vlastních dělitelů čísla p tedy plyne, že řád libovolného prvku a různého od e je roven p). □ Věta 14 je dalším důležitým faktem sama o sobě: existuje jediná grupa (až na izo-morfismus) daného prvočíselného počtu prvků. Například (Z?, +) je jediná sedmiprvková grupa, (Zn, +) je jediná jedináctiprvková grupa, apod. Získali jsme tedy úplnou informaci o grupách o prvočíselném počtu prvků - jsou cyklické, až na izomorfismus jediné (co se týká počtu prvků) a lze je generovat libovolným jejich prvkem a různým od neutrálního prvku. Věta 15 Rád každého prvku a E G je dělitelem řádu konečné grupy G. Důkaz: pro prvek c E G řádu m je < c > cyklickou podgrupou řádu m (libovolný prvek generuje cyklickou podgrupu grupy G), a tedy m je některý z dělitelů čísla což je řád grupy G. Definice 19 Protože přirozené číslo, které udává řád podgrupy \H\, je dělitelem řádu konečné grupy \G\, lze provést tuto operaci dělení přirozeným číslem a označit index podgrupy H v grupě G jako (G : H) = = počet navzájem různých tříd rozkladu {H \/a;aE G}. Homomorfismus grup Izomorfismus grup je bijektivním zobrazením, které zachovává výsledky operace. Tato vlastnost (zachování výsledků operace) se objevuje i u jiných zobrazení než bijekcí -taková zobrazení nazveme homomorfismy24. Definice 20 Grupový homomorfismus f : G —> H je takové zobrazení mezi grupami (G, v) a (H,*), které zachovává výsledky operace, tj. platí vlastnost Va,bEG: f(avb) = f(a)*f(b). 24Jazykově: izomorfismus = stejný tvar, totožný tvar; homomorfismus = podobný tvar, odvozený tvar (v jistém smyslu). Algebra 1 (MA 0003) 43 Příklad 15 Zobrazení grupy (Z, +) na grupu zbytkových tříd (Zq, +) definované vztahem „f (z) = zbytek po dělení čísla z číslem 6" je homomorfismus grup. Takto definované zobrazení opravdu splňuje podmínku zachování výsledku operace: například platí /(5 + 53) = /(5) + /(53), protože [4] = [5] + [5] (rovnost skutečně platí, protože v Z§ platí [5] + [5] = [10] = [4], neboli číslo 56 dává po dělení šesti zbytek 4, který určuje stejnou třídu rozkladu [4], která obsahuje prvek 10, což je součet zbytku po dělení čísla 5 šesti a zbytku po dělení čísla 53 šesti).□ Význam homomorfismu: Pod homomorfismem lze v řadě případů (tehdy, když / je surjekce grupy G na grupu H) vidět jistou projekci, která některé vlastnosti původní grupy ztrácí, ale zachová jednu jistou vlastnost. Třeba v právě uvedeném příkladu se při zobrazení / jistým způsobem ztrácí nekonečnost množiny Z a zůstává jen informace, jaké zbytky po dělení šesti existovaly mezi celými čísly, a dále zůstává na Z§ zachována vlastnost součtu zbytků, neboli součet dvou celých čísel dává po vydělení šesti zbytek, který je obsažen v té třídě rozkladu množiny Zq, která obsahuje součet zbytků obou původních čísel po vydělení šesti. Příklad 16 Zobrazení f : Zq —> Z3, přičemž na obou množinách uvažujeme operací sčítání, definované vztahem ( 0 1 2 3 4 5 \ /= I I I I I I \ 0 1 2 0 1 2 / je také grupový homomorfismus, protože zbytek po dělení šesti v grupě (Zq, +) je zobrazen na zbytek tohoto zbytku po dělení třemi v grupě (Z3, +). V důsledku zobrazení f se ztrácí jisté informace z grupy Zq, a sice celočíselná odchylka nejbližšího násobku šesti na číselné ose směrem vlevo od libovolného reprezentanta dané třídy rozkladu, ovšem zůstává zachována celočíselná odchylka nejbližšího násobku tří na číselné ose směrem vlevo od libovolného reprezentanta dané třídy rozkladu.\3 Definice 21 Pokud f : G —> H je grupový homomorfismus a současně surjekce, označujeme f(G) = H a grupa H se nazývá homomorfní obraz grupy G. Viz příklad 16: grupa (Z3, +) je homomorfním obrazem grupy (Zq,+) vzhledem k homomorfismu /. Podívejme se tedy na některé vlastnosti každého grupového homomorfismu. Tyto vlastnosti platí i pro izomorfismus, protože homomorfismus je obecnější pojem (každý grupový izomorfismus je současně i grupovým homomorfismem): 44 Katedra matematiky PedF MUNI v Brně Věta 16 Pro grupový homomorfismus f : G —> H grupy (G, xj) do grupy (H, *) platí: a) f(eG) = ch (grupový homomorfismus vždy zobrazuje jednotkový prvek grupy G na Jednotkový prvek grupy H); b) (/(a))-1 = /(a-1) (vzhledem ke grupovému homomorfismu platí: inverze obrazu = obraz inverze). Důkaz: • ad a) Prvek eG jistě můžeme psát jako eG xj eG, a po využití vlastnosti (h) homomorfismu (= vlastnosti zachování výsledků operace) dostaneme: f(eG) = F(eG y eG) = f{eG) * f(eG), dostali jsme tedy rovnost f(eG) = f(eG) * f(eG), ze které po vynásobení rovnosti prvkem (f(eG))~1 (který existuje díky vlastnosti (4) v grupě (H, *)) zprava dostaneme f(eG) * U^g))-1 = f(eG) * f(eG) * {f{eG))~\ a nyní použitím vlastnosti (3) grupy (H, *) na levé i pravé straně poslední rovnosti máme neutrální prvek e# grupy H a dostaneme sh = f(eG) * eH {3= f(eG), a to jsme chtěli dokázat (jednotkový prvek se zobrazí na jednotkový prvek). • ad b) chceme dokázat vztah f(a)*f(a-1) = eH, pak totiž podle věty 4 v grupě oba prvky, jejichž součin je neutrální prvek, si jsou navzájem inverzní. No ale to není těžké, začneme upravovat levou stranu rovnosti, kterou chceme dokázat, a využijeme vlastnost homomorfismu grup: f(a)*f(a ) = f(axya ) = f(eG) = eH, takže podle věty 4 inverzní prvek k prvku f (a) je prvek /(a-1), neboli (/(a))"1 = /(a-1). Důkaz je hotov. □ Definice 22 Jádro grupového homomorfismu f : G —» H se nazývá množina kerj ( označení 07)25 těch prvků z grupy (G, Xj), které se zobrazí na neutrální prvek e# grupy 0 Označení plyne z německého slova kernel - anglické core se z historických důvodů neprosadilo. Algebra 1 (MA 0003) 45 Příklad 17 a) V grupovém izomorfismu je jádrem zobrazení f pouze jednoprvková množina {ěq}. b) V homomorfismu f : Zq —>■ Z% z příkladu 16 je jádrem množina těch prvků, které se zobrazí na nulu: kerf = {0, 3}. Věta 17 Pro každý grupový homomorfismus platí tyto další vlastnosti: a) kerj je normálnípodgrupa v (G, v)/ b) f(G) je podgrupa v (H, *). Důkaz: ad a) vezměme libovolný a E ker/ a libovolný x E G. Chceme ukázat, že i y a y x-1 E ker/. Půjde to jednoduše, využijeme přitom předpokladu (p) věty (f(a) = eH) a vlastnosti (h) homomorfismu: f(x y a y x~v) = f(x) * f (a) * /(x_1) = f(x) * eH * /(x_1) = f(x) */(x'1) = eH, tj. protože se prvek x y a V x_1 zobrazil na neutrální prvek, patří do jádra ker/, protože právě těmito prvky je jádro definováno. ad b) i) f(G) je neprázdná množina, protože obsahuje minimálně neutrální prvek f(ea) = ch] ii) f(G) je uzavřená vzhledem k operaci *: pro f(x) a f(y) platí f(x)*f(y) = /(a; vy), tedy prvek f(x) * f(y) je obrazem prvku x y y E G, a tedy f (x) * f (y) E f {G), platí (1); iii) f (G) je uzavřená vzhledem k inverzím: pokud f (a) E f (G) také f (a-1) E f (G) a díky větě 22(b) víme že tyto dva prvky jsou navzájem inverzní, tj. našli jsme inverzi k prvku f (a), platí vlastnost (4). Celkem podle věty 6 je f (G) podgrupa grupy (H, *). □ 46 Katedra matematiky PedF MUNI v Brně 5 Týden 05 5.1 Cvičení 05: Rád prvku, cyklické grupy, grupy zbytkových tříd V prvním týdnu jsme už mluvili o n-té mocnině prvku. Jednoduše v každé grupě platí i zákonitosti, na které jsme zvyklí např. z operace násobení na množině všech zlomků: • am y an = am+n, • (am)n = am-n, • a~n = (a-1)™. Při našem hloubavém přemýšlení o vlastnostech obecných grup se ukazuje důležitým jeden pojem, který je s otázkou mocniny přirozeně spjatý - pojem řádu prvku. Uvidíme, že tento pojem je důležitý zejména pro konečné grupy, a v nekonečných grupách hraje svou specifickou roli, která souvisí s nekonečnými množinami. Definice 23 Rád prvku a grupy (G, v) je roven nejmenšímu přirozenému číslu n, pro které an = e (n-tá mocnina prvku a E G je rovna neutrálnímu prvku e E G. Pokud takové přirozené číslo neexistuje, říkáme, že řád prvku a je nekonečný. Příklad 18 Co se týká řádu jednotlivých prvků grupy (6*3,0), platí: • id1 = id, tj. id je prvek řádu 1; • (2,3)2 = (1,3)2 = (1,2)2 =id, tj. prvky (2,3), (1,3), (1,2) jsou řádu 2; • (1, 2, 3)3 = (1, 3, 2)3 = id, tj. prvky (1, 2, 3), (1, 3, 2) 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 id: id& = id, (2, 3)6 = ((2, 3)2)3 = id3 = id, (1, 3)6 = id, (1, 2)6 = id, (1, 2, 3)6 = ((1, 2, 3)3)2 = id2 = id, (1, 3, 2)6 = id. To je tedy zajímavá vlastnost, ke které jsme dospěli - v konečné grupě vždy po několikerém umocnění každého prvku dostaneme prvek jednotkový. Příklad 19 V grupě (Z, +) je řád všech prvků nekonečný, kromě prvku 0, jehož řád (jako řád každého neutrálního prvku) je roven jedné. Při krátkém zkoumání pojmu řádu prvku (ať už je konečný, nebo nekonečný), matematici dospěli k následujícím dvěma větám, které vrhají světlo na celou situaci: Algebra 1 (MA 0003) 47 Věta 18 Pro prvek a řádu n v grupě (G, y) platí: v této grupě existuje právě nrůzných hodnot a° = e = an (e je neutrální prvek grupy), a1, a2, ..., an~x. Důkaz: Dokážeme ve dvou částích: a) každá mocnina am prvku a řádu n je rovna některé z mocnin a°, a1, ..., a™-1; b) prvky a°, a1, ..., a™-1 jsou navzájem různé. Důkaz části a): Uvažujme libovolnou mocninu am prvku a 6 G, který je řádu n. Pak podle věty 21 z předmětu Základy matematiky (věta o dělení se zbytkem, která platí pro celá čísla - my ji nyní použijeme pouze pro čísla přirozená) vydělíme m : n a dostaneme, že existují přirozená čísla q, r tak, že m = n ■ q + r, 0 < r < n. Pak lze upravit am na tvar am = an-q+r = (an)q y ar = eq y ar = ar, a protože r je přirozené číslo, pro které 0 < r < n, musí být r rovno jednomu z čísel 0, 1, ..., n — 1. Důkaz části b): Zbývá dokázat, že prvky a°, a1, ..., a™-1 jsou navzájem různé. Pokud se některé z těchto dvou prvků rovnají, platí ar = as, kde r i s jsou dvě různá čísla z množiny {0, 1, 2, ..., n — 1}, tj. r ^ s. BUNO26 například s < r, tj. platí 0 < s < r < n, a tedy 0 < r — s < n. A protože ď = ď (to je náš předpoklad (p)), lze psát ar~s = ar\7 (ď)'1 = as y (ď)'1 = e. To je ovšem spor s definicí řádu n jako nejmenšího přirozeného čísla takového, že an = e, protože r — s < n. Náš předpoklad ar = as byl nesprávný, je tedy dokázán opak, že se jedná o n navzájem různých hodnot. □ Pokud se nad větou 18 zamyslíme, plyne z ní, že poté, co dosáhneme umocňováním prvku a konečného řádu n prvku an = e, další mocniny už nevytváří nové prvky, ale začínají opakovat předchozí prvky: an+1 = a, an+2 = a2, ..., a2™-1 = a™-1, a pak začíná druhé kolo opakování a2n = e, a2n+1 = a, atd. Věta 19 Pro prvek a nekonečného řádu v grupě (G, y) platí: v této grupě neexistují dvě mocniny tohoto prvku, které se rovnají, tj. pro dvě různá celá čísla r, s platí ď ^ as. Důkaz: je prostý, použijeme tutéž úvahu jako v důkazu věty 18, část b): Pokud by platilo ď = as, úpravou ď y (as)_1 dostaneme ar~s = ar\7 (a8)'1 = as y (a8)'1 = e, a to je spor s tvrzením, že řád prvku a je nekonečný, protože by existovala konečná mocnina prvku a rovná neutrálnímu prvku. Tj. předpoklad ar = as je nesprávný a důkaz 26BUNO = Bez újmy na obecnosti. 48 Katedra matematiky PedF MUNI v Brně sporem je hotov.□ To tedy znamená, že prvek nekonečného řádu „svým umocňováním"27 vede na nekonečně mnoho navzájem různých prvků grupy. A dodejme ještě větu, která upřesňuje situaci kolem konečného řádu prvku grupy: Věta 20 Pokud řád prvku a v grupě je n ( označení 08 : označme ord(a) = n), pak platí pro celočíselné t: a* = e <^> (n\t, tj. t = nxj q, pro nějaké q 6 Z). (mocnina prvku konečného řádu je rovna neutrálnímu prvku tehdy a jen tehdy28, když mocnitel t je násobek řádu n daného prvku). Důkaz: Dokážeme obě implikace: Ad „=>": Důkaz je podobný jako důkaz věty 18, část a): Pokud a1 = e, pak podle věty o dělení se zbytkem pro celá čísla platí t = n - q + r, kde 0 < r < n. Pak dosazením do naší rovnosti dostaneme e = at = an-q+r = (an)q \J ar = e\j ar. Ale protože n jako řád prvku a je nejmenší přirozené číslo takové, že an = e, Nemůže být r > 0, ale musí r = 0. Důkaz opačné implikace „<=": je zřejmý ... pokud t = n ■ q, pak a1 = an-q = (an)q = eq = e. Cyklické grupy Pojem cyklické grupy a jejího generátoru (jediného prvku) už byl vysvětlen dříve v dodatcích v kapitole 1. Nyní se podívejme na cyklické grupy ještě jednou poté, co známe pojmy izomorfismus grup a řád prvku grupy: Je jasné, že pokud < a > je cyklická grupa generovaná svým prvkem, který je řádu n, platí < a >= {e, a, a2,..., a™"1}. Existuje tedy izomorfismus grupy (Hn, +) pootočení hodinové ručičky s operací skládání pootočení na grupu (< a >,v) definovaný vztahem f(k) = ak pro k = 0,1,..., n — 1. Hned vidíme, že podmínka zachování výsledků operace je skutečně splněna: f(k + l) = ak+l = akVal = f(k)Vf(l). Touto kratinkou úvahou jsme vlastně dokázali větu 27Umocňování = opakované použití operace v na týž prvek. 28Poznámka pro čtenáře v angličtině: anglické matematické vyjadřování vyjadřuje někdy logickou spojku výrazem iff, což je zkráceně přesnějšího nematematického if and only if = tehdy a jen tehdy, když. Algebra 1 (MA 0003) 49 Věta 21 Každá konečná cyklická grupa řádu n (= grupa generovaná jediným prvkem řádu n) je izomorfní grupě (Hn, +). Speciálně, každé dvě konečné cyklické grupy řádu n29 jsou navzájem izomorfní. A podobně pro cyklickou grupu generovanou prvkem nekonečného řádu: lze psát r —2 —1 2 3i < a >= {..., a , a , e, a, a , a , ... j, a tedy můžeme definovat izomorfismus grupy (Z,+) na grupu (< a >,v) definovaný vztahem f (k) = ak pro jakékoli celé číslo k, který opět splňuje podmínku zachování výsledků operace. Dostáváme tak větu Věta 22 Každá nekonečná cyklická grupa (= grupa generovaná jediným prvkem nekonečného řádu) je izomorfní grupě (Z, +). Speciálně, každé dvě nekonečné cyklické grupy jsou navzájem izomorfní. Tedy věty 21 a 22 nám dávají nahlédnout do situace cyklických grup: všechny cyklické grupy jsou víceméně určeny grupami celých čísel - ať už nekonečné grupy jsou určeny a popsány grupou (Z, +), tak konečné cyklické grupy jsou určeny a popsány (až na přeznačení prvků) grupou (Zn, +) (což je grupa zbytkových tříd modulo n, která je izomorfní grupě pootočení hodinové ručičky (Hn,+))). Mohli bychom pracovat stále s grupou pootočení hodinové ručičky ale protože studenti už grupy zbytkových tříd absolvovali na cvičení, lze pracovat přímo s nimi. Následuje oddílek opakující znalosti ze cvičení o grupách zbytkových tříd. Grupy zbytkových tříd Klíčovou strukturu představuje následující pojem: Definice 24 množina zbytkových tříd modulo n ... popíšeme 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 5.8). 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). O relaci kongruence lze dokázat, že je to ekvivalence (tj. relace reflexivní, symetrická, tranzitivní). • 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. 29Připomínka bizarní definice řádu grupy: řád grupy = počet prvků grupy. 50 Katedra matematiky PedF MUNI v Brně Obrázek 5.8: Rozdělení celých čísel do šesti podmnožin. • 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. V každé třídě takto vytvořené jsou právě ta celá čísla, která jsou mezi sebou kongruentní modulo 6. Každá z daných 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 Z§ je konečná a má jen šest prvků!!!) a definujeme na této množině operace ©, 0 následovně: [a] © [b] := [a + b]: tj. součet tříd je třída, která obsahuje celé číslo a + b, [a] 0 [b] := [a ■ b]; Algebra 1 (MA 0003) 51 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 (Zq, 0) je grupa (zbytkových tříd modulo 6), (Zq*, ©) = (Zq — {[0]}, 0) je monoid (zbytkových tříd modulo 6). Příklad 20 a) Pomocí tabulky operace 0 dokažte, že (Zq,(B) je grupa: Tabulka 5.5: Tabulka operace 0 na množině Zq. © [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] b) Pomocí tabulky operace 0 dokažte, že(Ze,Q) je monoid: Tabulka 5.6: Tabulka operace 0 na množině Zq. 0 [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í 09 : Zn označení 10 : Z* množina zbytkových tříd modulo 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 52 Katedra matematiky PedF MUNI v Brně 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 23 Ve struktuře (Z*, 0) existuje k prvku [k] inverzní prvek vzhledem k násobení 0 právě tehdy, když k, n jsou nesoudělná. Například v (Zq, 0) neexistují k prvkům [2], [3], [4] inverzní prvky, protože čísla 2, 3, 4 jsou soudělná s číslem 6. Věta 24 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í Q, a tedy (Z*, 0) je grupa. Například (Zy,Q) je grupa. Čtenář by se o tom mohl snadno přesvědčit z tabulky operace 0 na množině Z7: 0 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1] Úloha 5.1 Cvičení k pojmu řád prvku: Ad Pinter 2010, str. 107-110: • Cvičení B (str. 108): Příklady řádu prvků. Například N.4-' Na grupě permutací (5V, °) jsou zadány prvky (formou součinu cyklů, který vypočtěte) a = (1,2,3,4) o (2,4,5), /3 = (1,6,7) o (2,5,7). Vypočtěte prvek (a3 o /34)5 a určete jeho řád. • Cvičení F: řád mocnin prvku. • Cvičení G: vztah mezi ord(a) a ord(ak). Úloha 5.2 Cvičení k pojmu cyklická grupa: • Na přednášce už nezbyl čas na důkaz věty: každá podgrupa cyklické grupy je cyklická, tj. lze ji generovat jediným prvkem - kterým?? (viz Pinter 2010, str. 114-115). • Cvičení A (str. 115): příklady cyklických grup. • Cvičení B: elementární vlastnosti cyklických grup. Algebra 1 (MA 0003) 53 • Cvičení C: generátory cyklické grupy. • Cvičení E: kartézský součin cyklických grup. Úloha 5.3 Cvičení k pojmu grupy zbytkových tříd: Například D. 2 z knihy Pinter 2010, str. 98: Všechny následující čtyři grupy jsou šestiprvkové. Vytvořte jejich rozklad do tříd tak, že v jedné třídě jsou grupy navzájem izomorfní. Najděte daný izomorfismus, popřípadě vysvětlete, proč grupy v různých třídách izomorfní nejsou. Grupa (5*3, o) permutací tříprvkové množiny na sebe sama - tabulku operace najdete v přednášce o nekomutativních grupách. Grupa (Z%, 0) (je vyloučena třída [0], ke které neexistuje inverze vzhledem k násobení): 0 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1] (Z6, ©) je grupa: © [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] Grupa (H3 x H2, +): + [0 0] [0 1] [1 0] [1 1] [2 0] [2 1] [0; 0] [0 0] [0 1] [1 0] [1 1] [2 0] [2 1] [0; i] [0 1] [0 0] [1 1] [1 0] [2 1] [2 0] [i; 0] [1 0] [1 1] [2 0] [2 1] [0 0] [0 1] [i; 1] [1 1] [1 0] [2 1] [2 0] [0 1] [0 0] [2; 0] [2 0] [2 1] [0 0] [0 1] [1 0] [1 1] [2; 1] [2 1] [2 0] [0 1] [0 0] [1 1] [1 0] 54 Katedra matematiky PedF MUNI v Brně Napríklad N.l: Jsou grupy (Zq, +) a (z3 x Z3) izomorfní? Pokud ano, daný izomorfis-mus najděte. Pokud ne, vysvětlete, proč izomorfní být nemohou. © [0] [1] [2] [3] [4] [5] [6] [7] [8] [0] [0] [1] [2] [3] [4] [5] [6] [7] [8] [1] [1] [2] [3] [4] [5] [6] [7] [8] [0] [2] [2] [3] [4] [5] [6] [7] [8] [0] [1] [3] [3] [4] [5] [6] [7] [8] [0] [1] [2] [4] [4] [5] [6] [7] [8] [0] [1] [2] [3] [5] [5] [6] [7] [8] [0] [1] [2] [3] [4] [6] [6] [7] [8] [0] [1] [2] [3] [4] [5] [7] [7] [8] [0] [1] [2] [3] [4] [5] [6] [8] [8] [0] [1] [2] [3] [4] [5] [6] [7] f [0 0] [ 0 1] [0;2] [1 0] [i;i] [1 2] [2 0] [2 1] [2 2] [0 0] [0 0] [ 0 1] [0;2] [1 0] [i;i] [1 2] [2 0] [2 1] [2 2] [0 1] [0 1] [ 0 2] [0;0] [1 1] [i;2] [1 0] [2 1] [2 2] [2 0] [0 2] [0 2] [ 0 0] [0; i] [1 2] [i;0] [1 1] [2 2] [2 0] [2 1] [1 0] [1 0] [ 1 1] [i;2] [2 0] [2;i] [2 2] [0 0] [0 1] [0 2] [1 1] [1 1] [ 1 2] [i;0] [2 1] [2; 2] [2 0] [0 1] [0 2] [0 0] [1 2] [1 2] [ 1 0] [i;i] [2 2] [2;0] [2 1] [0 2] [0 0] [0 1] [2 0] [2 0] [ 2 1] [2; 2] [0 0] [0;i] [0 2] [1 0] [1 1] [1 2] [2 1] [2 1] [ 2 2] [2;0] [0 1] [0;2] [0 0] [1 1] [1 2] [1 0] [2 2] [2 2] [ 2 0] [2;i] [0 2] [0;0] [0 1] [1 2] [1 0] [1 1] Například N.2: Najděte minimální (vzhledem k počtu prvků) množinu generátorů grupy (Z2 x Z2 x Z2,®): © [o 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1;0 1] [1 1 0] [1 1 1] [0 0; 0] [o 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1;0 1] [1 1 0] [1 1 1] [0 0; 1] [o 0 1] [0 0 0] [0 1 1] [1 0 1] [0 1 0] [1;0 0] [1 1 1] [1 1 0] [0 1;0] [o 1 0] [0 1 1] [0 0 0] [1 1 0] [0 0 1] 1] [1 0 0] [1 0 1] [1 0; 0] [i 0 0] [1 0 1] [1 1 0] [0 0 0] [1 1 1] [0;0 1] [0 1 0] [0 1 1] [0 [0 1 1] [0 1 0] [0 0 1] [1 1 1] [0 0 0] 0] [1 0 1] [1 0 0] [1 0; 1] [1 0 1] [1 0 0] [1 1 1] [0 0 1] [1 1 0] [0;0 0] [0 1 1] [0 1 0] [1 1;0] [1 1 0] [1 1 1] [1 0 0] [0 1 0] [1 0 1] [0;1 1] [0 0 0] [0 0 1] [1 [1 1 1] [1 1 0] [1 0 1] [0 1 1] [1 0 0] [0;1 0] [0 0 1] [0 0 0] Algebra 1 (MA 0003) 55 Napríklad D. 3: Všechny následující tři grupy jsou osmiprvkové. Zjistěte, zda některé z těchto grup jsou izomorfní, popřípadě vysvětlete, proč izomorfní nejsou: Grupa (Zg,©): © [0] [1] [2] [3] [4] [5] [6] [7] [0] [0] [1] [2] [3] [4] [5] [6] [7] [1] [1] [2] [3] [4] [5] [6] [7] [0] [2] [2] [3] [4] [5] [6] [7] [0] [1] [3] [3] [4] [5] [6] [7] [0] [1] [2] [4] [4] [5] [6] [7] [0] [1] [2] [3] [5] [5] [6] [7] [0] [1] [2] [3] [4] [6] [6] [7] [0] [1] [2] [3] [4] [5] [7] [7] [0] [1] [2] [3] [4] [5] [6] Grupa (Z2 x Z2 x Z2,®): + [0 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [0 0 0] [0 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [0 0 1] [0 0 1] [0 0 0] [0 1 1] [1 0 1] [0 1 0] [1 0 0] [1 1 1] [1 1 0] [0 1 0] [0 1 0] [0 1 1] [0 0 0] [1 1 0] [0 0 1] [1 1 1] [1 0 0] [1 0 1] [1 0 0] [1 0 0] [1 0 1] [1 1 0] [0 0 0] [1 1 1] [0 0 1] [0 1 0] [0 1 1] [0 1 1] [0 1 1] [0 1 0] [0 0 1] [1 1 1] [0 0 0] [1 1 0] [1 0 1] [1 0 0] [1 0 1] [1 0 1] [1 0 0] [1 1 1] [0 0 1] [1 1 0] [0 0 0] [0 1 1] [0 1 0] [1 1 0] [1 1 0] [1 1 1] [1 0 0] [0 1 0] [1 0 1] [0 1 1] [0 0 0] [0 0 1] [1 1 1] [1 1 1] [1 1 0] [1 0 1] [0 1 1] [1 0 0] [0 1 0] [0 0 1] [0 0 0] Grupa (_D4,o); (R0, R1) R2, R% jsou rotace čtverce o násobek pravého úhlu; S4, S5 osové souměrnosti vzhledem k úhlopříčkám čtverce; Sq, St osové souměrnosti vzhledem ke spojnicím středů protějších stran čtverce) Rq Ri R2 R3 54 55 Sq s7 o 56 Katedra matematiky PedF MUNI v Brně Napríklad N.3: Definujte presne izomorfismus (Zy,Q) na (Zq,(B), který zachováva výsledky operace. Grupa (Zy,Q) (je vyloučena třída [0], ke které neexistuje inverze vzhledem k násobení): Grupa (Zq, i 0 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1] © [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] Výsledky některých cvičení najdete v závěru textu v oddílu 13.5. 5.2 Přednáška 05 Tato přednáška nepřináší nové pojmy a zákonitosti, pouze procvičuje už dříve probrané - stejně na příkladech lze všechny pojmy vidět nejlépe. Příklad 21 Cvičení na podgrupy, které využívá poznatku Lagrangeovy věty: Pro grupu (1)5,0), kde D5 je desetiprvková množina transformací pravidelného pětiúhelníka na sebe sama a operace o (=vpou) je skládání transformací, vypište všechny její podgrupy. Použijte přitom informace o jejích prvcích (zachovejte prosím označení): • e ... identita (nedělá s pětiúhelníkem nic); • f ... pootočení pětiúhelníka v jeho středu o 72° po směru hodinových ručiček; • g ... pootočení pětiúhelníka v jeho středu o 144° po směru hodinových ručiček; • h ... pootočení pětiúhelníka v jeho středu o 216° po směru hodinových ručiček; • i ... pootočení pětiúhelníka v jeho středu o 288° po směru hodinových ručiček; Algebra 1 (MA 0003) 57 • u ... osová souměrnost vzhledem k ose AU, kde A je vrchol pětiúhelníka a U je střed strany CD; • v ... osová souměrnost vzhledem k ose BV, kde B je vrchol pětiúhelníka a V je střed strany DE; • w ... osová souměrnost vzhledem k ose CW, kde C je vrchol pětiúhelníka a W je střed strany E A; • x ... osová souměrnost vzhledem k ose DX, kde D je vrchol pětiúhelníka a X je střed strany AB; • y ... osová souměrnost vzhledem k ose EY, kde E je vrchol pětiúhelníka a Y je střed strany BC; a informace o vlastnostech, které platí: • Podle Lagrangeovy věty múze mít podgrupa konečné grupy jen jistý počet prvku; • uvažte také uzavřenost operace na podgrupě: některé prvky samy od sebe generují jiné prvky (a jejich zahrnutí v podgrupě tedy vyžaduje i zahrnutí dalších prvku); • ještě musíte do každé podgrupy zahrnout i všechny příslušné inverzní prvky. Příklad 22 Cvičení k pojmu levá a pravá třída prvku vzhledem k podgrupě (Pinter 2010, str. 130-135): • A. Příklady tříd prvku vzhledem k podgrupě konečné grupy • B. Příklady tříd prvku vzhledem k podgrupě nekonečné grupy: Například N.l: H =< 5 > je podgrupa grupy (Z, +) generovaná prvkem 5. Vypište všechny pravé třídy prvků vzhledem k podgrupě H. • C. Důsledky Lagrangeovy věty • D. Další důsledky Lagrangeovy věty • E. Vlastnosti tříd prvku vzhledem k podgrupě. Příklad 23 Lagrangeova věta (a její důsledek - věta 14) společně s větou 21 nám pomalu, ale jistě dává informace o všech konečných grupách o malém počtu prvků: • Jednoprvková grupa je (až na izomorfismus) jediná a obsahuje pouze neutrální prvek. • Grupa o prvočíselném počtu prvků 2, 3, 5, 7, atd. je cyklická (věta 14), a tedy až na izomorfismus stejná jako (Hp,+) neboli (Zp,+) (věta 21), tedy grupa prvočíselného počtu prvků je až na izomorfismus jediná. 58 Katedra matematiky PedF MUNI v Brně • Dále grupa o počtu prvků p2, který je druhou mocninou prvočísla, je podle cvičení G (Pinter 2010, str. 154-155) izomorfní buď (Zp2,+), nebo (Zv x Zp), tedy existují pouze dvě navzájem neizomorfní grupy řádu p2. • Přehled všech šestiprvkových grup: cvičení F, str. 132. • Přehled všech desetiprvkových grup: cvičení G, str. 132. • Přehled všech osmiprvkových grup: cvičení H, str. 133. Následující příklady viz Pinter 2010, str. 141-146: Příklad 24 Například A.l. a) Definujte nějaký (aspoň jeden) homomorfismus f : (Z$, +) —> (Z4,+): /01234567\ b) Určete jádro K homomorfismu z části (a). Příklad 25 Například A.5: Každá z dvanácti transformací pravidelného šestiúhelníka v grupě (Dq, o) (šest pootočení o násobek šedesáti stupňů, včetně identity = pootočení o úhel nulový; dalších šest jsou osové souměrnosti podle tří úhlopříček procházejících protějšími vrcholy (A,D a B,E a C,F) a podle tří spojnic středů protějších stran) nějak permutuje jeho tři úhlopříčky, které si označme čísly 1 (AD), 2 (BE) a 3 (CF), tj. tato současná permutace šesti vrcholů a permutace tří úhlopříček definuje homomorfismus f : Dq —> S3, v obou grupách uvažujeme operaci skládání permutací. Například f{id6)=id3, /(1,2,3,4,5,6) = (1,2,3). Napište, na jaké prvky se zobrazí tímto homomorfismem zbylých deset prvků grupy Dq. Grupa (£3,0) má prvky: id, (1,2,3), (1,3,2), (2,3), (1,3), (1,2). Příklad 26 B. Příklady homomorfismu nekonečných grup: Například B.2: Zdůvodněte, proč zobrazení ip je grupovým homomorfismem, a najděte jeho jádro: (p : (D(R), +) —> (F(R), +) je definované vztahem (p(f) = f (D(R) je množina reálných funkcí, u kterých existuje jejich derivace f, a F(R) je množina reálných funkcí). Například B.3: Zdůvodněte, proč zobrazení f je grupovým homomorfismem, a najděte jeho jádro: f : (R x R, +) —> (R, +) je definované vztahem f ([x, y]) = x + y ((R x R, +) je množina je množina uspořádaných dvojic reálných čísel, které sčítáme po složkách). Algebra 1 (MA 0003) 59 Příklad 27 F. Homomorfismus a řád prvku (postup a výsledky tohoto příkladu viz 13.5). Například F. í: Pro homomorfismus grup f : (G, v) ~~> (H, *) je a E G prvek řádu n. Vyzkoumejte na příkladech (např A. í), co lze říci o řádu prvku f (a) - POZOR, nemusí být stejný jako řád prvku a. Například N.3: Dokažte větičku: Grupový homomorfismus zobrazuje generátor cyklické podgrupy na generátor cyklické podgrupy. Například N.4-' Pomocí věty 16 a předchozích dvou větiček F.l, N.3 najděte všechny možné homomorfismy z příkladu A.l, tj. všechny možné homomorfismy grupy (Z$, ©) do grupy (Z4,©) a určete jejich jádra. Například N.2: Vypište všechny prvky grup (Zg,®), (6*3,0) a u každého prvku určete jeho řád. Potom popište všechny možné homomorfismy grupy (Zg, ©) do grupy (63,0), které existují - musíte při každém z nich určit, kam se zobrazí každý prvek množiny Zg. U každého z těchto homomorfismů určete jeho jádro. Příklad 28 Například N.l: Uvažujme homomorfismus ip grupy (Z$, ©) do grupy (Z4,®) definovaný y?(0) = 0, (p(l) = 1, atd. a) Určete jádro K tohoto homomorfismů; b) Jaké prvky má faktorgrupa Z$/k s operací rozšířenou na třídy? Je možné vyjádřit obrázkem, ale vyznačte zřetelně prvky faktorgrupy. Výsledky některých příkladů najdete v závěru textu v oddílu 13.5. 60 Katedra matematiky PedF MUNI v Brně 6 Týden 06 6.1 Cvičení 06: Rezerva, resty z minulých hodin, odpovědi na otázky 6.2 Přednáška 06: struktury se dvěma operacemi 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 25 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): V x,y, z E M : x ■ (y + z) = x ■ y + x ■ z, (y + z)-x = y- x + z- x (rovnice jsou dvě díky tomu, že operace • není obecně komutativní). Příklad 29 • Příkladem konečného okruhu je struktura zbytkových tříd (Zn,®,Q). • 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, •) vykazuje určité defekty, tj. obsahuje tzv, netriviální dělitele nuly: Definice 26 nenuloví dělitelé nuly jsou takové prvky a, b množiny M, které se nerovnají nule (0 = neutrální prvek v grupě (M,+)), ale jejich součin (= výsledek operace násobení v pologrupě (M, •)) je roven nule: a ■ b = 0; Příklad 30 Příkladem struktury s nenulovými dělitely nuly je množina Zq zbytkových tříd modulo 6: její prvky [2], [3] nebo [3], [4] jsou nenuloví dělitelé nuly, protože platí [2] 0 [3] = [0], [3] 0 [4] = [0]. Algebra 1 (MA 0003) 61 Je vidět, že právě dělitelé nuly způsobují, že v některých pologrupách či monoidech (např. (Zq, 0) je monoid vzhledem k operaci 0) neplatí zákon o krácení (7): např. právě v (Zq, 0, 0) vidíme, že [2] 0 [2] = [2] 0 [5], ale nemůžeme vykrátit z rovnosti třídu [2], protože [2] ^ [5] . 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 27 obor integrity30 (anglicky: integrál domain) je množina31 (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 komutativně operace ■ lze distributivní zákon psát v jediné rovnici: V x,y, z £ M : x-{y + z)=x-y + x- z = y- x + z- x={jj + z)-x. Příklad 31 • (Z7, 0, 0) je konečný obor integrity, protože 7 je prvočíslo, tj. (Zy, 0) 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: 30Vý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 integrál 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. 31 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í aO^l. 62 Katedra matematiky PedF MUNI v Brně Definice 28 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. ad a) Operace + nesplňuje nic nového, ad b) operace ■ splňuje navíc vlastnost (4), tedy (M — {0}, •) je grupa32; ad c) zde nic nového. Příklad 32 • (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í: Obrázek 6.9: Vztah mezi pojmy okruh, obor integrity, těleso. Každé těleso je oborem integrity, každý obor integrity je i okruh (a z tranzitivity pojmů plyne, že i každé těleso je okruh). Ale naopak to neplatí: existují okruhy, které nejsou oborem integrity, např. (Zq, ©, ©); a existují obory integrity, které nejsou tělesem, např. (Z, +, •). Kromě termínů okruh, obor integrity, těleso se někdy v algebraické teorii vyskytují pojmy ideál a hlavní ideál, které bude asi dobré doplnit společně s příklady, a tím se semestr uzavře. 32Vlastnost (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". Algebra 1 (MA 0003) 63 Definice 29 Ideál je neprázdna podmnožina B okruhu (M, +, •) taková, že (B, +) je pod-grupa (tj. B vzhledem k operaci + splňuje vlastnosti (1) a (4)) a navíc B absorbuje součiny na množině M, tj. Vfo G B, m E M : b ■ m G B (vynásobíme-li prvek množiny B prvkem množiny M, výsledek padne do množiny B). Příklad 33 Nejpřirozenějším příkladem ideálu je podmnožina B sudých celých čísel okruhu (Z, +, •); B = {...,-4,-2,0,2,4,...}. Je zřejmé, že (B, +) je podgrupa grupy (Z, +) a vynásobíme-li sudé číslo jakýmkoli celým číslem, výsledek je opět sudé číslo, tj. množina B absorbuje všechny násobky sebe sama s lichými čísly. Tedy B je ideál v (Z, +, •). Definice 30 V teorii ideálů hraje klíčové místo tzv. hlavní ideál okruhu, který definujeme jako takový ideál B, který vygenerujeme jediným prvkem b, jenž vynásobíme se všemi prvky množiny M. Příklad 34 Pro M = (Z, +, •) jsou hlavními ideály tyto množiny: • B\ :=< 1 > ... ideál generovaný prvkem 1 a všemi součiny 1 • z pro z E Z, tj. B\ = Z (okruh (Z, +, •) je sám o sobě hlavním ideálem); • B2 :=< 2 > ... ideál generovaný prvkem 2 a všemi součiny 2 • z pro z E Z, tj. jedná se o ideál z příkladu 6.5: B = {...,-4,-2,0,2,4,...}. • S3 :=< 3 > ... ideál generovaný prvkem 3 a všemi součiny 3 • z pro z E Z, tj. B3 = {...,-6,-3, 0, 3,6,...}. • atd. • Pokud v okruhu (Z, +, •) vezmeme ideál generovaný dvěma prvky, například B =< {3, 7} >, jeho prvky jsou například celá čísla dělitelná třemi nebo sedmi, ale POZOR, to nejsou všechny jeho prvky: B musí být grupou vzhledem k operaci sčítání, obsahuje tedy i číslo 7 — 3 = 4, a pokud obsahuje čísla 3 i 4, obsahuje také jejich rozdíl 4 —3 = 1, a pokud obsahuje jedničku, obsahuje vlastně všechna celá čísla, protože jednička vzhledem ke sčítání vygeneruje celou množinu Z, a to je hlavní ideál vzhledem k prvku 1, tedy došli jsme k tomu, že < {3,7} >= Z =< 1 > . Takže není tak jednoduché najít ideál, který není hlavní, protože o množině Z víme, že je hlavním ideálem vzhledem ke generátoru 1. Ve skutečnosti je docela schůdné dokázat matematickou větu, že každý ideál okruhu (Z, +, •) je hlavním ideálem. 64 Katedra matematiky PedF MUNI v Brně Čtenář tohoto textu či student předmětu Algebra 1 si určitě říká, nač je toto vše podrobné studium pojmů, vycházejících většinou z vlastností operací sčítání, násobení, průniku a sjednocení. Rád bych jej ubezpečil, že kromě toho, že zákonitosti jsou samy o sobě zajímavé, posloužily v historii právě v tom nej důležitějším úkolu algebry, a tedy ke hledání řešení algebraických rovnic. Ve druhé polovině semestru se budeme právě řešením algebraických rovnic zabývat podrobně. Procvičení pojmů okruh, obor integrity, těleso: např. viz Pinter 2010, kapitola 17 a cvičení na str. 174-178. Například N.l: a) Které z vlastností (1) až (10) splňuje struktura (2P, U, n) pro P = {a, b, c}? b) Jak byste strukturu (2P, U, Pl) z části (a) nazvali (okruh, obor integrity, těleso, nebo něco jiného)? c) Najděte netriviální dělitele nuly na struktuře (2P, U, Pl). Dejte pozor na to, že „nula" je vždy prvek vzhledem k první uvedené operaci struktury, zatímco dělitelnost se zkoumá vzhledem ke druhé operaci struktury. d) Najděte netriviální dělitele nuly na struktuře (2P, n, U). Dejte pozor na to, že „nula" je vždy prvek vzhledem k první uvedené operaci struktury, zatímco dělitelnost se zkoumá vzhledem ke druhé operaci struktury. Například N.2: Uveďte příklad nekonečného oboru integrity, který není tělesem. Například D.l: a) Uvažujme množinu 2P všech podmnožin množiny P = {a, b, c}. Na této množině lze definovat operaci symetrického rozdílu A 4- B := (A — B) U (B — A) a klasickou operaci n průniku. Sestavte tabulky operací 4- a n na množině 2P. b) Jak byste strukturu (2P, 4-, n) z části (a) algebraicky popsali (je to okruh, obor inte- grity, těleso, nebo něco jiného)? Procvičení pojmů ideál, hlavní ideál, homomorfismus okruhů: viz Pinter 2010, kapitola 18 a cvičení na str. 185-189. Například N.3: Ideál (D, +, •) okruhu celých čísel (Z,+,-) je takový jeho podokruh, který je uzavřený vzhledem k násobení celým číslem, tj. d ■ z E D V d G D, z (E Z. Uveďte příklad ideálu D okruhu (Z, +, •), který obsahuje číslo 2 a neobsahuje číslo 3. Algebra 1 (MA 0003) 65 7 Týden 07 7.1 Cvičení 07: Polynomy 01 Rozklad polynomu na součin polynomů prvního stupně, kořen polynomu, Hornerovo schéma, největší společný dělitel polynomů. Studenti měli Hornerovo schéma i Eukleidův algoritmus a dělení polynomů v předmětu Diskrétní matematika (MA0001), aleje potřeba zopakovat. Doporučené materiály k využití: • Označení: (Z[x],+, ■), (Q[x],+,-), (R[x], +, •), ... po řadě okruhy polynomů s koeficienty z okruhu celých čísel, tělesa racionálních čísel a tělesa reálných čísel. Tyto okruhy neobsahují netriviální dělitele nuly, takže se jedná o obory integrity (Budínová 2013, str. 7, věta 1). Ideální definice okruhu Z\x\. jedná se o rozšíření okruhu (Z, +, •) o prvek x, kde nevíme, co je, může tam být cokoliv, třeba33 číslo 7T. Množina polynomů tedy neobsahuje všechny inverze vzhledem k násobení polynomů. • Budínová 2013, str.8-10: stupeň polynomu, dělení polynomů se zbytkem ... studenti znají, ale připomeňte. • Hornerovo schéma (Budínová 2013, str. 10-12), základní věta algebry, vydělte polynom 6x3 + 13x2 — 1 polynomem {x — 1) nebo (x + 2): an ■ xn + an-\ ' xn~x + • • • + a\ ■ x + ao = an ■ {x — x±) ■ {x — x2) ■ ■ ■ {x — xn), například 1 2 6x3 + 13x2 - 4 = 6(x + 2)(x - -)(x + -). 2 3 • Budínová 2013, str. 18-21 po pojem ireducubilní polynom, objasnění, že v základní větě algebry se vyskytují ireducibilní polynomy. Dělitel polynomů, největší společný dělitel polynomů, Eukleidův algoritmus: znají, ale připomeňte (na příkladu). Normovaný největší společný dělitel. • Nalezněte NSD polynomů: Eukleidovým algoritmem (Budínová 2013, str.20, př. 16), rozkladem na součin ireducibilních polynomů (př. 18,19, str. 23 ... upozorněte studenty, že rozklad lze realizovat substitucí (př.18) nebo postupným vytýkáním). Pinter, 2010, str. 241. 66 Katedra matematiky PedF MUNI v Brně 7.2 Přednáška 07: Struktury se dvěma operacemi II Analogie Cayleyho věty, analogie Lagrangeovy věty, analogie věty o homomorfismu, analogie dobře definované operace na faktorgrupě. Věta o rozšíření těles: polynom s koeficienty z tělesa T nemusí mít kořeny přímo v tělese T, ale to lze rozšířit na těleso Ft, které už obsahuje kořeny původního polynomu. Algebra 1 (MA 0003) 67 8 Týden 08 8.1 Cvičení 08: Polynomy 02 Věta o racionálních kořenech polynomu v (Z[x],+, ■). Odstranění násobných kořenů polynomu. Využijte například následující materiál: • Věta o racionálních kořenech polynomu z (^[x], +, •) - Budínová 2013, str. 33, věta 24. Příklad. 21 na str. 28: Nalezněte kořeny polynomu x5 — 5x4 + 7x3 — 2x2 + 4x — 8. Pojem násobnosti kořene, základní věta algebry v terminologii násobnosti kořene. • Příklady na procvičení: str.34-př.29, str.35-př.30 ... je nutné dělat ty znaménkové změny? To rozhodne cvičící. • Odstranění násobných kořenů: str.32 poznámka až str. 33 příklad 28. Pak ještě nějaký příklad s násobnými kořeny, např. polynom čtvrtého stupně se dvěma dvojnásobnými komplexně sdruženými kořeny. 68 Katedra matematiky PedF MUNI v Brně 8.2 Přednáška 08: Přehled algebraických metod hledání kořene polynomu Algebra 1 (MA 0003) 69 9 Týden 09 9.1 Cvičení 09: Polynomy 03 Dodělání osnovy na cvičení pro polynomy viz plán cvičícího. 70 Katedra matematiky PedF MUNI v Brně 9.2 Přednáška 09: Přehled numerických metod hledání kořene polynomu Hledání iracionálních a komplexních kořenů polynomu numerickými metodami - metoda půlení intervalu, Newtonova metoda. Použijte např. následující materiál: • Budínová, Př. 23-str.29: nalezněte řešení algebraické rovnice 2x5 + 3x4 - 7x3 + 6x2 - llx + 5 = 0. Homérovým schématem ověříme, že žádné racionální řešení neexistuje. Všechna řešení tedy jsou reálná iracionální, nebo komplexní. • A) Hrubá detekce (Budínová, str.29, věta 16): všechny kořeny leží v komplexní rovnice uvnitř kružnice se středem v počátku a poloměrem r _ 1 max {|q0|, |qi|, ..., |an_i|} \an\ Dosazením do tohoto vzorce v našem příkladu máme . . max{3, 7, 6,11, 5| 11 xA < 1 +-1,11—= 1 + — = 6,5. 1 1 - 2 2 To znamená, že všechna řešení, imaginární i komplexní (a kdyby byla některá racionální, což v našem příkaldu nejsou, tak i ta) leží v Gaussově rovině v kruhu se středem v počátku a poloměrem 6,5. • B) Jemnější detekce reálných řešení: Ad A ... stále stejný řešený příklad, \xt\ < 6, 5: Víme, že xt E (—6,5; 6,5), řešíme rovnici p{x) = 0 pro p(x) = 2x5 + 3x4 - 7x3 + 6x2 - llx + 5. Protože pix) je spojitá funkce, tj. vypočteme p(ht) pro ht postupně rovno —6,5, pak —6,4, pak —6,3, ..., pak 6,3, pak 6,4, pak 6,5. Pokud se stane pro nějaké i, že pihi) ■ pih^i) < 0, znamená to, že dvě po sobě jdoucí hodoty mají rozdílná znaménka, tedy objevíme, že na intervalu {hf, hl+i) leží nějaké řešení. Další možností je nakreslit si graf funkce p(x) a intervaly s řešením upřesnit z grafu. Celý postup lze snadno předvést v jazyce R (lze volně stáhnout a nainstalovat), což je takové lepší offline kalkulačka a kreslička. Napíšeme v tomto prostředí za zobáček x < —seq(from = —6.5, to = 6.5, by = 0.5) Algebra 1 (MA 0003) 71 (a stiskneme ENTER ... vytvoří se vektor x našich hodnot ht), pak napíšeme p < — 2* x5+ 3* x4 — 7* x3+ 6* x2 — 11 * x + 5 (a stiskneme ENTER). V paměti se vypočte vektor funkčních hodnot, musíme jej ještě zobrazit na obrazovce, když např. napíšeme pouze písmenko označující proměnnou „p" a stiskneme ENTER. Tímto způsobem jsme odhalili, že kořeny leží v intervalech (—3,5;—3), (0,5; 1), (1; 1,5). Pokud máme jistotu, že krok 0,5 byl zvolen dostatečně jemně, takže na žádném z těchto tří intervalů se nevyskytuje více řešení současně (to bychom mohli zpřesnit třeba volbou 0,1), znamená to, že zbývající dvě řešení jsou komplexní (a díky větě „pokud a + ib je kořenem polynomu z (fž[x], +, •), tak nutně i a — íb je kořenem tohoto polynomu") víme, že tato řešení jsou komplexně sdružená čísla. Jiný způsob by zde spočíval v nakreslení grafu polynomu p(x), lze též v jazyce R zadáním posloupnosti bodů, které se vykreslí (ENTER po každém řádku): y < —seq(from = —3.5, to = 3.5, by = 0.01) pp < — 2 * y5 + 3 * y4 — 7 * y3 + 6 * y2 — 11 * y + 5 plot(y, pp) (obrázek lze „zvětšit" zadáním kratšího intervalu při definici vektoru y, například from = 0 a to = 1.5 nakreslí graf na sporném intervalu, na kterém existují dvě řešení). • C) Finální dopočtení kořenů: Do proměnné pol v prostředí R si nadefinujeme polynom, jehož funkční hodnoty jsme počítali, jako funkci, která vypočte polik) pro jakoukoli hodnotu k: pol < —function(z)return(2 * z5 + 3 * z4 — 7* z3+ 6* z2 — 11 * z + 5) a stiskneme ENTER. Poté zkusíme najít řešení rovnice na intervalu (—3, 5; —3) metodou půlení intervalu (vysvětlení viz BP (Trombiková, 2019, str. 28-30)). Celý algoritmus lze naprogramovat v R pomocí cyklu WHILE, například s tou přesností, že délka zkracujícího se intervalu bude menší než 0,00001: a < - -3.5 a ENTER (první minus je součástí přiřazovací šipky, druhé minus je součástí čísla), b < - - 3 a ENTER, a dále celý cyklus WHILE napíšeme na jeden řádek (v prostředí R to bude možné, zde v textu to vyjde na více řádků) a stiskneme ENTER: while(abs(a - b) > 0.00001) {*/ (pol((a + b)/2) * polib) < 0) {a < -{{a + b)/2);print{{a + b)/2)} else {b < -((a + b)/2);print((a + b)/2)}} 72 Katedra matematiky PedF MUNI v Brně (na obrazovku se nyní vypíše posloupnost středů intervalů blížících se k řešení, které zhruba s přesností na pět desetinných míst je z\ = —3,12991). Pokud celý postup (posloupnost tří kroků ukončených ENTER) zopakujeme pouze pro volbu a = 0,5, b = 1, najdeme řešení z2 = 0,56489. Toho lze dosáhnout velmi jednoduše, protože v prostředí R nemusíme už jednou napsané příkazy vypisovat znovu, ale volbou šipky nahoru se lze dostat na předchozí tři příkazy, ve kterých pozměníme pouze hodnoty a, b a celý cyklus while beze změny ještě jednou potom zobrazíme šipkou nahoru a stiskneme ENTER. Poslední reálné iracionální řešení pro a = 1, b = 1,5 najdeme podobně s přesností na pět desetinných míst z3 = 1,22892. Výhoda metody půlení intervalu (metody bisekce): vždy najde řešení, pokud na počátku algoritmu víme, že na daném intervalu existuje řešení právě jedno. Teoreticky (pokud bychom hledali tímto způsobem i kořeny racionální) by mohla po jistém počtu kroků nastat situace, že střed intervalu bude přesně roven hledanému řešení - to ovšem u hledání iracionálního řešení nemůže nastat, protože půlení racionálních čísel a, b a středů z nich vzniklých nelze dostat číslo iracionální, tato posloupnost středů intervalů se pouze bude limitně blížit k řešení. Metoda Newtonova = metoda tečen: obrázek a vysvětlení viz BP Trombiková, str. 34-38: zvolíme vhodně zq a počítáme posloupnost hodnot z±, z2, ■ ■ ■ užitím vzorce Výpočet v prostředí R: Navíc k definici funkce polik) z předchozího algoritmu, kterou máme stále v paměti prostředí nadefinovanou (a pokud jsme ukončili práci a při ukončování zvolili ANO na otázku, zda si má prostředí pamatovat uložená data, bude nadefinovaná i při opětovném spuštění prostředí R), budeme potřebovat ještě nadefinovat funkci pro výpočet derivace p'ix) našeho polynomu: der < — function{w){return{\Q * w4 + 12 * u>3 — 21 * w2 + 12 * w — 11)} (a ENTER). Nyní podobným cyklem WHILE najdeme všechna tři řešení jako u metody půlení, nicméně nyní pomocí metody Newtonovy: rozdíl je zde v tom, že místo intervalu se zadává pouze jediný vstupní bod z: zn+l PJZn) P'{zn)' z < - -3.5 a ENTER, a provedeme cyklus WHILE: while(abs(pol(zj) > 0.00001){z < -z pol(z) ; prínt(z)} der(z) Algebra 1 (MA 0003) 73 (a ENTER) ... po několika krocích bude nalezeno řešení z\ = —3,12991. Podobně pro vstupní z = —1 dostaneme z% = 1,22892 a pro vstupní z = 0,5 dostaneme z2 = 0,54689. Slabina Newtonovy metody: díky konstrukci pomocí tečny může postup zcela zhavarovat, směřovat do nekonečna nebo najít řešení, které už známe z jiného intevalu (jak se to stalo při volbě z = 1). Výhody Newtonovy metody ovšem jsou značné: a) najde řešení (pokud je tedy najde) mnohem rychleji než metoda půlení, b) najde i řešení komplexní!!!!!!!!!! Newtonově metodě (ani jazyku R) principiálně nevadí, když pracujeme s čísly komplexními. Jedinou podmínkou zde je, aby počáteční z bylo komplexní, nikoli reálné číslo - pro reálné vstupní z se totiž vzorec metody sám od sebe nikdy nedostane. Zkusme tedy najít zbývající řešení Z4, z5, které podle základní věty algebry víme, že musí existovat. Newtonovou metodou: — Volme vstupní z = 1 + li, najeďme šipkou na příkaz cyklu WHILE a stiskněme enter ... dospíváme k řešení z2 = 0,56489 ... to se tedy může stát, že volbou komplexního vstupního z celá posloupnost konstruovaných čísel konverguje k řešení reálnému. — Zkusme jiné vstupní z = 1 + 3í z našeho kruhu v komplexní rovině \z\ < 6,5: dojdeme k řešení Z4 = —0,07295 + i ■ 1,08773 s přesností na pět desetinných míst, a díky teoretické větě o komplexně sdružených kořenech už nemusíme dále počítat, stačí psát z5 = —0,07295 — i ■ 1,08773. • Našli jsme tedy podle numerických metod všechna řešení, která podle přesných algebraických postupů najít nelze - přesněji řečeno, nenašli jsme je zcela přesně, pouze s přesností na pět desetinných míst, to je ovšem přesnost dostatečná. • Celkem jednoduchou metodou lze najít komplexní řešení speciální rovnice, tzv. binomické rovnice, protože je v této rovnici pouze binom = dvojčlen: mocnina neznámé z a nějaké komplexní číslo. Tento poslední rychlý způsob pro tuto speciální rovnici se studenti naučí v následujících čtrnácti dnech, které budou věnovány komplexním číslům. 74 Katedra matematiky PedF MUNI v Brně 10 Týden 10 10.1 Cvičení 10: Komplexní čísla 01 Operace s komplexními čísly algebraický a goniometrický tvar komplexního čísla (argument a velikost komplexního čísla), geometrický význam násobení a dělení komplexních čísel. Lze postupovat podle nejnovější učebnice pro střední školy (Robova, Hála, Calda 2013), ale vše se asi nestihne, tj. cvičící rozhodnou, co přesně ve cvičeních 10 a 11 stihne probrat. 10.2 Přednáška 10: Konstrukce číselných oborů Peanova množina (= axiomy množiny N), konstrukce N —> Z, konstrukce Z —> Q, konstrukce Q —>■ R. 11 Týden 11 11.1 Cvičení 11: Komplexní čísla 02 n-tá mocnina a n-tá odmocnina z komplexního čísla, řešení binomických rovnic. 11.2 Přednáška 11: Konstrukce oboru C, o komplexních číslech 12 Týden 12 12.1 Cvičení 12: Prověrka-b na polynomy a komplexní čísla Algebra 1 (MA 0003) 75 12.2 Přednáška 12: Příprava a otázky ke zkoušce Otázka 01. Struktury s jednou binární operací a jejich vlastnosti. • Definice binární operace na množině. • Vyberte si příklad jedné konečné množiny s jednou operací, a jedné nekonečné množiny s jednou operací (prosím volte jiné operace než operace průniku, sjednocení, rozdílu, symetrického rozdílu ... množinové operace budou tématem otázky 02) - vypište vlastnosti těchto operací a řekněte, o jaké algebraické struktury se vzhledem k této operaci jedná. • Pokud je to možné či snadno proveditelné či to víte, zdůvodněte, proč vlastnosti platí: např. platí vlastnost neutrálního prvku, protože jím je ... ; platí vlastnost existence inverzí, protože například pro ... je inverzí ... Otázka 02. Množinové operace a jejich vlastnosti. Uvažujte strukturu 2A pro A = {1, 2, 3, 4, 5}, tj. množinu všech podmnožin množiny A. • Co za algebraickou strukturu (viz přednáška 6: struktury se dvěma operacemi) je (2A, -4-, n)? Uveďte u každé z operací neutrální prvek a příklad, že existuje-neexistuje inverzní prvek. • Jednotlivé vlastnosti těchto operací jsou vlastně vztahy mezi množinami. Dokažte některý z nich, ideálně například distributivní zákon (pomocí Vennových diagramů). • Obsahuje tato struktura nenulové dělitele nuly? Uveďte příklad. • Doplňující nedůležitá34 otázka: Operace průniku, sjednocení a symetrického rozdílu jsou tzv. binární operace. Znáte nějaký příklad unární množinové operace - do operace vstupuje jen jedna množina, nikoli dvě? Odpověď: příkladem unární operace je operace doplňku - doplněk vždy hledáme jen pro jednu množinu. Zajímavou vlastností jsou tzv. de Morganova pravidla (Základy mat., přednáška 4), která vyjadřují vztah mezi binární operací sjednocení-průniku a unární operací doplňku. Dokazují se jak jinak, pomocí Vennových diagramů. • Doplňující nedůležitá, ale zajímavá otázka: Mají operace průniku a sjednocení množin nějakou vlastnost, kterou nemají operace sčítání a násobení čísel? Odpověď: jednu zajímavost speciální pro sjednocení a průnik v kombinaci jsem říkal v přednášce číslo 6 (zaměnitelnost operací v distributivním zákonu). Ale existují i další vlastnosti např. samotného průniku či samotného sjednocení (tzv. idempotence35), nebo další vlastnosti interakce operací sjednocení a průniku (absorbce, modularita). Všechny se dokazují pomocí Vennových diagramů. 34Nedůležité otázky jsou zajímavé z hlediska matematiky, ale nerozhodnou o tom, zda zkoušku složíte nebo ne - věnujte se v prvé řadě otázkám, které jako nedůležité označeny nejsou; ty byste znát měli. Nedůležité otázky ovšem můžete dostat třeba u státnic, tj. je dobré se zamyslet nad odpovědí. 35Např. X2 = X U X = X, nebo X3 = X U X U X = X ... tj. vzhledem k operaci sjednocení neexistují mocniny, „umocňováním" dostaneme zase jen množinu X. Naprosto jiné než u čísel. 76 Katedra matematiky PedF MUNI v Brně Otázka 03: Pojem homomorfismu a jeho význam. • Uveďte definici homomorfismu mezi grupoidy. • Řekněte, jak se přirozeně (jak jsme si říkali na přednášce 03) definuje homomorfismus grupy (Z, +) do grupy (Zq, +). Tento homomorfismus není prostý, aleje surjektivním zobrazením. Co je pro pojem surjektivního homomorfismu charakteristické? Odpověď na část otázky: Surjektivní homomorfismus redukuje množinu Z na menší množinu Zq, na které některé vlastnosti zůstaly zachovány (např. zbytek po dělení číslem 6 je stejný u vzoru i obrazu tohoto zobrazení), kdežto některé vlastnosti zachovány nebyly (ztratila se nekonečnost množiny Z, např. všech nekonečně mnoho násobků čísla 6 se zredukovalo do jednoho prvku [0]). Tedy pokud chceme pracovat pouze se zbytky po dělení šesti, vlastně ve svém přemýšlení-vyjadřování provádíme fiktivní homomorfismus množiny celých čísel na množinu zbytků. • Co je charakteristické pro pojem injektivního homomorfismu? Odpověď: Pojem injektivního homomorfismu se objevuje například při konstrukci nebo koncepčním přechodu od množiny N na množinu Z. Formálně do množiny N „přidáváme" další prvky, a přitom ovšem chceme, aby dosavadní pojetí přirozených čísel (včetně výsledků operací sčítání a násobení) zůstalo zachováno. To přesně „kontroluje", dokazuje či „zaručuje" homomorfismus ifj : N —> N x N/^. Mluvíme o VNOŘENI množiny N do množiny N x N/^, která má více prvků (nekonečně mnoho dalších prvků) - ty jsou „modelem" nuly a záporných čísel. Tedy v tomto pohledu injektivní homomorfismus přesně matematicky ukazuje, že při přechodu od N k Z na ZS zachováváme dosavadní pojetí práce s čísly, pouze „rozšiřujeme" toto pojetí čísla na nadmnožinu Z. (podobnou argumentaci lze provést při rozšíření Z na Q) • Nějaké vlastnosti homomorfismu dokažte: — homomorfismus zobrazuje neutrální prvek na neutrální prvek, — homomorfismus „zachovává inverze" v tom smyslu, že prvky /(x-1) = (f(x))-\ — Ker(ip) je podgrupa grupy (G±, v) při homomorfismu grupy (G±, v) do grupy — Im(ip) je podgrupa grupy (G2,*) při homomorfismu grupy (G±, v) do grupy (G2,*). • U pojmu jádra homomorfismu se zkuste zamyslet nad příklady 24 a 26 na str. 58, nebo si přečtěte příklad 27 na str. 59 a jeho řešení na konci skript v oddílu 13.5. Algebra 1 (MA 0003) 77 Otázka 04: Pojem izomorfismu a jeho význam. • Definice izomorfismu mezi grupoidy36. • Jaký je význam izomorfismu? Odpověď: Izomorfismus i homomorfismus v algebře slouží pro porovnávání různých algebraických struktur - pokud mezi dvěma strukturami lze zavést homomorfismus nebo izomorfismus, popíšeme tím dosti velkou příbuznost těchto struktur, protože při homomorfismu i izomorfismu jsou zachovány výsledky dané operace. Izomorfismus (= bijekce zachovávající výsledky operace) nám představuje velmi silné algebraické tvrzení: operace na obou množinách vykazuje naprosto stejné vlastnosti. Například — izomorfismus zobrazí podgrupu na podgrupu o stejném počtu prvků. Srovnání s homomorfismem: Homomorfismus též zobrazí podgrupu na podgrupu, ale počet prvků se může redukovat - uvažujte například homomorfismus (Z$, +) na (^4,+). definovaný /01234567\ \01230123/ Podgrupa (2) := {0,2,4,6} grupy Z8 se zobrazí na podgrupu (2) := {0,2} grupy Z4. — izomorfismus zobrazí prvek řádu 3 na prvek řádu 3. Srovnání s homomorfismem: řád obrazu u homomorfismu může být nižší než řád vzoru - uvažujte například homomorfismus (Z$, +) na (Z4,+) (viz výše): řád prvku 2 v Z$ je roven čtyřem, řád obrazu 2 v Z4 je roven dvěma (řád obrazu u homomorfismu nemusí být stejný, ale je dělitelem řádu vzoru). — izomorfismus zobrazí cyklickou podgrupu na cyklickou podgrupu o stejném počtu prvků. Srovnání s homomorfismem, ad homomorfismus (Z$, +) na (Z4, +) (viz výše): Cyklická čtyřprvková podgrupa (2) grupy Zg se zobrazí na cyklickou dvouprvkovou podgrupu (2) grupy Z4. — atd. Tedy pokud přeznačíme prvky první struktury příslušnými prvky druhé struktury určenými izomorfismem, daná tabulka operace první struktury (pokud prvky v záhlaví tabulky napíšeme ve stejném pořadí) bude naprosto totožná jako tabulka operace druhé struktury. • Příklad: Rozhodněte, které z grup ({1, —1, i, —i}, •), (Z4, +), (Z2 x Z2, +) jsou mezi sebou izomorfní (= vykazují naprosto stejné vlastnosti dané operace, kromě toho, že se jedná o bijekci)a které ne. 36Grupoidy jsou struktury s nejmenším možným počtem podmínek (jedinou - uzavřeností operace na dané množině), mezi kterými lze homomorfismus nebo izomorfismus definovat. V realitě pak velmi často studujeme či popisujeme homomorfismus či izomorfismus grup, kde platí v každé struktuře už podmínky čtyři. 78 Katedra matematiky PedF MUNI v Brně • Další příklady, které by se mohly objevit: Str. 52, příklad 5.1, například N.4; str. 53, příklad 5.2, různé napříklady o izomorfismu. Otázka 05: Grupa permutací a Cayleyho věta • Vypište celou tabulku operace skládání permutací grupy 63. • Z tabulky vyčtěte základní informace o inverzních prvcích a podgrupách, neutrálním prvku. • Co říká Cayleyho věta? • Ilustrujte Cayleyho větu na konečné grupě (Z3, +) a nekonečné grupě (Z, +). • Mohl by se objevit např. příklad: Jakou osmiprvkovou podgrupu grupy (64, o) vygenerují cykly (1, 2, 3,4) a (1, 2) při operaci skládání permutací? Nápověda: nemusíte vypisovat celou tabulku operace, ale při vytváření tabulky operace se objevují různé prvky jako výsledky, tj. sestavit aspoň část této tabulky by vám pomohlo. Otázka 06: Dihedrální grupy D3 (grupa symetrií trojúhelníka), D'4 (grupa symetrií čtverce), D5 (grupa symetrií pětiúhelníku pravidelného), D$ (grupa symetrií šestiúhelníka pravidelného) a Lagrangeova věta. • Vysvětlete prvky těchto grup geometricky i v jejich algebraickém tvaru. • Zkonstruujte tabulky operace skládání zobrazení v těchto grupách, nebo v některých podgrupách. • Co je tvrzením Lagrangeovy věty? • Vypište na základě geometrického významu i Lagrangeovy věty všechny podgrupy těchto grup. • Určete množinu generátorů dané grupy. • Mohl by se třeba objevit příklad 25 ze str. 58. Otázka 07: Struktury se dvěma operacemi. Viz přednáška 6: • Definujte okruh; uveďte příklad okruhu zbytkových tříd, který není oborem integrity, včetně vysvětlení a příkladu nenulových dělitelů nuly. • Definujte obor integrity; uveďte příklad a) okruhu zbytkových tříd, který je oborem integrity; b) oboru integrity, který není tělesem. Algebra 1 (MA 0003) 79 • Definujte těleso; uveďte příklad a) konečného, b) nekonečného tělesa. • Dokážte větičku: Každý konečný obor integrity je už automaticky tělesem (důkaz viz video 12). • Dokažte větičku (důkaz lépe viz video 12): V okruhu platí: Daný okruh (M, +, •) je obor integrity právě tehdy, když v něm platí vlastnost krácení (7*) pro okruhy: Otázka 08: Polynomické rovnice — algebraické metody řešení. Viz přednáška 7 a kousek předn 8. U zkoušky z algebry 1 tato otázka nebude, ale bude opět u bakalářských zkoušek na konci třetího ročníku. • Co je to množina všech polynomů (R[x],+,-) s reálnými koeficienty, s operacemi sčítání a násobení, z algebraického hlediska? • Co je to polynom stupně n, vedoucí koeficient polynomu, kořen polynomu, násobnost kořene? Co říká základní věta algebry? • Co říká věta o racionálních kořenech polynomu a jak je lze určit pomocí Hornerova schématu? • Co říká „věta o odstranění násobných kořenů polynomu"? Popište postup, příklad uvádět nemusíte (přednáška 8, oddíl B). • Co je zajímavé na komplexních kořenech polynomu z R[x\l Odpověď: věta z oddílu C přednášky 8. Otázka 09: Polynomické rovnice — numerické metody řešení. Viz přednáška číslo 8, nebo i ve skriptech cvičení číslo 9. • Jak lze zhruba vymezit všechny kořeny polynomu? Odpověď: Oddíly A ze cvičení 9 v tomto textu. • Jak lze zhruba najít interval, na kterém existuje reálné řešení polynomu, který jsme zbavili násobných kořenů37? Odpověď: oddíl B ze cvičení 9 v tomto textu. 37Tento předpoklad jsem v přednášce 8 nezmínil a je důležitý: Kdybychom totiž zkoumali polynom p(x), aniž bychom snížili stupeň polynomu při vícenásobných kořenech postupem popsaným na přednášce, mohlo by dojít k situaci, že některé reálné kořeny mají násobnost 2 nebo 4 atd. zkrátka násobnost sudou. Při zkoumání grafu funkce p(x) pak neplatí skutečnost, že by funkce přecházela v bodě kořene se sudou násobností ze záporných funkčních hodnot na kladné (nebo z kladných funkčních hodnot na záporné), nýbrž graf funkce p(x) se v blízkosti kořene blíží k ose x, v bodě kořene x^ se jí dotkne a „odrazí se na tutéž stranu", tj. např. p(x) < 0 pro x < Xk, pak p(xk) = 0, ale pak p(x) < 0 nastane i pro x > Xk, tj. 80 Katedra matematiky PedF MUNI v Brně • Popište na příkladu, jak upřesníme iracionální kořen polynomu získaný z oddílu F, pomocí metody půlení intervalu a metody Newtonovy. Najděte řešení rovnice x5 —x2 — 1 = 0 na intervalu (1; 2) oběma těmito numerickými metodami ... proveďte tři kroky u každé z metod. Je možné, že u zkoušky zde bude jiná rovnice, například rovnice 2x3 + 5x — 1 = 0, a interval délky 1, který obsahuje řešení, budete muset sami najít. Otázka 10: Peanova množina P, množina N přirozených čísel. Viz předn. 9. • Peanovy axiomy, • vztah množin P a N, • definice uspořádání na P, • Z Peanových axiomů lze tedy zkostruovat algebraickou strukturu (P0,+,-), resp. (iVo,+, •)• Celý tento postup jsme si vlastně neříkali (ještě zbývá definovat operace sčítání a násobení na Peanově množině a dokázat, že splňují běžné vlastnosti), uveďte pouze pojem, který strukturu (Nq, +, •) vystihuje. Otázka 11: Algebraický popis, jak z N zkonstruujeme Z. Viz přednáška 9, odkazy jsou vzhledem ke skenu přípravy. • Popište konstrukci intuitivně (viz předn. 9, strana 3, oddíl (a)) a řekněte, jaké jsou algebraické vlastnosti výsledku (Z, +, •). • Popište konstrukci přesně algebraicky - minimálně poslední strana z přednášky 9, mohl by stačit i dobře okomentovaný obrázek z té poslední strany (když se naučíte celou stranu, to je vlastně komentář k obrázku)38. Otázka 12: Algebraický popis, jak ze Z zkonstruujeme Q neplatí, že by funkční hodnoty p(x) při průchodu proměnné x bodem x^ měnily znaménko. To znamená, že postupné počítání funkčních hodnot z intervalu (— r;r) takový kořen neodhalí. Tomuto problému se vyhneme, když provedeme postup odstranění násobných kořenů polynomu. Potom při výpočtu funkčních hodnot v intervalu (—r;r) s dostatečně malým krokem odhalíme už všechny iracionální jednonásobné kořeny pomocí na přednášce popsané změny znaménka funkční hodnoty při procházení tohoto kořene. 38Poznámka k bodu (iii) této konstrukce: Faktormnožinu jsme mockrát nevytvářeli, ale jedná se o proces analogický vytvoření struktury zbytkových tříd, například Z$ - přitom jsme také rozdělili množinu na podmnožiny a definovali sčítání a násobení mezi těmito podmnožinami pomocí tzv. „reprezentantů" z těchto podmnožin, tj. jakýchkoli prvků z nich vybraných. Přesně stejný proces zde děláme, ale nikoli tedy s množinou Z, ale s množinou N x N - rozdělíme ji na podmnožiny, každá z podmnožin má nekonečně mnoho prvků, definujeme pak v kroku (iv) sčítání mezi těmito podmnožinami pomocí libovolných reprezentantů z podmnožin vybraných, a výsledkem sčítání není jen jedna uspořádaná dvojice, ale zase jedna celá podmnožina, která součet těch dvou vybraných reprezentantů obsahuje. Algebra 1 (MA 0003) 81 • Popište konstrukci intuitivně (viz předn. 9, strana 3, oddíl (b) vzhledem ke skenu přípravy) a řekněte, jaké jsou algebraické vlastnosti výsledku (Q, +, •). • Popište konstrukci přesně algebraicky - minimálně první strana z přednášky 10, mohl by stačit i dobře okomentovaný obrázek z této strany (doporučuji se kroky a,b,c,d též naučit). Otázka 13: Algebraický popis, jak z Q zkonstruujeme R pomocí řezů množiny Q. Otázka 14: Algebraický popis, jak z R zkonstruujeme C. Informace ke zkoušce v předmětu Algebra 1 v roce 2021: u zkoušky dostanete čtyři z předchozích otázek nebo jejich části, asi v následujícím složení: 1. jednu z otázek 1,2,7 ... základní definice vlastností operace, algebraických struktur; 2. jednu z otázek 3,4,5,6 ... něco o homomorfismu, izomorfismu, grupě permutací Sn nebo dihedrální grupě Dn; 3. otázku 8 nedostanete, ta byla prozkoušena na cvičení; ale všichni dostanete otázku 9, tj. přineste si kalkulačku a pro zadanou rovnici a interval a) najdete interval délky 1 obsahující řešení, b) zpřesníte řešení metodou půlení, c) zpřesníte řešení metodou Newtonovou; 4. jednu z otázek 10 až 14 nebo jejich části. 82 Katedra matematiky PedF MUNI v Brně 13 Výsledky některých příkladů 13.1 Výsledky ke cvičení 1.1 — zatím žádné nejsou uvedeny 13.2 Výsledky ke cvičení 1.2 — Určování vlastností různých operací Ad úloha 1.3: a) (N, +) je komutativní pologrupa. 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. □ b) (Z, +) je komutativní grupa. c) (Z,-) je komutativní monoid. 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 |, ale to není celé číslo, inverzí k 3 je |, ale | ^ Z, atd. □ d) (Q, •), (iž, •) jsou komutativní monoidy. Opravdu, přece jen chybí ještě jeden inverzní prvek vzhledem k operaci násobení, 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í. □ e) (Q ~ {0}i ')) (-^ ~~ {0}'') Jsou komutativní grupy. Někdy též značíme Q*:=Q-{0}, R*:=R-{0}, tj- [Q*i')) C^*)') Jsou komutativní grupy. f) ,g) (2A,U), (2A, n) jsou komutativní monoidy. 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 U a n nezáleží na uzávorkování - platí (2). Jednotkovým prvkem vzhledem ke sjednocení je 0, 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} U X = 0, a to neexistuje. h) (Z,—) je jen grupoid, protože operace MINUS není asociativní, tj. záleží na uzávorkování; (Z,:) není ani grupoid, protože výsledek dělení řady celých čísel není celé číslo. Algebra 1 (MA 0003) 83 i) (M,+), kde M = {-100,-99,-98,...,-1, 0,1, 2,..., 99,100} není ani grupoid, protože součtem některých dvojic dostaneme číslo, které neleží v množině M. 13.3 Výsledky ke cvičení 3.1 — Vlastnosti grup, podgrupy a generátory grupy Ad úloha 3.3 - F.2: Na jednom řádku operace v grupě nemohou být stejné dva prvky, protože v grupě platí zákon o krácení (7). Sporem: Na jednom řádku se vyskytují různé X\ a x2. Rovnici a*xi=y = a*x2 vynásobíme prvkem A-1 zleva a dostaneme po využití vlastnosti (3) na obou stranách rovnosti dostaneme x\ = x2, což je spor s tím, že x\ a x2 jsou různé prvky. Ad F.3: Tabulku lze doplnit na: e a b e e a b a a b e b b e a Ad úloha 3.6 - A.l: H je podgrupou grupy G, protože (1) součet logaritmuje logaritmus součinu a součin kladných hodnot je zase kladná hodnota, tj. H je uzavřená vzhledem k součtu. Dále je neprázdná, obsahuje např. prvek log 1, což je neutrální prvek vzhledem ke sčítání (platí (3)). Asociativita se sveze z asociativity grupy (R, +), platí (2). A nakonec inverzní prvek k prvku loga je prvek log ^, protože platí (4): pro každé loga G H log a + log - = log 1 = 0. a Ad A.5:ano, jedná se o podgrupu, prvky grupy jsou body na přímce procházející počátkem, operace sčítání těchto prvků (funguje stejně jako operace sčítání vektorů s počátečním bodem v počátku a koncovým bodem v daném prvku) splňuje vlastnosti (1), (4 ... inverzní prvek k prvku (x, 2x) je prvek (—x, —2x), který opět leží na dané přímce) a množina je jasně neprázdná. Ad D.5: Pokud dané součiny jsou navzájem různé prvky (to plyne mimo jiné z úlohy F.2 z minulého cvičení, že na jednom řádku operace grupy nemohou být stejné prvky), jeden z těchto součinů musí být roven neutrálnímu prvku n, tj. nechť například aj*a; = n, pak podle věty 4 platí a"1 = a;, našli jsme inverzi k prvku al5 platí vlastnost (4). Ad úloha 3.7 - ad N.l: H = {6,12,2,8,14,4,10,0} a prvky jsou napsány v tom pořadí, jak je získáváme užitím prvku 6. Ad E.l: podgrupy jsou čtyři: a) celá Hio generovaná prvkem 1 nebo prvkem 3 nebo prvkem 7 nebo prvkem 9; 84 Katedra matematiky PedF MUNI v Brně b) druhá triviálni podgrupa ({0}, +) generovaná prvkem 0; c) podgrupa ({0, 2,4, 6, 8}, +) generovaná prvkem 2 nebo prvkem 4 nebo prvkem 6 nebo prvkem 8; d) podgrupa ({0, 5}, +) generovaná prvkem 5; Ad E.3: < 6, 9 >= {6, 0, 9, 3} vzhledem k operaci skládání otáčení. Ad E.7 modifikace: prvek [1,1] je generátorem podgrupy {[1; 1; ], [0; 2], [1; 3], [0; 0]} vzhledem ke sčítání. Ad E.6: ano, prvek [1,1] je generátorem celé grupy vzhledem ke sčítání. Grupa má šest prvků a výsledek lze vyčíst z tabulky operace v této grupě. 13.4 Výsledky ke cvičení 4.1 — nekomutativní grupy Ad úloha 4.1: Podle definice skládání zobrazení platí PoR2 = PoRoR = f 1 2 3 4 5 6 7^ l l l l l l i 7 1 6 3 4 2 5 l l l l l l l 5 7 2 6 3 1 4 l l l l l l l \6 7 3 2 1 5 4 y i 2 3 4 5 6 7 i l l l l l 6 7 3 2 1 5 4 Ad úloha 4.3: Zde je jen výsledek k první části příkladu, a sice tabulka operace o na množině D% symetrií trojúhelníku: Tabulka 13.7: Tabulka operace o na množině D% symetrií trojúhelníku. o Rq Ri R2 R3 R4 R5 Rq Rq Ri R2 R3 R4 R5 Ri Ri R2 Rq R5 R3 R4 R2 R2 Rq Ri R4 R5 R3 R3 R3 R4 R5 Rq Ri R2 R4 R4 R5 R3 R2 Rq Ri R5 R5 R3 R4 Ri R2 Rq Pokud tuto tabulku porovnáme s tabulkou grupy (63, o) v příkladu 4 je vidět, že mezi oběma grupami existuje izomorfismus, tj. příslušné tabulky operace se liší pouze Algebra 1 (MA 0003) 85 přeznačením prvků: f (e) = Rq, f (s) = Ri, f (t) = R2, f (u) = R%, f (v) = r4, f (vo) = R5 (toto izomorfní přiřazení je vidět i na obrázku 1.1). Aby zobrazení / bylo izomorfismem, musíme z tabulky operace první grupy dostat přeznačením prvků vzhledem k zobrazení / přesně tutéž tabulku vzhledem k operaci v druhé grupě. 13.5 Výsledky ke cvičení 5.1 — řád prvku, cyklické grupy, grupy zbytkových tříd ad Cvičení 5.1. Například N.4: a i /3 vyjádříme jako součin navzájem nezávislých cyklů: a = (1,2) o (3,4,5), /3 = (1,6, 7,2,5). Pak lze cykly zvlášť umocnit a spojit: a3 = (1,2) o id = (1,2), /34 = (1,5,2 , 7, 6)39. Spočteme „součin" a rozložíme na dílčí „součin" navzájem nezávislých cyklů: a3 o /34 = (1,5) o (2, 7, 6). Při umocnění na pátou nyní opět umocníme každý cyklus zvlášť: (a3o/34)5 = (l,5)o(2,6,7). Rád cyklu (1, 5) je 2, řád cyklu (2, 6, 7) je 3, a tedy řád jejich složení je nejmenší společný násobek dílčích řádů, tedy 6. Následují některé výsledky příkladů z přednášky ?? o homomorfismu a Lagrangeově větě: Ad příklad 27 Ad Například F.l: Rád obrazu je dělitelem řádu vzoru. Lze i celkem jednoduše dokázat: Sporem ... předpokládejme, že prvek a řádu k se zobrazí na prvek řádu Z, kde Z není dělitelem k, tj. k = l ■ q + m, kde 0 < m < Z. Označme ještě e\ neutrální prvek v grupě G\ = (G, \/), e2 je neutrální prvek v grupě G2 = (H, *). Celkem máme e2 = 0, 1 —> 1 ... podle podmínky homomorfismu nyní dopočteme, že musí nastat 2 = 1 + 1-^ 0, 5 —> 3, 6 —> 2, 7 —> 1. Jádrem je množina {0,4} grupy Zg. Ad Například N.2: (Zq, ©) sestává z prvků: (operací „umocňování" je sčítání prvků) [0] je řádu 1, [1] je řádu 9, [2] je řádu 9, [3] je řádu 3, [4] je řádu 9, [5] je řádu 9, [6] je řádu 3, [7] je řádu 9, Pinter2010 je řádu 9. Dále (6*3,0) sestává z prvků (ve zkráceném zápisu pomocí disjunktních cyklů): id je řádu 1, (1, 2, 3) je řádu 3, (1, 3, 2) je řádu 3, (1, 2) je řádu 2, (1, 3) je řádu 2, (2, 3) je řádu 2. Pojďme ke hledání všech různých homomorfismu: neutrální prvek se musí vždy zobrazit na neutrální prvek - tedy [0] se zobrazí na id. Vzhledem k předchozímu příkladu N.l řád obrazu musí být dělitelem řádu vzoru, tj. žádný z dalších prvků 58du tři nebo devět se nemůže zobrazit na dvouprvkové cykly (1, 2), (1, 3) nebo (2, 3), protože ty jsou řádu 2. Dále si všimněme, že grupa Zg má řadu prvků řádu devět, je tedy cyklická, tj. stačí zobrazit jeden z generátorů celé grupy, například prvek [1], a všechny obrazy ostatních prvků jsou už jednoznačně určeny z podmínky homomorfismu (podmínky zachování výsledku operace. Díky těmto faktům lze dospět ke třem různým homomorfismům: hom 01: 2([3]) = ^2([2] + [l]) = (l,2,3)o(l,3,2) = id; y2([4]) = ^2([3] + [l]) = ido(l,3,2) = (l,3,2); ¥>2([5]) = ^2([4] + [l]) = (l,3,2)o(l,3,2) = (l,2,3); atd. Je vidět, že jádrem homomorfismu jsou prvky id, [3], [6], protože ty se zobrazí na neutrální prvek druhé grupy hom 03: y?3([0]) =id, ^([l]) =id, a nyní už ^3([2]) = ^([l] + [l]) = idoid = id;