Algebra 1 (MA 0003) RNDr. Břetislav Fajmon, Ph.D. Katedra matematiky Pedagogické fakulty Masarykovy univerzity v Brně — verze 2024 3 Obsah 1 Týden 01: Základní vlastnosti operace na množině M 6 1.1 Cvičení 1: Vlastnosti číselných operací.................... 6 1.2 Cvičení 2: Určování vlastností různých operací................ 10 1.3 Přednáška 1................................... 12 1.4 Dodatky 1.................................... 22 2 Týden 02 - další vlastnosti operace na množině 27 2.1 Přednáška 2................................... 27 3 Týden 03 32 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy ......... 32 3.2 Přednáška 3: Izomorfismus, homomorfismus, Calyeho věta ......... 36 4 Týden 04 48 4.1 Cvičení 04: Nekomutativní grupy....................... 48 4.2 Přednáška 04: Grupa symetrií čtverce, Lagrangeova věta, faktorgrupa ... 49 4.3 Dodatky .................................... 53 5 Týden 05 59 5.1 Cvičení 05: Rád prvku, cyklické grupy, grupy zbytkových tříd ....... 59 5.2 Přednáška 05.................................. 70 6 Týden 06 77 6.1 Přednáška 06: struktury se dvěma operacemi................. 77 6.2 Cvičení 06: Algebraické struktury se dvěma binárními operacemi...... 85 7 Týden 07 87 7.1 Cvičení 07: Polynomy 01............................ 87 7.2 Přednáška 07: Přehled algebraických metod hledání kořene polynomu ... 88 8 Týden 08 98 8.1 Cvičení 08: Polynomy 02............................ 98 8.2 Přednáška 08: Přehled numerických metod hledání kořene polynomu .... 99 9 Týden 09 106 9.1 Cvičení 09: Polynomy 03............................106 9.2 Přednáška 09: Konstrukce číselných oborů..................106 9.2.1 Peanova množina............................106 9.2.2 Nástin této a následující přednášky intuitivně............108 9.2.3 Konstukce N ->■ Z..........................109 Algebra 1 (MA 0003) 4 10 Týden 10 111 10.1 Cvičení 10: Komplexní čísla 01.........................111 10.2 Přednáška 10: Konstrukce oborů Q, R, C...................111 10.2.1 Konstrukce Z ->■ Q..........................111 10.2.2 Konstrukce Q ->■ R .........................112 10.2.3 Konstrukce R ->■ C:.........................114 11 Týden 11 116 11.1 Cvičení 11: Komplexní čísla 02.........................116 11.2 Přednáška 11: Opakování a příprava ke zkoušce ...............116 12 Výsledky některých příkladů 125 12.1 Výsledky ke cvičení 1.1 - Opakování definic z předmětu Základy matematikyl25 12.2 Výsledky ke cvičení 1.2 - Určování vlastností různých operací.......126 12.3 Výsledky ke cvičení 3.1 - Vlastnosti grup, podgrupy a generátory grupy . . 127 12.4 Výsledky ke cvičení 4.1 - Nekomutativní grupy ...............129 12.5 Výsledky ke cvičení 5.1 - Rád prvku, cyklické grupy, grupy zbytkových tříd 129 5 Úvod Tato skripta jsou napsána jako doplňující text do předmětu Algebra 1 pro 2. semestr bakalářského studia budoucích učitelů matematiky na 2.stupni ZS. Předmět svým charakterem navazuje na témata předmětu MA0001 (Základy matematiky) a předpokládá, že studenti si budou pamatovat některé základní pojmy předmětu, které jsou shrnuty v otázkách 1 až 5 ke zkoušce v kapitole 11 tohoto textu. V předmětu Základy matematiky jsme studovali zejména relace a jejich vlastnosti. Nyní v předmětu Algebra 1 budeme studovat zejména pojem operace. Tento text by nemohl vzniknout bez knihy (Pinter 2010), ze které jsem podstatně čerpal jak pro přednášku, tak pro cvičení. I když tento předmět se studentům nutně bude zdát teoretický, Charles Pinter napsal svou knihu s přesvědčením, že algebra je pro matematiku potřebná - stejně potřebná jako geometrie. Rád bych zde vyjádřil díky za to, že studentka Andrea Danešová přepsala asi 50 stran tohoto textu z mého rukopisu do počítače v prostředí sazby textu TEX - jedná se o velmi pečlivý přepis, kde kromě velmi heslovitých poznámek z mé strany u některých přednášek se dobře zorientovala v tomto prostředí sazby tabulek a textů. Text není úplně samonosný, odkazuje se i na učební pdf text kolegyně dr. Budínové o polynomech, pro část „komplexní čísla" bude obohacením i středoškolská učebnice (Robova, Hála, Calda 2013). Břetislav Fajmon, verze textu květen 2024 Algebra 1 (MA 0003) 6 1 Týden 01: Základní vlastnosti operace na množině M 1.1 Cvičení 1: Vlastnosti číselných operací Podívejme se na tzv. Axiomy euklidovské geometrie: 1. Každé dva různé body lze spojit úsečkou. 2. Úsečku lze libovolně daleko prodloužit v přímku. 3. Pro dva různé body S, A lze sestrojit kružnici se středem v S, která prochází bodem A. 4. Přímý úhel lze kolmicí rozdělit na dva pravé úhly. 5. Bodem A, který neleží na přímce p, lze vést právě jednu přímku q rovnoběžnou s přímkou p. Tyto axiomy si budete ještě procházet v předmětu geometrie. Nyní si pouze všimněme toho, že axiomy udávají vztahy mezi jednotlivými geometrickými pojmy (ty jsou podtrženy), nebo vlastnosti některých pojmů (např. přímý úhel je speciální úhel, který lze rozdělit kolmicí na dva shodné pravé úhly ... vlastnost 4). Úkol cca na 10 min ve dvojicích. Přemýšlejte nad vlastnostmi známých operací sčítání, odčítání, násobení a dělení reálných čísel a pokuste se sestavit pět axiomů, které tyto operace splňují. Máte na to deset minut a poraďte se se sousedem (ve skupinkách o třech lidech). Axiomy pro počítání s čísly (které studenti znají ze střední školy) zhruba daly základ pro definice následujících vlastností, jež budou hrát klíčovou roli: Vlastnost (1) Uzavřenost množiny M vzhledem k operaci *: Vx, y G M : x * y G M. Vlastnost (1) je přirozená - chceme, aby operace na množině byly definované takovým způsobem, aby výsledek operace zase byl prvkem dané množiny. Vlastnost (2) Asociativita operace *: Vx, y, z G M : (x * y) * z = x * (y * z). Vlastnost (2) platí pro většinu operací, o kterých bude za chvíli řeč - jednoduše řečeno, několikanásobné použití jedné operace nezávisí na uzávorkování. Snad jen operace — a : nejsou asociativní. 7 Vlastnost (3) Existence jednotkového prvku vzhledem k operaci *: 3eGM:x*e = e*x = x Vx G M. Příklad pro vlastnost (3): jednotkový prvek vzhledem k operaci sčítání je 0 (někdy nazýván též nulový prvek, aby nedošlo k záměně s prvkem 1), jednotkový prvek vzhledem k operaci násobení je 1. Vlastnost (4) Existence inverzních prvků vzhledem k operaci *: Vx G M 3 x-1 G M : x * x-1 = x-1 * x = e. Příklad pro vlastnost (4): Pro číslo 2 je inverzním prvkem vzhledem k operaci sčítání číslo —2, vzhledem k operaci násobení číslo |. Uveďme nyní základní definice některých struktur, které splňují dané vlastnosti: Definice 1 Grupoid (M, *) ... množina M, na které operace * splňuje vlastnost (1); Definice 2 Pologrupa (M, *) ... množina M, na které operace * splňuje vlastnosti (1),(2); Definice 3 Monoid (M, *) ... množina M, na které operace * splňuje vlastnosti (1),(2),(3) (někdy též podle starší terminologie: pologrupa s jednotkou, pologrupa s jednotkovým prvkem); Definice 4 Grupa (M, *)... množina M s operací*, která splňuje na množině M vlast-nosti (1), (2), (3), (4). Kromě těchto čtyř základních struktur, které byly právě definovány, ještě řada operací splňuje vlastnost (5) - viz následující definice. Tato vlastnost (5) už do samotné definice stěžejního pojmu grupy není zahrnuta, protože jak uvidíme v následujících dvou kapitolách, existují význačné příklady grup, které ji nesplňují. Proto slovo „komutativní" musíme k právě definovaným strukturám zvlášť dodat jako novou vlastnost. Vlastnost (5) Operace * se nazývá komutativní na množině M, pokud platí vlastnost (5): Vx, y E M : x * y = y * x. Definice 5 (M, *) se nazýva komutativní grupoid, pokud je grupoid a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Definice 6 (M, *) se nazývá komutativní pologrupa, pokud je pologrupa a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Definice 7 (M,*) se nazývá komutativní monoid, pokud je monoid (tj. pokud je pologrupa s jednotkou) a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Algebra 1 (MA 0003) 8 Definice 8 (M, *) se nazýva komutativní grupa, pokud je grupa a operace * splňuje vlastnost (5), tj. je komutativní na množině M. Při přemýšlení nad základními vlastnostmi operací sčítání a násobení lze ještě najít často axiom, který si všímá „interakce" = vzájemného vztahu mezi těmito dvěma operacemi: interakce operací + a • splňuje tzv. distributivní zákon = vlastnost (6) : V x,y, z 6 M : x ■ (y + z) = x ■ y + x ■ z, (y + z) ■ x = y ■ x + z ■ x. Název „distributivní" lingvisticky odpovídá tomu, že po odstranění závorek se prvek x rozdělí = distribuuje k oběma členům součtu. Matematicky se jedná o pravidlo násobení závorky, ve které se nachází „součet" prvků, kde „součet" je operace s nižší prioritou než násobení. Například známá operace sčítání reálných čísel má nižší prioritu než násobení reálných čísel: 8 + 2 • 3 = 14, tj. operace • váže jednotlivá celá čísla s větší prioritou než je tomu u sčítání a odčítání (a pokud bychom chtěli nejprve sečíst čísla 8 a 2, a teprve pak výsledek vynásobit třemi, musíme díky větší prioritě násobení užít pro sčítání závorky). Axiom (6) lze formulovat pro různé dvojice operací, tj. obecně bychom měli psát, že distributivní zákon mezi operacemi * a y je V x, y, z £ M : x * (y X/ z) = (x * y) X/ (x * z), (y v z) * x = (y * x) V (z * x)- To, že rovnice distributivity jsou dvě, musíme mít na mysli tam, kde operace * není komutativní, tj. nesplňuje vlastnost (5). Určitě si zopakujte ty nej důležitější pojmy předmětu Základy matematiky: Úloha 1.1 Uvedte definice následujících základních pojmů z předmětu Základy matematiky a u každé uveďte příklad: a) množina; b) kartézský součin; c) relace d) ekvivalence; e) uspořádání; f) zobrazení; g) operace; h) (reálná) posloupnost; 9 i) (reálná) funkce. Úloha 1.2 Uveá'te násleáující áefinice vlastností relací a u kažáé z nich uveá'te příklaá: • Relace p na množině M je reflexivní , káyž ... • Relace p na množině M je symetrická, káyž ... • Relace p na množině M je tranzitivní, káyž ... • Relace p na množině M je úplná, káyž ... • Zobrazení f z X áo Y je taková relace na X x Y, že platí ... Definice z obou úloh najdete v textu Základy matematiky. Úloha 1.3 V množině celých čísel je áefinována operace o přeápisem xoy = x + y — xy. Zjistěte, záa operace o je: a) neomezeně áefinovaná, b) komutativní, c) asociativní. Dále zjistěte, záa množina Z vzhleáem k operaci o obsahuje prvek neutrální a přípaáně, ke kterým celým číslům existují prvky inverzní. Úloha 1.4 V množině M = {0,2,3,4} je áefinována operace o vztahem x o y = (x — l)(y — 1). Zjistěte, záa je operace neomezeně áefinovaná. Sestavte operační tabulku. Úloha 1.5 V množině A = {x,y} jsou áány operace A, □ tabulkami. Určete všechny vlastnosti uveáených operací. A x y X x x y x y □ x y X x y y y x Úloha 1.6 Na množině K = {1, 2, 3} je áefinovaná operace Určete její vlastnosti. 1 2 3 1 3 1 2 2 1 2 3 3 1 3 1 Úloha 1.7 Na množině Z je áefinována operace —. Určete její vlastnosti. Algebra 1 (MA 0003) 10 Úloha 1.8 V množině Q je definována operace o takto: a o b = 2a + 2b — 5. Pro operaci určete neomezenou definovanost, komutativnost, asociativnost, neutrální prvek] a ke kterým prvkům množiny existují prvky inverzní. Úloha 1.9 V množině R je definována operace o takto: x o y = x1 + y2. Pro operaci určete neomezenou definovanost, komutativnost, asociativnost, neutrální prvek, a ke kterým prvkům množiny existují prvky inverzní. Výsledky některých cvičení najdete v závěru textu v oddílu 12.1. 1.2 Cvičení 2: Určování vlastností různých operací Úloha 1.10 Zjistěte, jaké struktury vzhledem k uvedené známé operaci (běžné označení) jsou následující množiny: a) (N,+). b) (Z,+). c) (Z,-). d) (Q,-), (R,-). e) (Q-{0},-), (Ä-{0},-). f) (2A, U), kde A = {a, b, c, d, e} je pětiprvková množina. g) (2A, n), kde A = {a, b, c, d, e) je pětiprvková množina. h) (Z,-), (Z,:). i) (M, +), kde M = {-100, -99, -98,..., -1, 0,1, 2,..., 99,100}. Úloha 1.11 Opakování definic a práce s nimi a) Nadiktujte sousedovi v lavici definici grupy a on ji zapíše zkráceným matematickým zápisem, ve kterém se nevyskytuje ani jedno české slovo, kromě slova „grupa". b) Co to znamená, že (M, *) není grupoid, tj. není splněna vlastnost (1)? Negujte vlast- nost (1). c) Co to znamená že není splněna vlastnost (4) z definice grupy? Negujte vlastnost (4). Úloha 1.12 a) Uveďte definici vlastnosti (4) pro operaci XJ na množině M ve stručném matematickém zápisu. b) Uveďte příklad struktury (M,\/), která splňuje vlastnost (4). c) Uveďte příklad struktury (M,\/), která NEsplňuje vlastnost (4). 11 Úloha 1.13 Dokážte, že množina všech podmnožin tŕíprvkové množiny s operací symetrického rozdílu 4- je grupa (viz Pinter 2010, str. 30, oddíl C). Úloha 1.14 V množině M = {1, 2} je operace V tabulkou: V 1 2 1 1 1 2 1 2 Určete typ algebraické struktury (M, V). Úloha 1.15 V množině M = {a, b, c} je operace A tabulkou: A a b c a c a b b a b c c b c a Určete typ algebraické struktury (M, A). Úloha 1.16 Určete typ algebraické struktury: (N — {0}, *), kde x * y = xv. Úloha 1.17 Určete typ algebraické struktury: (R+, o), kde x o y = ^Jxy. Výsledky některých cvičení najdete v závěru textu v oddílu 12.2. Algebra 1 (MA 0003) 12 1.3 Přednáška 1 Poznámka na úvod: První přednáška tohoto textu nepoužívá všechny pojmy a definice z prvního cvičení záměrně, protože je možné, že se bude konat před prvním cvičením. A pokud je použije, doporučuji je při prvním čtení ignorovat a vrátit se k nim až po absolvování příkladu 6 přednášky 2. Vlastní text přednášky: Algebra je nauka o řešení rovnic1. Proto bychom mohli zmínit, co je to rovnice s neznámou x na množině M, na níž je definována operace v: • Rovnost je relace ekvivalence na množině výrazů, ve kterých vystupují prvky množiny M a operace V- Příklad: běžně rovnost na množině reálných čísel chápeme jako relaci ekvivalence na množině výrazů, v nichž vystupují reálná čísla, reálné funkce a známé operace s reálnými čísly. • Rovnítko je symbol relace rovnosti. • Rovnice s neznámou x na množině M je výroková funkce, ve které vystupuje neznámý prvek x, symbol rovnosti (rovnítko), prvky množiny M nebo výrazy na množině M. Jak víme, výroková funkce není výrokem, protože bychom museli dosadit za x, abychom dostali výrok pravdivý či nepravdivý. • Řešit rovnici s neznámou x na množině M znamená najít obor pravdivosti2 K všech prvků z množiny M, pro které se stává daná rovnice pravdivým výrokem. Podívejme se na některé jednoduché příklady: a) Specifikace množiny M je také pro řešení rovnice důležitá. Například rovnice 7 + x = 2 nemá řešení na množině přirozených čísel (tedy tato rovnice nemá řešení na monoidu (No, +))!! Nebo rovnice 7-x = 2 nemá řešení na množině celých čísel (tj. na monoidu (Z,-)). Tj. vidíme, že už na monoidech (strukturách s jednou operací) některé rovnice nemají řešení!! Nebo rovnice x2 - 2 = 0 nemá řešení na množině racionálních čísel (v této rovnici uvažujeme současně výrazy s operací sčítání (odčítání) i násobení, hledáme tedy řešení na tělese (Q, +, •)). b) Ve většině tohoto textu se budeme zabývat rovnicemi s výrazy, ve kterých vystupuje jediná operace, a množina, na které budeme řešení rovnice hledat, bude zpravidla grupa nebo monoid vzhledem k této operaci. Oběma operacemi současně (tedy algebraickými strukturami se dvěma operacemi) se budeme zabývat až v kapitole 5. 1 Arabské ,,'al gebr" znamenalo „složit" rovnici, tj. vyřešit ji = nalézt její řešení - Viz úvod knihy Pinter 2010. Zejména se jedná o polynomické rovnice, kterými se budeme zabývat ve druhé polovině semestru. 2K označuje tzv. množinu kořenů dané rovnice na množině M. 13 Až dosud (v prvním týdnu) byly uvedeny různé axiomy operací, se kterými se v matematice setkáváme (operací sčítání, násobení čísel, operace průniku a sjednocení množin). Zkusme se nyní odpoutat od konkrétních operací, které známe. Podobně jako v předmětu Základu matematiky jsme se odpoutali od relací „menší nebo rovno", „je dělitelem" a „je podmnožinou" a studovali obecně vlastnosti uspořádaných množin, tj. množin, na nichž je definována relace reflexivní, antisymetrická a tranzitivní, nyní se na chvíli odpoutáme od konkrétních operací a budeme studovat obecně vlastnosti grupy - tj. vlastnosti množiny, na níž je definována operace *, jež splňuje vlastnosti (1), (2), (3), (4). Začněme ovšem jedním příkladem konečné, šestiprvkové grupy: Příklad 1 Grupa pootočení hodinové ručičky. Uvažujme čísla 0 až 5 rozmístěna po obvodu kružnice (např. obvodu ciferníku hodin) tímto způsobem (viz obrázek): Číslo 0 se nachází tam, kde se obyčejně na hodinách vyskytuje číslo 12. Dále čísla 1 až 5 jsou společně s nulou rozmístěna rovnoměrně po obvodu kružnice tak, že úhel určený středem kružnice a rameny procházejícími dvěma sousedními čísly je 60° neboli |. Dále se budeme zabývat množinou pootočení jedné ručičky s osou otáčení ve středu kružnice: • prvek 0 představuje nulové pootočení ručičky - s ručičkou se nic nestane; • prvek 1 představuje pootočení o jednu jednotku, tj. o 60 °; • prvek 2 představuje pootočení ručičky o dvě jednotky, tj. o 120 °; • prvek 3 přestavuje pootočení o 180 °; • prvek 4 přestavuje pootočení o 240 °; • 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 Algebra 1 (MA 0003) 14 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) +43, dostaneme prvek 1 stejně jako při postupu 1 + (2 + 4) - složením těchto tří pootočení dostaneme vždy úhel 420°, po jehož aplikaci ručička ukazuje na prvek 1. Tedy skládání pootočení nezávisí na jejich uzávorkování4. 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ým když jej složíme, dostaneme ručičku zase do polohy 0: • inverzí k 0 je opět 0; • inverzí k 1 je 5 - a naopak, inverzí k 5 je 1; • inverzí k 2 je 4 - a naopak, inverzí k 4 je 2; • inverzí k 3 je opět 3. Tedy celkem naše množina pootočení (označme ji Hq = {0,1,2,3,4,5}) vzhledem k operaci skládání pootočení je grupa = operace + na ní definovaná splňuje vlastnosti (1) až (4). Protože Hq je konečná množina, lze si výsledky operace + napsat do tabulky: Tabulka 1.1: Tabulka operace + na množině Hq. + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 3Operaci 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. 4Dokonce 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. 15 Danou tabulku operace * konstruujeme tak, že na průsečíku řádku prvku x a sloupce prvku y se vyskytuje výsledek operace x * y (a této logiky konstrukce tabulek operací se budeme držet v celém textu): * y X x * y Máme-li k dispozici úplnou tabulku operace * na množině m, máme při zjišťování vlastností operace vyhráno. Jak lze nahlédnout v tabulce 1.1, vlastnosti (1), (2), (3), (4) operace + na množině Hq lze všechny z této tabulky vyčíst. Dále nás může zajímat, zda existují nějaké podmnožiny množiny Hq uzavřené vzhledem k operaci skládání pootočení. Vlastnost (1) je splněna na následujících podmnožinách: • P1 = {0} - triviální podmnožina množiny Hq - podmnožina obsahující pouze neutrální prvek je vždy uzavřená na výsledek operace; • P2 = Hq - triviální podmnožina množiny Hq - tato podmnožina je také vždy uzavřená na výsledek operace; • ^3 = {0,3}; • P4 = {0, 2, 4} - výsledky operace sčítání na této podmnožině znázorňuje tabulka 1.2. Tabulka 1.2: Tabulka operace + na podmnožině {0, 2, 4}. + 0 2 4 0 0 2 4 2 2 4 0 4 4 0 2 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ů. • Definice 9 Triviální podgrupy (= nevlastní podgrupy) grupy (G, v) se nazývají dvě podgrupy: a) S± = {n} je podgrupou vzhledem k \/, která obsahuje pouze neutrální prvek (je neprázdná a splňuje (1) a (4)), b) S2 = G (samotná celá grupa je též podgrupou sama sebe). Každou jinou podgrupu nazveme vlastní podgrupou grupy (G, v)- Algebra 1 (MA 0003) 16 Příklad 2 Prozkoumejte vlastnosti operace sčítání na množině celých čísel. Z je nekonečná množina, proto by tabulka výsledků operace + obsahovala nekonečně mnoho výsledků. Můžeme ji však naznačit alespoň pro několik prvků množiny: Tabulka 1.3: Tabulka operace + na množině Z. + ... -2 -1 0 1 2 ... -1 ... -3 -2 -1 0 1 ... -2 ... -4 -3 -2 -1 0 ... 0 ... -2 -1 0 1 2 ... 1 ... -1 0 1 2 3 ... 2 ... 0 1 2 3 4 ... Vidíme, že všechny výsledky operace budou z množiny Z, jelikož sečtením dvou celých čísel získáváme opět číslo celé. Množina Z s operací sčítání tedy splňuje vlastnost (1). Splněna je rovněž vlastnost (2), jelikož operace sčítání je na množině celých čísel asociativní. 0 je neutrálním prvkem, platí tedy vlastnost (3). Každý prvek množiny celých čísel má svůj inverzní prvek (platí vlastnosti (4)): • inverzí k 0 je opět 0; • inverzí k 1 je —1 - a naopak, inverzí k —1 je 1; • inverzí k 2 je —2 - a naopak, inverzí k —2 je 2; • inverzí k 3 je —3 - a naopak, inverzí k —3 je 3; • inverzí k 4 je —4 - a naopak, inverzí k —4 je 4; • atd. Vidíme, že na struktuře (Z, +) jsou splněny vlastnosti (1) až (4). Můžeme se opět podívat také na podmnožiny množiny celých čísel, které jsou uzavřené na výsledky operace sčítání: • Pi = {0} je triviální podmnožina obsahující pouze neutrální prvek; • P2 = Z je triviální podmnožina množiny celých čísel. 17 • existují i netriviální podmnožiny uzavřené na výsledky operace sčítání, ale jsou nekonečné: - P3 = {...- 9, -6, -3, 0, 3, 6, 9,12,... }; - P4 = {••• -2,0,2,4,...}; - atd. Podmnožin množiny Z uzavřených na operaci sčítání je tedy nekonečně mnoho. • Příklad 3 Označme (F(R),o) množinu všech funkcí (= zobrazení R —> R, viz předmět Základy matematiky) s operací skládání funkcí. Prozkoumejte vlastnosti této operace na množině všech funkcí. Operace skládání funkcí o čteme jako „po", což nám napovídá, jak získáme výsledky dané operace: ex+3 o smx = esmx+3 sinx o ex+s = sín(ex+s) ex+3 D ex+3 = ee*+3+3 x5 ox5 = x25 Můžeme vidět, že když zaměníme pořadí funkcí, se kterými provádíme operaci skládání, dostáváme různé výsledky. Skládání funkcí tedy není komutativní. Stejně jako v předchozím příkladě, i tentokrát se jedná o nekonečnou množinu. Můžeme tedy opět naznačit tabulku výsledků operace skládání pouze pro část prvků dané množiny. Tabulka 1.4: Tabulka operace o na množině F(R). o gX+3 sinx X5 ex+3 eex+3+3 „sinx+3 e ex5+3 ... sinx ... sin(ex+s) sin(sinx) sín(x5) ... x5 . .. (ex+3f (sinx)5 x25 Neutrálním prvkem vzhledem ke skládání funkcí je funkce fix) = x, kterou můžeme označit id{x). Platí: sinx o id{x) = sinx Algebra 1 (MA 0003) 18 idix) o sinx = sinx idix) o íd(x) = idix) atd. Skládání funkcí, potažmo jakýchkoli zobrazení, je asociativní operace: (/ o g) o h(x) = (/ o g)(h(x)) = f{g{h{x))) = f o (g(h(x))) = f o (g o h)(x). Jsou tedy splněny vlastnosti (2) a (3). Složením dvou reálných funkcí získáme opět reálnou funkci, takže vlastnost (1) platí také. Naopak vlastnost (4) platit nebude, protože aby platila, musela by ke každé reálné funkci existovat funkce inverzí. Stačí najít nějaký protipříklad, kterým je např. funkce f(x) = x2. • Příklad 4 Důležitým příkladem grupy, na kterou se nyní zaměříme blíže, je grupa bijekcí n-prvkové množiny na sebe sama, kde operací je skládání zobrazeni'. Často se jí též říká grupa permutací - označení opravdu má blízko ke středoškolskému pojmu permutace, kdy např. permutace 5-prvkové množiny {1,2,3,4,5} byla chápána jako určité pořadí všech jejích prvků, např. pořadí 51324. Nyní budeme na tyto permutace pohlížet jako na zobrazení, které základní vzestupné pořadí 12345 přemění na pořadí např. 51324. Permutace n—prvkové množiny je bijekce množiny {1,2,..., n} na sebe sama. Sn je množina všech permutací tohoto typu. Například permutace / : M —> M pro M = {1, 2, 3,4, 5} definovaná 1 2 3 4 5 \ \~ 4' 4' 4' 4' I 5 1 3 2 4 / je bijektivní, takže existuje permutace /_1 k ní inverzní 1 2 3 4 5 \ t t t t t 5 1 3 2 4 / Důležité úsporné označení permutace V dalším textu budeme permutace zadávat úspornějším způsobem, který napíše každé číslo jen jednou, nikoli dvakrát. V tomto úsporném označení budeme permutaci / 1 2 3 4 5 \ /= li i i i i \ označovat jako / = (1,5,4,2) \ 5 1 3 2 4 / (v tomto označení se jedná o uzavřený cyklus zobrazení: 1 se zobrazí na následující zapsané číslo, tj. 5, číslo 5 se zobrazí na 4, číslo 4 na 2 a poslední zapsané číslo v závorce se zobrazí 5Až do konce této přednášky se všechny informace týkají tohoto příkladu. 19 na první číslo 1, a tím se cyklus uzavře!!). Číslo 3 není v zápise uvedeno, protože se zobrazením / nemění, tj. /(3) = 3. Podobně permutaci / 1 2 3 4 5 \ /_1 = ( T T T T T J budeme vyjadřovat jako /_1 = (1,2,4,5) \ 5 1 3 2 4 / (tj. změnil se změr cyklu, veškeré zobrazování otočilo směr; mohli bychom zapsat i /_1 = (2,4,5,1), protože nezáleží na tom, které číslo je v uzavřeném cyklu jako první; stále se jedná o stejný prvek: f'1 = (1, 2,4, 5) = (2,4, 5,1) = (4, 5,1, 2) = (5,1, 2, 4); a protože nezáleží na pořadí prvků v cyklu, zavedeme další úmluvu, a sice první prvek každého cyklu napíšeme to nej menší možné číslo). Operace skládání permutací Protože permutace je zvláštní případ zobrazení a zobrazení M —>■ M lze skládat za sebou, můžeme mluvit o operaci „skládání zobrazení", respektive „skládání permutací". • označení: o ... (čti „po") operace skládání zobrazení, ve které je nejdříve aplikováno druhé zobrazení v pořadí, a pak první - proto i čtení tohoto symbolu pomocí předložky „po" je zcela instruktivní; Ilustrujeme situaci pro n = 3: Uvažujme množinu permutací tříprvkové množiny {1, 2, 3} do sebe - označme ji S3. Množina S3 má šest prvků: e := id (tímto symbolem budeme označovat identické zobrazení, jež zobrazí všechny prvky na sebe sama, tj. 1 na 1, 2 na 2 a 3 na 3), s := (1, 2, 3) (pozor, neplést s identitou, u této permutace v souladu s úsporným označením platí s(l) = 2, s(2) = 3, s(3) = 1), t := (1, 3, 2) (pozor, (3, 2,1) a (2,1, 3) je pořád stejný prvek t, ve kterém r(l) = 3, r(3) = 2, í(2) = 1), u := (2,3) (u(2) = 3, u(3) = 2, u(l = 1)), a nakonec v := (1,3), w := (1,2). Permutací tříprvkové množiny je tedy šest. Tyto permutace lze skládat, výsledkem složení je zase permutace tříprvkové množiny: například soe = (l,2,3)oid= (1,2,3) = s nebo uov = (2,3) o (1,3) = (1,2,3) = s (všimněte si, že zobrazování skládáme ZPRAVA DOLEVA, tj. 1 se zobrazí na 3, pak v levé permutaci 3 na 2, tj. celkem 1 na 2; dvojka v permutaci psané napravo není, tj. zobrazí se na sebe sama, složením s permutací vlevo se zobrazí na 3, celkem tedy 2 se zobrazí na 3; a konečně 3 se v permutaci napravo zobrazí na 1, v levé permutaci se 1 zobrazí na sebe sama, tj. celkem 3 na 1) nebo v o u = (1,3) o (2,3) = (1,3, 2) = t. Algebra 1 (MA 0003) 20 Čili z posledních dvou příkladů je vidět, že v o u ^ u o v, tj. operace o je nekomutativní (neplatí vlastnost (5))! Propočítáním všech možných 36 kombinací dostaneme přehlednou tabulku výsledků operace o: Nejprve je potřeba říci, že u každé tabulky operace * na konečné množině prvků je prvek x v levém sloupcovém záhlaví vybrán jako první a prvek y v horním řádkovém záhlaví jako druhý6. Tedy konkrétně u operace o na množině 63 dostaneme tabulku operace: Tabulka 1.5: Tabulka operace o na množině 63. 0 id (1,2,3) (1,3,2) (2,3) (1,3) (1,2) id id (1,2,3) (1,3,2) (2,3) (1,3) (1,2) (1,2,3) (1,2,3) (1,3,2) id (1,2) (2,3) (1,3) (1,3,2) (1,3,2) id (1,2,3) (1,3) (1,2) (2,3) (2,3) (2,3) (1,3) (1,2) id (1,2,3) (1,3,2) (1,3) (1,3) (1,2) (2,3) (1,3,2) id (1,2,3) (1,2) (1,2) (2,3) (1,3) (1,2,3) (1,32,) id Z tabulky je vidět, že operace je uzavřená na množině S3, tj. platí vlastnost (1). Asociativita (2) platí pro skládání jakýchkoli zobrazení, viz příklad 3. A nakonec, je splněna i vlastnost (4), protože: jednotkový prvek id je (jako každý jednotkový prvek v grupě) inverzní sám k sobě; z tabulky dále vidíme, že (1,2,3)_1 = (1,3,2), (1, 3, 2)_1 = (1, 2, 3), a prvky (2, 3), (1, 3), (1, 2) jsou inverzemi sebe sama! Dále existuje šest podgrup grupy (63, o): tzv. triviální podgrupa, která obsahuje pouze jednotkový prvek id, s tabulkou operace 0 id id id další podgrupou je celá šestiprvková grupa (63, o) samotná. Kromě těchto dvou extrémně malých nebo velkých podgrup existují též tři dvouprvkové podgrupy 0 id (2,3) 0 id (1,3) 0 id (1,2) id id (2,3) , id id (1,3) , id id (1,2) (2,3) (2,3) id (1,3) (1,3) id (1,2) (1,2) id 6Toto je klíčově důležitá domluva, řečená už výše. Pořadí hraje roli právě u tohoto příkladu, kdy se jedná o operaci nekomutativní, tj. na pořadí prvků do operace vstupujících záleží. 21 a jedna tříprvková podgrupa s tabulkou operace o id (1,2,3) (1,3,2) id id (1,2,3) (1,3,2) (1,2,3) (1,3,2) (1,2,3) id (1,3,2) (1,3,2) id (1,2,3) K čemu je dobrá grupa permutací 63? Má i svůj geometrický význam, tj. lze ji použít při popisu některých základních geometrických zobrazení, například bijektivních zobrazení trojúhelníku na sebe sama (tzv. symetrií trojúhelníku, odtud i původ písmene S v označení množiny), kterých je také šest, stejně jako prvků množiny S3 - jedná se o tři otočení a tři osové souměrnosti. Každé z těchto geometrických proměn (= transformací) trojúhelníku lze přiřadit jednu permutaci jeho tří vrcholů. Obrázek 1.1: Množina D3 permutací odpovídajících symetriím trojúhelníku. Algebra 1 (MA 0003) 22 1.4 Dodatky 1 V této části jsou uloženy součásti textu, které možná nebudou probrány - některé obecné důkazy, některé teoretické věci jsou zde „matematicky přesněji vyloženy". Studenti by měli z těchto dodatkových částí vědět definice, a pak jen to, co jim speciálně zdůrazní vyučující, respektive co se na přednášce stihne probrat. 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ů?7 Věta 1 (o jednoznačnosti neutrálního prvku) V každé grupě (G, y) existuje jediný neutrální prvek. Důkaz: Sporem: předpokládejme, že v grupě existují dva různé neutrální prvky n\ a ni takové, že n\ ^ ni. Jaké z toho plynou vlastnosti těchto dvou prvků? Klíčová myšlenka: pokud je prvek neutrální, tak nemění výsledek operace v vůči jakémukoli dalšímu prvku, tj. např. g y ni = 9- Mohlo by tedy být zajímavé, co se stane, když aplikujeme operaci na dané dva neutrální prvky ni, niS: (3)2 (3)! což je spor s tím, že oba neutrální prvky jsou navzájem různé9. □ Tak to je zajímavé, neutrální prvek grupy může být pouze jeden jediný. A jak je to s inverzními prvky grupy? Víme, že v grupě existuje inverze ke každému prvku vzhledem k operaci v ~~ musí také ke každému prvku existovat jediná inverze? Mohli bychom najít v grupě nějaký prvek, ke kterému existují inverze dvě? Věta 2 (o jednoznačnosti inverzních prvků) V každé grupě (G, y) existuje ke každému prvku x jediný inverzní prvek x_1 vzhledem k operaci y. 7Ví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? 8Vlastnost (3)i znamená, že využíváme vlastnosti (3) pro prvek n\, vlastnost (3)2 platí pro neutrální prvek U'2- 9Celý důkaz je možné formulovat i jako přímý důkaz typu 2: předpokládáme, že prvky n\, ri2 oba se chovají jako neutrální, tj. uvedené odvození by o nich dokázalo, že se musí nutně rovnat - tj. z toho plyne přímo, že prvek neutrální je pouze jeden. 23 Důkaz: Předpokládejme opět, že k nějakému prvku a E G vykazují dva prvky a1 , aX1 vlastnost inverze, tj. platí a y o-i1 = n, A aX1 XJ a = n (musí platit oba vztahy, protože o operaci v zatím nevíme, zdaje komutativní) a současně a y a-21 = ni A aX1 XJ a = n. Klíčová myšlenka: vynásobením10 aX1 xj aX1 pravděpodobně nic nezískáme. Prvky aľ/1, aX1 vystupují ve vlastnosti (4), tj. měli bychom studovat něco jako rovnice ve vlastnosti (4). VYUŽIJEME TOHO, ŽE VE VLASTNOSTI (4) SE VYSKYTUJÍ DVĚ ROVNOSTI, A JEDNU APLIKUJEME NA PRVEK a ZLEVA, DRUHOU ZPRAVA: -1 (3) _ -1 (4)i / -i \ _ -1 (2) -i / „ -U (4)2 _i _ (3) _! a2 = nxj a2 = {a1 XJ a) XJ a2 = a1 xj [a xj a2 j = a1 XJ n = a1 . Využili jsme platnosti asociativního zákona (2) pro kaskádu tří prvků uprostřed spojených operací xj. Z uvedené kaskády rovností je vidět, že prvky aX1 a a2x musí nutně být stejné. Důkaz je hotov - inverzní prvek k prvku a existuje v grupě právě jeden. □ Věta 3 (můžeme „krátit"11 v rovnostech, ve kterých se vyskytují prvky grupy G a operace XJ?) V kažáé grupě (G, Xj) platí zákony o krácení (7), tj. Va, b,c G G : (axjb = axjc^-b = c) A (bxja = cxja^-b = c). Důkaz: Provedeme například pro první z implikací: Vztah a XJ b = a XJ c rozšíříme zleva aplikací inverzního prvku na obě strany rovnice (to je vlastně vlastnost anti-(7), která ovšem plyne z vlastnosti (1): „vynásobením" téhož prvku grupy G (který je na obou stranách rovnice) dostaneme opět prvek grupy G: a-1 xj axj b = a-1 • a XJ c, a s využitím asociativity (2) (v grupě nezáleží na uzávorkování „součinu" tří prvků vzhledem k operaci xj), vlastnosti inverzí (4) a vlastnosti neutrálního prvku (3) dostaneme b = c. Důkaz druhé nerovnosti bychom museli provádět vynásobením obou stran rovnice zprava, abychom mohli aplikovat vlastnost inverzí (4). □ Příklad 5 Určete algebraické vlastnosti struktury (Zq, •). Algebra 1 (MA 0003) 24 Tabulka 1.6: Tabulka operace • na množině Z§. [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] Začneme tím, že si sestavíme tabulku výsledků operace: Když máme nyní sestavenou tabulku výsledků operace • na množině Zq, můžeme s její pomocí určit vlastnosti dané struktury: V tabulce jsou pouze prvky množiny Zq, je tedy splněna vlastnost (1). Z tabulky sice nepoznáme, zda je operace • asociativní, ovšem obecně platí, že tato operace asociativní je, takže vlastnost (2) platí také. Neutrálním prvkem je [1], je tedy splněna i vlastnost (3). Vlastnost (4) však splněna není, jelikož prvky [0], [2], [3] a [4] nemají inverzní prvek. Vlastnost (5) platí, což vidíme z tabulky, jelikož je souměrná podle hlavní diagonály. Dohromady je tedy (Zq, •) komutativní monoid. Můžeme si všimnout, že v této struktuře nemůžeme provádět krácení podle věty 3. Např. z tabulky vidíme, že [2] • [2] = [2] • [5], ovšem [2] ^ [5]. Uvedená struktura totiž nesplňuje vlastnost (4), není tedy grupa.* Věta 4 (o vzájemně inverzních prvcích) V kažáé grupě (G, v) z rovnosti axj b = n (káe n je neutrální prvek) plyne, že platí a-1 = b, a současně = a (teáy prvek b je inverzní k prvku a, a současně prvek a je inverzním prvkem k prvku b). Důkaz: je prostý, neboť plyne z věty 2: pokud b vykazuje vlastnosti inverze (4), tak musí být inverzní k prvku a, protože více inverzních prvků k danému prvku v grupě být 10Všimněte si, že říkám „vynásobením", ikdyž nyní nestudujeme operaci násobení, ale operaci y ... 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 y na dané prvky v daném pořadí, tj. na uspořádanou dvojici prvků ... nOpět terminologie: i když mluvíme obecně o operaci y, pro vlastnost (7) se vžil termín „zákony o krácení", třebaže krácení je termín vzatý z rovností, ve kterých se vyskytuje běžná operace násobení. 25 nemůže. Další možnost důkazu: pokud rozšíříme rovnost a XJ b = n prvkem a 1 zleva, dostaneme -1 . -1 (3) -1 a y a y b = a y n = a , po aplikaci vlastnosti (4) na první výraz dostaneme b = a-1. □ Věta 5 (o výpočtech inverzních prvků) V každé grupě (G, y) platí: i) (a y = V a_1 (inverze součinu dvou prvků je součin jejich inverzí, ale v opačném pořadí!!!); ii) (a-1)-1 = a (inverzí k inverzi je původní prvek). Důkaz: ad i) Přímo ověřením vlastnosti (4) pro prvky a y b a v a_1; a V b V V a_1) — a V (fr V V a_1 — a V n V a_1 — a V a_1 — n- Protože nevíme, zda operace v Je komutativní, měli bychom ověřit i druhý za zákonů (4), tj. upravovat výraz (V1 y a"1) V a V b analogickým způsobem se v něm „vyruší" nejprve a-1 XJ a, a pakfo-1 y b a dostaneme opět pouze n. ad ii) Z rovnosti a XJ a-1 = n a věty 4 o vzájemné inverzi máme (a-1)-1 = a. □ Definice 10 Rád konečné grupy se nazývá počet jejích prvků, označujeme \G\. Označení počtu prvků je standardní, nazývat tento počet prvků řádem je poněkud bizarní, ale má jakési opodstatnění u cyklických grup. Rozšíření vlastnosti (2) na k prvků Ve větě 5 se vyskytuje „součin" čtyř prvků za sebou - přesně pracující matematik by měl prozkoumat, zda se nedopouští při důkazu něčeho, co není definováno. Pokud definujeme součin čtyř prvků vzhledem k operaci VJako součin prvního prvku se součinem následujících tří prvků, tj. a y 0 Vc Vá), postupným užitím vlastnosti (2) pro tři prvky dostaneme a y 0 V c) V d = a y b y (c V d) = {a y b) v (c V d) = {a y b) v c v d a jedná se stále o týž výsledek. „Součin" čtyř prvků je tedy definován korektně a platí pro něj vlastnost (2)' ... v sekvenci třikrát za sebou použité operaci y nezáleží na Algebra 1 (MA 0003) 26 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í v v řetězci za sebou, například analogii části (a) věty 5: (ai y «2 V • • • V afc)_1 == ak1 V ak-i V • • • V a-21 V ai"1-Dále pro nás bude užitečná například definici n-té mocniny vzhledem k operaci V: Definice 11 n-tá mocnina prvku a grupy (G, v) se definuje jako prvek získaný v řetězci operací o" := a y a y ■ ■ ■ V fl • N-*-' n-krát A pokud už máme definovanou mocninu, má smysl ptát se, zda existují odmocniny, a sice v následujícím smyslu: Definice 12 n-tá odmocnina prvku a grupy (G, v) Je takový prvek x G G (pokud tedy existuje), že a = xn. Definice 13 zápornou odmocninu a-5 grupy (G, v) definujeme jako pátou mocninu jejího inverzního prvku, tj. a-5 := (a-1)5. 27 2 Týden 02 — další vlastnosti operace na množině 2.1 Přednáška 2 Podgrupa (S, y) grupy (G, y) Zabývejme se nyní otázkou: kdy je neprázdná podmnožina S grupy (G, y) také grupou? Definice 14 Podgrupa (S, y) gruPy (G, y) Je taková neprázdná podmnožina S množiny G, která je uzavřená vzhledem k operaci y (vlastnost 1) a s každým prvkem a obsahuje i jeho inverzi a-1 (vlastnost 4)- Kupodivu se ukazuje, že dané dvě vlastnosti (1), (4) neprázdné12 podmnožině S grupy (G, v) stačí na to, aby byla grupou vzhledem k téže operaci v: 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): Díky tomu, že S je neprázdná, obsahuje aspoň jeden prvek, označme jej a. a (4) _i c (i) _i c tedy neutrální prvek n patří i do množiny S a pro (S, y) platí (3). □ Označení 01 ... hvězdička znamená, že z dané množiny Z, Q, R vyloučíme nulu, značíme tedy symbolem Z*, Q*, R*. Příklad 6 Podmnožina Q* všech zlomků kromě nuly je podgrupou grupy (R*,-): vynásobením dvou nenulových zlomků dostaneme nenulový zlomek (platí (1)), inverzí k nenulovému zlomku vzhledem k násobení je jeho převrácená hodnota (platí (4)) a Q* je neprázdná. 12Ve skutečnosti podmínka neprázdnosti je třetí podmínkou, která musí platit - uvidíme v důkazu, že z neprázdnosti a vlastnosti (4) už plyne vlastnost (3) o neutrálním prvku. Algebra 1 (MA 0003) 28 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í13, a nejen to: musíme brát všechny možné konečné sekvence prvků spojených operací y, ve kterých se vyskytují (i opakovaně) prvky a, b, c a jejich inverze. Typickými takto vytvářenými prvky jsou například a V b V a V c_1 nebo c-1 y a-1 y b\y b\y c. Je jasné že součinem dvou prvků tohoto typu je zase prvek tohoto typu (tj. platí (1)): Například „součinem" prvku a y b y a a prvku c y y a y c je prvek a\j b\j a\j cxj b'1 xj a\j c. Dále jsou prvky tohoto typu uzavřené vzhledem k inverzi, tj. k prvku a y y c-1 y a je inverzí (podle věty 5.a bereme součin dílčích inverzních prvků v opačném pořadí) prvek a"1 y c y bxj a"1 (tedy platí i (4)). Dokázali jsme celkem, že množina prvků tohoto typu tvoří podgrupu grupy (G, y). Nazývá se Definice 15 podgrupa grupy G generovaná množinou S, prvky množiny S nazýváme generátory podgrupy < S >. Podgrupu generovanou podmnožinou S označujeme jako ( označení 02 ) < S >. A ještě jedna definice, která s tím souvisí: Definice 16 Pokud podgrupa < S > je celá generována některým svým prvkem a, nazývá se cyklická podgrupa grupy G. Cyklickou podgrupu generovanou prvkem a někdy označujeme ( označení 03 ) < a > a je jasné, že obsahuje prvky a, a2 := a y a, a3 := a y a y a,..., a také prvky a-1, a-1 y a-1, a-1 y a-1 y a-1,..., a také prvek n = a y a-1. Ad Příklad 1: Grupa (Hq, +) s operací pootočení hodinové ručičky je příkladem cyklické grupy, generované jediným prvkem - kterým? □ V této chvíli už se v daných součinech vyskytuje neutrální prvek n G G, protože a\/ a = n. 29 Ad příklad 4: Ohledně generátorů grupy S3 lze říci, že (63, o) je generována dvěma svými prvky, a sice (1,3) a (1,2), protože všechny další čtyři prvky grupy lze vyjádřit pomocí operace o a prvků (1, 3), (1, 2): id = (l,3)o(l,3); (1,2,3) = (l,3)o(l,2); (1, 3, 2) = (1, 2, 3) o (1, 2, 3) = ((1, 3) o (1, 2))2 = ((1, 3) o (1, 2)) o ((1, 3) o (1, 2)); (2,3) = (1,2) o (1,2,3) = (1,2) o ((1,3) o (1,2)). Podle označení množiny generátorů lze psát (53,0) =< (1,3),(1,2)>. Tato grupa tedy není cyklická, protože naše množina generátorů je dvouprvková a žádnou jednoprvkovou množinu generátorů v ní nelze najít. □ Věta 7 (5„, o), množina permutacŕ4 M —> M pro M = {1, 2,... , n} vzhledem k operaci skládání permutací je pro n > 3 nekomutativní grupa. Důkaz pro obecné n: Operace o je na množine Sn uzavřená, tj. platí vlastnost (1), protože složení dvou permutací je opět permutace. Asociativita (2) platí pro skládání jakýchkoli zobrazení, viz příklad 3. Identické zobrazení id definované Va G {1,2,... ,n} vztahem íd(a) = a je neutrálním prvkem na množině permutací, tj. platí (3): Pro obecnou permutaci p : {1, 2,... , n} —> {1, 2,... , n} totiž máme pro každné a G {1, 2,... , n}: p o íd(a) = p(a) A id o p(a) = íd(p(a)) = p(a). Zbývá důkaz vlastnosti (4): V obecném případě (5„, o) permutací na n-prvkové množině M = {1,. .. ,n} najdeme pro libovolnou permutaci p £ Sn její inverzní prvek p~x následujícím způsobem. Jelikož p : M —>■ M je bijektivní zobrazení, podle věty 17 ze základů matematiky (inverzní relace k prostému zobrazení je také zobrazení) víme, že inverzní relace p~x je zobrazením. Dále p je surjekce, tj. p~x je definováno pro každé a G {1,2,... ,n}. Tedy pro bijekci p je p~x také bijekce (v grafické reprezentaci relace pouze zaměníme směr všech šipek), a tedy permutace {1, 2, ..., n} —> {1, 2, ..., n}. A konečně pro n > 4 stačí najít jednu dvojici, pro kterou operace o nekomutuje, a to je např. cyklus (1, 2) a cyklus (1,2,... ,n): (1, 2) o (1, 2, ..., n) = (2, 3, n - 1, n) ^ (1, 2,... , n) o (1, 2) = (1, 3, 4, n - 1, n). Důkaz je hotov. □ 14Pozor, prvky množiny Sn nejsou podmnožiny či jednotlivé prvky množiny M, ale zobrazení množiny M do sebe!! Jedná se už o složitější strukturu. Algebra 1 (MA 0003) 30 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ě generované jediným prvkem) H grupy G je komutativní, třebaže na celé grupě G tato operace komutativní být nemusí. Například podgrupa {id, (1, 2, 3), (1, 3, 2)} grupy (63, o) je generovaná prvkem (1, 2, 3), a tedy je to cyklická podgrupa, tj. cyklická grupa. Je vidět, že tabulka operace na {íd, (1, 2, 3), (1, 3, 2)} je symetrická, tj. operace je na ní komutativní. Důkaz faktu, že operace na každé cyklické grupě je komutativní, je lehký - pokuste se o něj v rámci cvičení. Názvy a vlastnosti algebraických struktur - příklady Příklad 7 Zopakujte vlastnosti (1) až (5) a přiřaďte názvy algebraických struktur k příkladům z minulé přednášky podle definic 1 až 8. • Vlastnost (1): Vx, y G M : x * y G M. .. .uzavřenost množiny M vzhledem k operaci * • Vlastnost (2): Vx, y, z G M : (x * y) * z = x * (y * z). ... asociativita operace * na množině M • Vlastnost (3):3eGM:x*e = e*x = x VxG M. .. .existence neutrálního prvku vzhledem k operaci * • Vlastnost (4): Vx G M 3 x"1 G M : x * x 1 = x 1 * x = e. ... existence inverzních prvků vzhledem k operaci * • Vlastnost (5): Vx, y £ M : x *y = y * x. ... komutativita operace * na množině M Pro dvojici operací * a y můžeme navíc definovat tzv. distributivní zákon 8: • Vlastnost (6): V x,y, z G M : x*(yyz) = (x*y)y(x*z), (y\jz)*x = (y*x)y(z*x). Množině M s operací * se pak podle toho, kolik splňuje vlastností říká: • Grupoid (M, *) - operace * splňuje na množině M vlastnost (1); • Pologrupa (M, *) - operace * splňuje na množině M vlastnosti (1), (2); • Monoid (M, *) - operace * splňuje na množině M vlastnost (1), (2), (3); • Grupa (M, *) - operace * splňuje na množině M vlastnost (1), (2), (3), (4). Pokud množina M s operací * splňuje navíc vlastnost (5), pak do jejího označení přidáváme slovo komutativní. (M, *) tedy může být komutativní grupoid / pologrupa / monoid / grupa. Nyní můžeme přiřadit názvy algebraických struktur příkladům z minulé přednášky: 31 • Struktura (H$, +) z příkladu 1 splňuje vlastnosti (1), (2), (3), (4) a navíc je i komutativní, tedy je splněna vlastost (5). Dohromady je tedy (Hq, +) komutativní grupa. • Struktura (Z, +) z příkladu 2 také splňuje všechny vlastnosti (1), (2), (3), (4) i (5). (Z, +) je také komutativní grupa. • Struktura (F(R), o) z příkladu 3 splňuje pouze vlastnosti (1), (2), (3). Dohromady je tedy (F(R), o) monoid. • Struktura (6*3,0) z příkladu 4 splňuje vlastnosti (1), (2), (3), (4), ovšem nikoliv vlastnost (5). (63, o) je tedy grupa, která ale není komutativní. • Příklad 8 V grupě permutací (6*3,0) řešte rovnici (1,2) o x = (1,2,3), kde x označuje neznámou permutaci. (63, o) je nekomutativní grupa. Provedeme krácení zleva pomocí inverzního prvku k permutaci (1,2), kterým je opět prvek (1,2). (1,2) ox = (1,2,3) / o (1,2)(zleva) (1,2) o (1,2) ox = (1,2) o (1,2,3) x = (1,2) o (1,2,3) x = (2, 3) Řešením dané rovnice je tedy permutace (2, 3). • Algebra 1 (MA 0003) 32 3 Týden 03 3.1 Cvičení 03: Vlastnosti grup, podgrupy a generátory grupy Úloha 3.1 Príklady z Pinter 2010, str. 39, oddíl B: Například B.í: Dokažte, že v každé grupě platí následující implikace (e je neutrálni prvek grupy), nebo uveďte protipříklad, že neplatí: x2 = e => x = e. Například B.2: Dokažte, že v každé grupě platí následující implikace, nebo uveďte protipříklad, že neplatí: 9 9 x = a. 2 2 x = a Například B.4: Dokažte, že v grupě platí následující implikace, nebo uveďte protipříklad, že neplatí (e je neutrální prvek grupy): T*^ - T* \ nf - (D Například B. 5: Dokažte, že v grupě platí následující fakt, nebo uveďte protipříklad, že neplatí: Vi e G 3 i/ £ G : x = y2 (tj. každý prvek x má v grupě svou „odmocninu" y). Úloha 3.2 Příklady z Pinter 2010, str. 40, oddíl E: počet prvků a jejich inverzí - výborné příklady. Úloha 3.3 Příklady z Pinter 2010, str. 41, oddíl F: vytváření tabulky operace pro grupy s malým počtem prvků - např.: Například F.2: Může v grupě (G,*) nastat situace, že v tabulce její operace se dvakrát opakuje stejný prvek na jednom řádku? Xi . x2 ... a ... y . ■ y ■■■ Zdůvodněte, proč ano - proč ne. Například F.3: M = {e, a, b}. Doplňte tabulku operace * tak, aby (M, *) byla grupa. e a b e e a b a a b b 33 Například F.4: Čtyřprvková grupa G = {e, a, b, c, } splňuje Vx G G : x2 = e (kde e je její neutrální prvek). Sestavte tabulku operace * této grupy: * e a b c e a b c Například F.5: Čtyřprvková grupa G = {e, a, b, c, } splňuje a2 = e, b2 ^ e (kde e je její neutrální prvek). Sestavte tabulku operace * této grupy: * e a b c e a b c Úloha 3.4 (text Pinter 2010, str. 42, oddíl G): Dokážte, že kartézský součin grup (G, v) a (H, *) je grupa (G x H, □) - jak definovat operaci □? Úloha 3.5 Príklady z Pinter 2010, str. 43, oddíl H: mocniny a odmocniny v grupě -výborné příklady. Například H.O: a) zopakujte si definici n-té mocniny a n-té odmocniny v grupě, b) Jak byste definovali v grupě zápornou mocninu a-5 pro nějaký prvek a? Úloha 3.6 Příklady z Pinter 2010, str. 48, oddíl A: rozeznání podgrupy - výborné příklady. Například A.l: G = (R,+) je grupa vzhledem k běžné operaci sčítání. Je H = {loga; a 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, *) je konečná grupa, H její neprázdná podmnožina uzavřená vzhledem k operaci *, a navíc e G H, kde e je jednotkový prvek grupy G. Dokažte, že pro a G H také a-1 G H (tj. H je uzavřená vzhledem k inverzím). Nápověda k důkazu : H = {a±, a2, ..., an} a vyberme si libovolné at G H. Uvažujme nyní navzájem RUZNE prvky at * a±, (Zj * a2, ■ ■ ■, Oj * an: atd. Úloha 3.7 Příklady z Pinter 2010, str. 50, oddíl E: generátory grupy - výborné příklady. Algebra 1 (MA 0003) 34 Například N.l (není v textu Pinter 2010): Vypište všechny prvky podgrupy < 6 > grupy (Hie, +) = grupy všech pootočení ručičky o jednu šestnáctinu plného úhlu. Například E.l: Vypište všechny cyklické podgrupy grupy (Hio,+) skládání otáčení hodinové ručičky o násobky desetiny plného úhlu. Například E.3: Vypište všechny prvky podgrupy < 6, 9 > grupy (i/12, +)• Například E.7 - modifikace15: V grupě h2 x h4 je operace sčítání po složkách zadaná tabulkou Tabulka 3.7: Tabulka operace + na množině H2 x ii4. + [0 0] [0 1] [0 2] [0 CO [1 0] [1 1] [1 2] [1 CO [0 0] [0 0] [0 1] [0 2] [0 3] [1 0] [1 1] [1 2] [1 3] [0 1] [0 1] [0 2] [0 3] [0 0] [1 1] [1 2] [1 3] [1 0] [0 2] [0 2] [0 3] [0 0] [0 1] [1 2] [1 3] [1 0] [1 1] [0 3] [0 3] [0 0] [0 1] [0 2] [1 3] [1 0] [1 1] [1 2] [1 0] [1 0] [1 1] [1 2] [1 3] [0 0] [0 1] [0 2] [0 3] [1 1] [1 1] [1 2] [1 3] [1 0] [0 1] [0 2] [0 3] [0 0] [1 2] [1 2] [1 3] [1 0] [1 1] [0 2] [0 3] [0 0] [0 1] [1 3] [1 3] [1 0] [1 1] [1 2] [0 3] [0 0] [0 1] [0 2] Určete, jakou podgrupu generuje prvek [1; 1]. Například E.6: Sestavte tabulku operace grupy (ii2 x ii3) vzhledem k operaci sčítání po složkách. A druhý úkol: dokažte o této grupě, že je cyklická. Například N.3: Zjistěte, zda je grupa z příkladu E.7 cyklická, a pokud ne, tak najděte nějakou minimální množinu jejích generátorů (existuje nějaké dva prvky, které už generují celou tuto grupu?). Úloha 3.8 Vyřešte v grupě (G, *) systém rovnic: a) x2 = b, x5 = e b) ax2 = b, x3 = e 15 Jediný důvod, proč je prí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. 35 \ 9 O ty x = a , x = e Úloha 3.9 Pro následující grupy nalezněte podgrupy: a) (Z,+) b) (R-{0},-) c) (F(R),+) Úloha 3.10 Určete tabulku pro grupu všech symetrií rovnostranného trojúhelníka s operací skládání (D3, o). Úloha 3.11 Vypište všechny cyklické poágrupy grupy (i/10, +) sklááání otáčení hoáinové ručičky o násobky áesetiny plného úhlu. Úloha 3.12 Vypište všechny cyklické poágrupy grupy (hi2,+) sklááání otáčení hoáinové ručičky o násobky ávanáctiny plného úhlu. Výsledky některých cvičení najdete v závěru textu v oddílu 12.3. Algebra 1 (MA 0003) 36 3.2 Přednáška 3: Izomorfismus, homomorfismus, 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 stejnostech16. I když se tento český překlad neujal, vystihuje snahy moderní algebry všímat si shodných či podobných vlastností různých objektů. Ve shodě s navrhovaným starým překladem názvu tohoto předmětu nyní budeme zkoumat pojem izomorfismu. Lapidárně řečeno, dva objekty jsou izomorfní, když mají tutéž strukturu. I řecké slovo izomorfismus je podobného obsahu (isos = stejný, morfé = tvar, tj. izomorfní budou objekty, které mají možná jinou podstatu, ale v jistém smyslu stejný tvar). ( R+ vztahem fix) = ex. Snaáno se viáí, že zobrazení f je injekce, protože nenabývá ávou stejných hoánot pro ávě různá Xi,x% E R. Dále je f surjekce R na R+ - pro kažáé y E R+ existuje x E R tak, že ex = y. Celkem teáy f je bijekce. Dále poámínka zachování výsleáků operace nyní má vzhleáem k zaáaným operacím tvar f(a + b) = f(a)-f(b). 18Diagram komutuje = nezáleží na pořadí: operace v v první (výchozí) množině následovaná zobrazením dává tentýž výsledek jako zobrazení následované operací * ve druhé (cílové) množině. Algebra 1 (MA 0003) 38 Tato podmínka také platí, protože ea+h = ea ■ e6. Celkem f je grupovým izomorfismem.* Při hledání odpovědi na otázku, zda jsou dvě různé grupy izomorfní, musíme tedy projít tři kroky: a) definovat zobrazení / : G\ —> G2', b) dokázat o tomto zobrazení, že je injektivní a surjektivní, a tedy bijekce; c) dokázat, že platí vlastnost zachování výsledků operace. Pokud jsou dvě grupy izomorfní, tak chování operace na té druhé je přesnou kopií chování operace na první grupě. Tedy pokud první grupa (G±, v) má vlastnost, kterou grupa (G2, *) nemá, nemohou být tyto grupy izomorfní. Například • G\ je komutativní, ale G2 ne. • G\ má nějaký prvek, který je inverzí sebe sama, ale G2 takový prvek nemá. • G\ je generována dvěma svými prvky, ale G2 není generována žádnou dvojicí svých prvků. • Atd., možná více viz cvičení. Před více než 100 lety dokázal Arhur Cayley větu, kterou se nyní budeme zabývat: Každá grupa (libovolná, konečná i nekonečná, komutativní i nekomutativní) je izomorfní nějaké podgrupě grupy permutací (ty byly představeny v minulé kapitole). Tento výsledek je revolučním ve studiu grup, protože vlastně tvrdí, že žádné jiné grupy (až na přeznačení prvků) než grupy permutací vlastně neexistují!!! A o to více je tento výsledek revoluční ve studiu operací - tvrdí totiž, že na grupách neexistuje žádná jiná operace než operace skládání permutací!!!! Jinými slovy, pomocí operace SKLÁDÁNÍ PERMUTACÍ lze reprezentovat jakékoli další operace na grupách, tj. sčítání, násobení, atd. Věta 8 (Cayley) Každá grupa (G, v) je izomorfní nějaké grupě permutací. Důkaz: dokážeme ve třech krocích: 1. Ke každému prvku a E G vytvoříme permutaci ira : G —> G (a dokážeme, že se jedná o permutaci G, tedy o bijekci). 2. O množině těchto permutací G* := K;aGG} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekci G —>■ G). 39 3. Definujeme zobrazení / : G —> G* a dokážeme o něm, že je izomorfismus mezi grupami. Tak pojďme na to!! Důkaz podrobněji: 1. Ke každému prvku a E G vytvoříme permutaci ira : G —> G (a dokážeme, že se jedná o permutaci G, tedy o bijekci). Definujme pro libovolný prvek a E G zobrazení ira definované vztahem Vx E G : 7ra(x) := axj x (zobrazení 7ra zobrazí každé x E G na prvek axj x E G). Dokažme o 7ra, že se jedná o bijekci: • 7ra je injekce G —> G: Předpokládejme, že 7ra(xi) = 7ra(x2) - to by znamenalo podle definice zobrazení 7ra, že axj xx = axj x2, a protože v grupě platí vlastnost (7), můžeme vykrátit po vynásobení rovnosti prvkem a-1 zleva a dostaneme x\ = x2 ... tedy rovnost hodnot zobrazení 7ra může nastat jen pro tentýž prvek tedy / je injekce. • 7ra je surjekce G na G: Pro libovolný prvek y E G musíme najít jeho vzor vzhledem k zobrazení ira - jakmile najdeme aspoň jeden vzor, budeme vědět, že jedná se o surjekci, protože všechny prvky y E G hy pak byly pokryty nějakými vzory vzhledem k zobrazení /. Odpověď: hledaný vzor z G je prvek a~1 V Ví Pak totiž 7ra(a_1 XJ y) = axj a'1 XJ y = y- • Celkem 7ra je bijekce. 2. O množině těchto permutací G* := K;aGG} dokážeme, že je podgrupa grupy Sq všech permutací množiny G (= grupy všech bijekci G —» G). G* je podmnožinou grupy Sq všech permutací na G —> G. Dokážeme o G*, že je podgrupa: • G* je neprázdná, nejmenší možná grupa G je totiž minimálně jednoprvková (obsahuje neutrální prvek e), a tedy minimálně 7re(x) := e XJ x je identická permutace, která náleží do G*. Algebra 1 (MA 0003) 40 • (G*, o) splňuje vlastnost (1), tedy pro dvě různé permutace ira, 717, musíme najít prvek c G G, že ttc = pía o 717,. Skutečně to platí - pokud vezmeme c := a \/ b, potom Podrobněji rozepsáno, VieG: 7rav6(x) = (a\/b)x/x = a\/(b\/x) = a\/7rh(x) = 7ra(7r6(x)) = (717,0717,) (x). Tedy složením dvou prvků ira a 717, z G* je zase prvek z G*, tj. množina G* je uzavřená vzhledem k operaci o. • (G*,o) splňuje vlastnost (4): Stačí dokázat, že ke každému ira E G* existuje inverzní permutace vzhledem ke skládání permutací: A to opravdu existuje, je to totiž permutace 7ra-i odpovídající prvku a-1 G G - pak platí (podle vlastnosti (1) je složením permutací permutace odpovídající „násobku" obou dílčích prvků) • Tedy celkem G* je neprázdná a splňuje vlastnosti (1) a (4) - podle věty 6 je G* podgrupa grupy Sq, a tedy hlavně sama (G*, o) je grupou. 3. Definujeme zobrazení / : G —> G* a dokážeme o něm, že je izomorfismus mezi grupami. • Jako zobrazení / se nabízí přiřazení, o kterém už dlouho mluvíme: prvku a E G přiřadíme jím definovanou permutaci ira G G*, neboli f (a) = ttq. • / je injekce: Pokud f (a) = f(b), znamená to, že 7ra = 717,, tedy Vx G G : 7Ta(x) = 7i7,(x); a tak i speciálně pro jednotku e E G platí 7ra(e) = 717,(e), což znamená a y e = b y e, to ale znamená, že a = b. Rovnost obrazů si vynucuje rovnost vzorů, tedy / je injekce. • / je surjekce: Tato vlastnost je zaručena už tím, jak je množina G* vytvořena: jsou do ní vybírány jen ty permutace 7ra, které odpovídají prvku a E G, tj. každá permutace 7ra má svůj vzor a E G vzhledem k zobrazení /. • / 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) = 7rav6 = 7ra o 717, = f (a) o f(b). 41 Celkem / je izomorfismus grupy {G, v) na grupu {G*, o). Příklad 10 Tříprvková grupa pootočení (i/3, +) je izomorfní s podgrupou grupy permutací (5*3, o) obsahující tři prvky id, (1, 2, 3) a (1, 3, 2). Grupa (i/3, +): Grupa (5*3, o): + 0 1 2 0 0 1 2 1 1 2 0 2 2 1 0 o id (1,2,3) (1,3,2) id id (1,2,3) (1,3,2) (1,2,3) (1,2,3) (1,3,2) id (1,3,2) (1,3, 2) id (1,2,3) (i/3, +) se izomorfně zobrazila na podgrupu grupy (63, o) se stejným počtem prvků, která je sama grupou (je uzavřená vzhledem k operaci skládání a obsahuje inverze ke všem svým prvkům). Z tabulek je vidět, že pokud se 0 zobrazí na id, 1 na (1, 2, 3) a 2 na (1,3,2), tak výsledky operace zůstávají v tabulce na přesně stejném místě (pokud tedy prvky v záhlaví tabulky napíšeme ve stejném pořadí). • Příklad 11 Grupu permutací, která je izomorfní k dané grupě je možné najít i v případě, kdy je původní grupa nekonečná. Pokusme se najít izomorfní grupu permutací k množině {Z,+). Hledaná grupa existuje a bude to grupa bijekcí na množině, která má nekonečný počet prvků {Sz, °)- Grupa {Z, +): + ... -2 -1 0 . -2 ... -4 -3 -2 . -1 ... -3 -2 -1 . 0 ... -2 -1 0 . °): ( - . -1 0 1 0 ... i l i \- . -3 -2 -1 -1 0 1 .. •\ i" . -1 0 1 l l 1 ... l l l -3 -2 -1 .. •/ V- . -5 -4 -3 -1 o 1 4- 4' ^ -2 -1 o -1 o 1 \~ 4' 4' -4 -3 -2 Algebra 1 (MA 0003) 42 Prvek —2 z grupy celých čísel se zobrazí na bijekci Z do Z, která posouvá všechna čísla na čísla o —2 nižší, prvek —1 se zobrazí na bijekci, která všechna čísla posouvá na čísla o —1 nižší atd. Výsledek operace zůstane zachován. Grupy (Z,+) a (Sz,°) jsou tedy skutečně izomorfní. • Kniha Pinter 2010, str. 97-102, opět poskytuje řadu cvičení na pojem izomorfismu: Příklad 12 Například C.3: Zjistěte, zda je grupa 2^a'h^ s operací symetrického rozdílu 4 (stejná operace jako v úloze 1.13) izomorfní s grupou (V, ■), kde V = {1, —í} a ■ je operace násobení komplexních čísel. Své zjištění zdůvodněte. Nejprve si opět sestavíme tabulky operací na daných množinách. Grupa (2^,4): Grupa (V7, 4 í ) w {b} {a,b} 0 í ) {a} {b} {a,b} {a} {a} 0 {a,b} {b} {b} {b} {a,b} 0 {a} {a,b} {a, b} {b} {a} 0 1 -1 i —i 1 1 -1 i —i -1 -1 1 —i i i i —i 1 -1 —i —i i 1 -1 Při pohledu na tabulky není na první pohled vidět, zda se jedná o bijekci zachovávající výsledky operace. Proto se zvlášť podíváme na vlastnosti obou grup. Zkusme se podívat na inverze. Pro grupu (2^a'6^, 4) platí: 0 Ifl {a} {a} {b} « {b} {a, b} {a, b} 1 1 -1 -1 i — i Aby platila vlastnost zachování výsledků operace, musely by se dvojice invezních prvků zobrazit opět na dvojice inverzních prvků, což v tomto případě neplatí. Grupy Pro grupu (V7, •) platí: 43 (2^a'6^, -=-) a (V, •) tedy nejsou izomorfní. • Například D.l: Prozkoumejte grupy a) (i/i,+)/ b) (H2 X H2,+) (sčítání definováno po složkách po složkách); c) grupu komplexních jednotek (V, ■), kde V = {1, —1, í, —í} a ■ je operace násobení komplexních čísel. Které dvě z nich jsou izomorfní, a proč ta třetí s nimi není izomorfní? Tabulku struktury (V, •) máme sestavenou z předcházejícího příkladu. Sestavme tedy ještě tabulky zbylých dvou struktur. Grupa (i/4, +): + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Grupa (H2 x H2,+): + [0;0] [0;i] [i;0] [i;i] [0;0] [0;0] [0;i] [i;0] [i;i] [0;i] [0;i] [0;0] [i;i] [i;0] [i;0] [i;0] [i;i] [0;0] [0;i] [i;i] [i;i] [i;0] [0; i] [0;0] Ani v tomto příkladě nejsme na základě tabulek schopni na první pohled říci, zda jsou dané struktury izomorfní. Zkusme tedy zjistit, zda izomorfismus existuje, pomocí inverzních prvků: (i/4,+): 0 0, 1 3, 2 2 (V,-): 1 1, -1 -1, 1 -i (H2xH2,+): [0;0]^[0;0], [0;1]^[0;1], [1;0]^[1;0], [1; 1] <-> [1; 1] Můžeme vidět, že struktura (H2 x H2,+) není izomorfní ani s jednou ze zbývajících dvou, jelikož izomorfismus musí zachovávat inverze. (i/4, +) i (V, •) obsahují dva prvky, které jsou inverzní k sobě samému. Struktura inverzí je u obou struktur stejná. Na základě inverzí by tedy zobrazení mohlo vypadat takto: 0 —> 1, 1 —> i, 2 —> —1, 3 —> —i. Vypišme si nyní tabulku (V, •) s přehozenými prvky. Dostaneme: 1 i -1 -l 1 1 i -1 -l i i -1 -l 1 -1 -1 —i 1 l —i —i 1 l -1 Algebra 1 (MA 0003) 44 Tabulky jsou nyní zcela stejné až na přeznačení prvků. Grupy (iÍ4,+) a (V,-) jsou tedy izomorfní. Návrh dalších příkladů na procvičení z knihy Pinter: The Book of Absract Algebra: Například D.2: Viz cvičení 05, kde budou zhruba probrány grupy zbytkových tříd. (cvičení sady G): Izomorfní grupy na množině reálných čísel. (cvičení sady J): Regulární reprezentace grupy - rychlá konstrukce podgrupy grupy Sn, která je s grupou G izomorfní!! Homomorfismus grup Definice 18 Grupový homomorfismus f : G —> H je takové zobrazení mezi grupami (G, v) a (H,*), které zachovává výsledky operace (ZVO) podobně jako izomorfismus, ale na rozdíl od izomorfismu nemusí být bijektivní. Příklad 13 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. Grupa (Z, +): Va,foGG: f (a V b) = f{a) */(&). (ZVO) + -2 - 1 0 -2 -1 0 -4 -3 -2 3 -2 2 -1 1 0 Grupa (Zq,+) + 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 1 2 3 2 3 4 3 4 5 4 5 0 5 0 1 3 4 5 4 5 0 5 0 1 0 1 2 1 2 3 2 3 4 Takto definované zobrazení opravdu splňuje podmínku zachování výsledků operace: například platí /(5 + 53) = /(5) + /(53), 45 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). Obecně platí: Celá čísla Qk+m a Ql+n se mezi sebou sečtou na Qik + l)+m+n = Qp+r. Tato celá čísla se zobrazí na jejich zbytky: 6k + m —> m, 61 + n —> m a 6p + r —> r. Musí platit, že součet zbytku m a n je roven r, což skutečně platí (součet zbytků po dělení šesti je zase zbytek po dělení šesti), tedy je splněna podmínka zachování výsledků operace. □ Význam homomorfismu: Pod homomorfismem lze v řadě případů (tehdy, když / je surjekce grupy G na grupu H) vidět jistou projekci, která některé vlastnosti původní grupy ztrácí, ale zachová jednu jistou vlastnost. Třeba v právě uvedeném příkladu se při zobrazení / jistým způsobem ztrácí nekonečnost množiny Z a zůstává jen informace, jaké zbytky po dělení šesti existovaly mezi celými čísly, a dále zůstává na Z§ zachována vlastnost součtu zbytků, neboli součet dvou celých čísel dává po vydělení šesti zbytek, který je obsažen v té třídě rozkladu množiny Zq, která obsahuje součet zbytků obou původních čísel po vydělení šesti. Příklad 14 Zobrazení f : Zq —> Z3, přičemž na obou množinách uvažujeme operací sčítání, definované vztahem ( 0 1 2 3 4 5 \ /= I I I I I I \ 0 1 2 0 1 2 / je také grupový homomorfismus, protože zbytek po dělení šesti v grupě (Zq, +) je zobrazen na zbytek tohoto zbytku po dělení třemi v grupě (Z$, +). V důsledku zobrazení f se ztrácí jisté informace z grupy Zq, a sice celočíselná odchylka nejbližšího násobku šesti na číselné ose směrem vlevo od libovolného reprezentanta dané třídy rozkladu, ovšem zůstává zachována celočíselná odchylka nejbližšího násobku tří na číselné ose směrem vlevo od libovolného reprezentanta dané třídy rozkladu.\3 Definice 19 Pokud f : G —» H je grupový homomorfismus a současně surjekce, označujeme f(G) = H a grupa H se nazývá homomorfní obraz grupy G. Viz příklad 14: grupa (Z3, +) je homomorfním obrazem grupy (Zq,+) vzhledem k homomorfismu /. Podívejme se tedy na některé vlastnosti každého grupového homomorfismu. Tyto vlastnosti platí i pro izomorfismus, protože homomorfismus je obecnější pojem (každý grupový izomorfismus je současně i grupovým homomorfismem): Algebra 1 (MA 0003) 46 Věta 9 Pro grupový homomorfismus f : G —> H grupy (G, v) do grupy (H, *) platí: a) f(eG) = eH (grupový homomorfismus vždy zobrazuje jednotkový prvek grupy G na Jednotkový prvek grupy H); b) (f (a))-1 = f (a-1) (vzhledem ke grupovému homomorfismu platí: inverze obrazu = obraz inverze). c) / zobrazípodgrupu (S,\/) na podgrupu (f(S),*). Důkaz: • ad a) Prvek eG jistě můžeme psát jako eG xj eG, a po využití vlastnosti (ZVO) homomorfismu (= vlastnosti zachování výsledků operace) dostaneme: f{eG) = F{eG y eG) {Z=0) f{eG) * f(eG), dostali jsme tedy rovnost f(eG) = f(eG) * f(eG), ze které po vynásobení rovnosti prvkem (/(ec))_1 (který existuje díky vlastnosti (4) v grupě (H, *)) zprava dostaneme f(eG) * (/(ec))"1 = f(eG) * f(eG) * {f{eG))~\ a nyní použitím vlastnosti (3) grupy (H, *) na levé i pravé straně poslední rovnosti máme neutrální prvek eH grupy H a dostaneme eH = 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 (ZVO) a právě dokázanou vlastnost (a): takže podle věty 4 inverzní prvek k prvku f (a) je prvek f (a-1), neboli (/(a))"1 = /(a-1). Důkaz je hotov. □ 47 ad c) i) f (S) je neprázdná množina, protože obsahuje minimálně neutrální prvek /(eg) = ii) f (S) je uzavřená vzhledem k operaci *: pro fix) a f(y) platí f(x)*f(y) {z=0) f(xw), tedy prvek fix) * f(y) je obrazem prvku x\/ y G G, a tedy /(x) *f(y) G f (S), platí uzavřenost operace * na množině f (S); iii) /((S) je uzavřená vzhledem k inverzím: pokud f(a) G f (S), tak podle výše dokázané vlastnosti (b) víme, že f (a)-1 = f (a-1), a protože S je podgrupa uzavřená na inverze a a G S, tak také a-1 G S, tedy f (a-1) G /(S) ... a protože f (a-1) je inverzní prvek k prvku /(a), je f (S) uzavřená na inverze. Celkem podle věty 6 je f (G) podgrupa grupy (H, *). □ Definice 20 Jádro grupového homomorfismu f : G —> H se nazývá množina kerj ( označení 04 )19 těch prvků z grupy (G, Xj), které se zobrazí na neutrální prvek e# grupy Příklad 15 a) V grupovém izomorfismu je jáárem zobrazení f vžáy pouze jeánoprvková množina {ěq}. b) V homomorfismu f : Z§ —» Z% z příklaáu 21 je jáárem množina těch prvků, které se zobrazí na nulu: kerf = {0, 3}. Věta 10 Pro grupový homomorfismus f : G —> H grupy (G, v) do grupy (H, *) platí: Jááro Kerip grupového homomorfismu je poágrupou grupy (G,\/). Důkaz: viz poslední video, přednáška 11. 9 Označení plyne z německého slova kernel - anglické core se z historických důvodů neprosadilo. Algebra 1 (MA 0003) 48 4 Týden 04 4.1 Cvičení 04: Nekomutativní grupy Úloha 4.1 Jsou dány permutace P = (1, 5, 6, 2, 3), R= (1, 7, 5,4, 3, 6, 2). Vypočtěte P o R2 (výsledek najdete na konci tohoto textu). Úloha 4.2 Kniha Pinter 2010, str. 75, oddíl B, príklady na grupy permutací. Například B.2: Vypište prvky cyklické podgrupy grupy (Sq, o) generované prvkem f = (1,2, 3,4) o (5, 6). Například B.3: Najděte čtyřprvkovou komutativnípodgrupu grupy (6*5,0) a napište její tabulku operace. Například B.4: Podgrupa grupy (65, o) generovaná prvky f = (1,2), g = (3,4,5) má šest prvků. Vypište tyto prvky, označte je e, f, g, h, í, j a sestavte tabulku operace o. Například N.l: Podgrupa grupy (64, o) generovaná prvky f = (1,3) o (2,4), í7 = (3,4) má osm prvků. Najděte je všechny. Může vám pomoci vytváření tabulky operace o, ale nemusíte ji dělat celou. Například N.2: Vypište všechny prvky cyklické podgrupy grupy (67, o) generované prvkem f = (1,3) o (4, 5, 7). Například N.3: Grupa (6*4,0) má 24 prvků. Najděte nějakou její osmiprvkovou podgrupu - vypište podrobně zbylých sedm prvků kromě neutrálního prvku. Může vám pomoci vytváření tabulky operace o, ale nemusíte ji dělat celou, stačí vypsat daných osm prvků. Úloha 4.3 Dva úkoly pro grupu permutací (63, o) (použijte prosím označení prvků a tabulku operace o v příkladu 4)' cl) dokažte, že (6*3,0) není cyklická grupa; b) najděte dvouprvkovou podmnožinu grupy, která generuje celou grupu (63,0). Úloha 4.4 Pokud bude čas, je možné se zabývat některými dalšími vlastnostmi permutací (ad Pinter 2010, kapitola 8): Každou permutaci lze rozložit na součin cyklů, každý cyklus lze rozložit na součin transpozic. Sudá a lichá permutace podle počtu transpozic. Ale to spíše až do předmětu Algebra 2 (lineární algebra). Výsledky některých cvičení najdete v závěru textu v oddílu 12.4. 49 4.2 Přednáška 04: Grupa symetrií čtverce, Lagrangeova věta, faktorgrupa Na začátku této přednášky se vrátíme k příkladu na grupu permutací pravidelného n-úhelníka: Příklad 16 (ad Pinter 2010, str. 77, sada F) 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 0 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 Ri = (1,2,3,4) (v tom smyslu, že číslo 1 se pootočením dostalo na pozici čísla 2, číslo 2 se na pozici čísla 3, číslo 3 na 4 a číslo 4 na pozici 1). Podobně pootočení o 180° odpovídá permutace R2 = (1, 3) o (2, 4)20 a pootočení o 270° permutace fž3 = (1,4, 3, 2)21. (podrobněji viz obrázek 4.5). 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 4.6. Skládáním Ri o R5 například dostaneme iži o R5 = (1, 2, 3,4) o (2, 4) = (1, 2) o (3,4) = iž6, atd. Vyplněním operace pro každou dvojici prvků v obou pořadích (operace je opět nekomutativní, protože např. R5 o R1 = R7) dostaneme tabulku grupy (D4, o) symetrií čtverce, která odpovídá podgrupě grupy permutací s osmi prvky (viz tabulka 4.7). Všech permutací čtyřprvkové množiny je 24; tedy naše osmiprvková množina je podgrupou grupy S4. 20Pozor, tuto permutaci nelze lépe označit než spojením dvou disjunktních cyklů délky 2, protože dochází ke dvěma nezávislým prohozením během jedné permutace. 21Což je totéž jako (4, 3, 2,1), ale začínáme při zápisu nejmenším možným číslem, abychom se vyznali ve výsledcích operací a podle pozice nejmenšího čísla poznali jednoznačně daný prvek. Algebra 1 (MA 0003) 50 Obrázek 4.5: Permutace odpovídající pootočení čtverce. I A \ s 3 1 3 t ^ í 1 1 \ 1 | J 1 4 l i l 3 - --- 3 \ L Obrázek 4.6: Permutace odpovídající osové symetrii čtverce. 51 o id (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) (1,3) (2,4) (1,2) = (3,4) (1,4) ° (2,3) id id (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) (1,3) (2,4) (1,2) = (3,4) (1,4) ° (2,3) (1,2,3,4) (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) id (1,4) ° (2,3) (1,2) - (3,4) (1,3) (2,4) (1,3) ° (2,4) (1,3) ° (2,4) (1,4,3,2) id (1,2,3,4) (2,4) (1,3) (1,4) o (2,3) (1,2) ° (3,4) (1,4,3,2) (1,4,3,2) id (1,2,3,4) (1,3) ° (2,4) (1,2) ° (3,4) (1,4) ° (2,3) (2,4) (1,3) (1,3) (1,3) (1,2) ° (3,4) (2,4) (1,4) ° (2,3) id (1,3) - (2,4) (1,2,3,4) (1,4,3,2) (2,4) (2,4) (1,4) ° (2,3) (1,3) (1,2) ° (3,4) (1,3) - (2,4) id (1,4,3,2) (1,2,3,4) (1,2) ° (3,4) (1,2) ° (3,4) (2,4) (1,4) ° (2,3) (1,3) (1,4,3,2) (1,2,3,4) id (1,3) ° (2,4) (1,4) ° (2,3) (1,4) - (2,3) (1,3) (1,2) ° (3,4) (2,4) (1,2,3,4) (1,4,3,2) (1,3) " (2,4) id Obrázek 4.7: Tabulka operace o na množině D4 symetrií čtverce Pro každé přirozené n > 3 lze sestrojit grupu symetrií pravidelného n-úhelníku a označit ji Dn vzhledem k operaci skládání zobrazení. Například D5 označuje grupu symetrií pětiúhelníku, atd. Každému rovinnému útvaru, který je pravidelný vzhledem k otáčení nebo osové souměrnosti, lze přiřadit jistou grupu symetrií. Grupy symetrií se široce používají v teorii elektronové struktury a molekulárních vibrací. V elementární časticové fyzice byly tyto grupy symetrii využity k předpovězení existence částic, které ještě ani nebyly experimentálně zjištěny! Proto i studium nekomutativních grup má svoje místo v algebře. Úkol: Najděte všechny inverzní prvky a všechny podgrupy v grupě D4. Začneme tedy vypsáním inverzních prvků. K tomu nám pomůže jednak tabulka, ale také uvědomění si geometrických významů daných permutací: id -f-)* id (1,2,3,4) (1,4,3,2) (1,3) o (2,4) (1,3) o (2,4) (1.3) (1,3) (2.4) (2,4) (1,2) o (3,4) (1,2) o (3,4) (1,4) o (2,3) (1,4) o (2,3) Nyní k podgrupám grupy D4. Dvě z nich jsou triviální Pi = {id} a P2 = D4. Zkusme se teď podívat na dvouprvkové podgrupy. K tomu můžeme využít geometrického významu - všechny osové souměrnosti s identitou tvoří dvouprvkovou podgrupu, jelikož osová souměrnost je inverzní prvek sama k sobě: P3 = {id, (1,3)}, P4 = {id, (2,4)},P5 = {id, (1,2) o (3,4)}, P6 = {id, (1,4) o (2, 3)}. Algebra 1 (MA 0003) 52 Otočení o 180° je také samo sobě inverzí, takže jeho spojením s identitou získáme podgrupu P7 = {id, (1, 3) o (2, 4)}. Můžeme přejít k čtyřprvkovým podgrupám. První je množina čtyř pootočení P8 = {id, (1,2,3,4), (l,3)o(2,4), (1,4, 3, 2)}, další jsou P9 = {id, (l,3)o(2,4), (1,3), (2,4)} a P10 = {id, (1, 3) o (2,4), (1, 2) o (3,4), (1,4) o (2, 3)}. Tím jsme našli všechny podgrupy grupy DA. V dalším následném textu dodatků v této kapitole (pokud vyučující nebude chtít vašich znalostí více) budete vyloženě potřebovat jen Lagrangeovu větu - větu 15, která bude procvičena v příkladech následující přednášky. 53 4.3 Dodatky Z těchto dodatku možná vyučující probere jen část, na podrobné procházení není čas. Zejména věty 12, 14 a její důsledek jsou důležité, ale hlavně jsou tyto věty potřeba pro důkaz věty 15, kterou jedinou je určitě potřeba si pamatovat. Začneme zopakováním znalostí o pojmu ekvivalence (relace reflexivní, symetrická a tranzitivní) a pojmu rozkladu určeného 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, ..., Mfc 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 [J Mť = M. Přidejme nyní navíc k předmětu Základy matematiky: • Pro důkaz jednoho zajímavého tvrzení (věty 12) nám bude stačit si uvědomit, že pokud dvě třídy rozkladu Ml1 M3 mají neprázdný průnik, pak se musí rovnat, čili Mj = Mj a jedná se o tutéž třídu. Lze tedy rozklad množiny M na podmnožiny Mj definovat i následovně: - Vie {1,2,...,*;}: Mť^0; - a E Mil) Mj Mi = My, - každý prvek a E M leží v jedné třídě rozkladu. • Označení 05: Znak ~ bude značit relaci ekvivalence určenou daným rozkladem, tj. a ~ b právě tehdy, když a, b E Mj pro nějaké i. • Označení 06: 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 v, 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 21 Va z grupy (G, v) a její podgrupu (H,\/) lze definovat: levá třída prvku a E G vzhledem k podgrupě H je množina axj H := {axj h E G : h E H} Algebra 1 (MA 0003) 54 (množina výsledku operace axjh, kde prvek a E G je pevné a prvek h probíhá podgrupu H); podobně pravá třída prvku a E G vzhledem k podgrupě H je množina H y a := {hxj a E G : h E H} (množina výsledku operace hxj a, kde prvek a E G je pevné a prvek h probíhá podgrupu H). Pojmy levá a pravá třída prvku splývají jen tehdy pokud xj 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 17 Pro grupu G = {H4,+) = (Z4, +) = ({0,1,2,3,},+) a podgrupu H = ({0, 2}) dostáváme následující levé třídy prvků podle podgrupy: • levá třída prvku 0 vzhledem k H je 0 + H = {0, 2} = H = H + 0 (tedy levá třída prvku 0 je rovná pravé třídě prvku 0); • levá třída prvku 2 vzhledem k H je 2 + H = {0, 2} = H = H + 2 (tedy levá třída prvku 2 je rovná pravé třídě prvku 2); • levá třída prvku 1 vzhledem k H je 1 + H = {1, 3} = H + 1 (tedy levá třída prvku 1 je rovná pravé třídě prvku 1); • levá třída prvku 3 vzhledem k H je 3 + H = {1, 3} = H + 3 (tedy levá třída prvku 3 je rovná pravé třídě prvku 3); Příklad 18 Pro grupu G = (63, o) permutací z příkladu 4 a podgrupu H = ({id, (1,2,3), (1,3,2)}) dostáváme následující levé třídy prvků podle podgrupy (viz tabulka operace o u příkladu 4)' • levá třída prvku id vzhledem k H je id o H = {id, (1, 2, 3), (1, 3, 2)} = H = H o id (tedy levá třída prvku id je rovná pravé třídě prvku id vzhledem k operaci o); • levá třída prvku (1, 2, 3) vzhledem k H je (1, 2, 3)oH = {id, (1, 2, 3), (1, 3, 2)} = H = H o (1, 2, 3) (tedy levá třída prvku (1, 2, 3) je rovná pravé třídě prvku (1, 2, 3)); • levá třída prvku (1,3,2) vzhledem k H je (1,3,2) o H = {id, (1, 2, 3), (1, 3, 2)} = H o (1, 3, 2) (tedy levá třída prvku (1, 3, 2) je rovná pravé třídě prvku (1, 3, 2)); • levá třída prvku (2, 3) vzhledem k H je (2, 3) o H = {(2, 3), (1, 3), (1, 2)} = H o (2, 3) (tedy levá třída prvku (2, 3) je rovná pravé třídě prvku (2, 3)); • levá třída prvku (1, 3) vzhledem k H je (1, 3) o H = {(2, 3), (1, 3), (1, 2)} = H o (1, 3) (tedy levá třída prvku (1, 3) je rovná pravé třídě prvku (1, 3)); 55 • 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 18 je vidět, že například množina (2, 3) o H nemusí obsahovat žádný z původních prvků podgrupy H, a taky nemusí být podgrupa, protože neobsahuje neutrální prvek id, i když H podgrupa grupy G je (ze všech navzájem disjunktních tříd = podmnožin je podgrupou právě jedna - ta, která obsahuje neutrální prvek, a tedy třída H o íd neboli třída H). 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 11 je pouze pomocnou větou, která bude potřeba v důkazu věty 12 (věty 11 až 14 jsou řečeny za předpokladu označení z definice 21, tj. (H, y) je podgrupa grupy (G, y)). Věta 11 a E H y 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 H xj a & také b = e\/bEH\/b, z rovnosti množin plyne i a E H y b. „=>": předpokládejme, že a E H y fo, a tedy existuje h E H tak, že a = h\j b. Za tohoto předpokladu dokážeme množinovou rovnost z platnosti dvou inkluzí: H y a C H y b: Pokud x E H y a, tak x = h\ y a pro nějaké h\ E H. Z předpokladu věty dosaďme za a a dostaneme x = hx y a = hx y (h y b) = (hx y h) y b, a protože součin v poslední závorce je prvkem H, dostáváme celkem, že x E H y b. H y b C H y a: Pokud x E H y b, tak x = h2 y b pro nějaké h2 E H. Z předpokladu věty (a = hxjb) si vyjádřeme b, konkrétně (protože jsme v grupě G, všechny inverze existují) a = h\j b => hT1 y a = b, a po dosazení za b dostaneme x = h2\j b = h2\j (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 E H y a. Věta 11 netvrdí nic světoborného, v podstatě jen to, že pokud prvky a, b jsou spojeny v operaci y „přes podgrupu H", tak jejich pravé třídy jsou totožné. Následující věta 12 je prvním významným výsledkem této kapitoly. Algebra 1 (MA 0003) 56 Věta 12 Pravé22 třídy H XJ a pro všechny možné prvky a grupy (G, v) tvoří rozklad množiny G. Důkaz: Dokážeme ve dvou krocích: a) Hxja, Hxjb 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 XJ a, H XJ 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 G (H y a) íl (H y b) => (x = hiXj a) A (x = h2XJb) => hiXj a = h2XJb; vyjádřeme například prvek a z rovnosti, ke které jsme dospěli (jsme v grupě, tedy všechny inverze existují): a = hX1 XJ h2xj b. To tedy znamená, že a = (hX1 XJ h2) XJ b E H XJ b, a to podle věty 11 (tady právě ji potřebujeme!!) znamená, že H xj a = H xj b. b) Zbývá ukázat, že libovolný prvek c E G leží v některé z pravých tříd vzhledem k podgrupě H: to je už celkem snadné, protože c = exj c (kde e je neutrální prvek), a tedy c G H xj c. Našli jsme třídu rozkladu, ve které prvek c leží. Než se dostaneme k větě 14 vedoucí k Lagrangeově větě, ještě jedno označení a jeden výsledek, věta 13: Označení 07. Označme množinu tříd G/h rozkladu grupy G podle její komutativní podgrupy H ... vzhledem k operaci v definované pomocí vztahu (H V a)v(H V b) := H y (a V b) dostáváme tzv. rozkladovou grupu nebo též při doslovném překladu faktorgrupu23. Věta 13 Struktura G/h vytvořená z tříd podle nějaké své komutativní podgrupy H s operací XJ je grupa. Důkaz věty 13 je technický a nebudeme ho uvádět. Raději zde zmíníme, že G/h v příkladech 17 a 18 jsou tedy grupy, jejímiž prvky jsou podmnožiny původní množiny G, a operace sčítání či skládání zobrazení je tak definována mezi množinami! Základním často použitým příkladem v tomto textu je právě příklad 17, kde Z4 je tzv. množina zbytkových tříd. Zbytkovým třídám se budeme věnovat v příští kapitole, v této kapitole jsme pouze zmínili větu, v níž je klíčové zejména to, že operace „sčítání množin" je definována korektně, tj. bez ohledu na to, jaký prvek vybereme z první množiny a ze druhé množiny, výsledek jejich operace stále padne též do stejné množiny jako všechny ostatní takto zkonstruované výsledky. Věta 14 Existuje bijekce mezi podgrupou (H, v) cl každou pravou třídou H XJ a. 22Platí i analogická věta: Všechny levé třídy axj H ... 23Anglicky FACTOR znamená, „rozložit". 57 Důkaz: Bijekcí bude to nejpřirozenější zobrazení / : H —>■ H XJ ai které bychom asi vytvořili: f(h) = hxja. Takto definované / je injekce: f(h1) = f(h2)^ h1xja = h2xja^ hx = 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 XJ a Je tvaru h XJ a pro nějaké h £ H, a toto h je hledaným vzorem vzhledem k zobrazení /. Celkem / je tedy injekce i surjekce, a tedy bijekce. Důkaz je hotov. □ Důsledkem věty 14 pro konečné grupy G je: Všechny pravé třídy Hxj a mají tentýž počet prvků!!!!! Čtenář si určitě říká, kdy už přijde ta slavná Lagrangeova věta z názvu této kapitoly - už se blíží, je to věta následující!!! Ale ty nej důležitější věty, věta 12 a věta 14, už byly řečeny. Ta následující je pouze jejich důsledkem, tj. pan Lagrange je autorem souvislostí všech těchto vět. Podívejme se ovšem předtím na příklad ilustrující celou situaci: 1G| =5-lH| Obrázek 4.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 19 Uvažujme situaci na obrázku 4-8: všech pravých tříd vzhledem k podgrupě H konečné grupy G je pět - jedna z nich je H XJ e = H a další čtyři jsou H xj a, H XJ b, Hxjc, Hxjd. Existuje bijekce (podle věty 14) mezi těmito čtyřmi množinami a grupou H, tj. všech pět množin má stejný počet prvků. Při konečném počtu prvků grupy G by platil vztah \G\ =5 - \H\. Věta 15 Lagrangeova věta pro konečné grupy. Počet prvků libovolné podgrupy H je dělitelem počtu prvků konečné grupy G Algebra 1 (MA 0003) 58 (připomeneme-li si definici řádu grupy, tak: řád podgrupy H je dělitelem řádu grupy G). Důkaz Lagrangeovy věty je dalším důsledkem věty 14: 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 20 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 Ih). Příklad 21 Pokud \G\ je prvočíslo, tak grupa G má pouze nevlastní podgrupy (sebe samotnou a jednoprvkovou triviální podgrupu). Věta 16 Pokud \G\ = p je prvočíslo, tak grupa (G, v) je cyklická grupa a jakékoli a E G různé od neutrálního prvku e je jejím generátorem. Důkaz: Uvažujme a E G, a dále platí a ^ e (kde e je neutrální prvek). Rád prvku a je roven m > 1 (protože řádu 1 je pouze neutrální prvek grupy). Pak < a > je cyklická podgrupa, která má m prvků (a současně z předchozího platí m > 1), tj. celkem m\p A m > 1 => m = p (z neexistence vlastních dělitelů čísla p tedy plyne, že řád libovolného prvku a různého od e je roven p). □ Věta 16 je dalším důležitým faktem sama o sobě: existuje jediná grupa (až na izo-morfismus) daného prvočíselného počtu prvků. Například (Z?, +) je jediná sedmiprvková grupa, (Zn, +) je jediná jedináctiprvková grupa, apod. Získali jsme tedy úplnou informaci o grupách o prvočíselném počtu prvků - jsou cyklické, až na izomorfismus jediné (co se týká počtu prvků) a lze je generovat libovolným jejich prvkem a různým od neutrálního prvku. Věta 17 Rád každého prvku a E G je dělitelem řádu konečné grupy G. Důkaz: pro prvek c E G řádu m je < c > cyklickou podgrupou řádu m (libovolný prvek generuje cyklickou podgrupu grupy G), a tedy m je některý z dělitelů čísla což je řád grupy G. Definice 22 Protože přirozené číslo, které udává řád podgrupy \H\, je dělitelem řádu konečné grupy \G\, lze provést tuto operaci dělení přirozeným číslem a označit index podgrupy H v grupě G jako (G : H) = —— = počet navzájem různých tříd rozkladu {H \/a;aE G}. 59 5 Týden 05 5.1 Cvičení 05: Rád prvku, cyklické grupy, grupy zbytkových tříd V prvním týdnu jsme už mluvili o n-té mocnině prvku. Jednoduše v každé grupě platí i zákonitosti, na které jsme zvyklí např. z operace násobení na množině všech zlomků: • am y an = am+n, • (am)n = am-n, • a~n = (a-1)™. Při našem hloubavém přemýšlení o vlastnostech obecných grup se ukazuje důležitým jeden pojem, který je s otázkou mocniny přirozeně spjatý - pojem řádu prvku. Uvidíme, že tento pojem je důležitý zejména pro konečné grupy, a v nekonečných grupách hraje svou specifickou roli, která souvisí s nekonečnými množinami. Definice 23 Rád prvku a grupy (G, v) je roven nejmenšímu přirozenému číslu n, pro které an = e (n-tá mocnina prvku a E G je rovna neutrálnímu prvku e E G. Pokud takové přirozené číslo neexistuje, říkáme, že řád prvku a je nekonečný. Příklad 22 Co se týká řádu jednotlivých prvků grupy (6*3,0), platí: • id1 = id, tj. id je prvek řádu 1; • (2,3)2 = (1,3)2 = (1,2)2 = id, tj. prvky (2,3), (1,3), (1,2) jsou řádu 2; • (1, 2, 3)3 = (1, 3, 2)3 = id, tj. prvky (1, 2, 3), (1, 3, 2) jsou řádu 3. Z řádů jednotlivých prvků také vidíme, že existuje k = 6 (nejmenší společný násobek řádů jednotlivých prvků) tak, že libovolný z prvků umocněný na šestou se rovná jednotce id: id& = id, (2, 3)6 = ((2, 3)2)3 = id3 = id, (1, 3)6 = id, (1, 2)6 = id, (1, 2, 3)6 = ((1, 2, 3)3)2 = id2 = id, (1, 3, 2)6 = id. To je tedy zajímavá vlastnost, ke které jsme dospěli - v konečné grupě vždy po několikerém umocnění každého prvku dostaneme prvek jednotkový. Příklad 23 V grupě (Z, +) je řád všech prvků nekonečný, kromě prvku 0, jehož řád (jako řád každého neutrálního prvku) je roven jedné. Při krátkém zkoumání pojmu řádu prvku (ať už je konečný, nebo nekonečný), matematici dospěli k následujícím dvěma větám, které vrhají světlo na celou situaci: Algebra 1 (MA 0003) 60 Věta 18 Pro prvek a řádu n v grupě (G, v) platí: v této grupě existuje právě nrůzných hodnot a° = e = an (e je neutrální prvek grupy), a1, a2, ..., an~x. Důkaz: Dokážeme ve dvou částích: a) každá mocnina am prvku a řádu n je rovna některé z mocnin a°, a1, ..., a™-1; b) prvky a°, a1, ..., a™-1 jsou navzájem různé. Důkaz části a): Uvažujme libovolnou mocninu am prvku a E G, který je řádu n. Pak podle věty 21 z předmětu Základy matematiky (věta o dělení se zbytkem, která platí pro celá čísla - my ji nyní použijeme pouze pro čísla přirozená) vydělíme m : n a dostaneme, že existují přirozená čísla q, r tak, že m = n ■ q + r, 0 < r < n. Pak lze upravit am na tvar am = an-q+r = (an)q \J ar = eq \J ar = ar, a protože r je přirozené číslo, pro které 0 < r < n, musí být r rovno jednomu z čísel 0, 1, ..., n — 1. Důkaz části b): Zbývá dokázat, že prvky a°, a1, ..., a™-1 jsou navzájem různé. Pokud se některé z těchto dvou prvků rovnají, platí aľ = as, kde r i s jsou dvě různá čísla z množiny {0, 1, 2, ..., n — 1}, tj. r 7^ s. BUNO24 například s < r, tj. platí 0 < s < r < n, a tedy 0 < r — s < n. A protože ď = ď (to je náš předpoklad (p)), lze psát ar~s = ď y (a8)"1 = as y (a8)"1 = e. To je ovšem spor s definicí řádu n jako nejmenšího přirozeného čísla takového, že an = e, protože r — s < n. Náš předpoklad ar = as byl nesprávný, je tedy dokázán opak, že se jedná o n navzájem různých hodnot. □ Pokud se nad větou 18 zamyslíme, plyne z ní, že poté, co dosáhneme umocňováním prvku a konečného řádu n prvku an = e, další mocniny už nevytváří nové prvky, ale začínají opakovat předchozí prvky: an+1 = a, an+2 = a2, ..., a2™-1 = a™-1, a pak začíná druhé kolo opakování a2n = e, a2n+1 = a, atd. Věta 19 Pro prvek a nekonečného řádu v grupě (G, v) platí: v této grupě neexistují dvě mocniny tohoto prvku, které se rovnají, tj. pro dvě různá celá čísla r, s platí aľ 7^ as. Důkaz: je prostý, použijeme tutéž úvahu jako v důkazu věty 18, část b): Pokud by platilo aľ = as, úpravou aľ y (qS)_1 dostaneme ar~s = ar y (a8)"1 = as V (a")"1 = e, a to je spor s tvrzením, že řád prvku a je nekonečný, protože by existovala konečná mocnina prvku a rovná neutrálnímu prvku. Tj. předpoklad aľ = as je nesprávný a důkaz 24BUNO = Bez újmy na obecnosti. 61 sporem je hotov.□ To tedy znamená, že prvek nekonečného řádu „svým umocňováním"25 vede na nekonečně mnoho navzájem různých prvků grupy. A dodejme ještě větu, která upřesňuje situaci kolem konečného řádu prvku grupy: Věta 20 Pokud řád prvku a v grupě (G, v) je n ( označení 08 : označme ord(a) = n), pak platí pro celočíselné t: a* = e <^> (n\t, tj. t = nxj q, pro nějaké q G G). (mocnina prvku konečného řádu je rovna neutrálnímu prvku teháy a jen teháy26, káyž mocnitel t je násobek řááu n áaného prvku). Důkaz: Dokážeme obě implikace: Ad „=>": Důkaz je podobný jako důkaz věty 18, část a): Pokud a1 = e, pak podle věty o dělení se zbytkem pro celá čísla platí t = n - q + r, kde 0 < r < n. Pak dosazením do naší rovnosti dostaneme e = at = an-q+r = (an)q \J ar = e\j ar. Ale protože n jako řád prvku a je nejmenší přirozené číslo takové, že an = e, Nemůže být r > 0, ale musí r = 0. Důkaz opačné implikace „<=": je zřejmý ... pokud t = n ■ q, pak a1 = an-q = (an)q = eq = e. Cyklické grupy Pojem cyklické grupy a jejího generátoru (jediného prvku) už byl vysvětlen dříve v dodatcích v kapitole 1. Nyní se podívejme na cyklické grupy ještě jednou poté, co známe pojmy izomorfismus grup a řád prvku grupy: Je jasné, že pokud < a > je cyklická grupa generovaná svým prvkem, který je řádu n, platí < a >= {e, a, a2,..., a™"1}. Existuje tedy izomorfismus grupy (Hn, +) pootočení hodinové ručičky s operací skládání pootočení na grupu (< a >,v) definovaný vztahem fik) = ak pro k = 0,1,..., n — 1. Hned vidíme, že podmínka zachování výsledků operace je skutečně splněna: f(k + l) = ak+l = akVal = f(k)Vf(l). Touto kratinkou úvahou jsme vlastně dokázali větu 25Umocňování = opakované použití operace v na týž prvek. 26Pozná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ě if and only if = tehdy a jen tehdy, když. Algebra 1 (MA 0003) 62 Věta 21 Každá konečná cyklická grupa řádu n (= grupa generovaná jediným prvkem řádu n) je izomorfní grupě (Hn, +). Speciálně, každé dvě konečné cyklické grupy řádu n27 jsou navzájem izomorfní. A podobně pro cyklickou grupu generovanou prvkem nekonečného řádu: lze psát r —2 —1 2 3i < a >= {..., a , a , e, a, a , a , ... j, a tedy můžeme definovat izomorfismus grupy (Z,+) na grupu (< a >,v) definovaný vztahem f (k) = ak pro jakékoli celé číslo k, který opět splňuje podmínku zachování výsledků operace. Dostáváme tak větu Věta 22 Každá nekonečná cyklická grupa (= grupa generovaná jediným prvkem nekonečného řádu) je izomorfní grupě (Z, +). Speciálně, každé dvě nekonečné cyklické grupy jsou navzájem izomorfní. Tedy věty 21 a 22 nám dávají nahlédnout do situace cyklických grup: všechny cyklické grupy jsou víceméně určeny grupami celých čísel - ať už nekonečné grupy jsou určeny a popsány grupou (Z,+), tak konečné cyklické grupy jsou určeny a popsány (až na přeznačení prvků) grupou (Zn, +) (což je grupa zbytkových tříd modulo n, která je izomorfní grupě pootočení hodinové ručičky (Hn,+))). Mohli bychom pracovat stále s grupou pootočení hodinové ručičky ale protože studenti už grupy zbytkových tříd absolvovali na cvičení, lze pracovat přímo s nimi. Následuje oddílek opakující znalosti ze cvičení o grupách zbytkových tříd. Grupy zbytkových tříd Klíčovou strukturu představuje následující pojem: Definice 24 množina zbytkových tříd modulo n ... popíšeme celou konstrukci této množiny například pro n = 6: Rozdělíme všechna celá čísla do šesti podmnožin podle toho, jak daleko je dané číslo na číselné ose vpravo od nejbližšího násobku čísla 6 (viz obrázek 5.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. 27Připomínka bizarní definice řádu grupy: řád grupy = počet prvků grupy. G3 Obrázek 5.9: Rozdělení celých čísel do šesti podmnožin. • Třída [3] obsahuje čísla 3, 9, 15, atd. ale také záporná čísla —3, —9, —15, atd. • Třída [4] obsahuje čísla 4, 10, 16, atd. ale také záporná čísla —2, —8, —14, atd. • Třída [5] obsahuje čísla 5, 11, 17, atd. ale také záporná čísla —1, —7, —13, atd. • A konečně třída [0] obsahuje všechna celá čísla dělitelná šesti, tj. 0, 6, 12, atd. ale také záporná čísla —6, —12, —18, atd. V každé třídě takto vytvořené jsou právě ta celá čísla, která jsou mezi sebou kongruentní modulo 6. Každá z daných těchto šesti podmnožin je nekonečná, odtud tedy honosný název „třída". Nyní se budeme dále dívat na tyto třídy jako na prvky množiny Z6 (tj. množina Z6 je konečná a má jen šest prvků!!!) a definujeme na této množině operace ©, 0 následovně: [a] © [b] := [a + b\; tj. součet tříd je třída, která obsahuje celé číslo a + b, [a] ©[&]:= [a-b]: Algebra 1 (MA 0003) 64 tj. součin tříd je třída obsahující celé číslo a ■ b. Lze ukázat, že tyto dvě operace nezávisí na výběru celých čísel a, b z daných nekonečných množin. Pro takto definovanou šestiprvkovou množinu a operace na ní nyní platí, že (Zq, 0) je grupa (zbytkových tříd modulo 6), (Zq*, ©) = (Zq — {[0]}, 0) je monoid (zbytkových tříd modulo 6). Příklad 24 a) Pomocí tabulky operace 0 dokažte, že (Zq,(B) je grupa: Tabulka 5.8: Tabulka operace 0 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] b) Pomocí tabulky operace 0 dokažte, že(Ze,Q) je monoid: Tabulka 5.9: Tabulka operace 0 na množině Zq. 0 [0] [1] [2] [3] [4] [5] [0] [0] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [4] [5] [2] [0] [2] [4] [0] [2] [4] [3] [0] [3] [0] [3] [0] [3] [4] [0] [4] [2] [0] [4] [2] [5] [0] [5] [4] [3] [2] [1] • označení 09 : Zn • označení 10 : Z* množina zbytkových tříd modulo n; množina zbytkových tříd modulo n mimo prvek [0], tj. Z*n:=Zn-{[0]}. Toto označení používáme i pro klasické množiny Q* (racionální čísla mimo nuly), R* (reálná čísla mimo nuly), protože se nám hodí, že (Q*, •), (R*, •) jsou grupy (nulu 65 z těchto množin musíme vyloučit, protože pro ni neexistuje inverzní prvek vzhledem k operaci násobení). Zbytkové třídy lze sestavit nejen pro n = 6, ale pro jakékoli přirozené n > 1. Následující dvě věty studenti nemusí umět dokázat (ale je dobré si zapamatovat, co říkají): Věta 23 Ve struktuře (Z*, 0) existuje k prvku [k] inverzní prvek vzhledem k násobení 0 právě tehdy, když k, n jsou nesoudělná. Například v (Zq, 0) neexistují k prvkům [2], [3], [4] inverzní prvky, protože čísla 2, 3, 4 jsou soudělná s číslem 6. Věta 24 Důsledek předchozí věty: Pokud n je prvočíslo, tak k, n jsou nesoudělná čísla pro k = 1, 2,. .., (n — 1), tj. ke všem prvkům (kromě [0], kterou jsme vyloučili) existují inverzní prvky vzhledem k násobení Q, a tedy (Z*, 0) je grupa. Například (Zy,Q) je grupa. Čtenář by se o tom mohl snadno přesvědčit z tabulky operace 0 na množině Z7: 0 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1] Úloha 5.1 Cvičení k pojmu řád prvku: Ad Pinter 2010, str. 107-110: • Cvičení B (str. 108): Příklady řádu prvků. Například N.4-' Na grupě permutací (5V, °) jsou zadány prvky (formou součinu cyklů, který vypočtěte) a = (1,2,3,4) o (2,4,5), /3 = (1,6,7) o (2,5,7). Vypočtěte prvek (a3 o /34)5 a určete jeho řád. • Cvičení F: řád mocnin prvku. • Cvičení G: vztah mezi ord(a) a ord(ak). Úloha 5.2 Cvičení k pojmu cyklická grupa: • Na přednášce už nezbyl čas na důkaz věty: každá podgrupa cyklické grupy je cyklická, tj. lze ji generovat jediným prvkem - kterým?? (viz Pinter 2010, str. 114-115). • Cvičení A (str. 115): příklady cyklických grup. • Cvičení B: elementární vlastnosti cyklických grup. Algebra 1 (MA 0003) 66 • Cvičení C: generátory cyklické grupy. • Cvičení E: kartézský součin cyklických grup. Úloha 5.3 Cvičení k pojmu grupy zbytkových tříd: Například D. 2 z knihy Pinter 2010, str. 98: Všechny následující čtyři grupy jsou šestiprvkové. Vytvořte jejich rozklad do tříd tak, že v jedné třídě jsou grupy navzájem izomorfní. Najděte daný izomorfismus, popřípadě vysvětlete, proč grupy v různých třídách izomorfní nejsou. Grupa (5*3, o) permutací tříprvkové množiny na sebe sama - tabulku operace najdete v přednášce o nekomutativních grupách. Grupa (Z%, 0) (je vyloučena třída [0], ke které neexistuje inverze vzhledem k násobení): 0 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1] (Z6, ©) je grupa: © [0] [1] [2] [3] [4] [5] [0] [0] [1] [2] [3] [4] [5] [1] [1] [2] [3] [4] [5] [0] [2] [2] [3] [4] [5] [0] [1] [3] [3] [4] [5] [0] [1] [2] [4] [4] [5] [0] [1] [2] [3] [5] [5] [0] [1] [2] [3] [4] Grupa (H3 x H2, +): + [0 0] [0 1] [1 0] [1 1] [2 0] [2 1] [0; 0] [0 0] [0 1] [1 0] [1 1] [2 0] [2 1] [0; i] [0 1] [0 0] [1 1] [1 0] [2 1] [2 0] [i; 0] [1 0] [1 1] [2 0] [2 1] [0 0] [0 1] [i; 1] [1 1] [1 0] [2 1] [2 0] [0 1] [0 0] [2; 0] [2 0] [2 1] [0 0] [0 1] [1 0] [1 1] [2; 1] [2 1] [2 0] [0 1] [0 0] [1 1] [1 0] 67 Napríklad N.l: Jsou grupy (Zq, +) a (z3 x Z3) izomorfní? Pokud ano, daný izomorfis-mus najděte. Pokud ne, vysvětlete, proč izomorfní být nemohou. © [0] [1] [2] [3] [4] [5] [6] [7] [8] [0] [0] [1] [2] [3] [4] [5] [6] [7] [8] [1] [1] [2] [3] [4] [5] [6] [7] [8] [0] [2] [2] [3] [4] [5] [6] [7] [8] [0] [1] [3] [3] [4] [5] [6] [7] [8] [0] [1] [2] [4] [4] [5] [6] [7] [8] [0] [1] [2] [3] [5] [5] [6] [7] [8] [0] [1] [2] [3] [4] [6] [6] [7] [8] [0] [1] [2] [3] [4] [5] [7] [7] [8] [0] [1] [2] [3] [4] [5] [6] [8] [8] [0] [1] [2] [3] [4] [5] [6] [7] f [0 0] [ 0 1] [0;2] [1 0] [i;i] [1 2] [2 0] [2 1] [2 2] [0 0] [0 0] [ 0 1] [0;2] [1 0] [i;i] [1 2] [2 0] [2 1] [2 2] [0 1] [0 1] [ 0 2] [0;0] [1 1] [i;2] [1 0] [2 1] [2 2] [2 0] [0 2] [0 2] [ 0 0] [0; i] [1 2] [i;0] [1 1] [2 2] [2 0] [2 1] [1 0] [1 0] [ 1 1] [i;2] [2 0] [2;i] [2 2] [0 0] [0 1] [0 2] [1 1] [1 1] [ 1 2] [i;0] [2 1] [2; 2] [2 0] [0 1] [0 2] [0 0] [1 2] [1 2] [ 1 0] [i;i] [2 2] [2;0] [2 1] [0 2] [0 0] [0 1] [2 0] [2 0] [ 2 1] [2; 2] [0 0] [0;i] [0 2] [1 0] [1 1] [1 2] [2 1] [2 1] [ 2 2] [2;0] [0 1] [0;2] [0 0] [1 1] [1 2] [1 0] [2 2] [2 2] [ 2 0] [2;i] [0 2] [0;0] [0 1] [1 2] [1 0] [1 1] Například N.2: Najděte minimální (vzhledem k počtu prvků) množinu generátorů grupy (Z2 x Z2 x Z2,®): © [o 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1;0 1] [1 1 0] [1 1 1] [0 0; 0] [o 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1;0 1] [1 1 0] [1 1 1] [0 0; 1] [o 0 1] [0 0 0] [0 1 1] [1 0 1] [0 1 0] [1;0 0] [1 1 1] [1 1 0] [0 1;0] [o 1 0] [0 1 1] [0 0 0] [1 1 0] [0 0 1] 1] [1 0 0] [1 0 1] [1 0; 0] [i 0 0] [1 0 1] [1 1 0] [0 0 0] [1 1 1] [0;0 1] [0 1 0] [0 1 1] [0 [0 1 1] [0 1 0] [0 0 1] [1 1 1] [0 0 0] 0] [1 0 1] [1 0 0] [1 0; 1] [1 0 1] [1 0 0] [1 1 1] [0 0 1] [1 1 0] [0;0 0] [0 1 1] [0 1 0] [1 1;0] [1 1 0] [1 1 1] [1 0 0] [0 1 0] [1 0 1] [0;1 1] [0 0 0] [0 0 1] [1 [1 1 1] [1 1 0] [1 0 1] [0 1 1] [1 0 0] [0;1 0] [0 0 1] [0 0 0] Algebra 1 (MA 0003) 68 Napríklad D. 3: Všechny následující tři grupy jsou osmiprvkové. Zjistěte, zda některé z těchto grup jsou izomorfní, popřípadě vysvětlete, proč izomorfní nejsou: Grupa (Zg,©): © [0] [1] [2] [3] [4] [5] [6] [7] [0] [0] [1] [2] [3] [4] [5] [6] [7] [1] [1] [2] [3] [4] [5] [6] [7] [0] [2] [2] [3] [4] [5] [6] [7] [0] [1] [3] [3] [4] [5] [6] [7] [0] [1] [2] [4] [4] [5] [6] [7] [0] [1] [2] [3] [5] [5] [6] [7] [0] [1] [2] [3] [4] [6] [6] [7] [0] [1] [2] [3] [4] [5] [7] [7] [0] [1] [2] [3] [4] [5] [6] Grupa (Z2 x Z2 x Z2,®): + [0 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [0 0 0] [0 0 0] [0 0 1] [0 1 0] [1 0 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [0 0 1] [0 0 1] [0 0 0] [0 1 1] [1 0 1] [0 1 0] [1 0 0] [1 1 1] [1 1 0] [0 1 0] [0 1 0] [0 1 1] [0 0 0] [1 1 0] [0 0 1] [1 1 1] [1 0 0] [1 0 1] [1 0 0] [1 0 0] [1 0 1] [1 1 0] [0 0 0] [1 1 1] [0 0 1] [0 1 0] [0 1 1] [0 1 1] [0 1 1] [0 1 0] [0 0 1] [1 1 1] [0 0 0] [1 1 0] [1 0 1] [1 0 0] [1 0 1] [1 0 1] [1 0 0] [1 1 1] [0 0 1] [1 1 0] [0 0 0] [0 1 1] [0 1 0] [1 1 0] [1 1 0] [1 1 1] [1 0 0] [0 1 0] [1 0 1] [0 1 1] [0 0 0] [0 0 1] [1 1 1] [1 1 1] [1 1 0] [1 0 1] [0 1 1] [1 0 0] [0 1 0] [0 0 1] [0 0 0] Grupa (_D4, o) z příkladu 16: o id (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) (1,3) (2,4) (1,2) " (3,4) (1,4) ° (2,3) id id (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) (1,3) (2,4) (1,2) ° (3,4) (1,4) ° (2,3) (1,2,3,4) (1,2,3,4) (1,3) ° (2,4) (1,4,3,2) id (1,4) ° (2,3) (1,2) - (3,4) (1,3) (2,4) (1,3) ° (2,4) (1,3) ° (2,4) (1,4,3,2) id (1,2,3,4) (2,4) (1,3) (1,4) o (2,3) (1,2) ° (3,4) (1,4,3,2) (1,4,3,2) id (1,2,3,4) (1,3) ° (2,4) (1,2) ° (3,4) (1,4) ° (2,3) (2,4) (1,3) (1,3) (1,3) (1,2) ° (3,4) (2,4) (1,4) ° (2,3) id (1,3) - (2,4) (1,2,3,4) (1,4,3,2) (2,4) (2,4) (1,4) ° (2,3) (1,3) (1,2) ° (3,4) (1,3) ° (2,4) id (1,4,3,2) (1,2,3,4) (1,2) ° (3,4) (1,2) ° (3,4) (2,4) (1,4) ° (2,3) (1,3) (1,4,3,2) (1,2,3,4) id (1,3) ° (2,4) (1,4) ° (2,3) (1,4) ° (2,3) (1,3) (1,2) ° (3,4) (2,4) (1,2,3,4) (1,4,3,2) (1,3) ° (2,4) id 69 Napríklad N.3: Definujte presne izomorfismus (Zy,Q) na (Zq,(B), který zachováva výsledky operace. Grupa (Zy,Q) (je vyloučena třída [0], ke které neexistuje inverze vzhledem k násobení): 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 (Z6, ©): © [0] [1] [2] [3] [4] [5] [0] [0] [1] [2] [3] [4] [5] [1] [1] [2] [3] [4] [5] [0] [2] [2] [3] [4] [5] [0] [1] [3] [3] [4] [5] [0] [1] [2] [4] [4] [5] [0] [1] [2] [3] [5] [5] [0] [1] [2] [3] [4] Výsledky některých cvičení najdete v závěru textu v oddílu 12.5. Algebra 1 (MA 0003) 70 5.2 Přednáška 05 Tato přednáška nepřináší nové pojmy a zákonitosti, pouze procvičuje už dříve probrané - stejně na příkladech lze všechny pojmy vidět nejlépe. Na 1. přednášce jsme se začali zabývat různými vlastnostmi operace na množině -většinou dosti základními vlastnostmi, které platí pro běžné operace sčítání a násobení reálných čísel: (1) uzavřenost operace = neomezená definovanost operace na dané množině (2) asociativita operace (3) existence neutrálního prvku dané množiny vzhledem k této operaci (4) existence inverzních prvků (5) komutativita operace Na některých množinách se definuje více operací, přichází zde do hry souhrn těchto operací, ale tomu bude věnována samostatná přednáška. Jednotlivé vlastnosti operace lze dobře studovat v tzv. tabulce operace, až snad na asociativitu (2), jejíž platnost hned tak neodhalíme, ale stejně ji mezi základní vlastnosti počítáme, protože axiom asociativity platí pro sčítání i násobení přirozených i reálných čísel a asociativitu lze lehce dokázat pro skládání zobrazení i skládání geometrických transformací, tj. velká řada běžných operací asociativitu splňuje. Na 2. přednášce jsme pokračovali ve studiu těchto tabulek operace, ať už množin konečných nebo nekonečných - operace na nekonečné množině je dosti zdlouhavé do tabulky kreslit, ale přesto se o to pokoušíme alespoň u několika prvků dané množiny, protože se tímto schématem vyjasní, které dva prvky do operace vstupují a který prvek je výsledkem. Zjistili jsme, že (Hq, +) je komutativní grupa, (Z, +) je komutativní grupa, (CF, o) je nekomutativní monoid, (63, o) je nekomutativní grupa, (Zq, •) je komutativní monoid. Na 3. přednášce jsme zavedli pojmy homomorfismu a izomorfismu mezi algebraickými strukturami, minimálně mezi grupoidy, protože oba tyto typy zobrazení zachovávají výsledky operace, a to všechny (tzv. vlastnost ZVO). Každý izomorfismus je současně homomorfismem, ale nikoliv naopak, protože na rozdíl od homomorfismu je izomorfismus ještě navíc bijekce. Pokud zjistíme, že jsou dvě algebraické struktury izomorfní, znamená to nejen, že mají „stejný počet prvků" (u nekonečných množin říkáme, že mají stejnou mohutnost), ale operace V na množině M\ se chová zcela stejně, jako operace * na druhé množině Mi. Každý výsledek operace se zobrazí na příslušný výsledek operace (ZVO): f(aVb) = f(a)*f(b). Ad příklad 9: (R,+) a (R+, •) jsou izomorfní komutativní grupy. Izomorfismus lze definovat vztahem / : (R, +) —> (R+, •) tak, že f(x) = ex. Jedná se skutečně o bijekci -každému reálnému x (i třeba zápornému) se přiřadí číslo ex, které je vždy kladné (i když 71 x je záporné). Naopak ke každému reálnému číslu y lze inverzní funkcí lny přiřadit reálné číslo x tak, že ex = y. Navíc platí ZVO: f(a + b) = f(a)-f(b). ea+h = ea ■ eh. Důležité je, že izomorfismus zachovává přesně stejné algebraické vlastnosti. Tam, kde jsou při zobrazení mezi algebraickými strukturami zachovány jen některé vlastnosti, mluvíme o homomorfismu. Zmiňovali jsme příklad homomorfismu h : (Z, +) —> (Zq, +), který zobrazuje nekonečnou množinu na množinu konečnou - „ztrácí" informaci o daném celém čísle, zachovává pouze informaci o tom, jaký je zbytek daného celého čísla po dělení šesti. Říkal jsem vám, že matematik a chemik Cayley dokázal větu: Každá grupa je izomorfní nějaké podgrupě grupy permutací (Sn, o). Tato věta v podstatě říká, že studium jakékoliv množiny a jakékoliv operace na ní lze převést na studium operace skládání permutací na nějaké podmnožině množiny Sn, což je z matematického úhlu pohledu hodně zajímavé. Běžný uživatel matematiky se s Cayleyho větou setká v tom smyslu, že pomocí ní bylo dokázáno (Gauss, Galois), že neexistuje vzorec analogický vzorci x12 = ~b±X^2~4— pro algebraické rovnice stupně 5 a více, což je sice negativní skutečnost, ale je to skutečnost. Nyní na 5. přednášce již jenom shrneme to, co bylo dosud řečeno k algebraickým strukturám s jednou operací, na několika příkladech. V přednášce 6 se už začneme věnovat studiu množin, na kterých jsou definovány dvě operace. Příklad 25 Cvičení na podgrupy, které využívá poznatku Lagrangeovy věty: Počet prvků podgrupy konečné grupy je dělitelem počtu prvků této grupy. Pro grupu (D5, o), kde D5 je desetiprvková množina transformací pravidelného pětiúhelníka na sebe sama a operace o (=„po") je skládání transformací, vypište všechny její podgrupy. Použijte přitom informace o jejích prvcích (zachovejte prosím označení): • e ... identita (nedělá s pětiúhelníkem nic); • f ... pootočení pětiúhelníka v jeho středu o 72 0 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; Algebra 1 (MA 0003) 72 • w ... osová souměrnost vzhledem k ose CW, kde C je vrchol pětiúhelníka a W je střed strany E A; • x ... osová souměrnost vzhledem k ose DX, kde D je vrchol pětiúhelníka a X je střed strany AB; • y ... osová souměrnost vzhledem k ose EY, kde E je vrchol pětiúhelníka a Y je střed strany BC; a informace o vlastnostech, které platí: • Podle Lagrangeovy věty můž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ů); • ještě musíte do každé podgrupy zahrnout i všechny příslušné inverzní prvky. \D5\ = 10, tj. kromě triviálních podgrup Pi = {id}, P2 = D5 budou existovat ještě podgrupy, jejichž počet prvků je dělitelem čísla 10, tj. podgrupy dvouprvkové a pětiprvkové. Pokusme se všechny najít pomocí označení permutacemi pětiprvkové množiny: Klíčem je označit si vrcholy čísly 1 až 5, pak: • e = id; • / = (1,2,3,4,5); • 9 = (1,3,5,2,4); • h = (1,4,2,5,3); • i = (1,5,4,3,2); • u = (2,5) o (3,4) 73 • v = (1,3) o (4,5); • w = (1,5) o (2,4); • x = (1,2) o (3,5); . y = (1,4) o (2, 3). Je vidět, že pětiprvková podmnožina všech pootočení tvoří podgrupu P3 = {e, /, g, h, i}. Obsahuje všechny inverze: e e, f i, g h. Podobně jako tomu bylo i u D3 a D4, osové souměrnosti jsou inverzemi sebe sama, tj. jejich připojením k neutrálními prvku dostaneme dvouprvkové podgrupy: P4 = {e, u}, P5 = {e, v}, P6 = {e, w}, P7 = {e, x}, P8 = {e, y}. Žádné další netriviální podgrupy, než těchto šest, už neexistují. Celkem má tedy D5 osm podgrup. • Když vezmeme jakékoliv pootočení kromě identity, už pomocí něho vygenerujeme všechna další pootočení - a protože podgrupa musí být uzevřená na výsledek operace (= na složení transformací), musíme ty další pootočení přidat do téže podgrupy -tj. až vezmeme jakákoli dvě různá pootočení, musíme už do stejné podgrupy přidat i tři další pootočení. Např. f = f P = f°f = 9 r = f°f°f = h ř = f°f°f°f = * /5=/o/o/o/o/ = e Takové podgrupě, který je generována jediným prvkem, říkáme cyklická: P3 = (/) • • • je generovaná („vytvořená") prvkem /. • Kdybychom k některé z podgrup P4, P5, Pq, P7, P$ přidali jediný další prvek, už by nutně (aby platila uzavřenost operace) vygeneroval celou množinu D5. Např. přidáním w k množině P4 = {e,u}: w o u = (1,5) o (2,4) o (2,5) o (3,4) = (1,5,4,3,2) = i díky uzavřenosti podgrupy na operaci by už i muselo nutně ležet v naší podgrupě í2 = h díky uzavřenosti podgrupy na operaci by už h muselo nutně ležet v naší podgrupě iA = g díky uzavřenosti podgrupy na operaci by už g muselo nutně ležet v naší podgrupě í4 = f díky uzavřenosti podgrupy na operaci by už / muselo nutně ležet v naší podgrupě i o u = (1,5,4,3,2) o (2,5) o (3,4) = (1,5) o (2,4) = w díky uzavřenosti podgrupy na operaci by už w muselo nutně ležet v naší podgrupě Algebra 1 (MA 0003) 74 h o u = (1,4,2,5,3) o (2,5) o (3,4) = (1,4) o (2,3) = y díky uzavřenosti podgrupy na operaci by už y muselo nutně ležet v naší podgrupě g o u = (1,3,5,2,4) o (2,5) o (3,4) = (1,3) o (4,5) = v díky uzavřenosti podgrupy na operaci by už v muselo nutně ležet v naší podgrupě / o u = (1,2,3,4,5) o (2,5) o (3,4) = (1,2) o (3,5) = x díky uzavřenosti podgrupy na operaci by už x muselo nutně ležet v naší podgrupě Tímto generováním už nutně dostaneme celou desetiprvkovou množinu D5. • Příklad 26 Cvičení k pojmu levá a pravá třída prvku vzhledem k podgrupě (Pinter 2010, str. 130-135): • A. Příklady tříd prvku vzhledem k podgrupě konečné grupy • B. Příklady tříd prvku vzhledem k podgrupě nekonečné grupy: Například N.l: H =< 5 > je podgrupa grupy (Z, +) generovaná prvkem 5. Vypište všechny pravé třídy prvků vzhledem k podgrupě H. • C. Důsledky Lagrangeovy věty • D. Další důsledky Lagrangeovy věty • E. Vlastnosti tříd prvku vzhledem k podgrupě. Příklad 27 Lagrangeova věta (a její důsledek - věta 16) společně s větou 21 nám pomalu, ale jistě dává informace o všech konečných grupách o malém počtu prvků: • Jednoprvková grupa je (až na izomorfismus) jediná a obsahuje pouze neutrální prvek. • Grupa o prvočíselném počtu prvků 2, 3, 5, 7, atd. je cyklická (věta 16), a tedy až na izomorfismus stejná jako (Hp,+) neboli (Zp,+) (věta 21), tedy grupa prvočíselného počtu prvků je až na izomorfismus jediná. • Dále grupa o počtu prvků p2, který je druhou mocninou prvočísla, je podle cvičení G (Pinter 2010, str. 154-155) izomorfní buď (Zp2,+), nebo (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. Následující příklady viz Pinter 2010, str. 141-146: Příklad 28 Například A.l. 75 a) Definujte nějaký (aspoň jeden) homomorfismus f : (Z$, +) —> (Z4,+): /01234567\ b) Určete jádro K homomorfismu z části (a). Příklad 29 Například A.5: Každá z dvanácti transformací pravidelného šestiúhelníka v grupě (Dq, o) (šest pootočení o násobek šedesáti stupňů, včetně identity = pootočení o úhel nulový; dalších šest jsou osové souměrnosti podle tří úhlopříček procházejících protějšími vrcholy (A,D a B,E a C,F) a podle tří spojnic středů protějších stran) nějak permutuje jeho tři úhlopříčky, které si označme čísly 1 (AD), 2 (BE) a 3 (CF), tj. tato současná permutace šesti vrcholů a permutace tří úhlopříček definuje homomorfismus f : Dq —> s3, v obou grupách uvažujeme operaci skládání permutací. Například f{id6)=id3, /(1,2,3,4,5,6) = (1,2,3). Napište, na jaké prvky se zobrazí tímto homomorfismem zbylých deset prvků grupy Dq. Grupa (£3,0) má prvky: id, (1,2,3), (1,3,2), (2,3), (1,3), (1,2). Příklad 30 B. Příklady homomorfismu nekonečných grup: Například B.2: Zdůvodněte, proč zobrazení ip je grupovým homomorfismem, a najděte jeho jádro: (p : (D(R), +) —> (F(R), +) je definované vztahem (p(f) = f (D(R) je množina reálných funkcí, u kterých existuje jejich derivace f, a F{R) je množina reálných funkcí). Například B.3: Zdůvodněte, proč zobrazení f je grupovým homomorfismem, a najděte jeho jádro: f : {R x R, +) —> (R, +) je definované vztahem f ([x, y]) = x + y ((R x R, +) je množina je množina uspořádaných dvojic reálných čísel, které sčítáme po složkách). Příklad 31 F. Homomorfismus a řád prvku (postup a výsledky tohoto příkladu viz 12.5). Například F.l: Pro homomorfismus grup f : (G, v) ~~^ (H, *) je a E 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. Algebra 1 (MA 0003) 76 Napríklad N.4: Pomocí věty 9 a předchozích dvou větiček F.í, N.3 najděte všechny možné homomorfismy z příkladu A.í, tj. všechny možné homomorfismy grupy (Z$, ©) do grupy (Z4,®) a určete jejich jádra. Například N.2: Vypište všechny prvky grup (Z9,®), (6*3,0) a u každého prvku určete jeho řád. Potom popište všechny možné homomorfismy grupy (Zq, ©) do grupy (6*3,0), které existují - musíte při každém z nich určit, kam se zobrazí každý prvek množiny Zq. U každého z těchto homomorfismů určete jeho jádro. Příklad 32 Například N.l: Uvažujme homomorfismus ip grupy (Z$, ©) do grupy (Z4,®) definovaný y?(0) = 0, <^(1) = 1, atd. a) Určete jádro K tohoto homomorfismů; b) Jaké prvky má faktorgrupa Z$/K s operací rozšířenou na třídy? Je možné vyjádřit obrázkem, ale vyznačte zřetelně prvky faktorgrupy. Výsledky některých příkladů najdete v závěru textu v oddílu 12.5. 77 6 Týden 06 6.1 Přednáška 06: struktury se dvěma operacemi Okruh je po grupě druhou základní definicí struktury v kursech moderní algebry A je to definice naprosto přirozená. Když totiž zkoumáme množinu Z, nikdy o ní ne přemýšlíme jako o množině s jedinou operací, ale máme současně na mysli sčítání (odčítání je skryto v inverzních prvcích) a násobení (dělení je skryto v inverzních prvcích). Matematik se tedy snaží formulovat, jaké zákonitosti platí pro interakci operací + a •. Tato interakce je popsána v definici algebraické struktury zvané okruh: Definice 25 okruh (anglicky: ring) je množina (M, +, •) s operacemi + a ■, které splňují vlastnosti: a) Operace + splňuje vlastnosti (1), (2), (3), (4), (5), tj. (M,+) je komutativní grupa; b) operace ■ splňuje vlastnosti (1), (2), (3), tj. množina (M, •) je monoid (= pologrupa s jednotkou); c) interakce operací + a ■ splňuje tzv. distributivní zákon = vlastnost (6): (rovnice jsou dvě díky tomu, že operace • není obecně komutativní). Příklad 33 • Příkladem konečného okruhu je struktura zbytkových tříd (Zn, ©, ©). • Příkladem nekonečného okruhu je (Z, +, •), tedy množina celých čísel s tradičními operacemi sčítání a násobení. Podívejme se např. na množinu Zq zbytkových tříd, kde jsou celá čísla rozdělena do 6 podmnožin podle toho, jaký zbytek dávají po dělení šesti. Pouze z pohodlnosti tyto zbytkové třídy označujeme stejně jako celá čísla 0,1, 2, 3,4, 5. Na takto definovaných prvních lze zavést operace sčítání a násobení s následujícími tabulkami: V x,y, z E M : x ■ (y + z) x ■ y + x ■ z, (y + z)-x = y- x + z- x + 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 1 2 3 4 5 0 2 3 4 5 0 1 3 4 5 0 1 2 4 5 0 1 2 3 5 0 1 2 3 4 Algebra 1 (MA 0003) 78 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 Když prozkoumáme vlastnosti těchto operací, tak zjistíme, že a) + splňuje vlastnosti (0), (1), (2), (3), (4), (5) b) • splňuje vlastnosti (0), (1), (2), (3), (5), nesplňuje vlastnost (4), protože neexistují inverze vzhledem k násobení pro prvky 0, 2, 3, 4. c) +, • splňuje distributivní zákony (6a), (6b). Tedy celkem (Zq, +, •) je komutativní okruh. Ovšem struktura (Zn, ■) vykazuje určité defekty, tj. obsahuje tzv, netriviální dělitele nuly: Definice 26 nenuloví dělitelé nuly jsou takové prvky a, b množiny M, které se nerovnají nule (0 = neutrální prvek v grupě (M,+)), ale jejich součin (= výsledek operace násobení v pologrupě (M, ■)) je roven nule: a ■ b = 0; Příklad 34 Množina Z§ zbytkových tříd modulo 6 je příkladem struktury s nenulovými dělitely nuly: její prvky [2], [3] nebo [3], [4] jsou nenuloví 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, 0) vidíme, že [2] 0 [2] = [2] 0 [5], ale nemůžeme vykrátit z rovnosti třídu [2], protože [2] ^ [5] . Netriviální dělitelé nuly jsou dosti překvapivým jevem, který například u celých čísel nenastane - a také nežádoucím jevem. Okamžitá otázka pro matematický popis vyvstává, kdy se taková situace vyskytne a jak zaručit, že k ní nedojde. Z tohoto důvodu definujeme obor integrity: 79 Definice 27 obor integrity28 (anglicky: integrál domain) je množina29 (M,+, •) s operacemi + a ■, která je okruhem a navíc jsou splněny vlastnosti: ad a) Operace + nesplňuje nic navíc; ad b) operace ■ splňuje navíc: • M neobsahuje netrivální dělitele nuly (vzhledem k operaci ■); • vlastnost (5), tj. operace ■ je komutativní na M; ad c) díky komutativně operace ■ lze distributivní zákon psát v jeáiné rovnici: V x,y, z £ M : x-{y + z)=x-y + x- z = y- x + z- x={jj + z)-x. Příklad 35 • (Z7, ©, ©) je konečný obor integrity, protože 7 je prvočíslo, tj. (Zy, ©) neobsahuje netriviální áělitele nuly. • (Z, +, •) je nejen nekonečný okruh, ale i nekonečný obor integrity, protože neobsahuje netriviální áělitele nuly a násobení je komutativní, a teáy áistributivní zákon lze psát v jeáné 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 28 Těleso (anglicky: fielá ... 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), teáy (M — {0}, •) je grupa30; ad c) záe nic nového. 28Vý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. 29 Aby byla definice naprosto čistá, měli bychom dodat, že množina je minimálně dvouprvková, obsahuje totiž nulu jako jednotkový prvek vzhledem ke sčítání a jedničku jako jednotkový prvek vzhledem k násobení aO^l. 30Vlastnost (4) je silnější než vlastnost „neobsahuje netriviální dělitele nuly", tj. u bodu b) je dostatečné uvést, že operace • u tělesa splňuje (1),(2),(3),(4),(5). Lze dokázat tvrzení, že každé těleso je i oborem integrity, tj. těleso „neobsahuje netriviální dělitele nuly". Algebra 1 (MA 0003) 80 Příklad 36 • (Z?, ©, 0) je konečný obor integrity, ale též i konečné těleso, protože v případě konečné množiny M pojmy obor integrity a těleso splývají. • (Q, +, •) je nekonečné těleso, protože (Q — {0}, •) je grupa ... je splněna i vlastnost (4), že množina M obsahuje i inverzní prvky vzhledem k operaci násobení. • (Z, +, •) je nekonečný obor integrity, který není tělesem, protože množina Z neobsahuje většinu inverzních prvků vzhledem k operaci násobení. Tedy pojmy okruh, obor integrity a těleso představují struktury stále silnějších vlastností: Obrázek 6.10: Vztah mezi pojmy okruh, obor integrity, těleso. Příklad 37 Zjistěte, co jsou z algebraického hlediska struktury a) (2A, U, Pi), b) (2A, n, U) (2A . .. množina všech podmnožin množiny A pro A = {1, 2, 3, 4, 5}). a) (2A,U,n): Vypišme si vlastnosti operací U: (1), (2), (3) („nula" je 0), (5). ((4) neplatí, protože {1} U X = 0 pro žádnou podmnožinu X) H: (1), (2), (3) („jednotka" je A), (5). ((4) neplatí, protože (l}íll = {1,2,3,4,5} pro žádnou podmnožinu X) {1} n {2, 3} = 0 ... existují zde nenuloví dělitelé nuly! distributivní zákon (6): X n (Y U Z) = (X n Y) U (X n Z) ... lze dokázat Vennovými diagramy. Tuto strukturu bychom snad mohli nazvat polookruh, který obsahuje nenulové dělitele nuly, protože množina podmnožin není grupou vzhledem k žádné z operací u, n. b) (2A, n, U): Vlastně se jedná o tytéž operace, pouze vlastnost (6) je naopak (sjednocení ve významu „násobení", průnik ve významu „sčítání"): X U (Y n Z) = (X Uľ)í1 (X U Z) {1, 2} U {3, 4, 5} = A ... existují zde nenuloví dělitelé nuly! Opět (2A, n, U) je polookruh, který obsahuje nenulové dělitele nuly. 81 Co je na příkladech a), b) zajímavé, je to, že distributivní zákon zde platí, i když zaměníme pořadí obou operací! x n (Y u z) = (x n Y) u (x n z) x u (Y n z) = (x u Y) n (x u z) To je z algebraického hlediska hodně zajímavé a vedlo to ke studiu množiny všech podmnožin, zavedení pojmu distributivní uspořádané množiny, atd. a matematici zavedli označení, na základě něhož se množina všech podmnožin jisté množiny s operacemi sjednocení a průniku nazývá Booleho algebra (o tom někdy více v samostatné přednášce, snad v předmětu Algebra 3). Mohlo by vás zajímat, proč nadřazujeme vlastnost (4) v definici tělesa nad vlastnost NNDN v definici oboru integrity To ještě nebylo vysvětleno. Jednou z odpovědí na tuto otázku je existence oboru integrity (Z, +, •), který není tělesem. Tj. existují obory integrity, které nejsou tělesy ... a protože se obor integrity (Z, +, •) liší od tělesa pouze tím,, že nesplňuje vlastnost (4)*, říkáme, že vlastnost (NNDN) je slabší než vlastnost (4)* Platí to však vždy, že obor integrity je „méně než" těleso ( v tom smyslu, že obor integrity splňuje méně vlastností)? Druhou možností odpovědi je větička, že každý konečný obor integrity je tělesem (jinými slovy, pokud M je konečná, tak pojem obor integrity a těleso je jedno a totéž): Věta 25 Každý konečný obor integrity (M, v, *) je už tělesem. (Důkaz: Přímý - předpokládejme, že (M, v, *) je konečný obor integrity, dokážeme, že je tělesem, tj. to bude objasněno, jestliže najdeme v M inverze vzhledem k operaci * pro všechny prvky mimo prvek 0V. Pojďme na to: už na začátku víme, že neutrální prvek 1* je inverzní sám k sobě. Najděme inverze vzhledem k operaci * pro prvky zbývající: protože předpokládáme, že M = {0V, 1*, } je konečná množina, stačí najít inverze pro prvky x±, x2, ■ ■ ■, xn_2. Najděme bez újmy na obecnosti inverzi pro prvek x\ ... ten označuje libovolný další prvek mimo oba neutrální prvky. Jestliže prvek x\ násobíme všemi možnými nenulovými prvky, dostáváme součiny x\ * 1*, x\ * xi, x\ * x2, x\ * X3, . .., x\ * xn_2. Jedná se o in — 1) součinů, z nichž každé dva dávají různý výsledek - kdybychom totiž dostali dva stejné výsledky, mohli bychom v oboru integrity provést krácení, a dospěli k tomu, že v záhlaví tabulky operace * se vyskytují dva stejné prvky, což není možné (označení jsme od začátku konstruovali tak, že 1*, xi, x2, .. ., x„_2 označují různé nenulové prvky našeho oboru integrity). Protože M je konečná množina, některý z in — 1) výsledků součinu musí být číslo 1*, tedy pro nějaké s G {1, 2,.. ., n — 2} platí X\ * xs — 1*. Našli jsme tedy inverzi xs prvku x\ vzhledem k operaci *. Protože úvahu lze provést nejen pro x±, ale pro libovolný prvek různý od obou neutrálních, je tím prokázána existence všech inverzních prvků mimo inverze k nulovému prvku. Důkaz je hotov. □.) Algebra 1 (MA 0003) 82 Třetí odpověď jde přes vlastnost krácení. Pro zopakování: v grupě vlastnost krácení byla označena v tomto textu číslem (7), a číslem (7)* označíme nyní vlastnost krácení v okruhu: Va, ř), c G (M, \y,*),a^Ov:a*b = a*c^b = c (7)* (tedy jestliže prvek a E (M, \/, *) není neutrálním prvkem vzhledem k operaci v, pak jím lze v rovnici krátit). Věta 26 V každém tělese (M, y, *) platí: Z existence inverzí vzhledem k operaci * plyne, že je splněna vlastnost (7)*. (Důkaz jednoduše: Z existence inverzí vzhledem k operaci * plyne, že pro libovolné x E (M — {0V}, *) lze rovnost x * y = x * z vynásobit zleva inverzním prvkem x_1: y = 1 * y = x-1 * x * y = x-1 *x*z = l*z = z => y = z. To ovšem znamená, že pro nenulové x lze v rovnosti x * y = x * z krátit, a tedy platí (7)*. Důkaz je hotov. □.) Zkusme si položit otázku, která souvisí se zákonem o krácení: Lze krátit ve strukturách, ve kterých neexistuje inverze x-1 z předchozího důkazu - lze např. krátit v okruhu nebo v oboru integrity? (Zq, +•) je okruh, víme, že zde krátit nelze. (Z, +, •) je obor integrity a víme, že u celých čísel krátit lze. Platí to však vždy? Co když je to jen náhoda? Ukazuje se, že to platí vždy: Věta 27 V každém okruhu (M, +, •) platí: Je splněna vlastnost (7) * /3 NDN. Důkaz: "=>" Předpokládejme, že (M,+,•) je okruh splňující vlastnost (7)*, chceme dokázat, že neexistují nenuloví dělitelé nuly. Va, b, E M, pro které a • b = 0 1) pokud a = 0, jsme hotovi, protože b je nulový (triviální) dělitel nuly. 2) pokud a ^ 0, můžeme psát: a ■ b = 0 = a ■ 0, tedy: a ■ b = a ■ 0 => podle (7)* platí b = 0, tedy a je triviální (nulový) dělitel nuly. Celkem aspoň jedno z čísel a, b je nula =>, tj. nenašli jsme žádné nenulové dělitele nuly ... tedy žádní neexistují, a to jsme chtěli dokázat. "<<_" Předpokládejme, že (M,+, •) je okruh neobsahující nenulové dělitele nuly, ukážeme, že splňuje (7)*. Pokud a / 0, uvažujme rovnost a ■ b = a ■ c. Obecně prvek a-1 nemusí existovat, ale nyní využijeme druhé operace, tj. existence opačného prvku (—a • c) k prvku (a • c): a ■ b — a • c = 0 ... využijeme distributivní zákon (6a), dostaneme: a ■ (b — c) = 0 ... Víme, že okruh neobsahuje nenulové dělitele nuly => musí nastat 83 b — c = O, a tedy b = c, dokázali jsme (7)*. □. Teď už víme, že vlastnost (7)* je ekvivalentní s vlastností NNDN. Ale vlastnost (7)* se v každém tělese snadno dokáže vynásobením inverzí a-1, která tam vždy existuje pro a 0. Tedy ekvivalentně: žádné těleso neobsahuje nenulové dělitele nuly Každé těleso je oborem integrity, každý obor integrity je i okruh (a z tranzitivity pojmů plyne, že i každé těleso je okruh). Ale naopak to neplatí: existují okruhy, které nejsou oborem integrity, např. (Zq, ©, 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 29 Ideál je neprázdná podmnožina B okruhu (M, +, •) taková, že (B, +) je pod-grupa (tj. B vzhledem k operaci + splňuje vlastnosti (1) a (4)) a navíc B absorbuje součiny na množině M, tj. Vfo G B, m E M : b ■ m G B (vynásobíme-li prvek množiny B prvkem množiny M, výsledek padne do množiny B). Příklad 38 Nejpřirozenějším příkladem ideálu je podmnožina B sudých celých čísel okruhu (Z, +, •): B = {...,-4,-2,0,2,4,...}. Je zřejmé, že (B, +) je podgrupa grupy (Z, +) a vynásobíme-li sudé číslo jakýmkoli celým číslem, výsledek je opět sudé číslo, tj. množina B absorbuje všechny násobky sebe sama s lichými čísly. Tedy B je ideál v (Z, +, •). Definice 30 V teorii ideálů hraje klíčové místo tzv. hlavní ideál okruhu, který definujeme jako takový ideál B, který vygenerujeme jediným prvkem b, jenž vynásobíme se všemi prvky množiny M. Příklad 39 Pro M = (Z, +, •) jsou hlavními ideály tyto množiny: • B\ :=< 1 > ... ideál generovaný prvkem 1 a všemi součiny 1 • z pro z E Z, tj. B\ = Z (okruh (Z, +, •) je sám o sobě hlavním ideálem); • B2 :=< 2 > ... ideál generovaný prvkem 2 a všemi součiny 2 • z pro z E Z, tj. jedná se o ideál z příkladu 6.5: B = {...,-4,-2,0,2,4,...}. • S3 :=< 3 > ... ideál generovaný prvkem 3 a všemi součiny 3 • z pro z E Z, tj. B3 = {...,-6,-3, 0, 3,6,...}. Algebra 1 (MA 0003) 84 • atd. • Pokud v okruhu (Z, +, •) vezmeme ideál generovaný dvěma prvky, naprí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. Čtenář tohoto textu či student předmětu Algebra 1 si určitě říká, nač je toto vše podrobné studium pojmů, vycházejících většinou z vlastností operací sčítání, násobení, průniku a sjednocení. Rád bych jej ubezpečil, že kromě toho, že zákonitosti jsou samy o sobě zajímavé, posloužily v historii právě v tom nej důležitějším úkolu algebry, a tedy ke hledání řešení algebraických rovnic. Ve druhé polovině semestru se budeme právě řešením algebraických rovnic zabývat podrobně. 85 6.2 Cvičení 06: Algebraické struktury se dvěma binárními operacemi Je možné, že toto cvičení a pojmy související se strukturou se dvěma operacemi budete na cvičení probírat dříve než v šestém týdnu - sledujte rozvrh cvičícího. Úloha 6.1 V množině Q jsou definovány operace © a 0 předpisy: x(By = xJry,xQy = \xy. Ověřte, zda (Q, ©, ©) je těleso. Úloha 6.2 V množině Z jsou definovány operace © a 0 předpisy: a®fe = a + fe+1, aQb = a + b + ab. Určete typ algebraické struktury. Úloha 6.3 V množině R jsou definovány operace © a 0. Zjistěte, zda (R, ©, ©) je těleso. a) x © y = x2 + y2, x 0 y = xy b) x(By = x + y,xQy = ^xy Úloha 6.4 V množině (Z6, ©, ©) sestavte operační tabulku pro operace © a 0. Určete typ struktury (Zq, ©, ©). Úloha 6.5 Výpočtem určete typ algebraické struktury (Z5, ©, ©). Úloha 6.6 Určete všechny dělitele nuly v následujících komutativních okruzích: a) (Zi2,©, 0) b) (Zi5,©,0) Další procvičení pojmů okruh, obor integrity, těleso: např. viz Pinter 2010, kapitola 17 a cvičení na str. 174-178. Například N.l: a) Které z vlastností (1) až (10) splňuje struktura (2P, U, n) pro P = {a, b, c}? b) Jak byste strukturu (2P, U, Pl) z části (a) nazvali (okruh, obor integrity, těleso, nebo něco jiného)? c) Najděte netriviální dělitele nuly na struktuře (2P, U, Pl). Dejte pozor na to, že „nula" je vždy prvek vzhledem k první uvedené operaci struktury, zatímco dělitelnost se zkoumá vzhledem ke druhé operaci struktury. d) Najděte netriviální dělitele nuly na struktuře (2P, n, U). Dejte pozor na to, že „nula" je vždy prvek vzhledem k první uvedené operaci struktury, zatímco dělitelnost se zkoumá vzhledem ke druhé operaci struktury. Například N.2: Uveďte příklad nekonečného oboru integrity, který není tělesem. Algebra 1 (MA 0003) 86 Například D.l: a) Uvažujme množinu 2P všech podmnožin množiny P = {a, b, c}. Na této množině lze definovat operaci symetrického rozdílu A 4- B := (A — B) U (B — A) a klasickou operaci n průniku. Sestavte tabulky operací 4- a n na množině 2P. b) Jak byste strukturu (2P, -4, n) z části (a) algebraicky popsali (je to okruh, obor inte- grity, těleso, nebo něco jiného)? Procvičení pojmů ideál, hlavní ideál, homomorfismus okruhů: viz Pinter 2010, kapitola 18 a cvičení na str. 185-189. Například N.3: Ideál (D, +, •) okruhu celých čísel (Z,+,-) je takový jeho podokruh, který je uzavřený vzhledem k násobení celým číslem, tj. d ■ z E D V d G D, z (E Z. Uveďte příklad ideálu D okruhu (Z, +, •), který obsahuje číslo 2 a neobsahuje číslo 3. 87 7 Týden 07 7.1 Cvičení 07: Polynomy 01 Rozklad polynomu na součin polynomů prvního stupně, kořen polynomu, Hornerovo schéma, největší společný dělitel polynomů. Studenti měli Hornerovo schéma i Eukleidův algoritmus a dělení polynomů v předmětu Diskrétní matematika (MA0001), aleje potřeba zopakovat. Doporučené materiály k využití: • Označení: (Z[x],+, ■), (Q[x],+,-), (R[x], +, •), ... po řadě okruhy polynomů s koeficienty z okruhu celých čísel, tělesa racionálních čísel a tělesa reálných čísel. Tyto okruhy neobsahují netriviální dělitele nuly, takže se jedná o obory integrity (Budínová 2013, str. 7, věta 1). Ideální definice okruhu Z\x\. jedná se o rozšíření okruhu (Z, +, •) o prvek x, kde nevíme, co je, může tam být cokoliv, třeba31 číslo 7T. Množina polynomů tedy neobsahuje všechny inverze vzhledem k násobení polynomů. • Budínová 2013, str.8-10: stupeň polynomu, dělení polynomů se zbytkem ... studenti znají, ale připomeňte. • Hornerovo schéma (Budínová 2013, str. 10-12), základní věta algebry, vydělte polynom 6x3 + 13x2 — 1 polynomem {x — 1) nebo (x + 2): an ■ xn + an-\ ' xn~x + • • • + a\ ■ x + ao = an ■ (x — x±) ■ (x — x2) ■ ■ ■ {x — xn), například 1 2 6x3 + 13x2 - 4 = 6(x + 2)(x - -)(x + -). 2 3 • Budínová 2013, str. 18-21 po pojem ireducubilní polynom, objasnění, že v základní větě algebry se vyskytují ireducibilní polynomy. Dělitel polynomů, největší společný dělitel polynomů, Eukleidův algoritmus: znají, ale připomeňte (na příkladu). Normovaný největší společný dělitel. • Nalezněte NSD polynomů: Eukleidovým algoritmem (Budínová 2013, str.20, př. 16), rozkladem na součin ireducibilních polynomů (př. 18,19, str. 23 ... upozorněte studenty, že rozklad lze realizovat substitucí (př.18) nebo postupným vytýkáním). Pinter, 2010, str. 241. Algebra 1 (MA 0003) 88 7.2 Přednáška 07: Přehled algebraických metod hledání kořene polynomu Označme Z[x] := {anxn + an_\xn~x + • • • + a\x + ao;at G Z,n G N} množinu polynomů s celočíselnými koeficienty, x je proměnná Q[x] := {anxn + an_\xn~x + • • • + a\x + ao;at G Q,n G iV} množinu polynomů s racionálními koeficienty, x je proměnná R[x] := {anxn + dn-ix™-1 + ■ ■ ■ + aix + ao; at G R, n G V} množinu polynomů s reálnými koeficienty, x je proměnná C [x] := {anxn + ara_ixra_1 + • • • + aix + ao;at G C, n G V} množinu polynomů s komplexními koeficienty, x je proměnná Nyní se dostáváme k jádru předmětu algebra - k řešení polynomických rovnic typu pix) = 0, kde p(x) je právě některá z množin Z[x], Q[x], R[x], C[x], tzn. polynom. Co se týká množinového porovnání těchto množin, platí Z[x] C Q[x] C R[x] C C [x]: • polynom s celočíselnými koeficienty je současně i polynomem s koeficienty racionálními, reálnými i komplexními • polynom s racionálními koeficienty (tj. koeficienty ve tvaru zlomku) je současně i polynomem s koeficienty reálnými i komplexními • polynom s reálnými koeficienty je současně i polynomem s koeficienty komplexními Většinou nám bude v této přednášce stačit zabývat se polynomu z množin Z[x] nebo Q[x], ale několik věcí, které budou řečeny, bude platit i pro polynomy z množin R[x] a C[x\. Už v samotném tvaru polynomu se používají dvě operace, sčítání a násobení, pomocí těchto stejných operací můžeme sčítat a násobit i samotné polynomy, tj. máme struktury se dvěma operacemi (Z[x], +, •), (Q[x], +, •), (R[x], +, •), (C[x], +, •). První otázka matematického zkoumání zní, o jaké struktury se jedná z algebraického hlediska? 89 operace +: piop(x) = 2x3 —5x2+4, q(x) = 3x2 —2x+5 => p(x)+q(x) = 2x3—2x2—2x+9 (1) platí, výsledek je opět polynom, tj. operace je uzavřená (2) platí, což plyne z asociativity sčítání čísel (3) platí, neutrálním prvkem je polynom n{x) = 0 ... velmi jednoduchý polynom (4) platí, např. pro polynom p{x) = 2x3 — 5x2 + 4 je inverzí vzhledem ke sčítání polynom —p(x) = —2x3 + 5x2 — 4 (5) platí, p(x) + q(x) = q(x) + pix) operace •: pro p{x) = 2x3 — 5x2 + A,q(x) = 3x2 — 2x + 5 => p(x) ■ q(x) = (2x3 - 5x2 + 4) • (3x2 - 2x + 5) = 6x5 - 19x4 + 20x3 - 13x2 - 8x + 20 (1) platí, výsledek je opět polynom (2) platí, což plyne z asociativity násobení čísel (3) platí, neutrálním prvkem je polynom j{x) = 1 .. . tedy celkem jednoduchý polynom (4) neplatí, polynom p{x) nemá inverzi: (2x3 - 5x2 + 4) • 2x3_lx2+4 = 1, jenže 2x3_lx2+4 není polynom (nemá tvar ax3 + bx2 + cx + ď) Inverzní funkce u mnoha polynomů sice existuje, ale neleží v naší množině Z[x], Q[x], R[x], C[x]. (5) platí, p{x) ■ qix) = q{x) ■ pix) interakce operací +, •: lze ověřit, že p(x) ■ (q(x) + r(x)) = p(x) ■ q(x) + pix) ■ rix) ... Vjo(x), qix), rix) Tedy celkem všechny ze struktur (Z[x],+, ■), (Q[x],+, ■), (R[x],+, ■), (C[x],+, ■) jsou okruhy - a když si uvědomíme, že se v nich vlastně jedná o běžné sčítání a násobení čísel, zjistíme, že se zde nevyskytují nenuloví dělitelé nuly, tj. všechny tyto okruhy jsou současně i obory integrity. Pozor na záměnu označení: struktury (Q, +, •), (R, +, •), (C, +, •) samozřejmě tělesa jsou, jak již bylo dříve řečeno, ovšem nyní uvažujeme složitější objekty, které v sobě zahrnují neznámou hodnotu x, a dohromady tyto objekty vytvářejí pouze obory integrity. Definice 31 pix) = anxn + an_\xn~x + • • • + a\x + ao • • • prvek množiny Z[x], Q[x], R[x] nebo C[x] se nazývá polynom stupně n. Při tomto označení už předpokládáme, že an 7^ 0 (an je tzv. vedoucí koeficient polynomu pix)), jinak bychom an nepsali - s jedinou výjimkou, když pix) = 0, tam je ao = 0 vedoucí koeficient, který se nule rovnat musí. Definice 32 Říkáme, že číslo c je kořen polynomu p(x), respektive že c je řešení polynomické rovnice p(x) = 0, jestliže p(c) = 0, tj. po dosazení x = c • dostaneme hodnotu 0 ... v případě polynomu pix) • dostaneme pravdivou rovnost .. . v případě rovnice p(x) = 0 Tedy řešení polynomické rovnice souvisí s pojmem kořen polynomu. Někdy tyto dva pojmy bývají nepřesně spojovány, například v učebnicích pro ZS mluvíme o kořenech rovnice, což není přesné. VS terminologie zde rozlišuje pojmy „kořen polynomu" a „řešení rovnice". Nejprve si řekneme něco o vzorcích: Algebra 1 (MA 0003) 90 a) a ■ x + b = 0 ... to je tzv. lineárni rovnice Pozor, vzhledem k počtu řešení zde mohou nastat tři situace, např. 0 • x + 5 = 0 ... nemá řešení 2 • x + 5 = 0 ... nemá řešení v z, ale v q, r,C ano: x\ = =y 0-x + 2 = 2 ... má řešení nekonečně mnoho: každé číslo z množiny, které nás zajímá, je řešením rovnice po dosazení za x. b) a ■ x2 + b ■ x + c = 0 ... to je tzv. kvadratická rovnice Existují vzorce pro její řešení: všimněme si, že vzorce automaticky předpokládají, že a 0 jinak bychom ji zapsali jako rovnici lineární, viz výše. xit2 = ~b±V2Q2~4~ • • • dosadíme a vypočteme řešení. Pozor, už u kvadratických rovnic někdy dochází k tomu, že b2 — Aac je záporné číslo. Má smysl počítat odmocninu ze záporného čísla? Jinými slovy, existuje řešení kvadratické rovnice x2 + 1 = 0? Na množině r jistě takové řešení neexistuje, jelikož žádné číslo x se po umocnění na druhou a přičtení k 1 nerovná 0. Zde někde vzniká pojem komplexního čísla. Stejně jako se matematika stovky let zdráhala pracovat se zápornými čísly, nejprve se zdráhala pracovat s komplexními čísly. C := { a + bi, kde a, b G r, í je imaginární číslo: í2 = —1 } Už jsme si říkali v ZÁKLADECH MATEMATIKY, že komplexní čísla a + bi lze mezi sebou násobit i sčítat, dokonce existují i inverze vzhledem k oběma operacím (tj. komplexní čísla můžeme odčítat i dělit - vyjma dělení nulou, kterou jsme ovšem nemohli dělit ani v z,q,r). Zkrátka (C,+, •) je těleso, tj. struktura s hezkými algebraickými vlastnostmi k oběma operacím. Matematický model kompexního čísla tedy sestrojit lze, otázkou je, k čemu je to dobré kromě základní věty algebry, kterou si řekneme za chvíli. Nakonec se ukázalo, že kompexní čísla jsou užitečná tam, kdekoliv chceme něco znázornit v rovině: komplexnímu číslu a + bi totiž jednoznačně odpovídá bod [a; b] v rovině. A jakmile se spojilo komplexní číslo s geometrickým významem, ukázalo se, že řadu úkolů, operací s body a vektory v rovině lze stejně dobře popsat či řešit pomocí komplexních čísel. Příklad 40 V analytické geometrii lze přímku procházející bodem [2; 1] se směrovým vektorem (1, ^-) vyjádřit parametrickými rovnicemi x = 2 + t-l y = l+t-(=±) ,teR Tutéž přímku lze vyjádřit pomocí komplexních čísel jako 91 z = {2 +i) + t- (1 - —) ,teR neboli dvourozměrné vektory „schováme " do komplexních čísel, a pokud potřebujeme, k dílčím souřadnicím těchto čísel se dostaneme tak, že vezmeme/najdeme jejich reálnou část: x = Rez = to, co není koeficientem u čísla i y = Imz = to, co je koeficientem u čísla i Tímto způsobem převedeme reálný případ na komplexní a naopak. Příklad 41 Ještě zajímavější a užitečnější souvislosti najdeme při popisu pohybu bodu/objektu po kružnici o poloměru r: při popisu pomocí obloukové míry (proměnná t je rovna velikosti úhlu v radiánech) musíme užít funkcí sin, cos: souřadnice pohybujícího se objektu jsou [r ■ cost,r ■ sínt], dostáváme tedy rovnice x = r ■ cost,y = r ■ sínt. Při využití komplexních čísel se využívá starý Eulerův vzorec elt = cost + i ■ sínt, takže rovnoměrný pohyb objektu po kružnici lze popsat rovnicí z = r ■ elt (kde z = x + íy je vztah mezi komplexním číslem z a vektorem (x, y)). Protože pomocí vzorců pro okamžitý (či kmitavý) pohyb lze dobře popsat elektrický proud, komplexních čísel s oblibou využívají kolegové v elektrotechnice, místo aby pracovali s vektory v rovině. Budeme tedy mírně pracovat i s imaginární jednotkou i s tou informací, že jedním z jejích využití je popis práce s body a vektory v rovině. c) ax3 + bx2 + cx + d = 0, a J= 0 ... to je tzv. kubická rovnice Pro tuto rovnici a její řešení existují obecné vzorce pro a,b, c, d E R (tzv. Cardanovy vzorce - viz BP Ivety Trombikové, najdete v IS tohoto předmětu, str. 22 — 23). Tyto vzorce se příliš neužívají, i když z algebraického hlediska se jedná o totální vzorce. I při dosazování do těchto vzorců se opět velmi snadno mohou vyskytnout komplexní čísla - a to i v případě, že výsledné řešení je pouze reálné! Algebra 1 (MA 0003) 92 d) ax4 + bx3 + cx2 + dx + e = 0, a 7^ 0 ... to je tzv. kvartická rovnice, ovšem toto označení se příliš nepoužívá, mnohem názornější je říci algebraická rovnice 4. stupně nebo polynomická rovnice 4. stupně Opět k jejich řešení existují vzorce obecné, totální a kupodivu jednodušší než vzorce u kubické rovnice, protože po substituci x2 = y a „doplnění části polynomu na čtverec" dostaneme rovnici kvadratickou proměnné y. Tyto vzorce je možné užít častěji než u rovnice kubické. e) Obecné vzorce pro rovnice řádu 5 a výše neexistují, což bylo dokázáno pány Gauss a Galois. Matematika tedy běžnému uživateli, kterého by zajímalo řešení těchto rovnic, vzorce většinou nenabídne. Přesto existuje několik algebraických postupů, jak některá řešení najít: A) Hornerovo schéma: Zjistí, zda je polynom p(x) dělitelný polynomem {x — c) stupně 1. Příklad 42 (6x3 + 13x2 - 4) :(x + 2) = 6x2 + x - 2 x-{-2) 6 13 0 -4 -2 6 1 -2 0 Hornerovu schématu jste se věnovali v diskrétní matematice, ovšem vedoucí koeficient byl většinou roven jedné. Nyní budeme pracovat s obecným vedoucím koeficientem. Pokud se poslední hodnota na řádku Hornerova schématu rovná 0, víme, že c = —2 je kořenem polynomu 6x3 + 13x2 — 4, a tedy řešením polynomické rovnice 6x3 + 13x2 —4 = 0. Navíc koeficienty 6,1, —2 určují polynom, který vzniká jako podíl. Můžeme tedy dopočítat zbylé řešení: 6x3 + 13x2 -4 = 0 (x + 2) • (6x2 + x - 2) = 0 ~. _ O ~. _ -l±\/l+4-6-2 _ 1 _ -2 X\ — —A X253 — -J7j- X2 — 2 x3 — ~ Pomocí Hornerova schématu jsme tedy snížili stupeň zkoumaného polynomu a užitím vzorce 2:2,3 = ~b±^2~4— našli ostatní kořeny. Našli jsme tři řešení rovnice: Xi 2, X2 2"5 ^3 ~3~' ^ Otázkou je, zda tento rozklad polynomu na součin lineárních polynomů existuje vždy. Na ni odpověděl pan Gauss v roce 1797 a dnes se tato odpověď jmenuje Základní věta algebry: Věta 28 Základní věta algebry: Každý polynom p(x) = anxn + an_\xn~x + • • • + a\x + a0 E C[x] lze rozložit na součin vedoucího koeficientu a lineárních polynomů x — Xi, kde Xj E C, jsou jeho kořeny: c^n ' (x — ^l) ' — ^2) • • • — ^n}' 93 Ad Příklad 42: Náš polynom 6x3 + 13x2 — 4 lze psát jako 6 • (x + 2) • (x — |) • (x +1) tedy rovnici 6x3 + 13x2-4 = 0 při rozkladu polynomu na součin polynomů lineárních 6 • (x + 2) • (x — \) ■ (x + |) = 0 lze snadno řešit. Řešením jsou přesně ty hodnoty které po dosazení za x vynulují některou ze závorek. Základní věta algebry nám vlastně říká, že stejně jako každé přirozené číslo lze rozložit na součin prvočísel, i každý polynom stupně n lze rozložit na součin vedoucího koeficientu a jednoduchých lineárních polynomů typu ix — xt). Příklad 43 Hodnoty xl jsou obecně komplexní, což vidíme např. u polynomu (x2 + 1), který lze rozložit na součin ix + i) ■ (x — i) nebo u polynomu ix2 + x + 1) můžeme psát (x + | + i^) • ix + | — i^) (při výpočtu jsme \/—3 upravili na i ■ \/3 za využití označení, ze i = Můžete si zkusit zpětným roznásobením závorek, že dostanete původní polynom. Klíčovou otázkou zůstává, jakým způsobem jsme zjistili, že v příkladu 42 máme do Hornerova schématu dosadit zrovna číslo c = —2. Určitou odpověď na tuto otázku dává: Věta 29 Věta o racionálních kořenech polynomu: Pokud polynom p(x) = anxn + ara_ixra_1 + • • • + a\x + ao G Z[x] má nějaké kořeny ve tvaru zlomku j, tak k\a$ A l\an. Tato věta nám pomůže najít všechny racionální kořeny: Vypíšeme si všechny dělitele čísla ao, všechny dělitele čísla an a vytvoříme z nich zlomky. Tyto zlomky zkusíme užít jako vstupy do Hornerova schématu - tyto zlomky mohou i nemusí být kořenem polynomu, ale máme jistotu, že žádná další racionální čísla zkoušet nemusíme. Pozor na to, že postup funguje jen tehdy, když všechny koeficienty al5 nejen první a poslední, jsou celočíselné. Příklad 44 Řešte rovnici 2x5 + x4 — 12x3 — 20x2 — 19x — 6 = 0 6 má dělitele ±1, ±2, ±3, ±6 2 má dělitele ±1,±2 => Pokud existuje kořen ve tvaru zlomku, musí být obsažen v množině {±1,±±,±2,±3± §,±6} Zkusme postupně některé z nich: 2 1 -12 -20 -19 -6 1 2 2 2 -11 ...... zde se nezdá, že by na konci řádku vyšla 0 -1 2 2 0 -12 -14 -12 0 Jakmile jsme našli jedno řešení, díváme se už dál na polynom vzniklý jako podíl a vidíme, že všechny koeficienty jsou sudé, takže vytýkáme 2: Algebra 1 (MA 0003) 94 2x5 + x4 - 12x3 - 20x2 - 19x - 6 = 0 (x + i) • (2x4 - 12x2 - Ux - 12) = 0 2 • (x + \) ■ (x4 - 6x2 - 7x - 6) = 0 A dále už pracuji s polynomem x4 — 6x2 — 7x — 6. Opět proto použiji postup pro racionální kořeny polynomu a získávám, že další potenciální kořen musí být, pokud je racionální, z množiny {±1, ±2, ±3, ±6}: 1 0 -6 -7 -6 3 1 3 3 2 0 znovu přepočítáme a zjistíme, že potenciální kořeny jsou ±1, ±2 1 není kořen -1 není kořen 2 není kořen -2 1 1 1 0 Zase si vše napišme jako součin závorek: 2 • (x +1) • (x — 3) • (x + 2) • (x2 + x + 1) = 0. Dílčí polynom x2 + x + 1 má komplexní kořeny, jak víme z příkladu ??. Z tohoto zápisu již vidíme řešení: 2 • (x +1) • (x — 3) • (x + 2) • (x + (| + i^f)) • (x+ (| — i^)) = 0. Definice 33 Kořen c polynomu pix) se nazývá k-násobný, jestliže v rozkladu pix) na součin lineárních polynomů podle základní věty algebry se vyskytuje (x — c)k (závorka (x — c) je umocněna právě na mocninu k). Příklad 45 Možnost nalezení kořene s vyšší násobností nám napovídá, abychom např. při užití Homérova schématu nezapomněli na možnost užít znovu stejné číslo. Například při řešení rovnice x5 — 15x3 + 10x2 + 60x — 72 = 0 zkoušíme marně ±1, ale při dosazení c = 2 dostaneme: 1 0 -15 10 60 -72 2 1 2 -11 -12 36 0 a hned dosadíme 2 ještě jednou 2 1 4 -3 -18 0 2 1 6 9 0 všechny koeficienty jsou kladné, tj. eventuální -3 1 3 0 další řešení musí být záporné -3 1 0 Tedy po rozkladu získáváme (x — 2)3 • (x + 3)2 = 0. Řešení naší rovnice jsou tedy pouze dvě. * B) Odstranění násobných kořenů polynomu: Tento postup využívá derivace p'(x) a toho, že zderivováním se násobnost každého kořene sníží o 1. Věta 30 Vydělíme-li polynom p(x) polynomem d(x) = NSD(p,p') = největší společný dělitel polynomů p,p', dostaneme polynom vix), který má přesně stejné kořeny jako p(x), ale jsou všechny pouze jednonásobné. Tedy postup pix) —> vix) umožňuje snížit stupeň polynomu dříve, než začneme hledat jeho kořeny. 95 Příklad 46 Pokud p{x) žádné vícenásobné kořeny nemá, d(x) = NSD(p,p') = 1, takže v(x) = pix), polynom p{x) se při převodu na vix) vůbec nezmění. Příklad 47 Při řešení rovnice 16a;4 + 32a;3 + 40a;2 + 24a; + 9 = 0 bychom pomocí Homérova schématu zjistili, že žádné racionální řešení neexistuje. Zkusme tedy algoritmus odstranění násobných kořenů: p(x) = 16a;4 + 32a;3 + 40a;2 + 24x + 9 p'(x) = 64a;3 + 96a;2 + 80a; + 24 Hledejme NSD těchto polynomů Euklidovým algoritmem: (16a 32a;3 -(16x4+24a;3 8a;3 + 20a;2 + 18a; -f -Í8x3+12x2 + 10a; 40a;2 + 24a; + 9) : (64a;3 ■20a;2 + 6a;) -9 3) 96a;2 + 80a; + 24) = \x 8x2 + 8x + 6 (64a 96a;2 -(64x3+64x2 80a; H h48x) 24) : (8a;2 + 8x + 6) = 8x + 4 32x" + 32a; + 24 -(32x2 + 32x+24) Tedy d(x) = NSD = poslední nenulový zbytek tohoto procesu = 8x2 + 8x + 6. Pak: v(x) = pix) : d(x) <16x4 + 32a;3 + 40a;2 + 24a; + 9) : (8a;2 -(16x4+16x3 + 12a;2) 16a;3 + 28a;2 + 24a; + 9 -(16x3+16x2 + 12a;) 12a;2 + 12x + 9 -(12a;2 + 12x+9) b~ 8x + 6) = 2a;2 2x Tedy rovnici lze psát ve tvaru (8a;2 + 8x + 6) • (2a: (4a;2 +4x + 3)-(4x2 (4a;2 f 2x + |) = O Ax + 3) = O Ax + 3)2 = O _ -4±yT6-48 Xl,2 — -g- Xi = ^ + i^ . . . kořen násobnosti 2 x2 = +r — ■ ■ ■ kořen násobnosti 2 Celkem lze tedy náš polynom 16a;4 + 32a;3 + 40a;2 + 24a; + 9 rozložit a řešit rovnici ve tvaru: 16 • (x + \ + i^)2 • [x + \ — i^)2 = O . .. algebraický rozklad dané rovnice v komplexním oboru. * Algebra 1 (MA 0003) 96 C) Polynom pix) E R[x] musí mít komplexní kořeny „po dvojicích" ve tvaru a ± ž • b : Pokud ci = a + í ■ b je kořenem polynomu p(x) E R[x] (tj. polynomu s reálnými koeficienty), nutně z toho plyne, že i komplexní číslo c2 = a — í ■ b je kořenem téhož polynomu. Čísla a ± i • b se nazývají komplexně sdružená. D) Řešení binomické rovnice ve tvaru xn + a = 0 : Pro některé speciální polyno-mické (tedy algebraické) rovnice existují speciální metody řešení. Například u binomických rovnic vlastně hledáme n-tou odmocninu v komplexním oboru: x = \/—a = ... (dále viz učebnice o komplexních číslech pro střední školy, vzorec pro výpočet rite odmocniny z komplexního čísla ... víme už předem, že dostaneme n různých řešení, jejichž obrzy v komplexní rovině leží ve vrcholech pravidelného n-ůhelníka ... zejména nás tedy zajímá n > 3). E) Řešení reciproké rovnice, například 8x5 — 64x4 + 100x3 + 100x2 — 64x + 8 = 0: Pokud polynom na levé straně rovnice je lichého stupně, víme, že jeho řešením bude číslo x\ = — 1 (to plyne právě z toho, že reciproké koeficienty jsou stejné, tj. po dosazení x = — 1 dostaneme na levé straně hodnotu nulovou) - pomocí Hornerova schématu provedeme dělení polynomu polynomem ix + 1), a dostaneme reciprokou rovnici sudého stupně. Tu řešíme pomocí speciální substituce, vysvětleno na příkladu: ... F) (Budínová, str. 29, věta 16): Pro všechny kořeny polynomu anxn + ara_ixra_1 + • • • + a\x + ao platí: max {\a0\, \aľ\,... , |a„_i|} \Xi\ < 1 H--;—;-• Označíme-li konstantu na pravé straně r, tak všechny kořeny polynomu, reálné i komplexní, musí ležet v komplexní rovině uvnitř kruhu se středem v 0 a poloměrem r, jelikož absolutní hodnota komplexního čísla znamená vzdálenost xl od počátku. Jinými slovy, mezi kořeny a koeficienty dané algebraické rovnice existuje právě uvedený vztah: kořeny jsou blíže počátku než max {\a0\, \ai\, ..., |a„_i|} vydělené absolutní hodnotou \an\. Př. 23, str. 29: nalezněte řešení algebraické rovnice 2x5 + 3x4 - 7x3 + 6x2 - llx + 5 = 0. Dosazením do uvedeného vzorce v našem příkladu máme . . max{3, 7, 6,11, 5} 11 xA < 1 +-1,11—= 1 + — = 6,5. 1 1 - 2 2 To znamená, že všechna řešení, imaginární i komplexní (a kdyby byla některá racionální, což v našem příkladu nejsou, tak i ta) leží v Gaussově rovině v kruhu se středem v počátku a poloměrem 6,5. 97 Hranice algebry: Vysvětleno na příkladu: řešte rovnici 2x5 + 3x4 — 7x3 + 6x2 — llx + 5 = 0. A) Pomoci Homérova schématu a věty o racionálních kořenech ověříme, zda je některý ze zlomků ±1, ±5, ±5, ±|, ±| kořenem polynomu na levé straně rovnice. Zjistíme, že polynom žádné racionální kořeny nemá. B) Procesem odstranění násobných kořenů zjistíme, že polynom žádné vícenásobné kořeny nemá, tedy vix) = p(x). Tím jsme zjistili, že pix) má pět různých jednonásobných kořenů. C) pix) má jen reálné koecifienty => pokud má pix) komplexní koeficienty, tak vždy po dvojicích, komplexně sdružené kořeny tvaru a ± z • b. D,E) o tyto speciální případy rovnic se nejedná. F) Pro každý z pěti kořenů platí < 1 + ""^l3'^6'11'5! = \ _|_ Já = 6,5. Všechny kořeny leží uvnitř kruhu se středem v 0 a poloměrem 6, 5. G) Tím končí možnosti algebry a nastupují numerické metody, kterým se budeme věnovat na následující přednášce. I když pomocí tužky a papíru najít řešení této rovnice není možné pomocí žádných vzorců, numerické metody poměrně s velkou spolehlivostí naleznou každé z pěti řešení (iracionálních ič komplexních) s takovou přesností, která je dostatečná - například s přesností na pět desetinných míst, či s přesností na pět platných cifer u velmi malých čísel, apod. Algebra 1 (MA 0003) 98 8 Týden 08 8.1 Cvičení 08: Polynomy 02 Věta o racionálních kořenech polynomu v (Z[x],+, ■). Odstranění násobných kořenů polynomu. Využijte například následující materiál: • Věta o racionálních kořenech polynomu z (^[x], +, •) - Budínová 2013, str. 33, věta 24. Příklad. 21 na str. 28: Nalezněte kořeny polynomu x5 — 5x4 + 7x3 — 2x2 +4x — 8. Pojem násobnosti kořene, základní věta algebry v terminologii násobnosti kořene. • Příklady na procvičení: str.34-př.29, str.35-př.30 ... je nutné dělat ty znaménkové změny? To rozhodne cvičící. • Odstranění násobných kořenů: str.32 poznámka až str. 33 příklad 28. Pak ještě nějaký příklad s násobnými kořeny, např. polynom čtvrtého stupně se dvěma dvojnásobnými komplexně sdruženými kořeny. 99 8.2 Přednáška 08: Přehled numerických metod hledání kořene polynomu Hledání iracionálních a komplexních kořenů polynomu numerickými metodami - metoda půlení intervalu, Newtonova metoda. Vraťme se např. k následujícímu příkladu: • Budínová, Př. 23-str.29: nalezněte řešení algebraické rovnice 2x5 + 3x4 - 7x3 + 6x2 - llx + 5 = 0. Homérovým schématem jsme ověřili, že žádné racionální řešení neexistuje. Všechna řešení tedy jsou reálná iracionální, nebo komplexní. Víme také, že polynom nemá žádné vícenásobné kořeny, takže má pět různých jednonásobných kořenů. 1) Hrubá detekce reálných řešení: (Budínová, str. 29, věta 16): Všechny kořeny leží v komplexní rovině uvnitř kružnice se středem v počátku a poloměrem max {\a0\, \a±\, |a„_i|} r = 1 H--:—:-. \an\ Dosazením do uvedeného vzorce v našem příkladu máme . . max{3, 7, 6,11, 5| 11 xA < 1 +-L_l_lj—i—L = i + _ = 65. 1 1 - 2 2 To znamená, že všechna řešení, imaginární i komplexní (a kdyby byla některá racionální, což v našem příkladu nejsou, tak i ta) leží v Gaussově rovině v kruhu se středem v počátku a poloměrem 6,5. 2) Jemnější detekce reálných řešení: Z předcházejícího bodu víme, že x E (—6,5; 6,5). Když si v grafickém kalkulátoru nakreslíme graf funkce p{x) zjistíme, že se jedná o spojitou křivku, která třikrát protne osu x na daném intervalu. Tyto průsečíky s osou x jsou právě tři různá reálná řešení xi, x2, x%. Z faktu, že průsečíky jsou jen 3 dále plyne, že čtvrté a páté řešení jsou komplexně sdružená čísla x^ = a ±ib, kde a, b zatím neznáme. Protože pix) je spojitá funkce, tj. vypočteme p{h{) pro ht postupně rovno —6,5, pak —6,4, pak —6,3, ..., pak 6,3, pak 6,4, pak 6,5. Pokud se stane pro nějaké i, že p(ht) ■ p(ht_i) < 0, znamená to, že dvě po sobě jdoucí hodoty mají rozdílná znaménka, tedy objevíme, že na intervalu {hf, hl+i) leží nějaké řešení. Další možností je nakreslit si graf funkce p(x) a intervaly s řešením upřesnit z grafu. Algebra 1 (MA 0003) 100 Zkusme tedy postupně za x dosazovat hodnoty z intervalu (—6,5; 6,5) s krokem 0, 5 a počítat funkční hodnoty: p(—6,5) = —15598,25; p(—6) = —9865; p(—5,5) = -5908, 875; p(-5) = -3290; p(-4, 5) = -1646, 5; p(-4) = -687; p(-3, 5) = -183,125; p(-3) = 38; p(-2,5) = 101,25; p(-2) = 91; p(-l,5) = 58,625; p(-l) = 30; p(-0,5) = 13; p(0) = 5; p(0,5) = 0,375; p(l) = —2; p(l, 5) = 8, 75; p(2) = 63 ... další funkční hodnoty jsou už všechny kladné. 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 ht), pak napíšeme p < —2*x5 + 3*x4 — 7*x3 + 6*x2 — ll*x + 5 (a stiskneme ENTER). V paměti se vypočte vektor funkčních hodnot, musíme jej ještě zobrazit na obrazovce, když např. napíšeme pouze písmenko označující proměnnou „p" a stiskneme ENTER. Tímto způsobem jsme odhalili, že kořeny leží v intervalech (—3,5;—3), (0,5; 1), (1; 1,5). Pokud máme jistotu, že krok 0,5 byl zvolen dostatečně jemně, takže na žádném z těchto tří intervalů se nevyskytuje více řešení současně (to bychom mohli zpřesnit třeba volbou 0,1), znamená to, že zbývající dvě řešení jsou komplexní (a díky větě „pokud a + ib je kořenem polynomu z (R[x],+, ■), tak nutně i a — íb je kořenem tohoto polynomu") víme, že tato řešení jsou komplexně sdružená čísla. Jiný způsob by zde spočíval v nakreslení grafu polynomu p(x), lze též v jazyce R zadáním posloupnosti bodů, které se vykreslí (ENTER po každém řádku): y < —seq(from = —3.5, to = 3.5, by = 0.01) pp < — 2 * y5 + 3 * y4 — 7 * y3 + 6 * y2 — 11 * y + 5 plot(y, pp) (obrázek lze „zvětšit" zadáním kratšího intervalu při definici vektoru y, například from = 0 a to = 1.5 nakreslí graf na sporném intervalu, na kterém existují dvě řešení). 3) Finální dopočtení kořenů: Víme, že řešení zi,Z2,z% jsou iracionální, tj. jejich rozvoj je neperiodický neukončený, proto je nemůžeme přesně vyčíslit. Ovšem pokud se spokojíme s přesností třeba 5 platných číslic, počítat tuto přesnost najde velmi rychle. Podívejme se na dvě metody, jakými k řešení můžeme dospět: Metoda půlení intervalu při řešení rovnice pix) = 0 (vysvětlení viz BP (Trombiková, 2019, str. 28-30)) Vycházíme ze situace p(—3, 5) < 0; p(—3) > 0 101 a) Najdeme střed intervalu (—3,5; —3) podle vzorce x\ = tj. x\ = —3,25. b) V tomto bodě x\ = —3, 25 spočteme funkční hodnotu p(—3, 25) = —46, 06055 - důležité je to, že je záporná. V další fázi z intervalů (—3,5; —3,25), (—3,25; —3) vybereme jako (ai;fei) interval (—3,25;—3), protože v krajních bodech jsou rozdílná znaménka funkčních hodnot, záporné a kladné, tj. řešení leží na tomto intervalu. c) Najdeme střed x2 = 9^ = ~3'225"3 = -3,125, pak p(-3,125) > 0. Tedy jako (a2;b2) volíme (-3,25; -3,125), protože p(-3, 25) < 0,p(-3,125) > 0, tj, řešení leží v tomto intervalu. d) Najdeme střed x3 = 2a±ža = -3,25-3,125 = -3,1875, pak p(-3,1875) < 0. Tedy jako (a3; 63) volíme (—3,1875;—3,125). e) Najdeme střed x4 = 2a±k = -3,1875-3,125 = _3) 16525) pak ^_3) 16525) < o. Tedy jako (a4;fo4) volíme (-3,16525;-3,125). f) Atd. po dalších deseti krocích xi5 = —3,12991. A to je bod, který pokládáme za řešení z\ = —3,12991. 'VIS Obrázek 8.11: Metoda půlení intervalu Metoda půlení intervalu tedy spočívá v tom, že výchozí interval dělíme na poloviny, vybranou polovinu zase na poloviny atd. a pro další dělení vybíráme vždy tu polovinu, v jejíž krajních bodech má polynom p{x) opačná znaménka funkčních hodnot, což znamená, že tato polovina obsahuje řešení. Celý algoritmus jsme zastavili asi po 15 krocích, kdy už délka intervalu ((214; &14) byla menší než 0, 00001, tedy je jasné, že jeho střed xi5 je spočítán s přesností na pět desetinných míst. Tentýž algoritmus půlení intervalu použijeme i na další dva hrubě vymezené intervaly (0,5; 1) a (1; 1,5) a dostaneme další dvě řešení: z2 = 0,54689 a z3 = l, 22892. Výpočet v prostředí R: Do proměnné pol v prostředí R si nadefinujeme polynom, jehož funkční hodnoty jsme počítali, jako funkci, která vypočte polik) pro jakoukoli hodnotu k: pol < —function(z)return(2 *z5 + 3*z4 — 7* z3+ 6* z2 — 11 * z + 5) Algebra 1 (MA 0003) 102 a stiskneme ENTER. Poté zkusíme najít řešení rovnice na intervalu (—3, 5; —3) metodou půlení intervalu . Celý algoritmus lze naprogramovat v R pomocí cyklu WHILE, například s tou přesností, že délka zkracujícího se intervalu bude menší než 0,00001: a < - -3.5 a ENTER (první minus je součástí přiřazovací šipky, druhé minus je součástí čísla), b < - - 3 a ENTER, a dále celý cyklus WHILE napíšeme na jeden řádek (v prostředí R to bude možné, zde v textu to vyjde na více řádků) a stiskneme ENTER: while(abs(a - b) > 0.00001) {*/ (pol((a + b)/2) * polib) < 0) {a < -{{a + b)/2);print{{a + b)/2)} else {b < -((a + b)/2);print((a + b)/2)}} (na obrazovku se nyní vypíše posloupnost středů intervalů blížících se k řešení, které zhruba s přesností na pět desetinných míst je z\ = —3,12991). Pokud celý postup (posloupnost tří kroků ukončených ENTER) zopakujeme pouze pro volbu a = 0,5, b = 1, najdeme řešení z2 = 0,54689. 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í. Nevýhoda metody půlení intervalu spočívá v tom, že je velmi pomalá, pokud nepoužijeme počítač - na zpřesnění o jedno desetinné číslo potřebujeme zhruba tři kroky. Hledáme-li metodu, která je i za použití pouze kalkulačky značně rychlejší, můžeme použít metodu Newtonovu. Metoda Newtonova = metoda tečen: obrázek a vysvětlení viz BP Trombiková, str. 34-38: S velmi rychlou metodou přišel Izák Newton: využil při tom pojem tečny ke grafu funkce: 103 Obrázek 8.12: Newtonova metoda = metoda tečen a) Zvolíme bod xq vhodně blízko našeho řešení. b) Sestavujeme posloupnost bodů xi, x2, x3,... podle klíče: vedeme tečnu ke grafu pix) v bodě [xk,p(xk)] a tam, kde tato tečna protne osu x, bude ležet Xk+±: _ P{Xk) Xfc+l — xk P'(Xk)' V našem příkladu by měl vzorec tvar: 2x5k + 3xj - 7x3k + 6x2k - llxk + 5 10x4 + 12x3 _ 2ix2 + 12xk _ n Xfc+l — Xfc Ukazuje se, že se zbavíme znaménka MINUS před zlomkem a ušetříme několik operací, když rozdíl na pravé straně převedeme na společného jmenovatele: _ 10X5 + 12X^ _ 21x3 + 12x2 _ _ (2x5 + 3x4 _ 7x3 + 6x2 _ ^ + 5) Xfc+l — - Xfc+l 10x4 + 12x3 _ 2ix2 + 12xk _ 11 8x5k + 9x4 + 28x3 + 6x2 _ 5 10x4 + 12x| _ 21x2 + 12xk _ n A tento vzorec použijeme v našem příkladu. z\ G (—3,5; —3): Volme x0 = —3, 5: _ 8(-3,5)5+9(-3,5)4+28(-3,5)3+6(-3,5)2-5 _ _o ooqnrc; X1 10(-3,5)4+12(-3,5)3-21(-3,5)2+12(-3,5)-ll o, ZjZjWoo _ -8-3,2290555+9-3,2290554-28-3,2290553+6-3,2290552-5 _ _o 1 QQQr)9 2 — 10-3,2290554-12-3,2290553-21-3,2290552-12-3,229055-ll ~~ ' ioyouz _ -8-3,1393025+9-3,1393024-28-3,1393023+6-3,1393022-5 _ _o i QnnnQ 3 ~~ 10-3,1393024-12-3,1393023-21-3,1393022-12-3,139302-11 ~~ °' iouuuo -8-3,1300035+9-3,1300034-28-3,1300033+6-3,1300032-5 _o 1oqqnq = _9 1 9001 4 ~~ 10-3,1300034-12-3,1300033-21-3,1300032-12-3,130003-11 ~~ °' izyyuy — J, IZi^l Téhož výsledku jsme Newtonovou metodou dosáhli již po čtyřech krocích! Algebra 1 (MA 0003) 104 z2 G (0,5; 1): Volbou xq = 0, 5 dostaneme už po dvou krocích x2 = z2 = 0, 54689. Z3 G (1; 1,5): Volbou xq = 1, 5 dostaneme po čtyřech krocích X4 = z% = 1, 22892. Velkou předností Newtonovy metody je to, že najde i komplexní řešení! Musíme ovšem počáteční x0 volit komplexní s nenulovou imaginární částí, jelikož metoda se sama od sebe do komplexních čísel nedostane. Zkusme určit dvojici komplexně sdružených řešení v našem příkladu: 2x5 + 3x4 — 7x3 + 6x2 - llx + 5 = 0 Víme, že |^41 < 6,5, |z5| < 6,5, takže budeme volit jako xq různá komplexní čísla s velikostí menší, než 6, 5 a vložíme je do Newtonovy metody podle již známého vzorce: • xq = 1 + i ... Po pěti krocích x5 = 0, 54689. Posloupnost se blíží k reálnému řešení, které už známe. Nenašli jsme nové řešení s nenulovou imaginární částí. • xq = 1 + 2i ... Po jedenácti krocích xn = 0, 54689. Posloupnost se blíží k reálnému řešení, které už známe. Nenašli jsme nové řešení s nenulovou imaginární částí. • x0 = l+3i... Po deseti krocích se dostaneme k x10 = —0, 07295 + i ■ 1, 08773 = z4. A protože víme, že druhé komplexní řešení je pouze komplexně sdružené k předchozímu, můžeme bez počítání psát z5 = —0, 07295 — i ■ 1, 08773 Naše rovnice 2x5 + 3x4 - 7x3 + 6x2 - llx + 5 = 0 má tedy tři racionální řešení: z1 = -3,12991; z2 = 0, 54689; z3 = 1, 22892 a dvě komplexní řešení z4 = -0, 07295 + 1 ■ 1, 08773; z5 = -0, 07295 - 1 ■ 1, 08773 Výpočet v prostředí R: Navíc k definici funkce polik) z předchozího algoritmu, kterou máme stále v paměti prostředí nadefinovanou (a pokud jsme ukončili práci a při ukončování zvolili ANO na otázku, zda si má prostředí pamatovat uložená data, bude nadefinovaná i při opětovném spuštění prostředí R), budeme potřebovat ještě nadefinovat funkci pro výpočet derivace p'ix) našeho polynomu: der < — function{w){return{lQ * w4 + 12 * tu3 — 21 * w2 + 12 * w — 11)} (a ENTER). Nyní podobným cyklem WHILE najdeme všechna tři řešení jako u metody půlení, nicméně nyní pomocí metody Newtonovy: rozdíl je zde v tom, že místo intervalu se zadává pouze jediný vstupní bod z: z < - -3.5 a ENTER, a provedeme cyklus WHILE: whileíabsípolíz)) > 0.00001Hz < -z - P7°l[Z\;print(z)} der(z) (a ENTER) ... po několika krocích bude nalezeno řešení z\ = —3,12991. Podobně pro vstupní z = —1 dostaneme Z3 = 1,22892 a pro vstupní z = 0,5 dostaneme z2 = 105 0,54689. Slabina Newtonovy metody: díky konstrukci pomocí tečny může postup zcela zhavarovat, směřovat do nekonečna nebo najít řešení, které už známe z jiného intevalu (jak se to stalo při volbě z = 1). Výhody Newtonovy metody ovšem jsou značné: a) najde řešení (pokud je tedy najde) mnohem rychleji než metoda půlení, b) najde i řešení komplexní!!!!!!!!!! Newtonově metodě (ani jazyku R) principiálně nevadí, když pracujeme s čísly komplexními. Jedinou podmínkou zde je, aby počáteční z bylo komplexní, nikoli reálné číslo - pro reálné vstupní z se totiž vzorec metody sám od sebe nikdy nedostane. Zkusme tedy najít zbývající řešení Z4, z5, které podle základní věty algebry víme, že musí existovat. Newtonovou metodou: • Volme vstupní z = 1 + li, najeďme šipkou na příkaz cyklu WHILE a stiskněme enter ... dospíváme k řešení z2 = 0,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 + 3í z našeho kruhu v komplexní rovině \z\ < 6,5: dojdeme k řešení Z4 = —0,07295 + i ■ 1,08773 s přesností na pět desetinných míst, a díky teoretické větě o komplexně sdružených kořenech už nemusíme dále počítat, stačí psát z5 = —0,07295 — i ■ 1,08773. • Našli jsme tedy podle numerických metod všechna řešení, která podle přesných algebraických postupů najít nelze - přesněji řečeno, nenašli jsme je zcela přesně, pouze s přesností na pět desetinných míst, to je ovšem přesnost dostatečná. • Celkem jednoduchou metodou lze najít komplexní řešení speciální rovnice, tzv. binomické rovnice, protože je v této rovnici pouze binom = dvojčlen: mocnina neznámé z a nějaké komplexní číslo. Tento poslední rychlý způsob pro tuto speciální rovnici se studenti naučí v následujících čtrnácti dnech, které budou věnovány komplexním číslům. Algebra 1 (MA 0003) 106 9 Týden 09 9.1 Cvičení 09: Polynomy 03 Dodělání osnovy na cvičení pro polynomy viz plán cvičícího. 9.2 Přednáška 09: Konstrukce číselných oborů Peanova množina (= axiomy množiny N), konstrukce N —> Z. Zbývají poslední dvě přednášky ve kterých se bude částečně jednat o opakování některých pojmů, ovšem některé informace budou ještě nové. 9.2.1 Peanova množina Začneme vysokoškolským pohledem na přirozená čísla: Co jsou to přirozená čísla? Jaké jsou axiomy struktury přirozených čísel? Půjde o trochu jiný pohled, než jen tvrzení, že (No, +, •) je polookruh. Jedná o ještě trochu elementárnější pohled, na kterém je struktura polookruh vybudována. Co to je Peanova množina? Množina, na které platí A) triviální čtyři axiomy o rovnosti (viz video); B) netriviální čtyři až pět axiomů o pojmu následník: 1. Vx G P 3 tzv. následník prvku x, který označujeme jako x' G P. 2. 3 e G P: e není následníkem žádného prvku množiny P. 3. Vx, y G P : x 7^ y => x' 7^ y' (následníci různých prvků jsou různé). 4. Jestliže pro podmnožinu M C P platí: a) e G M b) Vx G P : x G M x' G M tak => M = P. Tyto čtyři axiomy platí na množině přirozených čísel N: Ad 1) Vn G N vime, že jeho následník n' se rovná n' = n + 1. Ad 2) 1 není následníkem žádného přirozeného čísla. Ad 3) (m + + platí Vm, n G N. Ad 4) Pokud procházíme prvky množiny N tak, že a) začneme prvkem 1 107 b) pro n E N víme, že i n + 1 E N tak tímto způsobem projdeme celou množinu N. Kdybychom kromě procházení množiny N u každého přirozeného čísla ještě ověřili nějakou vlastnost, která pro ně platí, tak vlastně provádíme důkaz matematickou indukcí - struktura axiomu 4 je tedy velmi podobná struktuře důkazu matematickou indukcí. Ještě je důležité říci, že: Věta 31 N je až na izomorfismus jediným modelem struktury zvané Peanova množina. C) Definujme na Peanově množině uspořádání: relaci < definujeme na P následovně: • Lze dokázat, že na Peanově množině, pokud x ^ e, existuje u E P : u' = x. Tj. všechny prvky krome e mají nějaký prvek, jehož jsou následníkem. Tento prvek nazveme předchůdce prvku x a označíme 'x = u. • Lze definovat U (a) = úsek Peanovy množiny příslušný prvku a E P takto: (Zkrátka U(a) vytvoříme pomocí prvku a a všech možných předchůdců, které lze • Pomocí pojmů předchůdce a úsek Peanovy množiny lze nyní definovat relaci uspořádání < takto: a 'x E U (a), pokud tedy 'x existuje najít.) Algebra 1 (MA 0003) 108 9.2.2 Nástin této a následující přednášky intuitivně To, co bude nyní následovat, bude pokusem o podobnou elementární „konstrukci" množin Z,Q, R a nakonec i C. Intuitivně ovšem budeme vědět, jaké vlastnosti daná struktura, kterou vytvářet chceme, má mít, protože jsme je procházeli v první polovině tohoto předmětu. • a) (Z, +, •) vytvoříme ze struktury (N, +, •) dodáním: - 0 jako neutrálního prvku vzhledem ke sčítání, - záporných čísel jako inverzích prvků vzhledem ke sčítání. Dostaneme tak strukturu (Z, +, •), která je obor integrity, tj. - (Z, +) je komutativní grupa - (Z*, •) je komutativní monoid (Z*= Z — {0}) - platí distributivní zákon a ■ (b + c) = ab + ac Va, b,c £ Z - a ■ b = 0 platí pro a = 0 nebo b = 0 • b) (Q, +, •) vytvoříme ze struktury (Z, +, •) dodáním inverzních prvků vzhledem k násobení (až na inverzní prvek k 0, který nedodáváme a spokojíme se s tím, že neexistuje). Dostaneme tak strukturu (Q, +, •), která je tělesem, tj. - (Q, +) je komutativní grupa - (Q*, •) je komutativní grupa - platí distributivní zákon a ■ (b + c) = ab + ac Va, b,c £ Q (nenuloví dělitelé nuly zde také neexistují, ale to se u tělesa myslí automaticky, jak jsme zjistili na přednášce 6). • c) (R, +, •) vytvoříme ze struktury (Q, +, •) dodáním tzv. iracionálních čísel. Vznikne struktura (R, +, •), která je také tělesem. • d) (C, +, •) vytvoříme ze struktury (R, +, •) dodáním tzv. imaginární jednotky i, pro kterou platí i2 = —1. Vznikne struktura (C, +, •), která je také tělesem. Tedy z intuitivního popisu je vidět, že množiny R, C už neznamenají algebraicky nový skok v pojmu, stále se jedná o tělesa jako u množiny Q. Tedy vzhledem k operacím +, • jsou množiny Q, R, C struktury stejného typu, pouze přibývají vlastnosti množin R, C, které přímo nesouvisejí s danými dvěma operacemi: u R je touto vlastností „iracionalita některých čísel", u C je novou vlastností „imaginarita" některých čísel. Další poznámka: Odčítání a dělení nepovažujeme na této úrovni za další operace na dané množiny, nýbrž odčítání prvku/čísla je vlastně jen přičtení „opačného čísla" = inverze vzhledem k +, dělení nenulovým prvkem/číslem je vlastně jen násobení „inverzí" 109 vzhledem k •. Ve zbytku této přednášky a v celé následující přednášce se podíváme na čtyři výše uvedené konstrukce. 9.2.3 Konstukce N ->■ Z Věta 33 Komutativní pologrupu (N, +) lze injektivně vnořit do grupy (= rozšířit na grupu) Z := (N x N/^, ©). Obrázek 9.13: Injektivní vnoření komutativní pologrupy (N, +) do grupy Z := (N x N/„,®) i) Na N x N vytvořme operaci po složkách, jako sčítání vektorů. ii) Na N x N definujme relaci ekvivalence: [a, b] ~ [c, d], když a + d = b + c. iii) Vytvořme faktormnožinu N X N/^, jejímiž prvky jsou podmnožiny určené danou ekvivalencí. iv) Na množine podmnožin definujme operaci © takto: vybereme reprezentanty tříd = nějaké prvky těch tříd neboli podmnožin, sečteme je a výsledek určuje výslednou třídu (tím, že v ní leží): {[a,b]}®{[c,d]} := {[a + c,b + d]} Tato operace © splňuje na množine N x N/^ vlastnosti: (1) Uzavřenost plyne z uzavřenosti „staré operace" + v jednotlivých souřadnicích = složkách. Algebra 1 (MA 0003) 110 (2) Asociativita © plyne ze „staré" asociativity operace + v jednotlivých souřadnicích = složkách. (3) Neutrálním prvkem je třída {[1,1]}, což je třída obsahující prvky [1,1], [2,2], [3,3],... (4) Např. pro {[6, 2]} je inverzí {[2, 6]}. =>■ Tedy (N x N/^, ©) je grupa! v) Zobrazení ifj definujeme vztahem ipin) = {[n + 1,1]}. Takto definované zobrazení ip : N —r N x N/^ je injektivní homomorfismus, tedy vnoření (N, +) do struktury (N x N/„,®). Tímto způsobem jsme algebraicky přesně vytvořili jen pomocí přirozených čísel: - číslo 0 jako {[1,1], [2, 2], [3, 3], [4, 4],... } - číslo -4 jako {[1, 5], [2, 6], [3, 7], [4, 8],... } atd. a přitom výsledky sčítání přirozených čísel zůstaly v nové struktuře zachovány, to je zajištěno homomorfismem ip. 111 10 Týden 10 10.1 Cvičení 10: Komplexní čísla 01 Operace s komplexními čísly, algebraický a goniometrický tvar komplexního čísla (argument a velikost komplexního čísla), geometrický význam násobení a dělení komplexních čísel. Lze postupovat podle nejnovější učebnice pro střední školy (Robova, Hála, Calda 2013), ale vše se asi nestihne, tj. cvičící rozhodnou, co přesně ve cvičeních 10 a 11 stihne probrat. 10.2 Přednáška 10: Konstrukce oborů Q, R, C Na této přednášce budeme pokračovat v konstrukcích číselných oborů. 10.2.1 Konstrukce Z ->■ Q Věta 34 Obor integrity (Z, +, •) injektivně vnořit do tělesa (= rozšířit na těleso) Q := {Z x £*/„,©,©). Obrázek 10.14: Injektivní vnoření komutativního oboru integrity (Z, +, •) do tělesa (Z x £*/„,©,©) a) Na Z x Z* definujme relaci ekvivalence ~ takto: [a, b] ~ [c, d], když a ■ d = b ■ c 32stará operace • v (Z, +, •) Algebra 1 (MA 0003) 112 b) Vytvoříme faktormnožinu Z x Z* j^ definujme operace ©, 0 takto: {[a, b}} © {[c, d}} := {[ad + bc,b- d]33}34 {[a,b]} 0 {[c,d]} := {[a ■ c,b • d]}35 (Pro {[a, b]} je inverzí vzhledem k © prvek {[—a, b]}, pro {[a, b]} je inverzí vzhledem k 0 prvek {[b, a]}.) Pak (Z x Z* j ^, ©) je komutativní grupa, (Z x Z* / ^, 0) je komutativní grupa, operace ©, 0 splňují distributivní zákon, tj celkem (Z x Z* j ^, ©, 0) je těleso! d) Zobrazení ifj : Z —r Z x Z*/^ je injektivní homomorfismus, tj. původní výsledky sčítání a násobení celých čísel zůstanou v nové struktuře zachovány. e) Zobrazení ifj definujeme vztahem ipi^z) = {[z ■ 1,1]}. Toto zobrazení je injektivním vnořením, tj. přenáší výsledky operací z množiny Z do nové struktury, kterou označíme jako Q. 10.2.2 Konstrukce Q ->■ R Jak již bylo řečeno na minulé přednášce, konstrukce Q —r R, R —r C už jsou jiného charakteru, protože nevytváříme strukturu nového typu (R a C jsou už stále tělesa), pouze obohatíme množinu Q o nějaké další prvky. Množina Q se skládá z racionálních čísel. Každé racionální číslo lze vyjádřit nekonečně mnoha zlomky a lze převést na číslo s desetinným rozvojem ukončeným nebo neukončeným periodickým. Přidáním iracionálních čísel z množiny /, jejichž desetinný rozvoj je neperiodický neukončený, dostaneme množinu R reálných čísel. Věta 35 Konstrukce Q —> R, první možný pohled: Doplníme-li množinu Q o limity všech možných posloupností prvků z Q, které v samotné množině Q neleží, dostaneme množinu R. Důkaz: iracionální čísla jsou právě ta čísla, která jsou limitami posloupností zlomků z množiny Q, a přitom nejsou prvky množiny Q. □ Věta 36 Konstrukce Q —> R, druhý možný pohled: R je množina řezů (A, B) množiny Q, které jsou 1. druhu (ty odpovídají racionálním číslům) nebo 3. druhu (ty odpovídají iracionálním číslům). 33„staré" operace na {Z, +, •); b ■ d nikdy není rovno 0, protože b ^ 0, d ^ 0 34definici si zapamatujte tak, že operace se chová stejně jako sčítání zlomků převodem na společného jmenovatele: f + f = 35chová se podobně jako násobení zlomků f • f = fŕf 113 Důkaz či objasnění: Nejprve musíme definovat pojem řezu (A, B) lineárně uspořádané množiny M (tedy M je poset = částečně uspořádaná množina, ve které jsou každé dva prvky srovnatelné = tzv. řetězec). Rez (A, B) řetězce M je rozklad množiny M na podmnožiny A, B (AílB = 0, A U B = M,A^$,B^$ takový, že Va G A, Vfo G B : a < b. Vzhledem k pojmům nejmenší prvek/největší prvek existují čtyři druhy řezů (vysvětleno na Hasseových diagramech množiny M): Rez 1. druhu: A obsahuje svůj nej větší prvek, B nemá nejmenší prvek Rez 2. druhu: A nemá největší prvek, B obsahuje svůj nejmenší prvek xcí. A. (WH\\ IQ K- TOTO, Obrázek 10.15: Řez 1. druhu a řez 2. druhu Racionálních čísel je právě tolik, kolik existuje řezů 1. druhu množiny Q, tj. existuje bijekce Q —> řezy Q 1. druhu. Podobně bychom mohli zlomek y umístit namísto do množiny A do množiny B, a tím způsobem vznikne řez 2. druhu. Racionálních čísel je tedy právě tolik, kolik existuje řezů 2. druhu množiny Q, tj. existuje bijekce Q —> řezy Q 2. druhu. Podle toho, do které z množin A, B řezu „hraniční" zlomek y umístíme, vznikne řez 1. druhu nebo řez 2. druhu - můžeme si tedy vybrat, jak budeme racionální čísla (reprezentovaná zlomky) chápat, zda jako řezy 1. druhu nebo řezy 2. druhu množiny Q. Do tvrzení věty 36 jsme si vybrali racionální čísla reprezentovaná jako řezy množiny Q 1. druhu. Řez 3. druhu neboli MEZERA: A nemá největší prvek, B nemá nejmenší prvek Řez 4. druhu neboli SKOK: A má největší prvek, B má nejmenší prvek Iracionálních čísel je právě tolik, kolik existuje MEZER (= řezů 3. druhu) v Q, tj. existuje bijekce I —> mezery v Q. Například mezera na obrázku odpovídá iracionálnímu Algebra 1 (MA 0003) 114 číslu v^-Cili doplnímedi racionálni čísla (= řezy 1. druhu) iracionálními čísly = řezy 3. druhu), dostaneme R. mezerami v ľ43. 4.tku.W. Šuk.: ŕrcvt\T^o\v\Wv K V % YWAov 1 | Obrázek 10.16: Řez 3. druhu neboli mezera a řez 4. druhu neboli skok V obrázku mezery y/2 v Q neexistuje největší prvek A, ani neexistuje nejmenší prvek množiny B - ovšem \/2 je supremum množiny A, a současně \/2 je infimum množiny B. Cili místo terminologie řezů lze kostrukci věty 36 formulovat i jinak: pomocí pojmu infimum nebo supremum - můžeme si vybrat, který z pojmů použijeme, protože \/2 je současně ínfB i supA, takže stačí použít jen jeden pojem, např. infimum: Doplnímedi množinu Q o infima otevřených intervalů v Q, která neleží v Q, dostaneme R. Konec důkazu či objasnění. Poznámka: Věty 35, 36 popisují tedy tutéž konstrukci Q —> R, pouze pomocí jiných pojmů: věta 35 pomocí pojmu limita posloupnosti, věta 36 pomocí pojmu řez. Konstukce pomocí pojmu řez je součástí bakalářské zkoušky ve 3. ročníku. 10.2.3 Konstrukce R C: Věta 37 Konstrukce R —> C: Těleso (R, +, •) lze vnořit do tělesa C := R X R, ve kterém má rovnice x2 + 1 = 0 řešení. a) Na R x R definujme operace +, • takto: [a, b] + [c, d] := [a + c, b + d] ... a + ib + c + id = a + c + i(b + d) [a, b]-[c, d] := [ac—bd, ad+bc] ... (_a-\-ib)-(c-\-id) = ac+i2bd+ibc+iad = ac—bd+i^ad+bc) 115 Pak struktura (R x R, +, •) je těleso. Opačný prvek k [a, b] je [—a,—b]. Invezní prvek k [a, b] (mimo [0,0], ke kterému inverzi nehledáme) je [^j, : (a + ib) ■ ^lh^ = 1 ...vlastnost inverzního prvku. je inverzní prvek, upravme jej do tvaru „něco 1 1 a — ib a — ib a — ib a . (—b) a + ib a + ib a — ib a2 — i2b2 a2 + b2 a2 + b2 a2 + b2 A ôt^ž + * • je algebraický tvar prvku , b) Platí [0,1] • [0,1] = [1,0], algebraicky i2 = -1, tj. [0,1], algebraicky i, je resemm rovnice x2 + 1 = 0. c) Zobrazení ip definujeme vztahem ipir) = [r, 0]. Zobrazení ip : R —>■ R x R je injektivní homomorfismus R —>■ Rx R vzhledem k definovaným operacím, tj. původní výsledky sčítání a násobení reálných čísel jsou v nové struktuře zachovány. Algebra 1 (MA 0003) 116 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: Opakování a příprava ke zkoušce a) součástí otázek budou do určité míry i pojmy probrané v prvních devíti týdnech předmětu Základy matematiky - matematika je v jistém smyslu „jazyk", který buduje složitější pojmy na základě těch jednodušších, proto určité procento otázek, asi dvacet procent, bude opakováním těchto základních pojmů; b) otázky jsou prezentovány jako větší celky, ale na testu bude vždy jen jedna dílčí část otázky, jedna odrážka, jeden pojem nebo příklad - test bude tedy obsahovat více otázek s kratším rozsahem (návrh přípravy: nevypracovávejte si tedy odpovědi v rámci jakýchsi maxiotázek 1 až 20, ale spíš si vytvářejte síť papírků s pojmy a příklady, kterých bude třeba sto nebo více, a vytvořte si mezi těmito pojmy a příklady nějaký systém), c) součástí testu budou i důkazy některých vět - které, bude uvedeno v odrážkách v seznamu otázek. Otázka 01. Několik pojmů a dovedností z matematické logiky. • Co je to výrok? Co je to kvantifikátor? U výroku Vn G N : 6\n => 2\n napište a) obrácení, b) obměnu, c) negaci, a to včetně kvantifikátorů. • Proveďte negace výrokových forem (elementárně, tak aby nezůstal znak negace před žádnou závorkou): a) A (B V C); b) (A^B)AC; c) (AAB)VC. • Které dvě důležité výrokové formy jsou jsou logicky ekvivalentní implikaci A => Bl Otázka 02. Množinové operace. • Ze symbolů AuB, AílB, A, A\B, A^rB, A x B jen čtyři jsou symboly označující binární operace, protože A je unární operace doplňku a A x B je kartézský součin, jehož výsledkem je množina uspořádaných dvojic, tj. struktura zcela jiného typu než vstupní množiny. • Definujte symbolickým zápisem všech šest typů označení v předchozí odrážce. Otázka 03. Relace a její vlastnosti. • Definice (binární) relace na množině M. • Definice šesti základních vlastností relace (a také schopnost provést negaci těchto vlastností). 117 • Co je to ekvivalence, uspořádání, řetězec? Otázka 04. Relace ekvivalence a relace uspořádání. • Co je to faktor množina? • Co je to relace kongruence na množině celých čísel? Uveďte příklad, znázorněte graficky. • Co je to rozklad množiny? Jak se definuje rozklad množiny určený relací ekvivalence ~? • Jak se v Hasseho diagramu znázorňují jednotlivé vlastnosti relace uspořádání? • Uveďte definici a příklad minimálního prvku množiny M, maximálního prvku množiny M, nejmenšího prvku množiny M, největšího prvku množiny M. • M je podmnožina uspořádané množiny P; prvek p E P se nazývá a) dolní závora množiny M, b) horní závora množiny M, c) infimum množiny M, d) supremum množiny M, jestliže ... Otázka 05. Zobrazení, různé typy a vlastnosti zobrazení. • / je zobrazení mezi množinami laľ, jestliže ... • a) / je zobrazení z X do Y, b) / je zobrazení X do Y, c) / je zobrazení z X na Y, d) / je zobrazení X na Y, e) / je prosté, f) / je injekce, g) / je „zobrazení na" (neboli surjekce), h) / je bijekce, jestliže ... definice viz: https://is.muni.cz/auth/el/ped/j aro2024/MA0003/um/zm2023.pdf#page=71 Otázka 06. Struktury s jednou binární operací a jejich vlastnosti. • Definice binární operace na množině. Různé vlastnosti operací napsané symbolickým zápisem. • Vyberte si příklad jedné konečné množiny s jednou operací, a jedné nekonečné množiny s jednou operací - vypište vlastnosti (názvy, nikoli čísly!!) těchto operací a řekněte, o jaké algebraické struktury se vzhledem k této operaci jedná. • Pokud je to možné či snadno proveditelné či to víte, zdůvodněte, proč vlastnosti platí: např. platí vlastnost neutrálního prvku, protože jím je ... ; platí vlastnost existence inverzí, protože například pro ... je inverzí ... • Uveďte důkaz větiček (viz nová verze skript): věta 1, věta 2, věta 3, věta 4, věta 5. • Co je to řád grupy a řád prvku? Jak se tyto pojmy liší? • Jak se definuje n-tá odmocnina prvku grupy a záporná mocnina prvku grupy? (definice 12 a 13) Algebra 1 (MA 0003) 118 • Co stačí ověřit u podmnožiny S grupy (G, \/), abychom měli jistotu, že (S, v) Je už také grupou? Věta 6 ... vyslovte j i a dokažte ji. Otázka 07. Množinové operace a jejich vlastnosti. Uvažujte strukturu 2A pro A = {1, 2, 3, 4, 5}, tj. množinu všech podmnožin množiny A. • Co za algebraickou strukturu se dvěma operacemi je (2A, n)? Uveďte u každé z operací neutrální prvek a příklad, že existuje-neexistuje inverzní prvek. • Jednotlivé vlastnosti těchto operací jsou vlastně vztahy mezi množinami. Dokažte některý z nich, ideálně například distributivní zákon (pomocí Vennových diagramů). • Obsahuje tato struktura nenulové dělitele nuly? Jaká rovnice by musela pro ně platit? Uveďte příklad těchto objektů sestavených do dané rovnice. • Uveďte a dokažte tzv. de Morganova pravidla (Základy mat., přednáška 4), která vyjadřují vztah mezi binární operací sjednocení-průniku a unární operací doplňku. Dokazují se, jak jinak, pomocí Vennových diagramů. • Mají operace průniku a sjednocení množin nějakou vlastnost, kterou nemají operace sčítání a násobení čísel? Odpověď: Vlastnost idempotence, nebo vlastnost absorbce. Napište tyto vlastnosti rovností a dokažte je (pomocí Vennových diagramů). Otázka 08: Pojem homomorfismu a jeho význam. • Uveďte definici homomorfismu mezi grupoidy. • Řekněte, jak se přirozeně (viz přednáška) definuje homomorfismus grupy (Z, +) do grupy (Zq,+). Tento homomorfismus není prostý, ale je surjektivním zobrazením. Co je pro pojem surjektivního homomorfismu charakteristické? Odpověď na část otázky: Surjektivní homomorfismus redukuje množinu Z na menší množinu Zq, na které některé vlastnosti zůstaly zachovány (např. zbytek po dělení číslem 6 je stejný u vzoru i obrazu tohoto zobrazení), kdežto některé vlastnosti zachovány nebyly (ztratila se nekonečnost množiny Z, např. všech nekonečně mnoho násobků čísla 6 se zredukovalo do jednoho prvku [0]). Tedy pokud chceme pracovat pouze se zbytky po dělení šesti, vlastně ve svém přemýšlení-vyjadřování provádíme fiktivní homomorfismus množiny celých čísel na množinu zbytků. Homomorfismus (zejména ten surjektivní, jak je v našem příkladu) tedy představuje zaměření pouze na dílčí vlastnost množiny, kterou je v našem příkladu zbytek celého čísla po dělení číslem 6. • věta 9a, věta 9b, věta 9c ... vlastnosti homomorfismu, číslování podle nově upravovaného textu, měli byste umět důkazy - též i na videu na konci čtvrté přednášky, ale na videu myslím prezentováno jako věta 10. 119 • Definice jádra Kerip homomorfismu ip, definice oboru hodnot homomorfismu ip ... definice 20 a následný příklad. Dokažte větičku (věta 10): jádro grupového homomorfismu je podgrupou té první (vstupní) grupy. • Co je charakteristické pro pojem injektivního homomorfismu? Odpověď: Pojem injektivního homomorfismu se objevuje například při konstrukci nebo koncepčním přechodu od množiny N na množinu Z. Formálně do množiny N „přidáváme" další prvky, a přitom ovšem chceme, aby dosavadní pojetí přirozených čísel (včetně výsledků operací sčítání a násobení) zůstalo zachováno. To přesně „kontroluje", dokazuje či „zaručuje" homomorfismus ifj : N —> N x N/^. Mluvíme o INJEKTIVNIM VNOŘENÍ (a je to totéž jako injektivní homomorfismus) množiny N do množiny N x N/^, která má více prvků (nekonečně mnoho dalších prvků) - ty jsou „modelem" nuly a záporných čísel. Tedy v tomto pohledu injektivní homomorfismus přesně matematicky ukazuje, že při přechodu od N k Z na ZS zachováváme dosavadní pojetí práce s čísly, pouze „rozšiřujeme" toto pojetí čísla na nadmnožinu Z (podobnou argumentaci lze provést při rozšíření Z na Q). Otázka 09: Pojem izomorfismu a jeho význam. • Definice izomorfismu mezi grupoidy36. • Jaký je význam izomorfismu? Odpověď: Izomorfismus i homomorfismus v algebře slouží pro porovnávání různých algebraických struktur - pokud mezi dvěma strukturami lze zavést homomorfismus nebo izomorfismus, popíšeme tím dosti velkou příbuznost těchto struktur, protože při homomorfismu i izomorfismu jsou zachovány výsledky dané operace. Izomorfismus (= bijekce zachovávající výsledky operace) nám představuje velmi silný algebraický pojem: operace na obou množinách vykazuje naprosto stejné vlastnosti. Například — izomorfismus zobrazí podgrupu na podgrupu o stejném počtu prvků. Srovnání s homomorfismem: Homomorfismus též zobrazí podgrupu na podgrupu, ale počet prvků se může redukovat - uvažujte například homomorfismus (Z$, +) na (Z4,+). definovaný /01234567\ \01230123/ Podgrupa (2) := {0,2,4,6} grupy Z$ se zobrazí na podgrupu (2) := {0,2} grupy Z4. 36Grupoidy jsou struktury s nejmenším možným počtem podmínek (jedinou - uzavřeností operace na dané množině), mezi kterými lze homomorfismus nebo izomorfismus definovat. V realitě pak velmi často studujeme či popisujeme homomorfismus či izomorfismus grup, kde platí v každé struktuře už podmínky čtyři. Algebra 1 (MA 0003) 120 — izomorfismus zobrazí prvek řádu 3 na prvek řádu 3. Srovnání s homomorfis-mem: řád obrazu u homomorfismu může být nižší než řád vzoru - uvažujte například homomorfismus (Z$, +) na (Z4,+) (viz výše): řád prvku 2 v Z$ je roven čtyřem, řád obrazu 2 v Z4 je roven dvěma (řád obrazu u homomorfismu nemusí být stejný, ale je dělitelem řádu vzoru). — izomorfismus zobrazí cyklickou podgrupu na cyklickou podgrupu o stejném počtu prvků. Srovnání s homomorfismem, ad homomorfismus (Z$, +) na (Z4, +) (viz výše): Cyklická čtyřprvková podgrupa (2) grupy Zg se zobrazí na cyklickou dvouprvkovou podgrupu (2) grupy Z4. — atd. U izomorfismu platí: pokud přeznačíme prvky první struktury příslušnými prvky druhé struktury určenými izomorfismem, daná tabulka operace první struktury (pokud prvky v záhlaví tabulky napíšeme ve stejném pořadí37) bude naprosto totožná jako tabulka operace druhé struktury. • Příklad: Rozhodněte, které z grup ({1, —1, i, —i}, •), (Z4, +), [Z2 x Z2, +) jsou mezi sebou izomorfní (= vykazují naprosto stejné vlastnosti dané operace, kromě toho, že se jedná o bijekci)a které ne. Otázka 10: Grupa permutací a Cayleyho věta • Vypište celou tabulku operace skládání permutací grupy 63. • Z tabulky vyčtěte základní informace o inverzních prvcích a podgrupách, neutrálním prvku. • Co říká Cayleyho věta? (věta 8 podle nového číslování, důkaz umět nemusíte) • Ilustrujte Cayleyho větu na konečné grupě (Z3, +) a nekonečné grupě (Z, +). • Mohl by se objevit příklad: Jakou osmiprvkovou podgrupu grupy (S4, o) vygenerují cykly (1, 2, 3,4) a (1, 2) při operaci skládání permutací? Nápověda: Nemusíte vypisovat celou tabulku operace, ale při vytváření tabulky operace se postupně objevují různé prvky jako výsledky, tj. sestavit aspoň část této tabulky by vám pomohlo. • Řešte v (S4, o) rovnici (1, 2, 3) o x = (2, 3, 4). Otázka 11: Dihedrální grupy D% (grupa symetrií trojúhelníku), D4 (grupa symetrií čtverce), D5 (grupa symetrií pravidelného pětiúhelníku), D$ (grupa symetrií pravidelného šestiúhelníku) a Lagrangeova věta. • Vysvětlete prvky těchto grup geometricky i v jejich algebraickém tvaru. 37Studenti někdy říkají-píší, že dané dvě struktury nejsou izomorfní, ale pořadí prvků může být v záhlaví tabulky operace přehozeno vzhledem k záhlaví tabulky operace první množiny - tedy izomorfismus nekontrolujeme pomocí naprosto totožné tabulky, ale pomocí zjišťování vlastností dané množiny, tj. například vztahy mezi inverzními prvky, podgrupy o jistém počtu prvků, apod. - tyto věci mají mnohem větší váhu, než jen první pocit ohledně vzhledu obou tabulek. 121 • Zkonstruujte tabulky operace skládání zobrazení v těchto grupách, nebo v některých podgrupách. • Co je tvrzením Lagrangeovy věty? (věta 15 podle nového číslování, důkaz umět nemusíte) • Vypište na základě geometrického významu i Lagrangeovy věty všechny podgrupy těchto grup (podívejte se na řešené příklady ve skriptech s těmito strukturami, najdete podle obrázků symetrie trojúhelníku, čtverce, pětiúhelníku a šestiúhelníku). • Určete množinu generátorů dané grupy. Otázka 12: Struktury se dvěma operacemi. • Definujte okruh; uveďte příklad okruhu zbytkových tříd, který není oborem integrity, včetně vysvětlení a příkladu nenulových dělitelů nuly. • Definujte obor integrity; uveďte příklad a) okruhu zbytkových tříd, který je oborem integrity; b) oboru integrity, který není tělesem. • Definujte těleso; uveďte příklad a) konečného, b) nekonečného tělesa. • Dokažte větičku (věta 25): Každý konečný obor integrity je už automaticky tělesem. • Dokažte větičku (věta 26): v každém tělese platí už zákon krácení (7)*. • Dokažte větičku (věta 27 podle nového číslování): V okruhu platí: Daný okruh (M, +, •) je oborem integrity právě tehdy, když v něm platí vlastnost krácení (7)* pro okruhy: Va, b,c £ M, a / 0, platí: a ■ b = a ■ c ==> b = c. Otázka 13: Polynomické rovnice — algebraické metody řešení. • Co je to množina všech polynomů (R[x],+,-) s reálnými koeficienty, s operacemi sčítání a násobení, z algebraického hlediska? • Co je to polynom stupně n, vedoucí koeficient polynomu, kořen polynomu, násobnost kořene? Co říká základní věta algebry? • Co říká věta o racionálních kořenech polynomu a jak je lze určit pomocí Hornerova schématu? • Co říká „věta o odstranění násobných kořenů polynomu"? Popište pomocí dobrého označení, příklad uvádět nemusíte. • Co je zajímavé na komplexních kořenech polynomu z R[x\l Odpověď: v polynomu s reálnými koeficienty se vyskytují oba současně, v rozkladu polynomu v R se jedná o dva různé komplexní kořeny x\ = a + bi, x2 = a — bí jednoho v R nerozložitelného polynomu 2. řádu. Algebra 1 (MA 0003) 122 Otázka 14: Polynomické rovnice — numerické metody řešení. • Jak lze zhruba vymezit všechny kořeny polynomu? Odpověď: Oddíl F z přednášky 8. • Jak lze zhruba najít interval, na kterém existuje reálné řešení polynomu, který jsme zbavili násobných kořenů38? Odpověď: Využijeme nerovnosti F, zjistíme interval (—r; r), kde r je poloměr kruhu v nerovnosti F, projdeme tento interval s dostatečně malým krokem, vypočteme p (x,) v bodech xl těchto kroků .... viz přednáška 8, řešený příklad. • Popište na příkladu, jak upřesníme iracionální kořen polynomu získaný z oddílu F, pomocí metody půlení intervalu a metody Newtonovy. Najděte řešení rovnice x5 —x2 — 1 = 0 na intervalu (1; 2) oběma těmito numerickými metodami ... proveďte tři kroky u každé z metod. Je možné, že u zkoušky zde bude jiná rovnice, například rovnice 2x3 + 5x — 1 = 0 a interval délky 1, který obsahuje řešení, budete muset sami najít. Otázka 15: Komplexní čísla (a reciproké rovnice): příklady a pojmy v rozsahu probraném na cvičení, podpořeno doporučenou učebnicí pro střední školy. • komplexní číslo v algebraickém, goniometrickém a exponenciálním tvaru - vysvětlení každého tvaru, převody mezi tvary; • násobení a dělení komplexních čísel, Moivreho věta; • výpočet n-té odmocniny z komplexního čísla, znázornění těchto n-tých odmocnin; • výpočet druhé odmocniny z komplexního čísla algebraicky; • řešení binomické rovnice: řešte rovnici x4 + 1 = 0 a znázorněte obrazy řešení v komplexní rovině ... vrcholy jakého obrazce jsou tato řešení? • (řešení reciproké rovnice): vysvětlete metodu při řešení rovnice x6 - 3x5 + 5x4 - 7x3 + 5x2 - 3x + 1 = 0; jen dokončete převod na rovnici třetího stupně, kterou už nemusíte řešit. 38Tento předpoklad jsem v přednášce 8 nezmínil a je důležitý: Kdybychom totiž zkoumali polynomp(a:), aniž bychom snížili stupeň polynomu při vícenásobných kořenech postupem z oddílu B, mohlo by dojít k situaci, že některé reálné kořeny mají násobnost 2 nebo 4 atd. zkrátka násobnost sudou. Při zkoumání grafu funkce p(x) pak neplatí skutečnost, že by funkce přecházela v bodě kořene se sudou násobností ze záporných funkčních hodnot na kladné (nebo z kladných funkčních hodnot na záporné), nýbrž graf funkce p(x) se v blízkosti kořene blíží k ose x, v bodě kořene x^ se jí dotkne a „odrazí se na tutéž stranu", tj. např. p(x) < 0 pro x < Xk, pak p(xk) = 0, ale pak p(x) < 0 nastane i pro x > Xk, tj. neplatí, že by funkční hodnoty p(x) při průchodu proměnné x bodem x^ měnily znaménko. To znamená, že postupné počítání funkčních hodnot z intervalu (—r; r) takový kořen neodhalí. Tomuto problému se vyhneme, když provedeme postup B, tj. odstraníme násobné kořeny polynomu. Potom při výpočtu funkčních hodnot v intervalu (—r;r) s dostatečně malým krokem najdeme všechny intervaly, na kterých existuje jediný jednonásobný kořen. 123 Otázka 16: Peanova množina P, množina N přirozených čísel. • uveďte nedůležité čtyři Peanovy axiomy které se týkají rovnosti; • uveďte důležitých čtyři až pět Peanových axiomů, které se týkají pojmu následníka; • uveďte definici předchůdce, úseku a uspořádání na P; • uveďte čtyři vlastnosti, které splňují operace sčítání a násobení, jež lze definovat na množině P; • uveďte, jak lze strukturu (N0, +, •) vystihnout algebraicky Otázka 17: Algebraický popis, jak z N zkonstruujeme Z. Studenti by měli umět nakreslit obrázek a celou konstrukci popsat. Bude též zkoušeno na následujících dílčích otázkách: • Co provedeme s množinou N nejdříve? Vytvoříme kartézský součin N x N. • Jak definujeme relaci ekvivalence ~? • Co je to N x N/^1 Popište tuto strukturu - jaké jsou její prvky? • Jak na struktuře N x N/^ definujeme operaci sčítání? Jaké má tato operace vlastnosti? Uveďte minimálně, který prvek je neutrální a jak se najde inverze pro nějaký prvek různý od neutrálního. • Jak se definuje zobrazení N —> N x N/^, jaké má vlastnosti a co zaručuje? • Jakým pojmem lze výslednou strukturu s operacemi sčítání a násobení vystihnout algebraicky? Otázka 18: Algebraický popis, jak ze Z zkonstruujeme Q. Studenti by měli umět nakreslit obrázek a celou konstrukci popsat. Bude též zkoušeno na následujících dílčích otázkách: • Co provedeme s množinou Z nejdříve? Vytvoříme kartézský součin Z x Z*. • Jak definujeme relaci ekvivalence ~? • Co je to Z x Z* jrJl Popište tuto strukturu - jaké jsou její prvky? • Jak na struktuře Z x Z*/^ definujeme operaci sčítání a operaci násobení? Jaké má tato operace vlastnosti? Uveďte u obou operací minimálně to, který prvek je neutrální a jak se najde inverze pro nějaký prvek různý od neutrálního. • Jak se definuje zobrazení Z-)2x Z*jaké má vlastnosti a co zaručuje? • Jakým pojmem lze výslednou strukturu s operacemi sčítání a násobení vystihnout algebraicky? Algebra 1 (MA 0003) 124 Otázka 19: Algebraický popis, jak z Q zkonstruujeme R pomocí řezů množiny Q. • Co je to řez množiny M? • Jaké čtyři typy řezů existují? Vysvětlete i graficky; • Jak se „zkonstruuje" R z množiny Ql Cemu odpovídají řezy Q prvního druhu, čemu odpovídají řezy Q třetího druhu? Otázka 20: Algebraický popis, jak z R zkonstruujeme C. Studenti by měli umět nakreslit obrázek a celou konstrukci popsat. Bude též zkoušeno na následujících dílčích otázkách: • Co provedeme s množinou R nejdříve? Vytvoříme kartézský součin R x R. • Jak na struktuře R x R definujeme operaci sčítání a operaci násobení? Jaké má tato operace vlastnosti? Uveďte u obou operací minimálně to, který prvek je neutrální a jak se najde inverze pro nějaký prvek různý od neutrálního (a že tato inverze je opět komplexním číslem!!). • Jak se definuje zobrazení R —>■ R x R, jaké má vlastnosti a co zaručuje? • Jakým pojmem lze výslednou strukturu s operacemi sčítání a násobení vystihnout algebraicky? Které z otázek můžete na testu čekat? Všechny, tj. z každého okruhu otázek budete prověřeni. • Některou z otázek 1 až 5 nebo její část (opakování některých pojmů); • některou z otázek 6,7,12 (vlastnosti operací, struktury s jednou operací nebo se dvěma operacemi); • některou z otázek 8,9,10,11 (něco o homomorfismu-izomorfismu, něco o permutacích) ; • některou a otázek 13,14 (řešení polynomické rovnice, zejména numericky, přineste si kalkulačky); • nějaký příklad a pojem z komplexních čísel (otázka 15), možná i zmínku-otázečku na reciproké rovnice; • nějako část otázky 16 až 20 (konstrukce číselných množin). 125 12 Výsledky některých příkladů 12.1 Výsledky ke cvičení 1.1 — Opakování definic z předmětu Základy matematiky Ad úloha 1.1: Definice základních pojmů: a) Množinou M rozumíme soubor navzájem rozlišitelných prvků, o kterých lze jedno- značně rozhodnout, že do něj patří. b) Kartézský součin množin M,N je množina všech uspořádaných dvojic [m,n], kde m G M a současně n G N. c) Relace na množině M je nějaká podmnožina kartézského součinu M x M. Relace mezi množinami X a V je nějaká podmnožina kartézského součinu X x Y. d) Relace ekvivalence na M je binární relace, která je reflexivní, symetrická a tranzitivní. e) Relace uspořádání na M je relace, která je reflexivní, antisymetrická a tranzitivní. f) Relace / na kartézském součinu Xxľse nazývá zobrazení z množiny X do množiny Y, jestliže pro ni platí podmínka: [x, y] G / A [x, z] G / => y = z. g) Binární operace V na množině M je zobrazení M x M —> M, t j. zobrazení, které přiřadí uspořádané dvojici [a, b] z kartézského součinu M x M výsledek této operace, prvek aVb. h) Zobrazení f : N —> R) (tedy D(f) je množina přirozených čísel, H (f) množina reálných čísel) se nazývá posloupnost reálných čísel. i) Zobrazení / z množiny reálných čísel R do množiny reálných čísel R se nazývá (reálná) funkce (jedné) reálné proměnné. Ad úloha 1.2: Definice vlastností relací: • Relace p na množině M je reflexivní, když Vx G M : xpx. • Relace p na množině M je symetrická, když Vx, y G M : xpy => ypx. • Relace p na množině M je tranzitivní, když Vx, y, z G M : xpy A ypz => xpz. • Relace p na množině M je úplná, když Vx, y G M : xpy V ypx. • Zobrazení / z X do F je taková relace Xx7, že platí [x, y] G / A [x, z] G / => y = z. Algebra 1 (MA 0003) 126 12.2 Výsledky ke cvičení 1.2 — Určování vlastností různých operací Ad úloha 1.10: 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 (A/o, +) je monoid). Vlastnost (4) na (N, +) neplatí, protože např. inverzní prvek k 2 je —2, ale —2 ^ N. □ b) (Z, +) je komutativní grupa. c) (Z,-) je komutativní monoid. Opravdu, násobení je komutativní - platí (5). Vynásobením dvou celých čísel je zase celé číslo - platí (1). Násobení tří čísel nezávisí na uzávorkování - platí (2). Jednotkovým prvkem vzhledem k násobení je číslo 1, což je celé číslo - platí tedy (3), tedy (Z, •) je monoid. Ovšem inverzní prvky vzhledem k násobení nejsou celá čísla: např. inverzí k číslu 2 vzhledem k násobení je |, ale to není celé číslo, inverzí k 3 je |, ale | ^ Z, atd. □ d) (Q, •), (iž, •) jsou komutativní monoidy. Opravdu, přece jen chybí ještě jeden inverzní prvek vzhledem k operaci násobení, a sice pro nulu: rovnice 0 • x = 1 nemá řešení na množině Q nebo R, tj. neplatí vlastnost (4), dané množiny nejsou grupami vzhledem k násobení. □ e) (Q ~ {0}i ')) (-^ ~~ {0}'') Jsou komutativní grupy. Někdy též značíme tj- [Q*i')) C^*)') Jsou komutativní grupy. f),g) (2A,U), (2A, n) jsou komutativní monoidy. Opravdu, sjednocením či průnikem dvou podmnožin dané množiny A je zase nějaká podmnožina množiny A - platí (1). Operace U a n nezáleží na uzávorkování - platí (2). Jednotkovým prvkem vzhledem ke sjednocení je 0, jednotkovým prvkem vzhledem k průniku je celá množina A ... platí (3) vzhledem k oběma operacím. Inverze ke mnoha prvkům této struktury neexistují - například pro operaci sjednocení a podmnožinu {a} množiny A = {a, b, c, d, e} by musela existovat podmnožina X množiny A, aby {a} U X = 0, a to neexistuje. h) (Z,—) je jen grupoid, protože operace MINUS není asociativní, tj. záleží na uzávorkování; (Z,:) není ani grupoid, protože výsledek dělení řady celých čísel není Q Q-{0}, R*:=R-{0}, 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. 127 Ad úloha 1.14 (M, V) je komutativní monoid. Ad úloha 1.15 (M, A) je komutativní grupa. Ad úloha 1.16 (N — {0}, *) je grupoid. Ad úloha 1.17 (R+, o) je komutativní grupoid. 12.3 Výsledky ke cvičení 3.1 — Vlastnosti grup, podgrupy a generátory grupy Ad úloha 3.3 - F.2: Na jednom řádku operace v grupě nemohou být stejné dva prvky, protože v grupě platí zákon o krácení (7). Sporem: Na jednom řádku se vyskytují různé X\ a x2. Rovnici a*xi=y = a*x2 vynásobíme prvkem A-1 zleva a dostaneme po využití vlastnosti (3) na obou stranách rovnosti dostaneme x\ = x2, což je spor s tím, že x\ a x2 jsou různé prvky. Ad F.3: Tabulku lze doplnit na: e a b e e a b a a b e b b e a Ad úloha 3.6 - A.l: H je podgrupou grupy G, protože (1) součet logaritmuje logaritmus součinu a součin kladných hodnot je zase kladná hodnota, tj. H je uzavřená vzhledem k součtu. Dále je neprázdná, obsahuje např. prvek log 1, což je neutrální prvek vzhledem ke sčítání (platí (3)). Asociativita se sveze z asociativity grupy (R, +), platí (2). A nakonec inverzní prvek k prvku loga je prvek log ^, protože platí (4): pro každé loga G H log a + log - = log 1 = 0. a Ad A.5:ano, jedná se o podgrupu, prvky grupy jsou body na přímce procházející počátkem, operace sčítání těchto prvků (funguje stejně jako operace sčítání vektorů s počátečním bodem v počátku a koncovým bodem v daném prvku) splňuje vlastnosti (1), (4 ... inverzní prvek k prvku (x, 2x) je prvek (—x, —2x), který opět leží na dané přímce) a množina je jasně neprázdná. Ad D.5: Pokud dané součiny jsou navzájem různé prvky (to plyne mimo jiné z úlohy F.2 z minulého cvičení, že na jednom řádku operace grupy nemohou být stejné prvky), jeden z těchto součinů musí být roven neutrálnímu prvku n, tj. nechť například aj*a/ = n, pak podle věty 4 platí a"1 = a/, našli jsme inverzi k prvku al5 platí vlastnost (4). Algebra 1 (MA 0003) 128 Ad úloha 3.7 - ad N.l: H = {6,12,2,8,14,4,10,0} a prvky jsou napsány v tom pořadí, jak je získáváme užitím prvku 6. Ad E.l: podgrupy jsou čtyři: a) celá Hio generovaná prvkem 1 nebo prvkem 3 nebo prvkem 7 nebo prvkem 9; b) druhá triviálni podgrupa ({0}, +) generovaná prvkem 0; c) podgrupa ({0, 2,4, 6, 8}, +) generovaná prvkem 2 nebo prvkem 4 nebo prvkem 6 nebo prvkem 8; d) podgrupa ({0, 5}, +) generovaná prvkem 5; Ad E.3: < 6, 9 >= {6, 0, 9, 3} vzhledem k operaci skládání otáčení. Ad E.7 modifikace: prvek [1,1] je generátorem podgrupy {[1; 1; ], [0; 2], [1; 3], [0; 0]} vzhledem ke sčítání. Ad E.6: ano, prvek [1,1] je generátorem celé grupy vzhledem ke sčítání. Grupa má šest prvků a výsledek lze vyčíst z tabulky operace v této grupě. Ad úloha 3.8 a) x = (b2)-\ b) x = * a c) x = (a4)-1 Ad úloha 3.10: Tabulka operace o na množině D% symetrií trojúhelníku: Tabulka 12.10: Tabulka operace o na množině D% symetrií trojúhelníku. o Ro Ri R2 R3 R4 R5 Rq Ro Ri R2 R3 R4 R5 Ri Ri R2 Ro R5 R3 R4 R2 R2 Ro Ri R4 R5 R3 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 (63, o) v příkladu 4 je vidět, že mezi oběma grupami existuje izomorfismus, tj. příslušné tabulky operace se liší pouze 129 přeznačením prvků: f (e) = Rq, f (s) = Ri, f (t) = R2, f (u) = R%, f (v) = R4, f (vo) = iž5 (toto izomorfní přiřazení je vidět i na obrázku 1.1). Aby zobrazení / bylo izomorfismem, musíme z tabulky operace první grupy dostat přeznačením prvků vzhledem k zobrazení / přesně tutéž tabulku vzhledem k operaci v druhé grupě. Ad úloha 3.11 Cyklické podgrupy grupy (i/10, +) : ({0}, +), ({0, 5}, +), ({0, 2,4, 6, 8}, +), (H10, +). Ad úloha 3.12 Cyklické podgrupy grupy (i/12, +) : ({0}, +), ({0, 6}, +), ({0, 2,4, 6, 8,10}, +), ({0, 3, 6, 9}, +), ({0,4, 8}, +), (H12, +). 12.4 Výsledky ke cvičení 4.1 — Nekomutativní grupy Ad úloha 4.1: Podle definice skládání zobrazení platí /1 2 3 4 5 6 7\ l l l l l l i 7 1 6 3 4 2 5 2 3 4 5 6 7 l i l l i i l = u i l l 5 7 2 6 3 1 4 7 3 2 1 5 4 l l i l l i i \6 7 3 2 1 5 12.5 Výsledky ke cvičení 5.1 — Řád prvku, cyklické grupy, grupy zbytkových tříd ad Cvičení 5.1. Například N.4: a i /3 vyjádříme jako součin navzájem nezávislých cyklů: a = (1,2) o (3,4,5), /3 = (1,6, 7,2,5). Pak lze cykly zvlášť umocnit a spojit: a3 = (1,2) o id = (1,2), /34 = (1,5,2 , 7, 6)39. Spočteme „součin" a rozložíme na dílčí „součin" navzájem nezávislých cyklů: a3 o /34 = (1,5) o (2, 7, 6). Při umocnění na pátou nyní opět umocníme každý cyklus zvlášť: (a3o/34)5 = (l,5)o(2,6,7). Rád cyklu (1, 5) je 2, řád cyklu (2, 6, 7) je 3, a tedy řád jejich složení je nejmenší společný násobek dílčích řádů, tedy 6. 39Mimochodem: protože Podgrupa generovaná permutací j3 je cyklická a prvek j3 je řádu 5 (cyklus délky k je řádu k, platí /35 = id, a tedy /34 = /3_1 ... inverzním prvkem k cyklu /3 je mocnina prvku /3 o jedničku nižší než řád prvku j3. Algebra 1 (MA 0003) 130 Ad příklad 31 Ad Například F.l: Řád obrazu je dělitelem řádu vzoru. Lze i celkem jednoduše dokázat: Sporem ... předpokládejme, že prvek a řádu k se zobrazí na prvek řádu /, 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, \/), e2 je neutrální prvek v grupě G2 = (H, *). Celkem máme e2 = 0, 1 ^> 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 —> 0, 5 —> 3, 6 —> 2, 7 —> 1. Jádrem je množina {0,4} grupy Z%. Ad Například N.2: (Zq, ©) sestává z prvků: (operací „umocňování" je sčítání prvků) [0] je řádu 1, [1] je řádu 9, [2] je řádu 9, [3] je řádu 3, [4] je řádu 9, [5] je řádu 9, [6] je řádu 3, [7] je řádu 9, [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ů řádu 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. 131 Dále si všimněme, že grupa Z$ má řadu prvků řádu devět, je tedy cyklická, tj. stačí zobrazit jeden z generátorů celé grupy, například prvek [1], a všechny obrazy ostatních prvků jsou už jednoznačně určeny z podmínky homomorfismu (podmínky zachování výsledku operace. Díky těmto faktům lze dospět ke třem různým homomorfismům: hom 01: v?i([0]) =id, 2([4]) = ^2([3] + [l]) = ido(l,3,2) = (l,3,2); y2([5]) = ^2([4] + [l]) = (l,3,2)o(l,3,2) = (l,2,3); atd. Je vidět, že jádrem homomorfismu jsou prvky id, [3], [6], protože ty se zobrazí na neutrální prvek druhé grupy. hom 03: y?3([0]) =id, y?3([l]) =id, a nyní už