Algebra 1 (MA-0003) verze leden 2020 Břetislav Fajmon OBSAH 1 Obsah 1 Týden 01: Axiomy operací, vlastnosti (1) až (5) 4 1.1 Cvičení 1: Vlastnosti číselných operací.................... 4 1.2 Cvičení 2: Určování vlastností různých operací................ 7 1.3 Přednáška 1: Další vlastnosti grup, podgrupy, generátory podgrupy .... 8 2 Týden 02 přednáška 02 nekomutativní grupy 17 3 Týden 03 25 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy ......... 25 3.2 Přednáška 3: Izomorfismus, Calyeho věta................... 29 4 Týden 04 35 4.1 Cvičení 04: Nekomutativní grupy....................... 35 4.2 Přednáška 04: Lagrangeova věta, homomorfismus grup ........... 37 5 Týden 05 50 5.1 Cvičení 05: Rád prvku, cyklické grupy, grupy zbytkových tříd ....... 50 5.2 Přednáška 5: Faktorgrupa........................... 60 6 Týden 06 67 6.1 Cvičení 06: prověrka-a z toho, co se probralo................. 67 6.2 Přednáška 06: struktury se dvěma operacemi................. 68 7 Týden 07 73 7.1 Cvičení 07: Polynomy 01............................ 73 7.2 Přednáška 07: Struktury se dvěma operacemi II............... 74 8 Týden 08 75 8.1 Cvičení 08: Polynomy 02............................ 75 8.2 Přednáška 08: Přehled algebraických metod hledání kořene polynomu ... 76 9 Týden 09 77 9.1 Cvičení 09: Polynomy 03............................ 77 9.2 Přednáška 09: Přehled numerických metod hledání kořene polynomu .... 81 10 Týden 10 82 10.1 Cvičení 10: Komplexní čísla 01......................... 82 10.2 Přednáška 10: Vektorové prostory, stupeň rozšíření těles........... 83 11 Týden 11 84 11.1 Cvičení 11: Komplexní čísla 02......................... 84 11.2 Přednáška 11: Galoisova teorie - pokus o začátek přehledu......... 85 12 Týden 12 86 12.1 Cvičení 12: Prověrka-b na polynomy a komplexní čísla ........... 86 12.2 Přednáška 12: Galoisova teorie - pokus o hlavní krok............ 87 2 OBSAH 13 Výsledky některých příkladů 88 13.1 Výsledky ke cvičení 1.2 - Určování vlastností různých operací....... 88 13.2 Výsledky ke cvičení 3.1 - Vlastnosti grup, podgrupy a generátory grupy . . 89 13.3 Výsledky ke cvičení 4.1 - nekomutativní grupy................ 90 13.4 Výsledky k přednášce 4.2 - Lagrangeova věta, homomorfismus grup .... 90 13.5 Výsledky ke cvičení 5.1 - řád prvku, cyklické grupy, grupy zbytkových tříd 92 OBSAH 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 ZŠ. 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 [8], 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 knihu [8] 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 není zatím čas tato skripta upravit, ovšem pro část „polynomy" použijeme text kolegyně dr. Budínové, pro část „komplexní čísla" středoškolskou učebnici (Robova, Hála, Calda 2013). Aktuálně letos je přednáška rozvržena uprostřed různých skupin cvičení, což působí problémy, protože bych rád, aby první přednáška a první cvičení navázalo. Díky těmto obstrukcím je v textu první týden navržen do dvou cvičení, a pak na přednášku naváže cvičení až třetí týden. Břetislav Fajmon, verze textu leden 2020 4 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) 1 Týden 01: Axiomy operací, vlastnosti (1) až (5) 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) možná 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,yeM: x*yeM. (1) Vlastnost (1) je přirozená - chceme, aby operace na množině byly definované takovým způsobem, aby výsledek operace zase byl prvkem dané množiny. Vlastnost (2) Asociativita operace *: \/x, y, z E M : (x * y) * z = x * (y * z). (2) Vlastnost (2) platí pro většinu operací, o kterých bude za chvíli řeč - jednoduše řečeno, několikanásobné použití jedné operace nezávisí na uzávorkování. Snad jen operace — a : nejsou asociativní. Vlastnost (3) Existence jednotkového prvku vzhledem k operaci *: 3e E M : x * e = e * x = x \/x E M. (3) Příklad pro vlastnost (3): jednotkový prvek vzhledem k operaci sčítání je 0 (někdy nazýván též nulový prvek, aby nedošlo k záměně s prvkem 1), jednotkový prvek vzhledem k operaci násobení je 1. 1.1 CVIČENÍ 1: VLASTNOSTI ČÍSELNÝCH OPERACÍ 5 Vlastnost (4) Existence inverzních prvků vzhledem k operaci *: \/x G M 3 x'1 e M : x* x'1 = x'1 * x = e. (4) Příklad pro vlastnost (4): Pro číslo 2 je inverzním prvkem vzhledem k operaci sčítání číslo —2, vzhledem k operaci násobení číslo |. Uveďme nyní základní definice některých struktur, které splňují dané vlastnosti: • Definice 1.1. Grupoid (M, *) ... množina M, na které operace * splňuje vlastnost (i); • Definice 1.2. Pologrupa (M, *) ... množina M, na které operace * splňuje vlastnosti (i),(2); • Definice 1.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 1.4. Grupa (M, *)... množina M s operací *, která splňuje na množině M vlastnosti (1), (2), (3), (4). Kromě těchto čtyř základních struktur, které byly právě definovány, ještě řada operací splňuje vlastnost (5) - viz následující definice. Tato vlastnost (5) už do samotné definice stěžejního pojmu grupy není zahrnuta, protože jak uvidíme v následujících dvou kapitolách, existují význačné příklady grup, které ji nesplňují. Proto slovo „komutativní" musíme k právě definovaným strukturám zvlášť dodat jako novou vlastnost. • Vlastnost (5) Operace * se nazývá komutativní na množině M, pokud platí vlastnost (5): \/x,y G M : x * y = y * x. (5) • Definice 1.5. (M, *) se nazývá komutativní grupoid, pokud je grupoid a operace * splňuje vlastnost (5), tj. je komutativní na množině M. • Definice 1.6. (M, *) se nazývá komutativní pologrupa, pokud je pologrupa a operace * splňuje vlastnost (5), tj. je komutativní na množině M. se nazývá komutativní monoid, pokud je monoid (tj. pokud je pologrupa s jednotkou) a operace * splňuje vlastnost (5), tj. je komutativní na množině M. • Definice 1.8. (M,*) se nazývá 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 G M : x ■ (y + z) = x ■ y + x ■ z, (y + z) ■ x = y ■ x + z ■ x. (6) 6 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) 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 *ayje V x,y, z (-R, •)• e) (Q-{0},.), (Ä-{0},-). f) (2A, U), kde A = {a, b, c, d, e} je pětiprvková množina. g) (2A, Pi), 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}. Cvičení 2.2. 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). Cvičení 2.3. a) Uveďte definici vlastnosti (4) pro operaci y na množině M ve stručném matematickém zápisu. b) Uveďte příklad struktury (M, y), která splňuje vlastnost (4). c) Uveďte příklad struktury (M, y), která NEsplňuje vlastnost (4). Cvičení 2.4. Dokažte, že množina všech podmnožin tříprvkové množiny s operací symetrického rozdílu 4- je grupa (viz [8], str. 30, oddíl C). Výsledky některých cvičení najdete v závěru textu v oddílu 13.1. 8 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) 1.3 Přednáška 1: Další vlastnosti grup, podgrupy, generátory podgrupy 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 y; • 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 Zel x. abychom dostali výrok pravdivý či nepravdivý. • Řešit rovnici s neznámou x na množině M znamená najít obor pravdivosti K3 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 (N, +))!! Nebo rovnice 7-x = 2 nemá řešení na množině celých čísel (tj. na monoidu (Z, •)). Tj. vidíme, že už na mo-noidech (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, +, •)). 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 ve druhé části textu (kap. 7 až 12). 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 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. 1.3 PŘEDNÁŠKA 1: DALŠÍ VLASTNOSTI GRUP, PODGRUPY, GENERÁTORY PODGRUPY 9 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.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): 0 Čí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°; • 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é úhly 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ě 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. 10 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) 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 Hs je konečná množina, lze si výsledky operace + napsat do tabulky: Tabulka 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 Danou tabulku operace * konstruujeme tak, že na průsečíku řádku prvku x a sloupce prvku y se vyskytuje výsledek operace x * y: * 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, vlastnosti (1), (2), (3), (4) 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. 1.3 PŘEDNÁŠKA 1: DALŠÍ VLASTNOSTI GRUP, PODGRUPY, GENERÁTORY PODGRUPY 11 operace + na Množině H§ lze všechny z této )tabulky vyčíst (viz výklad ... elicit from 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ů. 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ů?6 (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 n2 takové, že n\ ^ n2. Jaké z toho plynou vlastnosti těchto dvou prvků? Klíčová myšlenka: pokud je prvek neutrální, tak nemění výsledek operace y vuci 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 rii, n2'T: (3)2 (3)i ni = n1\/n2 = n2, což je spor s tím, že oba neutrální prvky jsou navzájem různé8.□ 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 y ~~ 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ě? (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. Důkaz: Předpokládejme opět, že k nějakému prvku a E G vykazují dva prvky ajf1, a2 1 vlastnost inverze, tj. platí a y a^1 = n, A a^1 y a = n 6Ví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? 7Vlastnost (3)i znamená, že využíváme vlastnosti (3) pro prvek ni, vlastnost (3)2 platí pro neutrální prvek ri2. 8Celý důkaz je možné formulovat i jako přímý důkaz typu 2: předpokládáme, že prvky n±, n2 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. 12 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) (musí platit oba vztahy, protože o operaci y zatím nevíme, zdaje komutativní) a současně Klíčová myšlenka: vynásobením9 a11 y a2 1 pravděpodobně nic nezískáme. Prvky a11, a2 1 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 \ _l (2) _i , _n (4)2 _i (3) _± a2 == n y a2 = = \ai V a) V a2 = ai V (a V a2 ) = ai V n = ai ■ 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 a^1 a a^1 musí nutně být stejné. Důkaz je hotov - inverzní prvek k prvku a existuje v grupě právě jeden.□ (můžeme „krátit"10 v rovnostech, ve kterých se vyskytují prvky grupy G a operace y?) V každé grupě (G, v) platí zákony o krácení (7), tj. Va, b,c E G : (a\jb = a\jc^>b = c) A (b\ja = c\ja^b = c). Důkaz: Provedeme například pro první z implikací: Vztah a y b = a y 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 y a V b = a1 • a V c) a s využitím asociativity (2) (v grupě nezáleží na uzávorkování „součinu" tří prvků vzhledem k operaci y), 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).D Věta 4. (o vzájemně inverzních prvích) V každé grupě (G, y) z rovnosti a\j b = n (kde n je neutrální prvek) plyne, že platí a -i b, a současně b 1 (tedy prvek b je inverzní k prvku a, a současně prvek a je inverzním prvkem k prvku b). 9Vš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ů ... 10Opět terminologie: i když mluvíme obecně o operaci V, 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í. 1.3 PŘEDNÁŠKA 1: DALŠÍ VLASTNOSTI GRUP, PODGRUPY, GENERÁTORY PODGRUPY 13 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 y b = n prvkem a-1 zleva, dostaneme -1 l -1 (3) -1 ď V a V b = a x/ n = a , po aplikaci vlastnosti (4) na první výraz dostaneme b = a~ľ.O Věta 5. (o výpočtech inverzních prvků) V každé grupě (G, y) platí: i) (ay&)_1 = b~ľ Va_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 oyřia b~ľ y a 1; a y 6 y (6 1 y a X) — a V (P V b x) V a 1 — a V n V a 1 — a V a 1 — n. Protože nevíme, zda operace y Je komutativní, měli bychom ověřit i druhý za zákonů (4), tj. upravovat výraz (6_1 Va_1) V a V b analogickým způsobem se v něm „vyruší" nejprve a-1 y a? a pakfe-1 y b a dostaneme opět pouze n. ad ii) Z rovnosti a y cT1 = n a, věty 4 o vzájemné inverzi máme (a-1)-1 = a.O Definice 1.9. 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 (viz týden 05). 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 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 (6 y c y d), postupným užitím vlastnosti (2) pro tři prvky dostaneme a y (b y c) y d = a y b y (c y d) = (a y b) y (c y d) = (a y b) y c y 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 věty 5a): (ai y a2 y • • • y afc)_1 == ak 1 y ak\ y • • • y a2 1 y a^1. 14 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) Dále pro nás bude užitečná například definici n-té mocniny vzhledem k operaci y; Definice 1.10. n-tá mocnina prvku a grupy (G, y) se definuje jako prvek získaný v řetězci operací an := a y a y • • • y a . 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 1.11. n-tá odmocnina prvku a grupy (G,y) je takový prvek x E G (pokud tedy existuje), že a = xn. Definice 1.12. zápornou odmocninu a~5 grupy (G, y) definujeme jako pátou mocninu jejího inverzního prvku, tj. a~5 := (a-1)5. 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 1.13. 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é11 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 (1), (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): nVe 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. 1.3 PŘEDNÁŠKA 1: DALŠÍ VLASTNOSTI GRUP, PODGRUPY, GENERÁTORY PODGRUPY 15 Díky tomu, že S je neprázdná, obsahuje aspoň jeden prvek, označme jej a. s- o íi) -1 ^ o íl) ,—, -1 o a G b =>• a GD4flVfl = n G o, tedy neutrální prvek n patří i do množiny S* a pro (S, v) platí (3).D Příklad 1.2. • Podmnožina S* = {...,—4,-2,0,2,4,...} všech sudých celých čísel je podgrupou grupy (Z, +): opravdu, je neprázdná, uzavřená vzhledem ke sčítání ((1) ... součtem dvou sudých celých čísel je opět sudé celé číslo) a obsahuje všechny inverze ((4) ... nula je inverzí sama k sobě vzhledem ke sčítání, inverzí čísla 2 vzhledem ke sčítání je číslo —2, atd.). • Podmnožina Q* ( označení 01 ) 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á. Jedna z aplikací pojmu podgrupa je v tom, když dokazujeme o nějaké neprázdné množině, že je grupa: pokud víme, že tato množina S je podmnožinou množiny G, o které víme, že je grupa, stačí nám ukázat platnost (1) a (4) na množině S a jsme s důkazem, že S je grupa vzhledem k téže operaci, hotovi. Příklad 1.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í. Zřejmě tato množina je grupa, protože součtem dvou funkcí je zase funkce (platí (1)), toto sčítání funkcí je asociativní (platí (2)), existuje nulová funkce jako neutrální prvek (platí (3)), ke každé funkci f(x) existuje její inverze — f(x), takže součet obou těchto funkcí je nulová funkce. Na základě věty 6 nyní snadno uzavřeme, že neprázdná množina C{R) všech spojitých funkcí je grupa vzhledem ke sčítání funkcí, protože je neprázdnou podmnožinou grupy (F(R),+), splňuje vlastnosti (1) i (4) (součtem dvou spojitých funkcí je spojitá funkce, inverzí ke spojité funkci f(x) je spojitá —f(x). Podobně neprázdná množina všech diferencovatelných funkcí D(R), tedy funkcí, které mají derivaci v každém bodě, je podmnožinou grupy (F(R), +) a splňuje (1) i (4) z podobných důvodů jako C(R), je tedy grupou vzhledem ke sčítání funkcí. Definice 1.14. Triviální podgrupy (= nevlastní podgrupy) grupy (G, v) se nazývají dvě podgrupy: a) S± = {n} je podgrupou vzhledem k y? 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)- 16 1 TÝDEN 01: AXIOMY OPERACÍ, VLASTNOSTI (1) AŽ (5) 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í12, 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 y b y a y c-1 nebo c-1 y aT1 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 b~ľ y a y c je prvek ay&yaycy&^yayc. Dále jsou prvky tohoto typu uzavřené vzhledem k inverzi, tj. k prvku a y b~ľ 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 aT1 y c y b y aT1 (tedy platí i (4)). Dokázali jsme celkem, že množina prvků tohoto typu tvoří podgrupu grupy (G, y). Nazývá se ( definice 1.15 ) podgrupa grupy G generovaná množinou S a označujeme j i ( označení 02 ) < S >. Prvky množiny S nazýváme generátory podgrupy < S >. A ještě jedna definice, která s tí souvisí ( definice 1.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. Grupa (i?6)+) 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 sy a 1 = n. 17 2 Týden 02 — přednáška 02 — nekomutativní grupy Příklad 2.1. Grupy netvoří jen číselné množiny a operace na nich. Zajímavým příkladem grupy je množina FI(R) všech funkcí z R do R, ke kterým existuje inverzní funkce, společně s operací o = „po", neboli operací skládání zobrazení. Při tomto vymezení množiny a operace na ní je struktura (FI(R),o) grupa, neboť 1. složením dvou těchto funkcí je opět funkce z R do R, ke které existuje inverze -podle věty 5 o výpočtu inverzí platí (f ° g)'1 = g'1 ° f'1 (inverze ke složení funkcí je složení dílčích inverzí v opačném pořadí). 2. 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))) = fo(go h)(x). 3. Jednotkou vzhledem ke skládání funkcí je identita fid{x) = x \/x G R. 4. Vlastnost (4) je požadavkem, podle kterého jsou funkce vybírány, tj. platí. Právě uvedený příklad je důležitý v tom, že je příkladem nekomutativní grupy. Například pro funkce f(x) = sinx, g(x) = - je funkce / o g = sin - odlišná od funkce g°f = —- ^ J sin x Příklad 2.2. Grupa permutací 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í na vysoké škole budeme na tyto permutace pohlížet jako na zobrazení, které základní vzestupné pořadí 12345 přemění na pořadí např. 51324: Definice 2.1. 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- 4- I 5 1 3 2 4 / je bijektivní, takže existuje permutace f~ľ k ní inverzní 1 2 3 4 5 \ t t t t t 5 1 3 2 4 / 18 2 TÝDEN 02 - PŘEDNÁŠKA 02 - NEKOMUTATIVNÍ GRUPY 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 \ /= \ i i i i i \ označovat jako / = (1,5,4,2) V 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 \ f'1 = T T T T T budeme vyjadřovat jako f'1 = (1,2,4,5) V 5 1 3 2 4 j (tj. změnil se změr cyklu, veškeré zobrazování otočilo směr; mohli bychom zapsat i f~ľ = (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: T1 = (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 nejmenší 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í; Věta 7. (Sn,o), množina permutací13 M —> M pro M = {1,2,...,n} vzhledem k operaci skládání permutací je pro n > 3 nekomutativní grupa. Ilustrace důkazu: Pro lepší pochopení důkazu situaci nejprve ilustrujeme na příkladě permutací na tříprvkové množině: 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, í(3) = 2, 13Pozor, 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. 19 í(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 = (1,2,3) oid= (1,2,3) = s nebo u o v = (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 vou= (1,3) o (2, 3) = (1,3,2) =t. Čili z posledních dvou příkladů je vidět, že vou ^ uov, 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 levý prvek x vybrán14 z levého sloupce záhlaví a pravý prvek y z horního řádku záhlaví; výsledek operace pak je znázorněn na průsečíku „řádku xlí a „sloupce ylí: * y X x*y Tedy konkrétně u operace o na množině S3 dostaneme tabulku operace: Tabulka 2: Tabulka operace o na množině S3. 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 14Toto je klíčově důležitá domluva, řečená už v předchozí kapitole. Většina operací je komutativních, a tam je pořadí prvků vstupujících do operace zaměnitelné, ale u nekomutativních operací tomu tak není a u tabulky operace se musíme jednoznačně domluvit na pořadí první prvek - druhý prvek pro danou operaci. 20 2 TÝDEN 02 - PŘEDNÁŠKA 02 - NEKOMUTATIVNÍ GRUPY Z tabulky je vidět, že operace je uzavřená na množině Ss, tj. platí vlastnost (1). Asociativita (2) platí pro skládání jakýchkoli zobrazení, viz příklad 4.1. 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ů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 4.1. Identické zobrazení id definované Va G {1,2,... ,n} vztahem id(a) = a je neutrálním prvkem na množině permutací, tj. platí (3): Pro obecnou permutaci p : {1, 2,..., n} —y {1,2,..., n} totiž máme pro každné a G {1, 2,..., n}: p o id(a) = p(a) A id o p[a) = id(p(a)) = p(a). Důkaz vlastnosti (4): V obecném případě (Sn,o) permutací na n-prvkové množině M = {l,...,n} najdeme pro libovolnou permutaci p G Sn její inverzní prvek p~ľ následujícím způsobem. Jelikož p : M —y 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~ľ je zobrazením. Dále p je surjekce, tj. p~ľ je definováno pro každé a G {1,2,... ,n}. Tedy pro bijekci p je p~ľ také bijekce (v grafické reprezentaci relace pouze zaměníme směr všech šipek), a tedy permutace {1,2,... ,n} —y {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. □ Ad příklad 2.2. Uveďme nyní některé další vlastnosti této grupy, které vyplývají z kapitoly 3: Za prvé, existuje šest podgrup grupy (6*3,0): tzv. triviální podgrupa, která obsahuje pouze jednotkový prvek id, s tabulkou operace 0 id id id další podgrupou je celá šestiprvková grupa (S3, 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) 21 Dále, ohledně generátorů grupy S3 lze říci, že (S3, 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 (S3,o) =< (1,3),(1,2)>. Písmeno S v označení množiny Sn pravděpodobně pochází z toho faktu, že tyto permutace představují jakési jistým způsobem symetrické útvary, nebo modelují struktury, kterým se říká symetrie. Ukažme si, jak tyto grupy permutací vznikají ze grup symetrií, například na grupě symetrií čtverce. Příklad 2.3: grupa symetrií čtverce: 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 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 Rq = id, pootočení o 90° odpovídá permutace R\ = (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 R2 = (1,3) o (2,4)15 a pootočení o 270° permutace R3 = (1,4,3,2)16. (podrobněji viz obrázek 1). Podobně dostaneme permutace odpovídající přeměně čísel ve vrcholech čtverce při osové souměrnosti vzhledem ke čtyřem hlavním osám souměrnosti, viz obrázek 2. Skládáním R\ o R4 například dostaneme R1oR4 = (1, 2, 3,4) o (2,4) = (1, 2) o (3,4) = Re, atd. Vyplněním operace pro každou dvojici prvků v obou pořadích (operace je opět nekomutativní, protože např. f?4 o R1 = R7) dostaneme tabulku grupy (_D4, o) symetrií 15Pozor, 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. 16Což 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. 22 2 TÝDEN 02 - PŘEDNÁŠKA 02 - NEKOMUTATIVNÍ GRUPY o. A h <1 i .'---~- 1 i ■b h in í Í 1 <9 4 2 3 Obrázek 1: Permutace odpovídající pootočení čtverce. čtverce, která odpovídá podgrupě grupy permutací s osmi prvky (viz tabulka 3). Všech permutací čtyřprvkové množiny je 24; tedy naše osmiprvková množina je podgrupou grupy 1S4. Pro každé přirozené n > 3 lze sestrojit grupu symetrií pravidelného n-úhelníka a označit ji Dn vzhledem k operaci skládání zobrazení. Například označuje grupu symetrií pětiúhelníka, 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 místo v algebře. Příklad 2.4. Posledním důležitým příkladem nekomutativní grupy, se kterou se studenti budou v budoucnu setkávat, je množina všech čtvercových matic, ke kterým existuje inverze vzhledem k násobení matic, společně s operací násobení matic. Tento příklad bude podrobně rozebrán v předmětu Algebra 2 - násobení matic, jak uvidíme, je nekomutativní operací. Pro zájemce je tento typ operace uveden jako příklad důležité nekomutativní operace už v úvodu knihy [8], str.7-8. 23 /V \ \ 2. •A H \ 'i 'i \ /ť % Z /k OH í> / -1 / cl A 1 I A* °- -1 *l 1 1» r5 4 M 2- » H Rif* V 4 1 4 3- /A 2- * ^ 12 ^ ? ^ 4 X "i 5 4 2. v C H 1 2. 1 Obrázek 2: Permutace odpovídající osové symetrii čtverce. Tabulka 3: Tabulka operace o na množině D4 symetrií čtverce. o Ro Ri Ä2 Rs i?4 R5 Rq Ri Rq Rq Ri R2 Rs i?4 R5 Rq Ri Ri Ri R2 Rs id Rq Ri R5 i?4 R2 R2 R3 Ro Ri R5 i?4 R7 Rq R3 R3 Ro Ri R2 R7 Rq i?4 R5 Ri R5 Rq Ro R2 Rs Ri R5 R5 Rq Ri R2 Ro Ri Rs Rq Rq i?4 Ri R5 Ri Rs Ro R2 R7 R7 i?5 Rq i?4 R3 Ri R2 Ro Operace na cyklické podgrupě je vždy komutativní 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ě genero- 24 2 TÝDEN 02 - PŘEDNÁŠKA 02 - NEKOMUTATIVNÍ GRUPY vané 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 (S3, o) je generovaná prvkem (1, 2, 3), a tedy je to cyklická podgrupa, tj. cyklická grupa. Je vidět, že tabulka operace na {id, (1, 2,3), (1, 3, 2)} je symetrická, tj. operace je na ní komutativní. Další příklad: Grupa symetrií čtverce (příklad 2.3) je vzhledem ke skládání těchto symetrií nekomutativní grupou, ale například podgrupa {Rq, R\, R2, R3} pootočení čtverce je generována prvkem R\, odpovídajícím pootočení čtverce o 90°, tj. je cyklická. I z tabulky symetrií je též vidět, že příslušná část odpovídající podgrupě pootočení je symetrická, tj. operace je na této podgrupě cyklická. Nekomutativita je způsobena až osovými souměrnostmi. Důkaz faktu, že operace na každé cyklické grupě je komutativní, je lehký - přednášející jej na požádání předvede, když mu poskytnete tužku a papír. 25 3 Týden 03 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy Cvičení 3.1. Příklady z [8], str. 39, oddíl A: řešení rovnic v grupách - je zde vidět nutnost přidávat prvek na té správné straně výrazu při nekomutativní operaci a to, že obecně nemůžeme odmocňovat. Důležitější jsou ovšem příklady od cvičení 3.3 dále, proto se prvními dvěma cvičeními moc nezdržujte. Například A.O: Vyřešte v grupě (G, *) systém rovnic (e je neutrální prvek; dospějte ke vztahu x = ... na pravé straně bude výraz obsahující prvek b a žádné x clili x )'. x2 = b, x5 = e. Například A.3: Vyřešte v grupě (G, *) systém rovnic (vyjádřete prvek x v závislosti na prvcích a, b, c (a jejich inverzích), tj. dospějte ke vztahu x = ...). POZOR, v grupě obecně neplatí komutativní zákon pro všechny dvojice prvků: x2*a = b*x* c_1, a*c*x = x*a*c. Například A.4: Vyřešte v grupě (G, *) systém rovnic (vyjádřete prvek x v závislosti na prvcích a, b (a jejich inverzích), tj. dospějte ke vztahu x = ...). : a* x2 = b, x3 = e. Například A.5: Vyřešte v grupě (G, *) systém rovnic (e je neutrální prvek; dospějte ke vztahu x = ... na pravé straně bude výraz obsahující prvek a a neobsahující x): x2 — a2 x5 = e. Například A.6: Vyřešte v grupě (G, *) systém rovnic (nepředpokládejte, že obecně platí vlastnost (5) = komutativní zákon; dospějte ke vztahu x = ... na pravé straně bude výraz obsahující prvky a, b a žádné x): (x * a* x)3 = b * x, x2 * a = (x * a)^1 = .... Například B.l: Dokažte, že v každé grupě platí následující implikace (e je neutrální 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í: x2 = a2 =^ x = a. 26 3 TÝDEN 03 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): Například B.5: Dokažte, že v grupě platí následující fakt, nebo uveďte protipříklad, že neplatí: \/x e G 3 y e G : x = y2 (tj. každý prvek x má v grupě svou „odmocninu" y). Příklady z [8], str. 40, oddíl E: počet prvků a jejich inverzí - výborné příklady. Cvičení 3.3. Příklady z [8], str. 41, oddíl F: vytváření tabulky operace pro grupy s malým počtem prvků - výborné příklady. 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? ... X\ . x2 ... a ... y . • y ••• Zdůvodněte, proč ano - proč ne. Například F.3: M = {e, a, b}. Doplňte tabulku operace * e a b e e a b a a b b tak, aby (M, *) byla grupa. Například F.4: Čtyřprvková grupa G = {e, a, b, c, } splňuje Ví G G její neutrální prvek). Sestavte tabulku operace * této grupy: x2 = e (kde e je * 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 3.1 CVIČENÍ 03: VLASTNOSTI GRUP, PODGRUPY A GENERÁTORY GRUPY 27 Cvičení 3.4. (text [8], str. 42, oddíl G): Dokážte, že kartézský součin grup (G, y) a (H, *) je grupa (G x H, □) - jak definovat operaci □? Cvičení 3.5. Příklady z [8], 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? Cvičení k pojmům podgrupa, generátory podgrupy: Cvičení 3.6. Příklady z [8], 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 G 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,-k) 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 E H také a-1 G H (tj. H je uzavřená vzhledem k inverzím). Nápověda k důkazu : H = {ai,a,2, ■ ■ ■ ,an} a vyberme si libovolné a« G H. Uvažujme nyní navzájem RŮZNÉ prvky a,i * a1? a,i * a2, ..., a« * an: atd. Cvičení 3.7. Příklady z [8], str. 50, oddíl E: generátory grupy - výborné příklady. Například N.l (není v textu [8]): 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 (Hiq,+) 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 (H12,+). Například E.7 - modifikace17: V grupě H2 x iJ4 je operace sčítání po složkách zadaná tabulkou Určete, jakou podgrupu generuje prvek [1; 1]. Například E.6: Sestavte tabulku operace grupy (H2 x H3) vzhledem k operaci sčítání po složkách. A druhý úkol: dokažte o této grupě, že je cyklická. 17Jediný 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. 28 3 TÝDEN 03 Tabulka 4: Tabulka operace + na množině H2 x H4. + [0;0] [0; i] [0;2] [0;3] [i;0] [i;i] [1 2] [i;3] [0;0] [0;0] [0; i] [0;2] [0;3] [i;0] [i;i] [1 2] [i;3] [0; i] [0; i] [0;2] [0;3] [0;0] [i;i] [i;2] [1 3] [i;0] [0;2] [0;2] [0;3] [0;0] [0;i] [i;2] [i;3] [1 0] [i;i] [0;3] [0;3] [0;0] [0;i] [0;2] [i;3] [i;0] [1 1] [i;2] [i;0] [i;0] [i;i] [i;2] [i;3] [0;0] [0; i] [0 2] [0;3] [i;i] [i;i] [i;2] [i;3] [i;0] [0;i] [0;2] [0 3] [0;0] [i;2] [i;2] [i;3] [i;0] [i;i] [0;2] [0;3] [0 0] [0; i] [i;3] [i;3] [i;0] [i;i] [i;2] [0;3] [0;0] [0 1] [0;2] 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.2. 3.2 PŘEDNÁŠKA 3: IZOMORFISMUS, CALYEHO VĚTA 29 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 stejnostech18. 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 izimorfní, 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). Obrázek 3: Dvě izomorfní struktury toku v sítích. Například na obrázku 3 jsou nakresleny dva příklady toku v sítích19 - může se jednat o tok informací ve spravodajské síti, tok financí v ekonomické síti, tok proudu elektrickým obvodem, apod. Matematické grafy reprezentující tyto toky jsou příkladem diskrétních grafů (na rozdíl od spojitých grafů funkce v matematické analýze). Když studujeme síť A a síť B na obrázku, vidíme, že tyto dvě sítě jsou izomorfní, tj. mají stejnou vnitřní strukturu: existuje totiž bijekce 1 2 3 4 \ 1 1 1 1 ) 6 5 8 7 / která zobrazuje prvky sítě A na odpovídající prvky sítě B v tom smyslu, že prvek 1, ze kterého vycházejí dvě orientované hranu do dvou dalších uzlů sítě A, odpovídá prvku 6 sítě B, ze kterého rovněž vycházejí dvě orientované hrany. Podobně prvek 2 v síti A odpovídá prvku 5 v síti B, protože tyto dva uzly mají tutéž vlastnost (každý ve své síti), že do nich jedna hrana grafu vstupuje a dvě hrany z nich vycházejí, atd. Tj. izomorfismus těchto grafů je nejen bijekcí, ale navíc ještě zobrazuje prvek jedné sítě na prvek stejného strukturálního charakteru v jiné síti. Podobně na obrázku 4 vidíme dvě izomorfní grupy. Obě jsou tříprvkové a existuje mezi nimi bijekce / 0 1 2 111 y e a b 18Viz Alena Šolcova, přednáška o Cestách k české terminologii v některých partiích matematiky, Katedra matematiky Pdf, 14. března 2018. 19Pozor, obrázek 3 se neučte, jedná se jen o příklad „stejnosti" z teorie grafů, ovšem na uvedených strukturách není definována (binární) operace. Skutečná definice izomorfismu grup se týká obrázku 4 nebo 5, kde máme na obou strukturách definovanou operaci - jeden z nich se můžete naučit. 30 3 TÝDEN 03 (M 7- V v o A X 0> o A 2. Ä/ O a OL a. 2. o 1 *> Jb Obrázek 4: Dvě izomorfní grupy. ale nejen to - tato bijekce v jistém smyslu „zachovává výsledky operace", tj. např. prvek 1 V 2 z grupy G±, což lze v tabulce operace y gmPy Gi najít, že je 0, odpovídá v navrhované bijekci prvku e v grupě G2, který je výsledkem operace * mezi obrazy prvků 1 a 2, tj. mezi a a b, tedy platí a * b = e. Toto zachování výsledků operace musí platit pro každou dvojici prvků z G±. Definice 3.1. Izomorfismus grupy (G±, y) na grupu (G2,*) je bijekce / : G± —> G2, která splňuje vlastnost Wa,beG1: /(a y 6) = /(«)*/(&)• Obrázek 5: Podmínka zachování výsledků operace při zobrazení /. Jinými slovy (viz obrázek 5, izomorfismus mezi grupami je taková bijekce / : G± —> G2, při které jsou f {a y b) a f {a) * f {b) tytéž prvky, pro jakoukoli dvojici prvků a, b. A nebo ještě jinak, říkáme, že izomorfismus / mezi grupami je bijekce, pro kterou diagram na obrázku 6 komutuje, neboli když vypustíme na prvky a, b z „ohrady" Gi operaci y, 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 *20. 20Diagram 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í. 3.2 PŘEDNÁŠKA 3: IZOMORFISMUS, CALYEHO VĚTA 31 Obrázek 6: Komutativní diagram pro podmínku zachování výsledků operace. Příklad 3.1. (R, +) a (R+, •) jsou izomorfní grupy, pokud definujeme zobrazení R —> R+ vztahem f(x) = ex. Snadno se vidí, že zobrazení / je injekce, protože nenabývá dvou stejných hodnot pro dvě různá x±,x2 G R. Dále je / surjekce R na R+ - pro každé y G R+ existuje x E R tak, že ex = y. Celkem tedy / 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+b = ea . eb_ Celkem / 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, y) má vlastnost, kterou grupa (G2,*) nemá, nemohou být tyto grupy izomorfní. Například • Gi je komutativní, ale G2 ne. • Gi má nějaký prvek, který je inverzí sebe sama, ale G2 takový prvek nemá. • Gi 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í 32 3 TÝDEN 03 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. (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 7ra : G —> G (a dokážeme, že se jedná o permutaci G, tedy o bijekci). 2. O množině těchto permutací G* := {ira; a G G} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekci 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 G G zobrazení na definované vztahem \/x £ G : 7Ta(x) ■= a\7 x (zobrazení 7ra zobrazí každé x E G na, prvek a y x G G). Dokažme o 7ra, že se jedná o bijekci: • 7ra je injekce G —> G: Předpokládejme, že 7va(xi) = ^a{x2) ~ to by znamenalo podle definice zobrazení 7ra, že a V Xl = a V x2i 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í ira 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 G G by pak byly pokryty nějakými vzory vzhledem k zobrazení /. Odpověď: hledaný vzor z G je prvek a 1 V Ví Pak totiž ^(cT1 y y) = a v V V = V- 3.2 PŘEDNÁŠKA 3: IZOMORFISMUS, CALYEHO VĚTA 33 • Celkem na je bijekce. 2. O množině těchto permutací G* := {ira; a G G} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekcí G —> G). G* je podmnožinou grupy Sq všech permutací na G —> G. Dokážeme o G*, že je podgrupa: • G* je neprázdná, nejmenší možná grupa G je totiž minimálně jednoprvková (obsahuje neutrální prvek e), a tedy minimálně ire(x) := e yi je identická permutace, která náleží do G*. • (G*, o) splňuje vlastnost (1), tedy pro dvě různé permutace ira, irb musíme najít prvek c G G, že 7rc = pia o irb. Skutečně to platí - pokud vezmeme c := a \/ b, potom Podrobněji rozepsáno, Wx eG : navb(x) = (a\/b)\/x = a\/(b\/x) = a\/nb(x) = na(nb(x)) = (naonb)(x) Tedy složením dvou prvků ira a irb 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 ira-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ů) TTa O 7Ta-l = 7Tava-l = 7Te. • 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 ira G G*, neboli f (a) = na. • f je injekce: Pokud f {a) = f(b), znamená to, že 7ra = irb, tedy Wx G G : 7ra(x) = nb(x); a tak i speciálně pro jednotku e E G platí 7ra(e) = ^(e), což znamená a y e = b y e, to ale znamená, že a = b. Rovnost obrazů si vynucuje rovnost vzorů, tedy / je injekce. 34 3 TÝDEN 03 • / 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 G G, tj. každá permutace 7ra má svůj vzor a E G vzhledem k zobrazení /. • / zachovává výsledky operace: chceme dokázat podmínku Va,beG: 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 y b) = navb = naonb = f (a) o f(b). • Celkem / je izomorfismus grupy (G, v) na grupu (G*, o). Kniha [8], str. 97-102, opět poskytuje řadu cvičení: Cvičení 3.1. (sady C,D): Jsou dané grupy izomorfní? Například C.3: Zjistěte, zda je grupa 2^a'b^ izomorfní s grupou (V, •), kde V = {1, —i] a • je operace násobení komplexních čísel. Své zjištění zdůvodněte. Například D.l: Prozkoumejte grupy a) (H4,+); b) (H2 x iJ2,+) (sčítání definováno po složkách po složkách); c) grupu komplexních jednotek (V, •), kde V = {1, —i} 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í 3.2. (sada G): Izomorfní grupy na množině reálných čísel. Cvičení 3.3. (sada J): Regulární reprezentace grupy - rychlá konstrukce podgrupy grupy Sn, která je s grupou G izomorfní!! 35 4 Týden 04 4.1 Cvičení 04: Nekomutativní grupy Cvičení 4.1. Jsou dány permutace P =(1,5,6,2,3), R= (1,7,5,4,3,6,1). Vypočtěte P o R2 (výsledek najdete na konci tohoto textu). Cvičení 4.2. Kniha [8], str. 75, oddíl B, příklady na grupy permutací. Například B.2: Vypište prvky cyklické podgrupy grupy (Se, °) generované prvkem / = (1,2,3,4) o (5,6). Například B.3: Najděte čtyřprvkovou komutativní podgrupu grupy (S$, o) 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, /, g, h, i, j a sestavte tabulku operace o. Například N.l: Podgrupa grupy (S4, o) generovaná prvky / = (1,3) o (2,4), g = (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 (S7, o) generované prvkem / = (1,3) o (4,5,7). Například N.3: Grupa (S4, o) 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. Cvičení 4.3. Příklady [8], str. 77, sada F na grupu symetrií pravidelného n-úhelníka. Například F.O: Sestavte tabulku grupy D% symetrií rovnostranného trojúhelníka vzhledem k operaci skládání zobrazení (množina D% má šest prvků - tři rotace: o nula stupňů (R±), o 120 stupňů (R2), o 240 stupňů (R3); a tři osové souměrnosti vzhledem osám jednotlivých úhlů (f?4, R5, Re))- Těmto geometrickým transformacím lze přiřadit permutace tříprvkové množiny podle toho, jak se změní pozice čísel 1, 2, 3 přiřazeným jednotlivým vrcholům trojúhelníku vůči základní poloze - viz obrázek 7. Cvičení 4.4. Dva úkoly pro grupu permutací (S3, o) (použijte prosím označení prvků a tabulku operace o ve větě 7): a) dokažte, že (S3, o) není cyklická grupa; 36 4 TÝDEN 04 Obrázek 7: Permutace D% odpovídající symetriím trojúhelníku. b) najděte dvouprvkovou podmnožinu grupy, která generuje celou grupu (S3, o). Uvicem 4.5. Pokud bude čas, je možné se zabývat některými dalšími vlastnostmi permutací (ad [8], 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.3. 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 37 4.2 Přednáška 04: Lagrangeova věta, homomorfismus grup 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 Mi, 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í, tj. je to systém po dvou disjunktních podmnožin, který pokrývá celou množinu M v tom smyslu, že\JMi = 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 Mi = Mj a jedná se o tutéž třídu. Lze tedy rozklad množiny M na podmnožiny Mj definovat i následovně: - ViG{l,2,...,fc}: M^0; - (I ... M; M; > M; Mj] - každý prvek a E M leží v jedné třídě rozkladu. • Označení 07: Znak ~ bude značit relaci ekvivalence určenou daným rozkladem, tj. a ~ b právě tehdy, když a, b E Mi pro nějaké i. • Označení 08: 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 y? 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 4.1. Va z grupy (G, v) a JeJí podgrupu (H, y) lze definovat: levá třída prvku a E G vzhledem k podgrupě H je množina a\/ H := {a\/ h E G : h E H} (množina výsledků operace a\/ h, kde prvek a E G ]e pevné a prvek h probíhá podgrupu H); podobně pravá třída prvku a E G vzhledem k podgrupě H je množina H x/ a := {h x/ a E G : h E H} 38 4 TÝDEN 04 (množina výsledků operace h\/ a, kde prvek a G G je pevné a prvek h probíhá podgrupu H). Pojmy levá a pravá třída prvku splývají jen tehdy, pokud y 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 4.1. 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 kiJje 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 ]e 3 + H = {1,3} = H + 3 (tedy levá třída prvku 3 je rovná pravé třídě prvku 3); Příklad 4.2. Pro grupu G = (5*3,0) permutací z věty 7 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 věty 7): • levá třída prvku id vzhledem k H je id o H = {id, (1, 2,3), (1, 3, 2)} = H = Ho 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) o H = {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)} = Ho (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 4.2 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. 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 16 je pouze pomocnou větou, která bude 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 39 potřeba v důkazu věty 17 (věty 16 až 18 jsou řečeny za předpokladu označení z definice 8.1, tj. (H, y) je podgrupa grupy (G, y)). Věta lôj a £ H \j b právě tehdy, když H y a = H y b. Důkaz: tato část důkazu je triviální: protože a = e y a G y a a také b = e\/ b £ H \/ b, z rovnosti množin plyne i a £ H \/ b. „=^": předpokládejme, že a £ H \y b, & tedy existuje h £ H tak, že a = /í y &. Za tohoto předpokladu dokážeme množinovou rovnost z platnosti dvou inkluzí: H \7 a £ H \7 b: Pokud x £ H \/ a, tak x = h\\/ a pro nějaké h\ £ H. Z předpokladu věty dosaďme za a a dostaneme i = ^ y a = Žij y (/í y 6) = (/í! y /í) y &, a protože součin v poslední závorce je prvkem iJ, dostáváme celkem, že x £ H \/ b. H \7 b £ H \7 a: Pokud x £ H y b, tak x = h2\/ b pro nějaké h2 £ H. Z předpokladu věty (a = h y 6) si vyjádřeme b, konkrétně (protože jsme v grupě G, všechny inverze existují) a = h\j b =>- h~ľ y a = b, a po dosazení za b dostaneme x = h2\/b = h2xj (h'1 y a) = (h2 y h'1) y a, a protože součin v poslední závorce je prvkem množiny H, dostáváme celkem, že x £ H y a. Věta 16 netvrdí nic světoborného, v podstatě jen to, že pokud prvky a, b jsou spojeny v operaci y „přes podgrupu Hlí, tak jejich pravé třídy jsou totožné. Následující věta 17 je prvním významným výsledkem této kapitoly. Pravé21 třídy H \/ a pro všechny možné prvky a grupy (G, y) tvoří rozklad množiny G. Důkaz: Dokážeme ve dvou krocích: a) H\/a, H\/b jsou buď disjunktní, nebo totožné; b) každý prvek grupy G leží v nějaké třídě takto vytvořeného rozkladu. a) Pokud množiny H y a, H y b mají prázdný 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 £ (H y a) n (H y b) (x = hx y a) A (x = h2\j b) ^ hx\j a = h2\j b\ vyjádřeme například prvek a z rovnosti, ke které jsme dospěli (jsme v grupě, tedy všechny inverze existují): a = h^1 y h2\j b. To tedy znamená, že a= Oľ1 V h) V b £ H y b, a to podle věty 16 (tady právě ji potřebujeme!!) znamená, že H \/ a = H \/ b. 21Platí i analogická věta: Všechny levé třídy ay H ... 40 4 TÝDEN 04 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 = e y c (kde e je neutrální prvek), a tedy c E H \/ c. Našli jsme třídu rozkladu, ve které prvek c leží. Věta 18. Existuje bijekce mezi podgrupou (H, y) a každou pravou třídou H \j a. Důkaz: Bijekcí bude to nej přirozenější zobrazení / : H —>• H y a, které bychom asi vytvořili: f(h) = h\j a. Takto definované / je injekce: f(h1) = f(h2) h1\/a = h2\/a^ h = h2 (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 y a Je tvaru h\/ 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ůsledek věty 18 pro konečné grupy G: Všechny pravé třídy H\j 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 19!!! Ale ty nej důležitější věty, věta 17 a věta 18, už byly řečeny. Věta 19 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: |G| =5-\H| Obrázek 8: 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 4.3. Uvažujme situaci na obrázku 8: všech pravých tříd vzhledem k podgrupě H konečné grupy G je pět - jedna z nich je H y e = H a další čtyři jsou H y a, H y 6, H y c, H y d. Existuje bijekce (podle věty 18) 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\. 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 41 Lagrangeova pro konečné grupy. Počet prvků libovolné podgrupy H je dělitelem počtu prvků konečné grupy G22. Důkaz Lagrangeovy věty je dalším důsledkem věty 18: 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 4.4. 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). Příklad 4.5. Pokud \G\ je prvočíslo, tak grupa G má pouze nevlastní podgrupy. Pokud \G\ = p je prvočíslo, tak grupa (G, y) 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 20 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 (Z7, +) 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 21. Řád každého prvku a G 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 \G\, což je řád grupy G. Definice 4.2. 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\ (G : H) = j—^ = počet navzájem různých tříd rozkladu {H \j a;a E G}. Cvičení 4.1. Cvičení k pojmu ekvivalence a rozklady - snad byl procvičeno dost v předmětu Základy matematiky, více viz [8]. str. 123-125 ... ovšem v naší situaci by bylo 22 Připomeneme-li si definici řádu grupy, tak: řád podgrupy H je dělitelem řádu grupy G. 42 4 TÝDEN 04 zajímavé cvičeníčko D na str. 124 - relace ekvivalence na grupě. Například D.0: Uvažujme grupu G = (Zq, ©) a její podgrupu H = (2). Definujme na G relaci a ~ b, když a + b^1 G H. Dokažte, že relace ~ je ekvivalence. Cvičení D.l: Pro grupu {G, ■) a její podgrupu H zkuste obecně dokázat, že relace ~:= {[a, b] G G x G : ab^1 G H} je ekvivalence. Cvičení D.2: Pro grupu {G, ■) a její podgrupu H zkuste obecně dokázat, že relace ~:= {[a, b] G G x G : a_16 G i/} je ekvivalence, popřípadě najděte konkrétní příklad, který tento fakt vyvrací. Cvičení D.3: Pro grupu {G, ■) a její podgrupu H zkuste obecně dokázat, že relace ~:= {[a, b] G G x G : 3x G G : a = rrĎrr-1} je ekvivalence. Cvičení 4.2. Cvičení na podgrupy, které využívá poznatku Lagrangeovy věty: Pro grupu (Z)5,o), kde je desetiprvková množina transformací pravidelného pětiúhelníka na sebe sama a operace o (=;jpo") 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); • / ... 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; • 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 ]e vrchol pětiúhelníka a F je střed strany BC; a informace o vlastnostech, které platí: • Podle Lagrangeovy věty může mít podgrupa konečné grupy jen jistý počet prvků; • 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 prvků); 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 43 • ještě musíte do každé podgrupy zahrnout i všechny příslušné inverzní prvky. Cvičení 4.3. Cvičení k pojmu levá a pravá třída prvku vzhledem k podgrupě ([8], 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ě. Důležitý dodatek, možno dělat na cvičení: Lagrangeova věta (a její důsledek - věta 20) společně s větou 12 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 20), a tedy až na izomorfismus stejná jako (Hp, +) neboli (Zp, +) (věta 12), tedy grupa prvočíselného počtu prvků je až na izomorfismus jediná. • Dále grupa o počtu prvků p2, který je druhou mocninou prvočísla, je podle cvičení G ([8], str.154-155) izomorfní buď (Zp2,+), nebo (Zp 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. 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 homomorfismy23. Definice 4.3. Grupový homomorfismus / : 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). 23Jazykově: izomorfismus = stejný tvar, totožný tvar; homomorfismus = podobný tvar, odvozený tvar (v jistém smyslu). 44 4 TÝDEN 04 Příklad 4.4. 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ýsledků 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 Z6 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 Z6, která obsahuje součet zbytků obou původních čísel po vydělení šesti. Příklad 4.5. Zobrazení / : Z§ —?■ Z3, přičemž na obou množinách uvažujeme operací sčítání, definované vztahem / 0 1 2 3 4 5 \ f= \ 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í / 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. □ Definice 4.4. Pokud / : 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 4.5: grupa (Z3, +) je homomorfním obrazem grupy (Z6, +) vzhledem k homomorfismu /. Podívejme se tedy na některé vlastnosti každého grupového homomorfismu. Tyto vlastnosti platí i pro izomorfismus, prtože homomorfismus je obecnější pojem (každý grupový izomorfismus je současně i grupovým homomorfismem): 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 45 Věta 22. Pro grupový homomorfismus / : G —>• H grupy (G, y) do grupy (H, *) platí: a) /(eg) = en (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 V eG, a P° využití vlastnosti (h) homomorfismu (= vlastnosti zachování výsledků operace) dostaneme: /(eG) = F(eG y eG) = /(eG) * /(eG), dostali jsme tedy rovnost /(eG) = /(eG) * /(eG), ze které po vynásobení rovnosti prvkem (/(eG))_1 (který existuje díky vlastnosti (4) v grupě (H, *)) zprava dostaneme /(eG) * (Kec))-1 = f(eG) * f(eG) * (/(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 en = f(eG) * eH (=H 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 )=/(oVfl ) = 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. Normální podgrupa grupy K definici normální podgrupy se dostaneme přes definici konjugovaného prvku: Definice 4.5. Pro grupu (G, v) a JeJí prvek a definujeme konjugovaný prvek b k prvku a E G, pokud existuje x E G tak, že b = x y a V x~ľ- Označení: protože relace konjugovanosti je relace ekvivalence, budeme značit a ~ b, nebo také symetricky b ~ a. 46 4 TÝDEN 04 Než půjdeme dále, všimněme si dvou trivialit: a) Každý prvek a grupy G je konjugovaný se sebou samotným(a ~ a), protože vždy platí a = a y a V a 1 (Pro ^ = a) nebo a = e y a y e 1 (Pro ^ = e? kde e je neutrální prvek grupy (G, y) a o neutrálním prvku víme, že je vždy inverzí k sobě samotnému). b) Jistě k některým prvkům a E G bude existovat více navzájem různých konjugovaných prvků jinak by tento pojem vůbec neměl smysl, kdyby každý prvek byl konjugovaný jen sám se sebou. Nicméně určitě víme, že k neutrálnímu prvku e E G neexistuje žádný jiný konjugovaný prvek než e samotný (e ~ e), protože w x-y -1 (3) -i (4) Vx E G : x x/ e x/ x = x y x = e. Příklad 4.6. Najděme v grupě (Ze, +) všechny konjugované prvky k prvku 2: budeme procházet všechna možná x E G a počítat konjugované prvky x + 2 + x~lm. 0 -\ -2H -0 = 2, H -2H -5 = 2, 2 -\ -2H -4 = 2, -2H -3 = 2, 4 -\ -2H -2 = 2, 5- f 2- f 1 = 2 Poslední dva řádky už byly zbytečné, protože daný součet prvku a jeho inverze byl proveden v jiném pořadí na řádcích druhém a třetím, ale díky tomu, že operace sčítání je komutativní, jsme mohli pořadí prvků zaměnit. Dospěli jsme k zjištění, že v našem příkladu je prvek [2] konjugovaný pouze se sebou samotným. A když si toto zjištění rozmyslíme podrobněji, poobný výsledek dostaneme v jakékoli komutativní grupě, protože prvky x a x~ľ lze díky komutativitě seskupit vedle sebe a provést operaci s nimi jako první, výsledkem je jednotkový prvek, a tak vždy bude platit -1 (5) -1 x x/ a\/ x = x\/ x ya = eya = a. Touto úvahou jsme dokázali tuto větičku: V komutativní grupě je k prvku a konjugovaný pouze prvek a samotný. Z toho plyne, že relace konjugovanosti bude hrát nějakou roli v nekomutativních grupách, protože v komutativní grupě se jedná o tzv. diagonální relaci - v relaci je pouze každý prvek sám se sebou, a to je vše. Příklad 4.7. Zkusme najít všechny konjugované prvky v grupě permutací (63,0) k prvku (2, 3) (viz tabulka operace o ve větě 7 kapitoly 4): id o (2,3) o id'1 = (2, 3), tj. (2,3) ~ (2, 3) (2,3) o (2, 3) o (2, 3)^ = (2, 3), 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 47 (1,3) o (2,3) o (1,3)^ = (1,2), tj. (2,3) ~ (1,2); (1,2) o (2, 3) o (1, 2)-1 = (1, 3, 2), tj. (2, 3) ~ (1, 3, 2); (1,2,3) o (2,3) o (1,2,3)^ = (1,3,2), (1,3,2) o (2,3) o (1,3,2)-! = (1,2). Tj. našli jsme kromě prvku (2,3) ještě dva další prvky s ním konjugované, a sice (1,2), (1,3,2). Nyní jsme připraveni na definici normální podgrupy: Definice 4.6. Podgrupa (H, y) grupy (G, y) se nazývá normální podgrupa, pokud je uzavřená vzhledem ke konjugovaným prvkům, tj. platí a E H, x E G x\j a\j x^1 E H. Díky větičce 24 platí věta 25: V komutativní grupě je každá podgrupa normálni. Ad příklad 4.7. Z příkladu 4.7 je vidět, že v nekomutativních grupách obecně existuje více konjugovaných prvků k danému prvku, tj. například podgrupa ({e, u}, o) grupy (S3, o) není normální, protože k prvku u kromě jeho samotného existují dva další konjugované prvky t, w, takže podgrupa ({e,u}, o) není uzavřená na konjugované prvky. Definice 4.7. Jádro grupového homomorfismu / : G —> H se nazývá množina ker/ ( označení 09 )24 těch prvků z grupy (G, v)? které se zobrazí na neutrální prvek e# grupy (#,*). Příklad 4.8. a)V grupovém izomorfismu je jádrem zobrazení / pouze jednoprvková množina {ec}- b) V homomorfismu / : Z$ —> Z3 z příkladu 9.3 je jádrem množina těch prvků, které se zobrazí na nulu: keif = {0, 3}. Pro každý grupový homomorfismus platí tyto další vlastnosti: a) keif je normální podgrupa v (G, v)i 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 x y a y x~ľ E ker/. Půjde to jednoduše, využijeme přitom předpokladu (p) věty (/(a) = e#) a vlastnosti (h) homomorfismu: f(x V a V x-1) => f(x) * f (a) * /(x"1) =* f(x) * eH * /(x"1) =* f(x) * /(x"1) (== eH, 24 Označení plyne z německého slova kernel - anglické core se z historických důvodů neprosadilo. 48 4 TÝDEN 04 tj. protože se prvek lyayi 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) = eH] ii) f(G) je uzavřená vzhledem k operaci *: pro f(x) a f(y) platí m*m = f(xvv), tedy prvek f(x) * f(y) je obrazem prvku x \/ y E G, a, tedy f(x) * f(y) G f (G), platí (1); iii) f {G) je uzavřená vzhledem k inverzím: pokud /(a) G /(G) také /(a-1) G /(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 /(a), platí vlastnost (4). Celkem podle věty 6 je f(G) podgrupa grupy (H, *). • Viz Pinter 2010, str. 141-146: A. Příklady homomorfismu konečných grup. Například A.l. a) Definujte nějaký (aspoň jeden) homomorfismus / : (Z8,+) —> (Z4,+): /0 1234567\ f = \ i i i i i i i i \- b) Určete jádro K homomorfismu z části (a). Například A.5: Každá z dvanácti transformací pravidelného šestiúhelníka v grupě {D§, 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 / : Dq —> S$, v obou grupách uvažujeme operaci skládání permutací. Například f(id6)=ids, /(1,2,3,4,5,6) = (1,2,3). Napište, na jaké prvky se zobrazí tímto homomorfismem zbylých deset prvků grupy As- Grupa (S3,o) má prvky: id, (1,2,3), (1,3,2), (2,3), (1,3), (1,2). • 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: f : (D(R), +) —> (F(R), +) je definované vztahem ip(f) = f (D (R) je množina reálných funkcí, u kterých existuje jejich derivace /', a F (R) je množina reálných funkcí). 4.2 PŘEDNÁŠKA 04: LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 49 Například B.3: Zdůvodněte, proč zobrazení / je grupovým homomorfismem, a najděte jeho jádro: / : (R x R, +) —y (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). • C. Základní vlastnosti homomorfismu. • D. Základní vlastnosti normální podgrupy. Například D.0: Zjistěte, zda {id, (1, 2, 3), (1, 3, 2)} je normální podgrupa grupy permutací tříprvkové množiny (S3, o). Můžete použít tabulku operace o z přednášky o nekomutativních grupách. • F. Homomorfismus a řád prvku. Například F.l: Pro homomorfismus grup / : (G, v) —> {H,*) je a G G prvek řádu n. Vyzkoumejte na příkladech (např A.l), 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 22 a předchozích dvou větiček N.l, N.3 najděte všechny možné homomorfismy z příkladu A.l, tj. všechny možné homomorfismy grupy (Z8, ©) do grupy (Z4, ©) a určete jejich jádra. Například N.2: Vypište všechny prvky grup (Z9, ©), (S3, o) a u každého prvku určete jeho řád. Potom popište všechny možné homomorfismy grupy (Z9, ©) do grupy (Ss,o), 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 homomorfismu určete jeho jádro. • G. Vlastnosti zachované homomorfismem. • I. Konjugované podgrupy vzhledem k podgrupě. Výsledky některých cvičení najdete v závěru textu v oddílu 13.4. 50 5 TÝDEN 05 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ů: • amx/an = am+n, • (am)n = am-n, • a~n = (a-1)11. 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 5.1. Řád prvku a grupy (G, v) Je roven nejmenšímu přirozenému číslu n, pro které an = e (n-tá mocnina prvku a G G je rovna neutrálnímu prvku e G G. Pokud takové přirozené číslo neexistuje, říkáme, že řád prvku a je nekonečný. Příklad 5.1. Co se týká řádu jednotlivých prvků grupy (S3, o), 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: id6 = 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 = 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ý. lad 5.2. 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: Věta 9. 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_1. 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, ..., an~ľ; b) prvky a°, a1, ..., an_1 jsou navzájem různé. 5.1 CVIČENÍ 05: ŘÁD PRVKU, CYKLICKÉ GRUPY, GRUPY ZBYTKOVÝCH TŘÍD 51 Důkaz části a): Uvažujme libovolnou mocninu am prvku a G G, který je řádu n. Pak podle věty 12 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 g, r tak, že m = n ■ q + r, 0 < r < n. Pak lze upravit am na tvar am = an-q+r = ^ny y flr = &q y flr = ^ 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, ..., an_1 jsou navzájem různé. Pokud se některé z těchto dvou prvků rovnají, platí ď = as, kde r i s jsou dvě různá čísla z množiny {0,1, 2,..., n - 1}, tj. r ^ s. BUNO25 například s < r, tj. platí 0 < s < r < n, a tedy 0 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 ď = ď je nesprávný a důkaz sporem je hotov.□ To tedy znamená, že prvek nekonečného řádu „svým umocňováním"26 vede na nekonečně mnoho navzájem různých prvků grupy. A dodejme ještě větu 11, která upřesňuje situaci kolem konečného řádu prvku grupy: BUNO = Bez újmy na obecnosti. Umocňování = opakované použití operace v na týž prvek. 52 5 TÝDEN 05 Pokud řád prvku a v grupě je n ( označení 04 : označme ord(a) = n), pak platí pro celočíselné t: a1 = e <í=> (n\t, tj. t = n y Q, pro nějaké q G Z). (mocnina prvku konečného řádu je rovna neutrálnímu prvku tehdy a jen tehdy27, 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 9a): Pokud a* = 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 \jar = e\jar. 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 a* = an-q = {an)q = é = e. Cyklické grupy Pojem cyklické grupy a jejího generátoru (jediného prvku) už byl vysvětlen dříve. 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,a ,... ,a j. 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: J(A; + /) = afc+ř = afcV«ř = /(fc)v/(0-Touto kratinkou úvahou jsme vlastně dokázali větu 12: Věta 12. 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 n28 jsou navzájem izomorfní. A podobně pro cyklickou grupu generovanou prvkem nekonečného řádu: lze psát < a >= {..., a~2, a-1, e, a, a2, a3,...}, 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í 27Pozná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 ordy if = tehdy a jen tehdy když. 28Připomínka bizarní definice řádu grupy: řád grupy = počet prvků grupy. 5.1 CVIČENÍ 05: ŘÁD PRVKU, CYKLICKÉ GRUPY, GRUPY ZBYTKOVÝCH TŘÍD 53 výsledků operace. Dostáváme tak větu 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 12 a 13 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í definice 5.2. : 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 9). 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. • 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 Z6 je konečná a má jen šest prvků!!!) a definujeme na této množině operace ©, 0 následovně: [a] © [b] := [a + b]; 54 5 TÝDEN 05 Obrázek 9: Rozdělení celých čísel do šesti podmnožin. tj. součet tříd je třída, která obsahuje celé číslo a + b, [a] 0 [b] := [a-b\. tj. součin tříd je třída obsahující celé číslo a ■ b. Lze ukázat, že tyto dvě operace nezávisí na výběru celých čísel a, b z daných nekonečných množin. Pro takto definovanou šestiprvkovou množinu a operace na ní nyní platí, že (Z6, ©) je grupa (zbytkových tříd modulo 6), (Ze*, 0) = (Z6 — {[0]}, 0) je monoid (zbytkových tříd modulo 6). a) Pomocí tabulky operace © dokažte, že (Z&, ©) je grupa: b) Pomocí tabulky operace 0 dokažte, že(Z6, 0) je monoid: • označení 05 : Zn ... množina zbytkových tříd modulo n: • označení 06 : Z*n ... množina zbytkových tříd modulo n mimo prvek [0], tj. Z*n:=Zn-{[0]}. Toto označení používáme i pro klasické množiny Q* (racionální čísla mimo nuly), R* (reálná čísla mimo nuly), protože se nám hodí, že (Q*, •), (R*, •) jsou grupy (nulu z těchto množin musíme vyloučit, protože pro ni neexistuje inverzní prvek vzhledem k operaci násobení). 5.1 CVIČENÍ 05: ŘÁD PRVKU, CYKLICKÉ GRUPY, GRUPY ZBYTKOVÝCH TŘÍD 55 Tabulka 5: Tabulka operace © na množině Z§. © [0] [1] [2] [3] [4] [5] [0] [0] [1] [2] [3] [4] [5] [1] [1] [2] [3] [4] [5] [0] [2] [2] [3] [4] [5] [0] [1] [3] [3] [4] [5] [0] [1] [2] [4] [4] [5] [0] [1] [2] [3] [5] [5] [0] [1] [2] [3] [4] Tabulka 6: Tabulka operace 0 na množině Z&. 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] 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í): 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 (Z6,0) neexistují k prvkům [2], [3], [4] inverzní prvky, protože čísla 2, 3, 4 jsou soudělná s číslem 6. 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í 0, a tedy (Z*, 0) je grupa. Například (Z^,Q) je grupa. Čtenář by se o tom mohl snadno přesvědčit z tabulky 56 5 TÝDEN 05 operace 0 na množině Z^: 0 [1] [2] [3] [4] [5] [6] [1] [2] [3] [4] [5] [6] [1] [2] [3] [4] [5] [6] [2] [4] [6] [1] [3] [5] [3] [6] [2] [5] [1] [4] [4] [1] [5] [2] [6] [3] [5] [3] [1] [6] [4] [2] [6] [5] [4] [3] [2] [1] Cvičení k pojmu řád prvku: Ad [8], str 107-110: • Cvičení B (str. 108): Příklady řádu prvků. Například N.4: Na grupě permutací (SV, o) 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). Cvičení 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 [8], str. 114-115). • Cvičení A (str. 115): příklady cyklických grup. • Cvičení B: elementární vlastnosti cyklických grup. • Cvičení C: generátory cyklické grupy. • Cvičení E: kartézský součin cyklických grup. Například D.2 z knihy [8], 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 (S3, 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í): Cvičení k pojmu grupy zbytkových tříd: 0 [1] [2] [3] [4] [5] [6] [1] [2] [3] [4] [5] [6] [1] [2] [3] [4] [5] [6] [2] [4] [6] [1] [3] [5] [3] [6] [2] [5] [1] [4] [4] [1] [5] [2] [6] [3] [5] [3] [1] [6] [4] [2] [6] [5] [4] [3] [2] [1] 5.1 CVIČENÍ 05: ŘÁD PRVKU, CYKLICKÉ GRUPY, GRUPY ZBYTKOVÝCH TŘÍD 57 © [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] (Z6, ©) je grupa: Grupa (Hs x H2, +): + [o 0] [0 1] [1 0] [i;i] [2 0] [2 1] [0; 0] [o 0] [0 1] [1 0] [i;i] [2 0] [2 1] [0; i] [o 1] [0 0] [1 1] [i;0] [2 1] [2 0] [i; 0] [i 0] [1 1] [2 0] [2; i] [0 0] [0 1] [i; i] [i 1] [1 0] [2 1] [2;0] [0 1] [0 0] [2; 0] [2 0] [2 1] [0 0] [0; i] [1 0] [1 1] [2; i] [2 1] [2 0] [0 1] [0;0] [1 1] [1 0] Například N. 1: Jsou grupy (Zg, +) a (Z^ x Z3) izomorfní? Pokud ano, daný izomorfismus 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] [í i] [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] [1 1] [1 2] [2 0] [2 1] [2 2] [0 0] [0 0] [0 1] [0; 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2] [0 1] [0 1] [0 2] [0; 0] [1 1] [1 2] [1 0] [2 1] [2 2] [2 0] [0 2] [0 2] [0 0] [0; 1] [1 2] [1 0] [1 1] [2 2] [2 0] [2 1] [1 0] [1 0] [1 1] [i; 2] [2 0] [2 1] [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; 1] [2 2] [2 0] [2 1] [0 2] [0 0] [0 1] [2 0] [2 0] [2 1] [2; 2] [0 0] [0 1] [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; 1] [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,0): 58 5 TÝDEN 05 © [0;0;0] [0;0; 1] [0;1;0] [1;0;0] [0;1 1] [1;0; 1] [i;i;0] [i; i; i] [0;0;0] [0;0;0] [0;0; 1] [0;1;0] [1;0;0] [0;1 1] [1;0; 1] [i;i;0] [i; i; i] [0;0; 1] [0;0;1] [0;0;0] [0; 1; 1] [1;0;1] [0;1 0] [1;0;0] [i;i;i] [i;i;0] [0;1;0] [0;1;0] [0; 1; 1] [0;0;0] [i;i;0] [0;0 1] [i; i; i] [1;0;0] [1;0; 1] [1;0;0] [1;0;0] [1;0; 1] [i;i;0] [0;0;0] [1;1 1] [0;0; 1] [0;1;0] [0; 1; 1] [0; 1; 1] [0;l;l] [0;1;0] [0;0; 1] [i;i;i] [0;0 0] [i;i;0] [1;0;1] [1;0;0] [1;0; 1] [i;0;i] [1;0;0] [i; i; i] [0;0;1] [1;1 0] [0;0;0] [0; 1; 1] [0;1;0] [i;i;0] [i;i;0] [i;i;i] [1;0;0] [0;1;0] [1;0 1] [0; 1; 1] [0;0;0] [0;0; 1] [i; i; i] [i; i; i] [i;i;0] [1;0; 1] [0; 1; 1] [1;0 0] [0;1;0] [0;0;1] [0;0;0] Napří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 (Z8, ©): © [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;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 (Ľ4,o): (J?0, J?1? R2, R% jsou rotace čtverce o násobek pravého úhlu; S4, S5 osové souměrnosti vzhledem k úhlopříčkám čtverce; Sq, Sj osové souměrnosti vzhledem ke 5.1 CVIČENÍ 05: ŘÁD PRVKU, CYKLICKÉ GRUPY, GRUPY ZBYTKOVÝCH TŘÍD 59 spojnicím středů protějších stran čtverce) o Ro Ri R2 R3 is4 s5 Se S7 Rq Rq Ri R2 R3 S4 s5 Se s7 Ri Ri R2 R3 Ro Se s7 s5 S4. R2 R2 R3 Ro Ri S4 s7 Se R3 Ro Ri R2 s7 Se S4 s5 s7 s5 Se Ro R2 Rs Ri s5 s5 Se S4 s7 R2 Ro Ri Rs Se Se s7 s5 Ri R3 Ro R2 S7 S7 S5 Se s4. R3 Ri R2 Ro Například N.3: Definujte přesně izomorfismus (Zj,Q) na (Z6,©), který zachovává výsledky operace. Grupa (Z7, 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] Grupa (Ze, ©): © [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. 60 5 TÝDEN 05 5.2 Přednáška 5: Faktorgrupa V minulé přednášce jsme se naučili poznat, kdy je H homomorfním obrazem grupy G (tehdy, když existuje surjektivní homomorŕismus G na H). Nyní uděláme velký skok a naučíme se zkonstruovat všechny možné homomorfní obrazy jakékoli grupy G. Nejdůležitejším pojmem při této konstrukci je právě pojem normální podgrupy (= podgrupy uzavřené vzhledem ke konjugovaným prvkům). Začneme tím, že si všimneme vztahu mezi normální podgrupou a levou a pravou třídou prvku vzhledem k této podgrupě (věta 27 představuje jakousi formu „komutativity" - sice díky ní nemáme zaručeno a y hľ = h\ y a (to platí jen tehdy, je-li grupa G komutativní), ale máme s využitím dvou prvků h1} h2 G H zaručeno, že a y ^i = h2 V ai jinými slovy, v normální podgrupě můžeme i při nekomutativní operaci zaměnit pořadí prvků, pokud nahradíme h\ G H obecně jiným prvkem h2 G H): H je normální podgrupa grupy (G, y), tj. a y h y a 1 G -řř Va G G. Pak a y H = H y a (levá a pravá třída prvku jsou totožné). Důkaz: „C": x G a y H =^ x = a y h x G H y a =>- x = hxj a Důkaz je hotov. □ Definice operace pro třídy prvků Co kdybychom nyní na pravých třídách prvku (podle věty 17 se jedná o třídy rozkladu G) chtěli definovat operaci y odvozenou od operace y, jejímž výsledkem by byla nějaká (obecně další) třída rozkladu grupy Gl Definiční vztah by mohl mít tvar (HVa)v(Hvb) :=HV(aVb). Problém je ten, že nevíme, zda tato operace je korektně definována - byla by korektně definována jen v případě, že při výběru jiného prvku c G H y a (což můžeme udělat, protože pro c G H \/ a platí podle věty 16, že H y a = H y c) a prvku d G H X/ b (protože pak podle věty 16 platí H \/ b = H \/ d) by platilo (H xj c)\i(H xj d) = H xj (c\j d) A H y (a y b) = H y (c y d). Pak by totiž (a tak se této vlastnosti i říká) nové definované „násobení tříd" (vzhledem k operaci y) nezáviselo na výběru reprezentantů: ať bychom ze třídy H y a = H y c vybrali reprezentanta a nebo c, a ze třídy H y b = H y d vybrali reprezentanta b nebo d, dostali bychom jednoznačně určenou třídu H y (a y b) = H y (c y d). = a y hxj (a y a) = (a y h y a ) ya =^ x G H y a. = (aya )y/iya = ay(a y/iya) =^ x G a y H. 5.2 PŘEDNÁŠKA 5: FAKTORGRUPA 61 Příklad 5.4. Obecně myšlenku právě navrženou nelze realizovat, například pro G = (S3, o) a H = ({id, (2, 3)}, o) pravé třídy jsou třídy Fo(l,3) = {(l,3),(l,2,3)} = iJo(l,2,3), o(l,3,2) = {(l,3,2),(l,2)} = # o(l,2), H o id = H = H o (2,3). Všechny pravé třídy prvků vzhledem k téže podgrupě H tedy tvoří podle věty 17 rozklad grupy G = (Ss,o), to samozřejmě platí pro libovolnou grupu, tedy i pro tu v tomto příkladu. Ovšem pokud bychom nyní chtěli definovat spojení tříd iJ o (1, 3) a iJ o (1,3, 2) způsobem (H o (1,3))o(H o (1, 3, 2)) := H o ((1, 3) o (1, 3, 2)) = H o (2, 3) = H, toto spojení tříd by záviselo na výběru reprezentanta, protože výběrem druhých možných prvků z daných tříd bychom dostali (tf o(l, 2,3))o(tf o(l,2)) :=iJo((l,2,3)o(l,2)) = iJo(l,3) = {(l,3),(l,2,3)}^iJ, tedy výběrem různých reprezentantů z těchto tříd dostáváme různé třídy - celý proces tedy není korektně definován, operace se třídami nefunguje jako zobrazení, kdy je každé dvojici tříd (v daném pořadí) jednoznačně přiřazen výsledek operace. Na třídách rozkladu podle podgrupy H = {id, (2, 3)} nelze toto spojení tříd korektně definovat. Pokud ovšem H je normální podgrupa, násobení tříd lze definovat korektně: Věta 28. Pokud H je normální podgrupa grupy (G, v) a platí H v a = H v c, H v b = H v d, tak operace y použitá na třídy prvků nezávisí na výběru reprezentantů, tj. H V (a V&) = H V (cy d). Důkaz: i) H \j a = H v c a G H y c, protože a G H y a (neboť a = e\/ a E H \/ a, kde e G H je neutrální prvek), tak podle předpokladu věty také a G H V c- Tedy a = h\\/ c pro nějaké h\ G H. H v b = H v d b G H y d, protože b E H \7 b (neboť b = e\/bEH\/b, kde e G H je neutrální prvek), tak podle předpokladu věty také b E H \/ d. Tedy b = h2 V d pro nějaké h2 E H. Dohromady z i) a ii) plyne: a v b = hx v c v h V d- 62 5 TÝDEN 05 Nyní využijeme předpokladu, že H je normální podgrupa, tj. podle věty 27 platí c y H = H y c, tedy c y ^2 lze upravit c y /i2 = /i3 y c pro nějaké /13 G H. Pokračujme v úpravě oyíia dostaneme a y & = h y (c V ^2) V d = hi V h Vc V d e H y (c V d)- Celkem protože a y 6 G H \/ (c\/ d), tak podle věty 16 platí H y (a V&) = H y (cv4 Důkaz je hotov!!□ Označení 10. Označme množinu tříd G/h rozkladu podle normální podgrupy H ... vzhledem k operaci y definované pomocí vztahu (HVa)v(Hvb) :=HV(aVb) jako tzv. rozkladovou grupu nebo též při doslovném překladu faktorgrupu29. Věta 29. Struktura G/h vytvořená z tříd podle normální podgrupy H s operací y Je grupa. Důkaz. Vlastnost (1): korektní definice operace y Pro třídy rozkladu a uzavřenost této operace plyne z věty 28. Vlastnost (2): Asociativita plyne z asociativity operace y na (G, y) a korektní definice operace mezi třídami (věta 28): ((H y a)v(H y b))y(# y c) = (# y (a y 6))y (# y c) = # y ((a y 6) y c) = = # y (a y (b y c)) = (H y a)y(# y (6 y c)) = (# y a)y((# y 6)y(# V c)). Vlastnost (3): Neutrálním prvkem je třída H y e, protože platí (e je neutrální prvek v (G, V)): (# y a)y(# y e) = iJ y a, (# y e)y (iJ y a) = H y a. Vlastnost (4): Inverzním prvkem ke třídě H y a je třída H y a-1: (# y a) v(# V = Hs/e, (H y a_1)y (iJ y a) = # y e. Rozkladová grupa (G/h, V) je homomorfním obrazem grupy (G, y), neboli přirozeně definované zobrazení /, které přiřadí prvku a E G třídu H \/ a E G/h, je 29 Anglicky FACTOR znamená, „rozložit" 5.2 PŘEDNÁŠKA 5: FAKTORGRUPA 63 surjektivní grupový homomorfismus. Důkaz. Zobrazení / je a) surjekce, což plyne z konstrukce zobrazení /: pro libovolnou třídu h v c Je vzorem prvek c G G; b) je splněna vlastnost zachování výsledků operace: Jedná se tedy o surjektivní homomorfismus, tedy grupa obrazů je homomorfním obrazem grupy vzorů. □ Tímto způsobem (= podle věty 30), jak brzy uvidíme (viz příklad 10.3), lze zkonstruovat všechny homomorfní obrazy grupy (G, Xj). Příklad 5.5. Pokud G = (Z, +) a h =< 6 >= {..., -12, -6, 0, 6,12,...} její cyklická podgrupa (která je současně normální podgrupou, protože (Z, +) je komutativní grupa -věta 25), třídy prvku vzhledem k podgrupě (h, +) jsou < 6 > +0 = {..., -12, -6, 0, 6,12, ...}=< 6 > +6, < 6 > +1 = {..., -11, -5,1, 7,13, ...}=< 6 > +7, < 6 > +2 = {..., -10, -4, 2, 8,14, ...}=< 6 > +8, < 6 > +3 = {..., -9, -3, 3, 9,15, ...}=< 6 > +9, < 6 > +4 = {..., -8, -2,4,10,16, ...}=< 6 > +10, < 6 > +5 = {..., -7, -1, 5,11,17, ...}=< 6 > +11, atd. Zkrátka všech různých tříd prvků vzhledem k podgrupě < 6 > je pouze šest, a těchto šest tříd (věta 17) tvoří rozklad množiny Z. Podle věty 25 je < 6 > normální podgrupa, tj. podle věty 28 sčítání těchto tříd nezávisí na výběru reprezentanta, tj. struktura Zq := (Z/<6>,+) je faktorgrupa (rozkladová grupa) grupy (Z, +). V této kapitole 10 jsme tedy dopodrobna popsali konstrukci grupy zbytkových tříd (Z6,+). Tato grupa je homomorfním obrazem grupy (Z, +), pokud definujeme zobrazení / přirozeně tím způsobem, že prvku z G Z je přiřazena třída [z] grupy (Z/<6>, +). Vraťme se ještě k základním vlastnostem podgrup a dokažme jednu vlastnost (a), kterou budeme potřebovat ve zbytku kapitoly, a druhou vlasnost (b), která platí triviálně a už jsme s ní pracovali, ale nyní bude vyslovena ve tvaru ekvivalence: Pro každou grupu (G, Xj) a jej í podgrupu h platí a) h \j a = h \j b ^ a xj b^1 G h. b) h xj a = h a e h. Důkaz.ad a) „=^": Pokud h xj a = h xj b, kde e G h je neutrální prvek vzhledem k operaci y? tak protože a = exj a G hx/ cl, musí a G h X/ b. Tedy f (x V V) = Hx7(xx/y) (h y x)v(h v y) dej. f(x)y_f(y). a = hxj b 64 5 TÝDEN 05 pro nějaké h E H a vynásobením této poslední rovnosti prvkem 6_1 zprava dostaneme a y 6_1 = h, tedy a y o-1 G iJ. a y ČT1 G H =>• a\/ b~ľ = h =>- a = h\jb =>- a E H \j b H \j a = H \j b. ad b) lze dokázat přímo (pomocí dvou implikací), ale tvrzení i důkaz je speciálním případem čisti (a) pro b = e (kde pro neutrální prvek e E H platí H y e = H a e-1 = e). Důkaz je hotov. □ Příklad 5.6. V tomto příkladu naznačíme, jak lze zkonstruovat homomorfní obraz grupy, ve kterém je zachována vlastnost, kterou jsme si zvolili jako pozitivní a kladnou, zatímco vlastnost, kterou chápeme jako nežádoucí, je v homomorfním obrazu „vyloučena": Dejme tomu, že se nám líbí vlastnost (5) = komutativita, ale grupa G je nekomutativní, tj. obsahuje dvojice prvků a, 6, pro které a\/b ^ o y a- Rádi bychom nekomutativní prvky „vyloučili" z této grupy, ale všechny ostatní prvky zachovali. Uděláme to následujícím způsobem: Uvažujme podmnožinu H všech komutátorů v G, neboli všech součinů tvaru ay6\7 gT1 y b~ľ. Důvod, proč se tyto prvky nazývají komutátory, je platnost podmínky a y b y gT1 y b~ľ = e <^ a\jb = b\ja (tedy pro komutativní dvojici prvků je komutátor z ní vytvořený (bez ohledu na jejich pořadí) roven neutrálnímu prvku, a právě ve všech ostatních případech nekomutativních dvojic prvků je komutátor z nich vytvořený jiný prvek než e). Tedy v komutativní grupě jsou všechny komutátory rovny neutrálnímu prvku e. V nekomutativní grupě G je počet všech komutátorů jakýmsi měřítkem toho, jak dalece se G odchyluje od vlastnosti (5). Pokud množina všech komutátorů H je normální podgrupou grupy G, pak tedy faktor-grupa G/H bude obsahovat jen jediný komutátor, a sice třídu H y e = H, tedy triviální komutátor, který v grupě existuje vždy - ale žádné jiné!! Tedy grupa G/H je komutativní - faktorizací neboli konstrukcí rozkladové grupy jsme „odstranili" nekomutativní prvky a „zachovali" pouze ty komutativní. To vskutku platí, ověřme podmínku komutativity operace y v podílové grupě G/H: (H y ar) y (H y y) = (H y y) y (H y x) lze upravit vzhledem ke korektně definované operaci (věta 28) na tvar H V (x vy) = H y (y y x), a to podle věty 31a) platí právě tehdy, když x y y y (y y x)~ľ E H. To je ovšem splněno, protože podle věty 5 o výpočtu inverze součinu (y y x)~ľ = x~ľ y y~ľ, a tedy xVVV(yV xY1 = x\7yX7x-1X7 y'1, 5.2 PŘEDNÁŠKA 5: FAKTORGRUPA 65 a to je právě prvek typu komutátor, který patří do H. Fundamentální věta o homomorfismu Ve větě 30 jsme viděli, že každá podílová grupa je homomorfním obrazem (vzhledem k surjektivnímu homomorfismu) grupy G. Nyní naopak dospějeme k větě 33, že každý homomorfní obraz grupy G je její rozkladovou grupou. Všimneme si totiž, že platí podmínka věty 32: Pro grupový homomorfismus / : (G, v) ~~^ {H, *) s jádrem K := ker f (které podle věty 26-(a) je normální podgrupou grupy G) platí KVa = KVb & f(a) = f(b). Důkaz: Využívá věty 31a), viz též obrázek 10 (každá třída K y x se zobrazí na jediný prvek): KVa = KVb v<*] ayb^eK & f(aVb-1) = eH f (a) * [fib)}'1 = eH, a poslední uvedenou rovnost lze ekvivalentně (pracujeme v grupě) upravit vynásobením f(b) zprava na rovnost f (a) = f(b), čímž dostaneme podmínku věty. Obrázek 10: Definice izomorfismu $ na základě homomorfismu /. Věta 33. Pro surjektivní grupový homomorfismus / : (G, y) -> (H, *) s jádrem K lze zkonstruovat podílovou grupu G/k a zobrazení $ : G/k —> H, které je grupovým izomorfismem. Důkaz: Definujeme-li zobrazení $ předpisem $(K V^) := f(x) (zobrazení $ přiřadí třídě K y x len prvek v H, který je obrazem prvku x vzhledem k homomorfismu /), toto zobrazení je podle věty 32 korektně definováno a dokonce z věty 66 5 TÝDEN 05 32 plyne, že se jedná o injekci: <Š>(KVa) = <Š>(KVb) ^ f(a) = f(b) # K V a = K V b. Surjektivita $ plyne ze surjektivity zobrazení /: každý prvek grupy (H, *) je tedy tvaru f(x) = (f)(K x/ x). A nakonec platí i podmínka zachování výsledků operace: $(K y av_K Vb) = <Š>(KVaVb) = f (a V 6) = f (a) * f(b) = <\>{K V a) * <\>{K V 6). Příklad 5.7. Homomorfismus / : (Ze, +) —> (Z3, +) z příkladu 9.2 definovaný vztahem / 0 1 2 3 4 5 \ V 0 1 2 0 1 2 / má jádro K = {0,3}. Podílová grupa podle tohoto jádra musí být (věta 33) izomorfní grupě (Z3,+): Z6/{0,3} = Z3 (s operací sčítání v obou grupách). Vhodná cvičení v knize [8]: za kapitolami 15 a 16. A. Příklady konečných faktorgrup: Například N.l: Uvažujme homomorfismus ip grupy (Z8,©) do grupy (Z4,©) definovaný 99(0) = 0, ip{\) = 1, atd. a) Určete jádro K tohoto homomorfismu; 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. B. Příklady nekonečných faktorgrup 67 6 Týden 06 6.1 Cvičení 06: prověrka-a z toho, co se probralo Prověrka podle pokynů cvičícího. 68 6 TÝDEN 06 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 6.1. podruhé 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£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říkladem konečného okruhu je struktura zbytkových tříd (Zn, ©, 0). • 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 6.2. netriviální 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 6.2. Příkladem struktury s netriviálními dělitely nuly je množina Zq zbytkových tříd modulo 6: její prvky [2], [3] nebo [3], [4] jsou netriviální dělitelé nuly, protože platí [2] 0 [3] = [0], [3] 0 [4] = [0]. 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) 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á, 6.2 PŘEDNÁŠKA 06: STRUKTURY SE DVĚMA OPERACEMI 69 kdy se taková situace vyskytne a jak zaručit, že k ní nedojde. Z tohoto důvodu definujeme obor integrity: Definice 6.3. 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 komutativitě operace • lze distributivní zákon psát v jediné rovnici: V x,y, zEM: x-(y + z)=x-y + x- z = y- x + z- x = (y + z)-x. Příklad 6.3. • (Zj, ©, 0) je konečný obor integrity, protože 7 je prvočíslo, tj. (Z^,Q) neobsahuje netriviální dělitele nuly. • (Z, +, •) je nejen nekonečný okruh, ale i nekonečný obor integrity, protože neobsahuje netriviální dělitele nuly a násobení je komutativní, a tedy distributivní zákon lze psát v jedné rovnici. V klasické teorii operací se definuje ještě jeden pojem, který je dokonce ještě silnější než obor integrity, a sice těleso: Definice 6.4. 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. 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í a 0 ^ 1. 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". 70 6 TÝDEN 06 • (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í. • {Qi +)') 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 11: 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ř. (Z6, ©, 0); 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. Definice 6.5. Ideál je neprázdná podmnožina B okruhu (M, +, •) taková, že (B, +) je podgrupa (tj. B vzhledem k operaci + splňuje vlastnosti (1) a (4)) a navíc B absorbuje součiny na množině M, tj. V6 G B, m G 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 6.5. Nejpřirozenějším příkladem ideálu je podmnožina B sudých celých čísel okruhu (Z, +, •): £ = {...,-4,-2,0,2,4,...}. 6.2 PŘEDNÁŠKA 06: STRUKTURY SE DVĚMA OPERACEMI 71 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, +, •). V teorii ideálů hraje klíčové místo tzv. hlavní ideál okruhu, který definujeme ( definice 6.6. ) jako takový ideál B, který vygenerujeme jediným prvkem b, jenž vynásobíme se všemi prvky množiny M. Příklad 6.6. 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 G Z, tj. jedná se o ideál z příkladu 6.5: £ = {...,-4,-2,0,2,4,...}. • B% :=< 3 > ... ideál generovaný prvkem 3 a všemi součiny 3 • z pro z G Z, tj. JB3 = {...,-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. Zde nyní je snad vhodné upozornit na matematickou větu, kterou za- končíme tento semestr (jejíž důkaz je nechán pro cvičení), že ideál je v okruhu analogie toho, co v grupě je normální podgrupa: Uvažujeme-li homomorfismus okruhů (= homomorfismus, který zachovává výsledky obou operací + i •), tak jeho jádro kerj (= množina všech prvků prvního okruhu, které se zobrazí na neutrální prvek vzhledem k + ve druhém okruhu) je ideálem prvního okruhu ... to je analogie věty 26a) pro homomorfismus okruhů, která říká, že jádro homomorfismu grup je normální podgrupa. Č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í, 72 6 TÝDEN 06 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 nejdů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 [8], 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}7 b) Jak byste strukturu (2p,U,n) 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,n). 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 H průniku. Sestavte tabulky operací 4- a H na množině 2P. b) Jak byste strukturu (2P, 4-, fl) 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 [8], 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 y de D, ze z. Uveďte příklad ideálu D okruhu (Z, +, •), který obsahuje číslo 2 a neobsahuje číslo 3. 73 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), ale je potřeba zopakovat. Doporučené materiály k využití: • Označení: (Z[x], +, •), +, •), (-R[rr], +, •), ... 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 7r. 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-i ■ xa~x + • • • + a\ ■ x + clq = an ■ (x — Xi) ■ (x — x2) ■ ■ ■ (x — xn), například 1 2 Qx3 + 13x2 - 4 = Q(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. 74 7 TÝDEN 07 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. 75 8 Týden 08 8.1 Cvičení 08: Polynomy 02 Věta o racionálních kořenech polynomu v (Z[rr],+, •). 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 (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 + Ax — 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. 76 8 TÝDEN 08 8.2 Přednáška 08: Přehled algebraických metod hledání kořene polynomu 77 9 Týden 09 9.1 Cvičení 09: Polynomy 03 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: • Vzorce pro kořeny polynomu 3. a 4. stupně (u 3. stupně např. Trombiková BP, str.22-23), pro 4.stupeň jsou vzorce trochu jedodušší (např. Wikipedia). Galois, Gauss: Vzorce pro rovnice 5. a vyššího stupně neexistují. Příklad: vyřešte rovnici x6 + x5 + 4x4 + 3x3 + 5x2 + 2x + 2 = 0. Homérovým schématem ověříme, že všech šest kořenů je iracionálních nebo komplexních. Jak je lze najít? • 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 max {a0, a1;..., an_i} Př. 23-str.29: nalezněte řešení algebraické rovnice 2x5 + 3x4 - 7x3 + 6x2 - llx + 5 = 0. Dosazením do vzorce věty 16 máme \xí\ < 1 + ^ = 6,5. B) Jemnější detekce reálných řešení: Ad A ... stále stejný řešený příklad, \xí\ < 6,5: Víme, že Xi G (—6,5; 6,5), řešíme rovnici p(x) = 0 pro p(x) = 2x5 + 3x4 - 7x3 + 6x2 - llx + 5. Protože p(x) je spojitá funkce, tj. vypočteme p(hi) pro hi 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 p(hi) ■ p(hi-i) < 0, znamená to, že dvě po sobě jdoucí hodoty mají rozdílná znaménka, tedy objevíme, že na intervalu (hf, hi+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) (a stiskneme ENTER ... vytvoří se vektor x našich hodnot hi), pak napíšeme p<-2*x5 + 3*x4-7*x3 + 6*x2-ll*x + 5 78 9 TÝDEN 09 (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 +, •), tak nutně i a — ib 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 frorn = 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 pol(k) 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) {i f (pol((a + b)/2)*pol(b) < 0) {a < -((a + 6)/2);print((a + b)/2)} else {b < -((a + b)/2);print((a + 6)/2)}} (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). 9.1 CVIČENÍ 09: POLYNOMY 03 79 Pokud celý postup (posloupnost tří kroků ukončených ENTER) zopakujeme pouze pro volbu a = 0,5, 6=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ě z0 a počítáme posloupnost hodnot z1} z2,... užitím vzorce Výpočet v prostředí R: Navíc k definici funkce pol(k) 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'(x) našeho polynomu: der < — function(w){return(10 * vŕ + 12 * vŕ — 21 * vŕ + 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: z<--3.5 a ENTER, a provedeme cyklus WHILE: (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). 80 9 TÝDEN 09 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,54689 ... 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 + 3i z našeho kruhu v komplexní rovině \z\ < 6,5: dojdeme k řešení z^ = —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 z^ = —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. 9.2 PŘEDNÁŠKA 09: PŘEHLED NUMERICKÝCH METOD HLEDANÍ KOŘENE POLYNOMU 81 9.2 Přednáška 09: Přehled numerických metod hledání kořene polynomu 82 10 TÝDEN 10 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: VEKTOROVÉ PROSTORY, STUPEŇ ROZŠÍŘENÍ TĚLES83 10.2 Přednáška 10: Vektorové prostory, stupeň rozšíření těles Definice vektorového prostoru, báze a dimenze - jen orientačne, pro potřeby příkladu a následného důkazu. Stupeň rozšíření těles. Algebraický důkaz nemožnosti trisekce úhlu a bisekce krychle jen za pomoci kružítka a pravítka. 84 11 TÝDEN 11 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: GALOISOVA TEORIE - POKUS O ZAČÁTEK PŘEHLEDF5 11.2 Přednáška 11: Galoisova teorie — pokus o začátek přehledu 86 12 TÝDEN 12 12 Týden 12 12.1 Cvičení 12: Prověrka-b na polynomy a komplexní čísla 12.2 PŘEDNÁŠKA 12: GALOISOVA TEORIE - POKUS O HLAVNÍ KROK 87 12.2 Přednáška 12: Galoisova teorie — pokus o hlavní krok 88 13 VÝSLEDKY NĚKTERÝCH PŘÍKLADŮ 13 Výsledky některých příkladů 13.1 Výsledky ke cvičení 1.2 — Určování vlastností různých operací Ad cvičení 2.1: 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 (Nq, +) 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, •), (R, •) 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})')? (R ~ {0})') Jsou komutativní grupy. Někdy též značíme Q*:=Q-{0}, R*:=R-{0}, tj- {Q*i')? {R* ■>') Jsou komutativní grupy. f) ,g) (2A, U), (2A, fl) 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 fl 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. 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.2 VÝSLEDKY KE CVIČENÍ ?? - VLASTNOSTI GRUP, PODGRUPY A GENERÁTORY GRUPY 89 13.2 Výsledky ke cvičení 3.1 — Vlastnosti grup, podgrupy a generátory grupy Ad cvičení 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\ ai2. Rovnici a*x1 = y = a*x2 vynásobíme prvkem A~ľ 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 cvičení 3.3 - F.3: Tabulku lze doplnit na: e a b e e a b a a b e b b e a Ad cvičení 3.6 - A.l: H je podgrupou grupy G, protože (1) součet logaritmů je 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 1 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 cvičení 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 Oj*a; = n, pak podle věty 4 platí a^1 = ai, našli jsme inverzi k prvku a^, platí vlastnost (4). Ad cvičení 3.7 - 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. E.l: podgrupy jsou čtyři: a) celá Hiq generovaná prvkem 1 nebo prvkem 3 nebo prvkem 7 nebo prvkem 9; b) druhá triviální 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; E.3: < 6, 9 >= {6, 0,9, 3} vzhledem k operaci skládání otáčení. 90 13 VÝSLEDKY NĚKTERÝCH PŘÍKLADŮ E.7 modifikace: prvek [1,1] je generátorem podgrupy {[1; 1; ], [0; 2], [1; 3], [0; 0]} vzhledem ke sčítání. 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.3 Výsledky ke cvičení 4.1 — nekomutativní grupy Ad cvičení 4.1: Podle definice skládání zobrazení platí (1 2 3 4 5 6 7\ i i i i i i i 7 1 6 3 4 2 5 2 3 4 5 6 7 i i i i i i ; = [i ; i ; i ; 5 7 2 6 3 1 4 7 3 2 i 5 4 i i i i i ; V 6 7 3 2 1 5 4 J Ad cvičení 4.3: Tabulka operace o na množině D3 symetrií trojúhelníku: Tabulka 7: Tabulka operace o na množině D% symetrií trojúhelníku. o Rq Ri R2 Rs R4 R5 R0 Rq Ri R2 R3 R4 R5 Ri Ri R2 Rq R5 Rs R4 R2 R2 Rq Ri R4 R5 Rs R3 R3 R4 R5 Ro Ri R2 R4 R4 R5 R3 R2 Ro Ri R5 R5 r3 R4 Ri R2 Ro Pokud tuto tabulku porovnáme s tabulkou grupy (S3, o), je vidět, že mezi oběma grupami existuje izomorfismus, tj. příslušné tabulky operace se liší pouze přeznačením prvků: /(e) = R0, f(s) = Ei, f(t) = R2, f(u) = R3, f (v) = R4, f(w) = R5 (toto izomorfní přiřazení je vidět i na obrázku 7). Izomorfismus bude precizně definován v následující kapitole, ale už teď můžeme říci, že 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.4 Výsledky k přednášce 4.2 — Lagrangeova věta, homomor-fismus grup Ad cvičení F: Řád prvku a homomorfismus: 13.4 VÝSLEDKY K PŘEDNÁŠCE ?? - LAGRANGEOVA VĚTA, HOMOMORFISMUS GRUP 91 Ad Například N.l: Řád obrazuje 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 /, kde / není dělitelem k, tj. k = l ■ q + m, kde 0 < m < l. Označme ještě e\ neutrální prvek v grupě G\ = (G, v), e2 Je neutrální prvek v grupě G2 = (H, *). Celkem máme e2 = ^(ei) = p(ak) = V9(ař'9+m) = ^{ap * V(a)m = e2 * V(a)m, což je spor s tím, že řád prvku íp(a) není m, ale větší číslo /. Ad Například N.3: Nevím, jak přesně dokázat, ale nebude to těžké - snad stačí říci, že to plyne z předchozí větičky N.l a vlastnosti zachování operace u homomorfismu. Pokud zobrazíme generátor na generátor, obrazy všech ostatních prvků už jsou jednoznačně určeny. Důkaz: Když a je generátor cyklické podgrupy první grupy, íp(a) jistě také vygeneruje nějaké prvky svými mocninami, a podle větičky N.l jich bude tolik, že jejich počet dělí řád prvku a v první grupě. Ad Například N.4: 0 se v každém homomorfismu zobrazí na 0. Dále ©) je cyklická grupa generovaná např.prvkem 1. Tedy celý homomorfismus je jednoznačně určen, zadáme-li obraz generátoru 1. hom 01: 0 A 0, 1 A 0 ... pokud se generátor zobrazí na nulu, aby byla splněna podmínka homomorfismu, všechny další prvky se zobrazí na nulu. Jádrem je tedy celá množina Zs- hom 02: 0 A 0, 1 A 1 ... podle podmínky homomorfismu nyní dopočteme, že musí nastat 2 = 1 + 1 4 if(l) + if(l) = 2, dále 3 = 2 + 1 4 y?(2) + ^(1) = 2+1 = 3, atd. Jádrem je množina {0,4} hom 03: 0 A 0, 1 A 2 ... prvek 2 G Z4 generuje podgrupu {0,2}, tj. podle podmínky homomorfismu se 0, 2, 4, 6 zobrazí na nulu, a 1, 3, 5, 7 na dvojku, tj. jádrem je {0,2,4,6,}. hom 04: 0 4 0, 1 4 3 ... prvek 3 G Z4 generuje celou Z4, a tedy 0, 1, 2, 3 se postupně zobrazí na 0, 3, 2, 1, a pak už se obrazy zopakují: 4 —y 0, 5 —> 3, 6 —> 2, 7 —> 1. Jádrem je množina {0,4} grupy Z8. Ad Například N.2: (Zg,©) 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, [8] 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: 92 13 VÝSLEDKY NĚKTERÝCH PŘÍKLADŮ hom 01: y?i([0]) =id, = (1, 2, 3), a nyní už ^i([2]) = ^i([l]+ [!]) = (1,2,3) o (1,2,3) = (1,3,2); ^([3]) = V91([2] + [l]) = (l,3,2)o(l,2,3)=id; ^([4]) = ^([3] + [l]) = ido (1,2,3) = (1,2,3); ^i([5]) = ^i([4] + [l]) = (1,2,3) o (1,2,3) = (1,3,2); 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 02: v?i([0]) =id, ^i([l]) = (1, 3, 2), a nyní už