Algebra I Radan Kučera, jarní semestr 2014 Literatura, do které míří odkazy z textu: J. Rosický: Algebra, skriptum PřF MU, 4. vydání, Brno 2002 (nebo později), str. 7-102. Operace na množině, grupoid Definice. Nechť G je množina. Libovolné zobrazení G x G —> G se nazýva (binární) operace na množině G. Označení. Operace budeme značit symbolem • (případně +, o, • apod.), obraz dvojice [a, b] G G x G v operaci • symbolem a ■ b. Definice. Operace • na množině G se nazýva ► komutativní, jestliže Va, Í)é G: a ■ b = b ■ a; ► asociativní, jestliže Va, Ď, c G G: a ■ (b • c) = (a ■ b) ■ c. Definice. Množina G spolu s operací • na G se nazýva grupoid, označujeme jej (G,-), nebo jen G, bude-li z kontextu jasné, jakou operaci máme na mysli. Definice. Grupoid (G, ■) se nazývá ► komutativní, jestliže • je komutativní operace na G; ► asociativní (neboli pologrupa), jestliže • je asociativní operace na G. Neutrální prvek, inverzní prvky, grupa Definice. Nechť (G, •) je grupoid. Prvek e G G se nazývá neutrální prvek (neboli jednotkový prvek) tohoto grupoidu, jestliže Va G G: e ■ a = a ■ e = a. Věta. Každý grupoid má nejvýše jeden neutrální prvek, [věta 1.6, str. 8] Definice. Nechť (G,-) grupoid s neutrálním prvkem e a nechť je pevně dáno a G G. Prvek b G G se nazývá inverzním prvkem k prvku a (v grupoidu G), jestliže platí a ■ b = b ■ a = e. Věta. V libovolné pologrupě s neutrálním prvkem ke každému prvku existuje nejvýše jeden prvek inverzní, [věta 1.8, str. 8] Definice. Grupoid G se nazývá grupa, jestliže ► G je pologrupa (tj. asociativní grupoid), ► G má neutrální prvek, ► ke každému prvku a G G existuje v G prvek inverzní. Označení. V grupě (G, •) tedy ke každému prvku a G G existuje právě jeden prvek inverzní, značíme jej a-1. Definice. Je-li (G, •) grupa a je-li navíc operace • komutativní, hovoříme o komutativní grupě. Definice. Grupa (G, •) se nazývá triviální, má-li množina G jediný prvek, tj. G = {e}. (Tento jediný prvek e je pak nutně neutrální, neboť musí platit e • e = e.) Příklad. (Z,+), (Q,+), (M, +), (C, +) jsou komutativní grupy; (Q*, •), (K*, •), (C*, •) jsou komutativní grupy, kde Q* = Q - {0}, R* =M-{0}, C* =C-{0}. Příklad. Nechť R značí kteroukoli z číselných množin Z, Q, M, C, pak pro libovolné m, n g N definujeme Mn^m(R) jako množinu všech matic typu n x m s prvky z R. Pak (M„im(/?), +) je komutativní grupa (zde + značí sčítání matic). Naopak (Mn „(/?), •), kde • značí násobení matic, je pologrupa s neutrálním prvkem, ale grupa to není. Je-li R kterákoli z číselných množin Q, M, C, označme GL„(/?) množinu všech regulárních matic typu n x n s prvky z R (tj. matic s nenulovým determinantem). Pak (GL„(/?), •) je grupa, která není komutativní, je-li n > 2. Permutace Příklad. Nechť X je množina, symbolem X značíme množinu všech zobrazení X —> X, symbol o značí skládání zobrazení. Připomeňme, že pro f,g& Xx je definováno (f o g)(x) = f(g(x)) pro libovolné x e X. Pak (Xx,o) je pologrupa s neutrálním prvkem, ale grupa to není. Definice. Permutací na množině X rozumíme libovolnou bijekci X —> X. Množinu všech permutací na množině X značíme S(X). Pokud X = {1, 2,..., n}, píšeme místo S(X) stručně jen S„. Příklad. (S(X),o) je grupa, která není komutativní, má-li X alespoň tři prvky. Jak označovat prvky grupy §„' dvouřádkovou maticí orientovaným grafem anebo schématem 1 2 3 4 5 6 4 1 5 2 6 3 Definice. Nechť /'i,..., ik jsou různé prvky množiny {1,2,..., n}, přičemž k > 2. Permutaci z §„ takovou, že '1 '2, '2 '3, '3 ^ '4, přičemž pro všechny prvky a £ {1, 2,..., n}, a ^ {/'i,..., /^} platí 3H>3, nazýváme cyklem délky /c a značíme (/'i,..., /^). Cykly délky 2 se nazývají transpozice. Definice. Cykly (/'i,..., /^), ... ,jr) G §„ se nazývají nezávislé, jsou-li množiny ..., i^} a {ji,... ,jr} disjunktní (tj. mají-li prázdný průnik). Věta. Každou neidentickou permutaci f G S„ lze napsat jako složení několika nezávislých cyklů, a to jednoznačně až na jejich pořadí. [Věta 2.5, str. 12] Věta. Nechť n > 1, pak každou permutaci f £ S„ lze napsat jako složení několika transpozic. [věta 2.6. str. 12] Definice. Nechť f G Sn. Řekneme, že uspořádaná dvojice [/,_/'] je inverze permutace f, jestliže 1 < i < j < n a platí > f(J). Permutace f se nazývá sudá nebo lichá podle toho, má-li sudý nebo lichý počet inverzí. Paritu p(f) permutace f definujeme: -1 je-li f sudá, je-li f lichá. n-l n Poznámka. Platí i=lj=i+l Jak zjistit paritu permutace f G §n? Je-li f dána dvouřádkovou maticí, spočítáme, kolikrát ve spodním řádku „je menší číslo předběhnuto větším": / 1 2 3 4 5 6 \ V 4 1 5 2 6 3 ) 4>1, 4>2, 4>3, 5 > 2, 5 > 3, 6 > 3: šest inverzí - sudá permutace. Je-li f dána schématem spočítáme, kolikrát se protínají šipky: šest průsečíků - šest inverzí - sudá permutace. co parita permutace f G §n zapsané jako složení cyklů? Věta. Pro libovolné f,g£§n platí p(fog) = p(f). p(g). Jinými slovy: složením libovolných dvou permutací stejné parity dostaneme sudou permutaci, kdežto složením libovolných dvou permutací různé parity dostaneme lichou permutaci, [věta 2.9, str. 13] Důsledek. Složení sudého počtu transpozic je sudá permutace, složení lichého počtu transpozic je lichá permutace. [Každá transpozice je lichá permutace.] Důsledek. Cyklus liché délky je sudá permutace a cyklus sudé délky je lichá permutace. [Cyklus délky k lze psát jako složení k — 1 transpozic] Důsledek. Neidentická permutace je sudá, pravé když ve svém rozkladu na složení nezávislých cyklů má sudý počet cyklů sudé délky. Je tedy lichá, pravé když v tomto rozkladu má lichý počet cyklů sudé délky. (Na počtu cyklů liché délky nezáleží.) Další příklad grupy: grupa (B„,o) Příklad. Nechť n > 3 je přirozené číslo a představme si pravidelný n-úhelník. Označme D„ množinu všech shodností tohoto n-úhelníka, tedy zobrazení, která zachovávají délky úseček a kterými je náš n-úhelník zobrazen sám na sebe. Pak D„ má 2n prvků, z toho n rotací kolem středu n-úhelníka (včetně identity -rotace o nulový úhel) a n osových souměrností (vzhledem k osám procházejících středem n-úhelníka a také dvěma z vrcholů a středů stran). Snadno se ověří, že vzhledem ke skládání dostáváme nekomutativní grupu (D„,o). Každá shodnost permutuje množinu vrcholů n-úhelníka, přičemž různým shodnostem odpovídají různé permutace vrcholů. Proto, očíslujeme-li vrcholy n-úhelníka po řadě čísly 1, 2,..., n, lze každou shodnost n-úhelníka ztotožnit s prvkem grupy §„. Rotace jsou ztotožněny s mocninami cyklu (1,2,..., n), každá osová souměrnost je ztotožněna se složením několika nezávislých transpozic. Dělitelnost v Z Definice. Říkáme, že celé číslo b g Z je dělitelem celého čísla a g Z, píšeme b | a, existuje-li c g Z tak, že a = b ■ c. Věta (o dělení se zbytkem). Pro každé a g Z a m g N existuje jediná dvojice čísel q, r g Z takových, žea = m- q + ra současně 0 < r < m. [Věta 3.1, str. 14] Definice. Číslo q se nazývá (neúplný) podíl a číslo r zbytek po dělení čísla a číslem m. Definice. Společným dělitelem čísel a, fa g Z rozumíme každé číslo c g Z splňující c | a a současně c | fa. Je-li alespoň jedno z čísel a, fa nenulové, existuje jen konečně mnoho jejich společných dělitelů; největší z nich se nazývá největší společný dělitel čísel a, b, značíme jej (a, b). Jestliže naopak a = b = 0, je jejich největší společný dělitel definován jako nula, tj. (0, 0) = 0. Poznámka. Zřejmě platí (a, b) = (|a|, \b\) a (a, 0) = |a|, zaměříme se proto na největší společný dělitel přirozených čísel a, b. Euklidův algoritmus Pro daná a, b g N provádějme postupné dělení se zbytkem: a = b ■ q0 + r0 b = r0 ■ gi + ri ro = 1 • 92 + r2 ri = r2 • 93 + '3 07-3 = rn-2 ' 9n-l + O7-I 07-2 = O7-I ' 9n + 0? rn-i = rn ■ qn+i + 0 Přitom b > ro > r\ > r2 > ..., proto skutečně po několika děleních nastane rn+\ = 0. Věta. Pro libovolná a, b g N platí (a, b) = r„. [věta 3.2, str. 15] Věta (Bezoutova rovnost). Pro libovolná a, b g Z existují «,i/ěZ ŕa/c, že (a, fa) = u • a + v • fa. [věta 3.3, str. 16] Nejmenší společný násobek Definice. Společným násobkem čísel a, b g Z rozumíme každé číslo c g Z splňující a | c a současně b | c. Poznámka. Je-li a = 0 nebo b = 0, je jediným společným násobkem čísel a, fa číslo 0. V opačném případě existují kladné společné násobky, například |a-£>|. Definice. Jsou-li obě čísla a, b g Z nenulová, rozumíme nejmenším společným násobkem čísel a, b nejmenšího ze všech kladných společných násobků těchto čísel. Je-li alespoň jedno z čísel a, b nulové, definujeme nejmenší společný násobek čísel a, b jako nulu. Věta. Nechť a, b g Z, a 7^ 0 7^ fa. Pa/c nejmenším společným násobkem čísel a, b je číslo jj^ý- Pro libovolné číslo c g Z p/aŕv, ze c je společným násobkem čísel a, b, právě když c je dělitelné nejmenším společným násobkem čísel a, b. Poznámka. Druhá část předchozí věty platí i v případě, kdy je některé z čísel a, b nulové. Důkaz věty o nejmenším společném násobku Věta. Nechť a, b G Z, a ^ 0 7^ b. Pak nejmenším společným násobkem čísel a, b je číslo • Pro libovolné číslo c G Z platí, že c je společným násobkem čísel a, b, právě když c je dělitelné nejmenším společným násobkem čísel a, b. Důkaz. Zřejmě = ±^^y • 3 = ^JTE) ' ^ Je sP°'e^ný násobek čísel a, b. Bezoutova věta dává u, v G Z taková, že (a, fa) = u ■ a + v • b. Nechť c je libovolný společný násobek čísel a, b. Pak existují celá čísla x, y tak, že c = x • a = y • b. Proto (a, fa) • c = u • a • c + v • b ■ c = a ■ b ■ (u ■ y + v • x), a tedy c = • (u • y + v • x). Tedy c je dělitelné číslem jj^ý ■ Je-li navíc c > 0, plyne odtud, že c > i^-rl. Další důsledky Bezoutovy rovnosti Věta (Bezoutova rovnost). Pro libovolná a, b g Z existují u, v g Z tak, že (a, b) = u ■ a + v ■ b. Následující důsledek vysvětluje, proč jsme dodefinovali (0,0) = 0. Důsledek. Pro libovolná a, b,d g Z platí d | (a, fa) -4=>- c/ | a, c/ | b. Definice. Čísla a, b g Z se nazývají nesoudělná, jestliže (a, fa) = 1. Důsledek. Čísla a, fa g Z jsou nesoudělná, právě když existují u, v g Z ŕa/c, ze u • a + v • /> = 1. Důsledek. Pro libovolná a, b,c g Z p/ar/ a | fa • c, (a, fa) = 1 =>■ a | c. [Důsledek 3.5, str. 16] Definice. Přirozené číslo p > 1 se nazývá prvočíslo, jestliže jeho jediným dělitelem větším než 1 je p samotné. Důsledek. Pro libovolné prvočíslo p a libovolná b,c g Z platí p | b ■ c =>■ p j b nebo p | c. Věra (o jednoznačném rozkladu v Z). Libovolné celé číslo a > 1 je buď prvočíslo, nebo jej lze napsat jako součin několika prvočísel, a to jednoznačně až na pořadí činitelů, [věta 3.6, str. 16] Důsledek. Prvočísel je nekonečně mnoho. [Jsou-li pi, p2, ■ ■ ■ , pn všechna prvočísla, neexistuje prvočíslo, které by dělilo číslo 1 + p\P2 ■ ■ ■ Pn-] Důsledek. Čísla a, b g Z jsou nesoudělná, právě když neexistuje prvočíslo p dělící a I t). [Jsou-li a, b soudělná, nějaké prvočíslo musí dělit číslo (a, b) > 1.] Poznámka. Předchozí větu lze pro malá přirozená čísla užít k hledání největšího společného dělitele tak, že obě čísla rozložíme na součin prvočísel a zjistíme, která prvočísla se vyskytují v obou rozkladech. Obecně však nalézt rozklad na prvočinitele je mnohem obtížnější úkol než nalézt největšího společného dělitele. Celý systém bezpečné komunikace v současnosti je založen na tom, že neumíme rozložit přirozené číslo, které je součinem dvou velkých (řekněme 150-ciferných) prvočísel (výpočet, který by trval několik století, je z praktického hlediska pochopitelně bezcenný). Kongruence, zbytkové třídy Definice. Nechť m G N, a, b G Z. Říkáme, že a, b jsou kongruentní modulo m, a píšeme a = £> (mod m), jestliže m | a — b. Poznámka. Zřejmě a = b (mod m), právě když a, fa mají stejný zbytek po dělení číslem m. Definice. Nechť m G N. Pro libovolné a G Z definujeme množinu [a]m = {a + k ■ m; k G Z}, kterou nazýváme zbytková třída modulo m obsahující a. Poznámka. Množina [a]m = {a + k ■ m; k G Z} se skládá z právě těch celých čísel, která mají stejný zbytek po dělení číslem m jako číslo a. Věta. Pro libovolná a, b G Z, m G N nasŕaVa [a]m = [fa]m praVě tehdy, když a = b (mod m), [věta 3.8, str. 17] Označení. Množinu všech zbytkových tříd podle modulu m G N značíme Zm. Je tedy Zm = {[0]m,[l]m,[2]m,...,[m- l]m}. Operace na množině Zm Věta. Nechť m £ N, a, b, c, d £ Z jsou libovolná. Jestliže platí [a]m = [c]m, [b]m = [d]m, pak také [a + b]m = [c + d]m, [a ■ b]m = [c ■ d]m. [Věta 3.9, str. 18] Důsledek. Nechť m £ N. Vztahy [a]m + [b]m = [a + b]m, [a]m ■ [b]m = [a ■ b]m pro libovolná a, b £ Z definují operace + a ■ na množině Zm. Věta. Pro libovolné m £ N je (Zm, +) komutativní grupa s neutrálním prvkem [0]m, v níž inverzním prvkem k libovolné třídě [a]m je třída [—a]m. [věta 3.11, str. 19] Věta. Pro libovolné m £ N je (Zm, •) komutativní pologrupa s neutrálním prvkem [1] m. [Věta 3.12, str. 19] Poznámka. Jestliže m > 1, pro každé a £ Z platí [a]m ■ [0]m = [a ■ 0]m = [0]m ^ [l]m, a tedy (Zm, •) není grupa. Grupa (Z*,-) Věta. Nechť m 6 N, a £ Z jsou libovolná. Zbytková třída [á\m má inverzní prvek v pologrupě (Zm, •), právě když celá čísla a, m jsou nesoudělná. [v»a 3.13, str. 19] Označení. Pro libovolné m 6 N označme Z* množinu všech zbytkových tříd [a]m, které mají inverzní prvek v pologrupě (Zm, •), tedy Z* ={[a]m; ae Z, (a,m) = l}. Důsledek. Pro každé m £ N _/e (Z^,, •) komutativní grupa. Označení. Pro libovolné m £ N označme (p(m) počet všech přirozených čísel nepřevyšujících m, která jsou nesoudělná s m, tedy ip(m) = \{a g Z; 0 < a < m, (a, m) = 1}|. Důsledek. Pro libovolné m £ N p/aí/ |Z^,| = (f(m). Definice. Výše definované zobrazení ip : N —>■ N se nazývá Eulerova funkce. První věta o Eulerově funkci (f(m) = |Z* | Označení. Pro libovolné m G N označme tp(m) počet všech přirozených čísel nepřevyšujících m, která jsou nesoudělná s m, tedy ip(m) = \{a G Z; 0 < a < m, (a, m) = 1}|. Příklad. (l) = 1, y?(2) = 1, ip(3) = 2, y?(4) = 2, (5) = 4, ... Věra. Je-li p prvočíslo a n G N, pak (f(pn) = (p — 1) • p"-1. Důkaz. Čísla soudělná s p" jsou právě ta, která jsou dělitelná p. Z každých p po sobě jdoucích čísel je právě jedno dělitelné p. Proto je mezi čísly 1, 2,... ,p" právě ^- = p"_1 čísel, která jsou soudělná s p". Nesoudělných s p" je mezi nimi právě (f(pn) čísel. Je tedy ip{pn) = p" - p"-1 = (p - 1) • p""1. Druhá věta o Eulerově funkci (f(m) = |Z* | Věta. Jsou-li a, b G N nesoudělná přirozená čísla, pak ip{a- b) = ip{a)-ip{b). Důkaz. Protože (a, b) = 1, nejmenší společný násobek čísel a, b je a • b. Definujme zobrazení f : 7Lab —> Za x Z^, předpisem f([c]ab) = {[c]a, [c]b) pro libovolné c G Z. Je třeba ověřit korektnost této definice: pro libovolné c, d G Z platí [c]afa = Mab, právě když ab\ c - d. Protože ab je nejmenší společný násobek čísel a, fa, platí ab\ c — d a j c — d a b | c — c/. Celkem tedy [c]ab = [d]ab ^ ([c]a, [c]b) = ([c/]a, Ověřili jsme nejen korektnost definice f, ale i to, že f je injektivní. A protože množiny Za/, i Za x Z/, mají obě afa prvků, je f bijekce. Libovolné c G Z splňuje (c, afa) 7^ 1, právě když existuje prvočíslo p tak, že p j c a současně p | afa, tj. že p | c, p | a nebo p \ c, p \ b, tj. právě když (c, a) 7^ 1 nebo (c, fa) 7^ 1. Celkem tedy [c]ab G právě když f{[c]ab) G Za xZtx. Proto |Z*b| = |Z^| • |Z*|. Výpočet hodnot Eulerovy funkce (f (m) = |Z* | Příklad. Předpoklad o nesoudělnosti je v předchozí větě podstatný, platí třeba (2 • 2) = 2 ^ 1 = (2) • (2). Důsledek. Nechť m G N. Rozložme m na součin mocnin různých prvočísel, tj. m = Pi ■ Pi ■ ■ ■ Ps% /cc/e pi, p2, ..., ps jsou různá prvočísla, ei, ě2, ..., es G N. Pa/c p/aŕv ^(m) = (pi - 1) • pf-1 • (P2 - 1) • P?"1 • • • (Ps - 1) • Ps*-1, coz je možné zapsat také takto: 1. Pak výsledek součinu prvků a\,...,an (v tomto pořadí) nezáleží na jejich uzávorkování, [věta 4.1, str. 23] Věta. Nechť (G, •) je komutativní pologrupa, a\,..., an £ G, přičemž n > 1. Pak výsledek součinu prvků a\,...,an nezáleží na jejich pořadí. [v»a 4.2, str. 24] Definice. Nechť (G, •) je pologrupa, a 6 G, n 6 N. Mocninu a" prvku a v pologrupě G definujeme jako součin n exemplářů prvku a: n (podle výše uvedené věty není nutné specifikovat uzávorkování). Věta. Nechť (G, •) je pologrupa, a G G, m, n G N. Pak platí -.m _n _ ~,m+n í ~,m\n _ _mn „,„ „ , a -a — a, ^a j — a . [věta 4.4. str. 24] Invertibilní prvky Označení. Nechť (G, •) je grupoid s neutrálním prvkem. Víme, že tento neutrální prvek je v G jediný. Budeme jej označovat symbolem 1 (přestože to nemusí být přirozené číslo 1). Definice. Nechť (G, •) je pologrupa s neutrálním prvkem 1. Pokud k nějakému a g G existuje v G prvek inverzní, říkáme, že prvek a je invertibilní. Inverzní prvek k prvku a budeme označovat symbolem a-1. Věta. Nechť (G, •) je pologrupa s neutrálním prvkem 1, a, 3i,..., an libovolné invertibilní prvky z G. Pak platí l-1 = 1, (a-1)"1 = 3, (Sl • . . . • 3„) 1 = an 1 • ... • 3j [Věta 4.6. str. 24] Veŕs (zákony o krácení). Nechť G je grupa, a, b,c g G. Ps/c p/aŕ/ a • b = a ■ c =>■ b = c, b • a = C • a b = C. [Věta 4.17. str. 27] Množina všech invertibilních prvků pologrupy, mocnina v grupě Věta. Nechť (G, •) je pologrupa s neutrálním prvkem 1, H množina všech invertibilních prvků z G. Pak (H, •) je grupa, [věta 4.7, str. 25] Poznámka. Operace • na množině H je zúžením původní operace na množině G (má stejný předpis, aleje definována na menším definičním oboru H x H a má menší obor hodnot H). Poznámka. Předchozí větu jsme už několikrát použili: na pologrupách čtvercových matic (Mn^n(R), •), zobrazení (Xx,o) a zbytkových tříd (Zm, •)■ Vznikly grupy GLn(R), S(X) a Z*. Definice. Nechť (G, •) je grupa s neutrálním prvkem 1, a G G. Mocninu a" prvku a v grupě G definujeme i pro nekladný celočíselný exponent: a° = 1, a~" = (a")-1 pro libovolné n G N. Vera. Nechť (G, •) je grupa, a G G, m, n G Z. Pa/c p/aŕ/ a -a — a, ya ) — a . [věta 4.9. str. 25] Věta. Nechť (G, •) je komutativní grupa, a, b G G, m G Z. Pa/c p/aŕ/ (a • Ď)m = am ■ bm. [věta 4.10. str. 26] Řád prvku v grupě Definice. Nechť G je grupa, a G G. Existuje-li přirozené číslo n tak, že a" = 1, pak nej menší přirozené číslo n s touto vlastností se nazývá řád prvku a v grupě G. Neexistuje-li žádné přirozené číslo n s touto vlastností, říkáme, že řád prvku a v grupě G je oo. Věta. Nechť G je grupa, a G G. Je-li řád prvku a v grupě G přirozené číslo n, pak pro libovolná k, I G Z platí ak = a1 <í=^> k = I (mod n). [věta 4.13 (i) a (2), str. 26] Je-li naopak řád prvku a v grupě G roven 00, pak pro libovolná k,l G Z platí k I 11 a = a <í==^ k = I. [Věta 4.13 (3). str. 26] Důsledek. Nechť řád prvku a v grupě G je n G N. Nechť r je zbytek po dělení čísla k G Z číslem n, pak ak = ar. Prvky a° = 1, a1 = a, a2, ..., a"-1 jsou po dvou různé. Důsledek. Řád prvku a v grupě G tedy udává, kolik existuje různých mocnin prvku a. V konečné grupě má každý prvek konečný řád. Důsledky věty Věta. Nechť G je grupa, a £ G. Je-li řád prvku a v grupě G přirozené číslo n, pak pro libovolná k, I £ Z platí ak = a1 m, spor. Příklad. Exponent grupy §3 je 6, přitom v §3 prvek řádu 6 není. Předpoklad, že G je komutativní, je v předchozí větě nutný. Podgrupa grupy Definice. Nechť (G, •) je grupa, H podmnožina množiny G. Řekneme, že H je podgrupa grupy G, a píšeme H < G, jestliže ► neutrální prvek 1 G H, ► pro každé a G H platí a-1 G H, ► pro každé a, Ď G H platí a • Ď G H. Poznámka. Nejvétší podgrupou grupy G (vzhledem k C) je celá G, nejmenší podgrupou je {1}. Věta. Nechť H je podgrupa grupy (G, •). Pak ■ určuje operaci na množině H, přičemž H je grupa vzhledem k této operaci. Je-li grupa G komutativní, pak je i grupa H komutativní, [věta 5.3, str. 29] Označení. Zmiňovanou operaci na podgrupé budeme označovat stejným symbolem jako původní operaci na celé grupě, přestože tyto operace nejsou stejné. Věta. Jestliže H je podgrupa grupy G a K je podgrupa grupy H, pak je K také podgrupou grupy G. rro je zřejmé.] Podgrupa grupy generovaná podmnožinou grupy Věta. Nechť G je grupa, I neprázdna množina taková, že pro každé i G / je dána podgrupa H, grupy G. Pak průnik P|(g/ H, všech těchto podgrup je opět podgrupou grupy G. [věta 5.5, str. 29] Definice. Nechť M je podmnožina grupy G. Symbolem (M) označíme průnik všech podgrup grupy G, jejichž podmnožinou je množina M. Podle předchozí věty je (M) podgrupou grupy G obsahující množinu M; evidentně je nejmenší s touto vlastností. Podgrupu (M) nazývame podgrupa generovaná množinou M, množinu M nazývame množina generátorů podgrupy (M). Označení. Je-1i M = {a\,..., an}, lze psát stručně (ai,..., a„) místo (M). Poznámka. Zřejmě (G) = G, (0) = {1}. Pro každou M C G platí (M) = (M U {a"1; a G M}). Podgrupa grupy generovaná podmnožinou grupy Věta. Nechť M je podmnožina grupy (G, •) taková, že M 7^ 0 a že pro každé a G M je také a-1 G M. Pak platí (M) = {a1- ... ■ an; n e N, si,..., a„ e M}. Důkaz. Označme X = {si • ... • a„; n G N, ai,..., an G M}. Jistě M C X (volbou n = 1). Protože M/fl, existuje Ď G M, pak i b^1 G M a 1 = b ■ b^1 G X. Pro libovolné c = ai • ... • an G X je c-1 = a^1 • ... • a-f1 G X. Protože součin n prvků z M vynásobený součinem m prvků z M je součinem n + m prvků z M, je X uzavřeno na operaci •. Je tedy X podgrupa grupy G. Naopak libovolná podgrupa Y grupy G obsahující M obsahuje také libovolný součin prvků z M, proto X C Y. Je tedy X nejmenší podgrupa grupy G obsahující M, tj. X = (M). Cyklické grupy Důsledek. Nechť (G,-) je grupa, a G G. Pak platí = {é?m| m G [Stačí užít větu pro M= {a,a~1} spolu s (a) = (a, a-1).] Důsledek. Nechť (G, •) je grupa, a G G je prvek řádu n G N U {oo}. Pak počet prvků podgrupy (a) generované prvkem a je roven n. [Víme, že řád prvku a v grupě G udává, kolik existuje různých mocnin prvku a. ] Definice. Grupa G se nazýva cyklická, existuje-li a G G tak, že G = (a). Příklad. Grupy (Z, +) i (Zm, +) pro libovolné m G N jsou cyklické. Definice. Řádem konečné grupy (G, •) rozumíme počet prvků této grupy, značíme |G|. Důsledek. Řád konečné cyklické grupy je roven řádu jejího generátoru. Konečná grupa řádu n je cyklická, právě když obsahuje prvek řádu n. [Obsahuje-li konečná grupa řádu n prvek a řadu n, má podgrupa (a) stejný počet prvků jako G, tedy (a) = G.] Důsledek. Nechť H, K jsou podgrupy komutativní grupy (G, •). Pak platí {HU K) = {h- k; h G H, k G K}. [Důsledek 5.9. str. 30] Homomorfismus grup Definice. Nechť (Gi, •) a (G2, *) jsou grupy, f : G\ —> G2 zobrazení. Řekneme, že f je homomorfismus grupy (Gi, •) do grupy (G2, *), jestliže pro každé a, fa G Gi platí f (a ■ b) = f (a) * f(b). I njektivní homomorfismus se nazývá vnoření, bijektivnímu homomorfismu říkáme izomorfismus. Poznámka. Nepřesně řečeno: homomorfismus je zobrazení mezi grupami, u kterého dostaneme totéž, ať už „napřed počítáme a pak zobrazujeme" anebo „napřed zobrazujeme a pak počítáme". Příklad. Pro libovolné m G N je zobrazení parita p : Sm —> {1, —1} homomorfismus grupy permutací (Sm, o) do grupy ({1, —1}, •), neboť pro libovolné permutace f,g G Sm platí p{f 0 g) = p{f) ' P{g)- V případě m = 2 jde o izomorfismus. Příklad. Zobrazení logaritmus log : M+ —> M je homomorfismus multiplikativní grupy všech kladných reálných čísel do aditivní grupy všech reálných čísel (M, +), neboť pro libovolná kladná reálná čísla a, b platí log(a • b) = (log a) + (log b). Protože je toto zobrazení bijekce, jde o izomorfismus. Homomorfismus grup Definice. Nechť (Gi, •) a (G2, *) jsou grupy. Zobrazení f : G\ —> G2 se nazývá homomorfismus, jestliže pro každé a, b G Gi platí f (a • b) = f (a) * ^(b). Vnoření je injektivní homomorfismus, izomorfismus je bijektivní homomorfismus. Příklad. Pro libovolné m G N je determinant det : GLm(M) ->• R* homomorfismus grupy regulárních matic typu m x m s reálnými prvky (GLm(M), •) do grupy nenulových reálných čísel (M*, •). Pro libovolné matice A, B G GLm(M) totiž podle Cauchyovy věty platí det(/4 • B) = det(A) • det(B). V případě m = 1 jde o izomorfismus. Věta. Jsou-li Gi, G2, G3 grupy, f : G\ —> G2 a g : G2 —> G3 homomorfismy pak je g o f : Gi —>■ G3 homomorfismus. [věta 8.3. str.«] Vera. Nechť f : G\ —> G2 je homomorfismus grup. Pak f(l) = 1 a pro /cazc/e a G Gi p/aŕv ^(a-1) = f{a)~1. [Věta 8.4. str. 41] Věta. Nechť f : G\ —> G2 je izomorfismus grup. Pak i inverzní zobrazení f^1 : G2 —?► Gi je izomorfismus grup. [věta 6.3. str. 33] Homomorfismus grup, jeho jádro Věta. Nechť f : G\ —> G2 je homomorfismus grup, a G G\ prvek řádu n G N. Pak řád prvku f (a) v grupě G2 je k G N a platí k | n. [Jestliže a" = 1, pak (f(a))n = f(a") = f(l) = 1, a proto řád k prvku f(a) je dělitelem čísla n.] Věta. Nechť f : G\ —> G2 je homomorfismus grup. Pak obraz f(G\) = {f{a)\ a G Gi} grupy G\ je podgrupou grupy G2. [věta 8.5, str. 42] Věta. Nechť f : G\ —> G2 je homomorfismus grup, H podgrupa grupy G2. Pak úplný vzor f~1(H) = {a G G\\ f (a) G H} podgrupy H je podgrupou grupy G\. [věta 8.9. str. 42] Definice. Nechť f : G\ —> G2 je homomorfismus grup. Množina ker f = {a G G\\ f (a) = 1} se nazýva jádro homomorfismu f. Důsledek. Je-li f : G\ —> G2 je homomorfismus grup, pak jeho jádro ker f je podgrupa grupy G\. Věta. Homomorfismus grup f : G\ —> G2 je injektivní, právě když ker f = {1}. [Věta 8.11, str. 43] Příklad. Popište všechny homomorfismy §3 —> Z4 a jejich jádra. V grupě S3 má neutrální prvek id řád 1, transpozice (1,2), (1,3) a (2,3) řád 2 a cykly (1,2,3) a (1,3,2) řád 3. V grupě Z4 má neutrální prvek [0)4 řád 1, prvek [2)4 řád 2, prvky [1)4 a [3)4 řád 4. Protože v Z4 není prvek řádu 3, v každém homomorfismu f : S3 —> Z4 se každá z permutací (1, 2, 3) a (1, 3, 2) zobrazí na [0)4. Permutace (1,2) se může zobrazit jen na prvek řádu 1 nebo 2, tj. na [0]4 nebo [2]4. Protože (1, 2) o (1, 2, 3) = (2, 3) a (1,2, 3) o (1,2) = (1,3), platí f ((2,3)) = f((l,2)) + f((l,2,3)) = f((l,2)) + [0]4 = f ((1,2)), f ((1,3)) = f((l,2,3)) + f((l,2)) = [0]4 + f((l,2)) = f ((1,2)). Máme tedy dvě možnosti, jak definovat f: v prvním případě se každý prvek grupy §3 zobrazí na [0)4, zřejmě to je homomorfismus a jeho jádro je §3. Ve druhém případě se každá transpozice zobrazí na [2)4 a ostatní prvky na [0)4. Protože liché permutace jsou zobrazeny na [2)4 a sudé permutace na [0)4, jde také o homomorfismus, jeho jádro je množina {id, (1, 2, 3), (1, 3, 2)}. Izomorfní grupy Definice. Řekneme, že grupy G\ a G2 jsou izomorfní, a píšeme G\ = G2, jestliže existuje alespoň jeden izomorfismus f : G\ —> G2. Příklad. Grupy •) a (M,+) jsou izomorfní, neboť logaritmus log : M+ —> M je izomorfismus. Věta. Jsou-li G\, G2, G3 grupy. Pak platí ► Gi = d, ► G\ = G2 )' G2 — G\, ► Gi = G2, G2 = G3 ^=^> Gi = G3. [Identita na množině G\ je izomorfismus. Inverzní zobrazení k izomorfismu je izomorfismus. Složení dvou izomorfismu je izomorfismus.] Věta. Libovolná nekonečná cyklická grupa je izomorfní s grupou (Z, +). Libovolná konečná cyklická grupa řádu n je izomorfní S grUpOU (Z„, +). [Věta 6.6, str. 34] Levé třídy rozkladu grupy podle podgrupy Definice. Nechť (G, •) je grupa, H její podgrupa. Pro libovolný prvek a G G definujeme jím určenou levou třídu a • H rozkladu grupy G podle podgrupy H předpisem a • H = {a ■ h; h G H}. Poznámka. Podle definice je levá třída a • H podmnožinou grupy G, je to množina všech součinů pevně zvoleného prvku a postupně se všemi prvky h G H. Věta. Nechť (G, •) je grupa, H její podgrupa, a, b G G libovolné. Následující podmínky jsou ekvivalentní: ► a- H = b-H, ► a G b- H, ► b'1 • a G H. [Věta 7.2, str. 37] Označení. Označme G/H množinu všech levých tříd grupy G podle podgrupy H, tj. G/H = {a • H; a G G}. Rozklad grupy podle podgrupy Příklad. Pro libovolné m G N tvoří množina H všech celých čísel dělitelných číslem m podgrupu grupy (Z, +) a platí Z/H = Zm. [Platí H = {mk; k S Z} a pro každé ä e ZJE ä + H = {a+m/r; ( E í) = [a]m.] Pŕ/Tc/aď. Pro G = S3 a H = {id, (1, 2)} je id oH = H, (l,3)oH = {(l,3)oid, (l,3)o(l,2)} = {(1,3), (1,2,3)} a (2, 3) o H = {(2, 3) o id, (2, 3) o (1, 2)} = {(2, 3), (1, 3, 2)}, a tedy G/H={H, {(1,3), (1,2,3)}, {(2,3), (1,3,2)}}. Poznámka. Připomeňme, že rozkladem na množině M rozumíme systém neprázdných podmnožin množiny M, jejichž sjednocení je rovno celé množině M a které jsou po dvou disjunktní. Věta. Množina G/H všech levých tříd grupy G podle podgrupy H tvoří rozklad na množině G. [věta 7.2, str. 37] Definice. Počet \G/H\ všech levých tříd grupy G podle podgrupy H se nazývá index podgrupy H v grupě G. Věta. Nechť (G, •) je konečná grupa, H jejípodgrupa. Pak platí \G\ = \ G / H\ • |H|. [Věta 7.6. str. 38] Lagrangeova věta a její důsledky Věta. Nechť (G, •) je konečná grupa, H jejípodgrupa. Pak platí \G\ = \G/H\ ■ \H\. Důsledek (Lagrangeova věta). Řád libovolné podgrupy konečné grupy G je dělitelem řádu grupy G. Důsledek. Rád libovolného prvku konečné grupy G je dělitelem řádu grupy G. [Řád libovolného a e G je roven řádu podgrupy (a), kterou generuje.] Důsledek. Libovolná grupa prvočíselného řádu je cyklická. [Důsledek 7.9, str. 39] Důsledek. Nechť G je konečná grupa řádu n = | G\. Pak pro libovolný prvek a G G platí an = 1. Jinými slovy: exponent konečné grupy G je dělitelem řádu grupy G. Speciálním případem předchozího důsledku je následující věta z teorie čísel: Věta (Eulerova). Nechť m G N, a G Z jsou libovolná nesoudělná čísla. Pak platí a^m^ = 1 (mod m). [věta 7.11. str. 39] Naivní pokus o zavedení operace na rozkladu G/H Inspirace. Zvolme pevně libovolné m G N a jako dříve označme H = [0]m = {mk; k G Z}. Pak H je podgrupa grupy (Z, +) a odpovídajícím rozkladem je Z//7 = Zm. Na Zm jsme definovali operaci + pomocí reprezentantů: pro libovolné a G Z je totiž a + H = [a]m a použitou definici sčítání zbytkových tříd [a]m + [b]m = [a + b]m pro libovolná a, b G Z lze psát ve tvaru {a + H) + {b + H) = {a + b) + H. Pokus o zobecnění. Nechť (G, •) je grupa a H její podgrupa. Pak bychom na rozkladu G/H rádi zavedli operaci • předpisem (a • H) ■ (b ■ H) = (a • b) ■ H pro libovolná a, b G G. Je to ale vždy možné? Příklad. Pro G = §3 a H = {id, (1, 2)} je id oH = (1, 2) o H = H, (1,3)oH = (1,2,3)oH = {(1,3), (1,2,3)} a (2, 3) o H = (1, 3, 2) o H = {(2, 3), (1, 3, 2)}, a tedy předchozí definice pomocí reprezentantů by dala (1, 3, 2) o H = ((1, 2) o H) o ((1, 3) o H) = (id oH) o ((1, 3) o H) (1,3) o /7, což však není pravda. Normální podgrupy Úvaha. Nechť (G, •) je grupa a H její podgrupa. Pro libovolné h G H platí h ■ H = 1 • H, a tedy pro každé a G G musí operace • na G/H splňovat (h ■ H) ■ (a"1 • H) = (1 • H) ■ (a"1 • H). Abychom mohli zavést operaci pomocí reprezentantů, muselo by platit (h ■ a'1) ■ H = a 1 ■ H, neboli a ■ h ■ a-1 G H. Definice. Nechť (G, •) je grupa a H její podgrupa. Řekneme, že H je normální podgrupou grupy G, jestliže pro každé h G H a každé a G G platí a ■ h ■ a-1 G H. Příklad. V každé grupě G jsou {1} i G normální podgrupy. Podgrupa H = {id, (1,2)} není normální podgrupou grupy §3. Věta. V komutativní grupě G je každá podgrupa normální. Věta. Je-li f : G —» K homomorfismus grup, pak jeho jádro ker f je normální podgrupa grupy G. [víme, že ker f je podgrupa. Je-li h G ker f, tj. f(h) = 1, pak pro každé a G G je f (a ■ h ■ a-1) = f(a) ■ f(h) ■ /"(a)-1 = 1, proto a ■ h ■ a-1 G ker f'.] Normální podgrupy - přehledné zopakování Nechť (G, •) je grupa, H její podgrupa. Každý prvek a G G určuje svou levou třídu a • H = {a ■ h; h G H}. Přitom Va, b G G : (a • H = b ■ H a G b ■ H b'1 ■ a G H). Rozklad grupy G podle podgrupy H je množina všech levých tříd G/H = {a-H; a G G}. Pokud má být možné na rozkladu G j H zavést operaci pomocí reprezentantů, tj. pro libovolné a, b G G definovat součin levých tříd a • H a, b • H předpisem (a • H) • (b ■ H) = (a • b) ■ H, pak musí podgrupa H být normální podgrupa grupy G, tj. pro každé h G H a každé a G G musí platit a • h • a-1 G H. Ukážeme si, že pokud H je normální podgrupa grupy G, pak tímto předpisem operace na rozkladu G/H skutečně vznikne. Dokonce platí, že G/H s touto operací tvoří grupu. Faktorgrupa Věta. Nechť (G, •) je grupa a H její normální podgrupa. Pak na rozkladu G/H lze zavést operaci ■ takto: pro libovolné a, b G G definujeme předpisem (a • H) ■ (b ■ H) = (a • b) ■ H součin levých tříd a • H a b • H. Navíc platí: (G/H,-) je grupa, [věta 9.4, str. 46] Definice. Nechť (G, •) je grupa a H její normální podgrupa. Grupa G/Hz předchozí věty se nazývá faktorová grupa grupy G podle (normální) podgrupy H, zkráceně faktorgrupa. Věta. Nechť (G, •) je grupa a H její normální podgrupa. Zobrazení 7T : G —» G/H dané předpisem 7r(a) = a ■ H pro libovolné a G G (tedy každý prvek grupy G je zobrazen na třídu, do níž patří) je surjektivní homomorfismus grup, jehož jádro ker tt = H. [věta 9.5, str. 46] Definice. Toto tt se nazývá projekce grupy G na faktorgrupu G/H. Důsledek. Normální podgrupy grupy G jsou právě jádra homomorfismů G —^ K grupy G do vhodných grup K. Věta. Nechť (G, •) je komutativní grupa, pak je každá podgrupa H grupy G normální a faktorgrupa G/H je komutativní, [věta 9.8, str. 47] Rozklad grupy podle jádra homomorfismu Věta. Nechť f : G —» K je homomorfismus grup, ker f jeho jádro. Pak pro libovolné a, b G G platí f (a) = f (b), právě když a-1 • b G ker f, tj. právě když a • (ker f) = b- (ker f). Důkaz. Víme, že pro libovolnou podgrupu H grupy G platí a-1 ■ b G H a- H = b- H, proto to platí i pro H = ker f. Jestliže platí f [a) = f(b), pak ^(a-1 • Ď) = f {a-1) ■ f {b) = f{a'1) ■ f {a) = f (a'1 ■ a) = f(l) = 1, a tedy a-1 • b G ker f. Jestliže naopak platí a-1 • Ď G ker f, pak f{a^1 • b) = 1, proto f(a) = f (a) ■ 1 = f {a) ■ f^-1 ■ b) = f (a ■ a"1 • b) = f (b). Úvaha Předpokládejme, že je dán homomorfismus grup f : G —» K. Navíc mějme dánu normální podgrupu H grupy G. Pak máme faktorgrupu G/H a projekci tt : G —» G/H. Chceme vědět, jestli existuje zobrazení f : G/H —» K splňující f o 7T = f. To můžeme znázornit diagramem takto: G---s- K y f G/H Pro každý prvek h G H platí vr (/j) = h • H = 1 • H = vr(l). Pokud takové f existuje, musí pro každý prvek h G H platit f (h) = (7 o ttX/0 = 7(tt(/i)) = 7(tt(1)) = (7 o ttXI) = f (1) = 1, a tedy h G ker f. Pokud tedy není splněna podmínka H C ker f, nemůže takové f existovat. Ale stačí tato podmínka, aby byla existence f zaručena? Hlavní věta o faktorových grupách Věta (Hlavní věta o faktorových grupách). Nechť f : G —» K je homomorfismus grup, H normální podgrupa grupy G splňující H C ker f. Nechť tt : G —» G/H je projekce grupy G na faktorgrupu G/H. Pak existuje, a to jediné, zobrazení 7: G/H^K splňující 7 o tt = f. G---*K Navíc platí: ► f je homomorfismus grup, ► f je injekce, právě když H = ker f, ► f je surjekce, právě když f je surjekce. Důkaz. Libovolný prvek G/H je tvaru a ■ H = ir(a) pro vhodné a G G. Pak pro libovolné zobrazení f : G/H —» K splňující foir = f musí platit 7 (a ■ H) = 7{n{a)) = (7 o vr)(a) = f (a). Jediná možnost, jak definovat f, je předpisem f [a • H) = f (a). Ale a- H = b- H a-1 ■ b e H a'1 ■ b G ker f f{a) = f (b). Odtud nejen korektnost definice f, ale také H = ker f 44> f injekce. Dále {f(a ■ H); a G G} = {f(a); a G G}, tj. f surjekce <=)> f surjekce. Rozklad grupy podle jádra homomorfismu podruhé Důsledek. Je-li f : G —» K surjektivní homomorfismus grup, pak platí G/(ker f) 2é K. Důsledek. Je-li f : G —» K homomorfismus grup, pak platí G/(ker f) 2é f (G), kde f (G) = {f (a); a G G} c K je obraz G. Příklad. Pro libovolnou grupu G je id : G —» G homomorfismus s jádrem ker id = {1}, proto G/{1} = G. Přitom G/{1} = {{a}; a G G} a v tomto izomorfismu {a} i-> a. Příklad. Zobrazení sgn : R* —> {1, —1}, které zobrazí kladná čísla na 1 a záporná na —1, je homomorfismus. Platí ker sgn = R+, proto R*/R+ = {R+,R-} = {1,-1}, přičemž R+ ^ 1, R- ^ -1. Příklad. Zobrazení abs : R* —> R*, určené předpisem abs(x) = |x| pro každé x G R*, je homorfismus grupy (R*, •) do sebe s jádrem ker abs = {1, —1} a obrazem abs(M*) = R+, proto faktorgrupa (M*/{1, -1}, •) 2á (M+, •)■ Zde třída {a, -a} >-> |a|. Další příklady Příklad. Nechť n G N, n > 1. Zobrazení parity p : §„ —> {1, —1} je surjektivní homomorfismus grup, jehož jádrem je normální podgrupa všech sudých permutací A„ = kerp, proto faktorgrupa (Sn/A„,o)^({l,-l},.). Příklad. Zobrazení f : M —> C* s předpisem f (x) = cos x + /' si n x je homomorfismus grupy (M,+) do grupy (C*, •), neboť platí cos(x + y) + /sin(x + y) = (cosx + /sinx) • (cosy + / siny) pro libovolné x, y G M. Jádrem je podgrupa ker f = {2/c7r; k G Z} všech celočíselných násobku 2tt. Obrazem f(M) = {cosx + /sinx; x G M} = {a G C; |a| = 1} je podgrupa všech komplexních čísel s absolutní hodnotou 1. Proto (M/{2/c7r; k G Z}, +) ^ ({a G C; |a| = 1}, •)■ Příklad. Zobrazení abs : C* —> W, určené předpisem abs(x) = |x| pro každé x G C*, je homorfismus grupy (C*, •) do grupy (M*, •) s jádrem ker abs = {a G C; |a| = 1} a obrazem abs(C*)=M+, proto faktorgrupa (C*/{a G C; |a| = 1}, •) ^ •). Součin grup Věta. Nechť (Gi, •) a (G2, •) jsou grupy. Definujme na kartézském součinu Gi x G2 novou operaci ■ po složkách, tj. definujeme (gi, £2) • {hi, h2) = (gi ■ h1,g2- h2) pro libovolné gi, hx G Gx a g2, h2 G G2. Pak (Gi x G2, •) je grupa, [věta 6.7, str. 35] Definice. Výše popsaná grupa (Gi x G2, •) se nazývá součin grup (Gi,-) a (G2,-). Zobrazení Pi : Gi x G2 —> Gi a P2 : Gi x G2 —> G2 určená předpisy p1((a,b)) = a, p2{{a,b)) = b pro libovolné (a, b) G Gi x G2 se nazývají projekce (ze součinu). Věta. Nechť (Gi x G2, •) je součin grup (Gi, •) a (G2, •). Pak obě projekce p\ a p2 jsou surjektivní homomorfismy. [věta 8.12. str. 43] Cayleyho věta Věta. Nechť (G, •) je grupa, zvolme libovolně a G G. Pak zobrazení ra : G —> G, určené předpisem ra(g) = a ■ g pro každé g G G, je bijekce, tedy ra G 8(G). [věta 4.i8, str. 28] Věta. Nechť (G, •) je grupa. Libovolnému prvku a G G přiřaďme bijekci ra z předchozí věty. Vznikne tak zobrazení r : G —> §(G) s předpisem r(a) = ra pro každé a G G. Pak platí: r je injektivní homomorfismus grup. [věta 8.13. str. 43] Důsledek (Cayleyho věta). Každá grupa G je izomorfní s vhodnou podgrupou grupy permutacíS(G). Každá konečná grupa řádu n je izomorfní s vhodnou podgrupou grupy § p. [Věta 8.14, str. 43] Poznámka. V předchozí větě jsme každý prvek a grupy (G, •) reprezentovali permutací ra nosné množiny G. Tuto situaci lze zobecnit, můžeme prvky grupy (G,-) reprezentovat permutacemi nějaké jiné množiny X, kterou můžeme libovolně zvolit. Budeme tedy studovat homomorfismy G —> S(X). Této situaci říkáme reprezentace grupy G permutacemi na množině X anebo stručně akce grupy G na množině X. Akce grupy G na množině X Definice. Nechť G je grupa, X množina a ip : G —> S(X) je homomorfismus grup. Pro libovolné a G G je tp(a) G §(X), je tedy tp(a) : X —> X bijekce. V bijekci tp(a) máme pro každý prvek y G X dán jeho obraz tp(a)(y) G X. Pro libovolné y G X se množina Sy = {a G G; tp(a)(y) = y} nazývá stabilizátor prvku y, množina Oy = { S(X), určující pro libovolný prvek y G X stabilizátor Sy = {a G G; (p(a)(y) = y} a orbitu Oy = { 8(X), určující pro libovolný prvek y G X stabilizátor Sy = {a G G; (p(a)(y) = y} a orbitu Oy = {ip(a)(y); a G G}. Věta (Burnsidovo lemma). Nechť je navíc G konečná grupa a X konečná množina. Pro libovolné a G G nechť Fa je množina fixních bodů permutace tp(a), tedy Fa = {y G X; tp(a)(y) = y} Pak pro počet orbit platí m = ^ J2aeG \^a\- Důkaz. Nechť v každé orbitě leží právě jeden z prvků yi,... ,yr, J2\Fa\ = |{(a,y)GGxX; íp(a)(y)=y}\ = J2\S) y\ — m m G m E E /=1 yeOYi E E isri = E E G/S, i=l yeOyi i=l yeOyj Príklad užití Burnsidova lemmatu v kombinatorice Příklad. Máme stejné korálky n různých barev. Děláme dětské náramky tak, že navlečeme 7 korálků na šňůrku a zavážeme. Kolik různých náramků lze takto vytvořit (poloha uzlíku nerozhoduje)? Řešení. Pro n = 1 je jediný, pro n = 2 lze promyslet, že jich je 18. Ale pro n > 2 už naivní metodou nakreslení všech možností neuspějeme. Užijme Burnsidovo lemma, kde X je množina všech obarvení vrcholů pravidelného ľúhelníka n barvami. Pak |X| = n7, každé obarvení určí náramek, ale různá obarvení mohou dát týž náramek. Abychom zjistili, která obarvení dávají stejný náramek, užijme grupu D7 všech symetrií pravidelného ľúhelníka a definujme tp : D7 —> S(X) takto: pro symetrii a G D7 a obarvení y G X je (p(a)(y) to obarvení, které z y vznikne, aplikujeme-li na ľúhelník symetrii a. Pak dvě obarvení z množiny X odpovídají témuž náramku, právě když patří do stejné orbity. Pro identitu id je l^id I = |X| = n7, pro libovolnou ze 6 zbylých rotací r G D7 je \Fr\ = n a pro každou ze 7 osových souměrností s je \FS\ = nA. Podle Burnsidova lemmatu je hledaný počet j^(n7 + lnA + 6n). Vnitřní izomorfismy grupy G Věta. Nechť (G, •) je grupa. Pro libovolné a G G definujme zobrazenípa : G —> G předpisem pa(g) = a ■ g • a-1 pro každé g G G. Pak pro každé a, b G G je pa o pb = pab. Navíc je pa izomorfismus a platí p^1 = pa-i. Důkaz. Pro libovolné a,b,g G G platí (pa o pt,)(g) = pa{pb{g)) = Pa(b ■ g ■ b-1) = a-b-g-b-1-a-1 = (a-b)-g-(a-b)'1 = pab(g). Zřejmě pi(g) = 1 • g ■ l"1 = g = id(g), a tedy px = id. Odtud plyne, že pa o pa-i = id a pa-i o pa = id, tedy pa je bijekce a platí p"1 = pa-i. Konečně pro libovolné a,g, h G G platí PÁS) ■ Pa{h) = a ■ g ■ a'1 ■ a ■ h ■ a'1 = a ■ g ■ h ■ a'1 = pa(g ■ h), je tedy pa homomorfismus. Definice. Izomorfismy z předchozí věty nazýváme vnitřní izomorfismy grupy G. Akce grupy G na množině G vnitřními izomorfismy Definice. Nechť (G, •) je grupa. Jejím centrem Z(G) rozumíme množinu všech prvků, které komutují s každým prvkem grupy G, tj. Z(G) = {aG G; G G : a ■ g = g ■ a}. Věta. Nechť (G, •) je grupa. Libovolnému prvku a G G přiřaďme vnitřní izomorfismus pa z předchozí věty. Vznikne tak zobrazení p : G —» S(G) s předpisem p(a) = pa pro každé a G G. Pa/c p/aŕ/: p je homomorfismus grup, udává tedy akci grupy G na nosné množině G této grupy. Přitom jádro kerp = Z(G). Pro libovolný prvek g G G p/aŕ/, že g má jednoprvkovou orbitu v této akci, právě když g je v centru grupy G, tj. Og = {g} 44> g G Z(G). Důsledek. Centrum Z(G) je normální podgrupa grupy G. Obraz p(G) grupy G v homomorfismu p je izomorfní s faktorgrupou I Gl G/Z(G). Grupa G má tedy právě ^(G)\ vn'ťřních izomorfismů. Poznámka. Je-li H podgrupa grupy G taková, ze H Q Z(G), pak H je normální podgrupa grupy G. [va e g vä e h. a • /, • a-1 = /, • a- a-1 = /, e «.] Užití předchozí akce na p-grupách Definice. Nechť p je prvočíslo. Konečná grupa G se nazývá p-grupa, jestliže \ G\ = pk pro vhodné k G N. Věta. Nechť p je prvočíslo a G je p-grupa. Pak \ Z(G)\ > 1, tj. G má netriviální centrum. Důkaz. Platí \ G\ = pk pro nějaké k G N. Užijeme výše popsanou akci p : G —> §(G) s předpisem p(a) = pa pro každé a G G. Víme: počet prvků libovolné orbity je index stabilizátoru, tento index je dělitelem řádu grupy G, tj. čísla \G\ = pk. Dále platí aeZ(G) |Oa| = l, a^Z(G) p\\Oa\. Každý prvek z G patří do právě jedné orbity, počet prvků grupy \G\ je dělitelný číslem p. Sečtením právě |Z(G)| jedniček a několika sčítanců dělitelných p dostaneme součet dělitelný p. Proto je počet těchto jedniček dělitelný p, tedy p | |Z(G)|. Konečné grupy Věta. Nechť p je prvočíslo a G je p-grupa řádu \G\ = p2. Pak je G komutativní. Důkaz. Podle Lagrangeovy věty a předchozí věty je |Z(G)| dělitel p2 větší než 1. Pokud |Z(G)| = p2, je G = Z(G) komutativní. Předpokládejme tedy |Z(G)| = p a dojděme ke sporu. Pak existuje a g G — Z(G), a tedy M = Z(G) u {a, a-1} má více než p prvků, proto podle Lagrangeovy věty (M) = G. Ovšem podle věty o podgrupě generované množinou je libovolný prvek (M) součinem několika prvků z M. Protože prvky z centra Z(G) komutují s každým prvkem grupy G, je G = (M) = {an ■ h j n g Z, h g Z(G)}. Pro libovolná h, h' g Z(G) a n, n' g Z pak platí (a" • /j) • (a"' • /j') = 3"+"' • h ■ h' = (a"' • h') ■ (a" • h). Je tedy grupa G komutativní, tudíž Z(G) = G, spor. Důsledek. Nechť p je prvočíslo. Pak existují, až na izomorfismus, právě dvě grupy řádu p2, a sice Zp2 a Zp x Zp. Důkaz. Nechť G je grupa řádu p2. Pokud v G existuje prvek řádu p2, je G cyklická a platí G = Zp2. Předpokládejme tedy, že v G žádný prvek řádu p2 neexistuje. Zvolme libovolně as G, a/l. Pak řád prvku a je p. Zvolme libovolně b £ G — (a). Rovněž řád prvku b je p. Nechť zobrazení f : Zp x Zp —> G je určené předpisem ^(([njp, [Hp)) = a" ' ■ Protože řády obou prvků a, b jsou p, je toto zobrazení definováno korektně. Protože G je komutativní, je f homomorfismus grup. Přitom obraz f(Zp x Zp) obsahuje všechny mocniny prvku a i prvek b, je to tedy podgrupa grupy G mající více než p prvků, tedy f je surjektivní. Protože |ZP x Zp| = p2 = \ G\, je f bijekce, tudíž izomorfismus. Motivace následujících vět Poznámka. Pro libovolnou konečnou grupu G nám Lagrangeova věta říká, že řád každé podgrupy grupy G dělí řád grupy G. Naopak se můžeme ptát, jestli pro každého dělitele d řádu grupy G existuje podgrupa H grupy G mající řád d. Takto obecně to pravda není, je možné ukázat, že například grupa A4 řádu 12 nemá žádnou podgrupu řádu 6. Pomocí akce grupy na množině v následujících větách ukážeme, že to je pravda, pokud je d mocnina prvočísla. Cauchyho věta Věta (Cauchy). Nechť G je konečná grupa a p prvočíslo dělící řád grupy G. Pak G obsahuje alespoň jednu podgrupu řádu p. Důkaz. Označme X = {(n,• • • ,yP) i yi,• • • ,yP e G, y1...yp = l}. Zřejmě |X| = |G|P~1 je dělitelné p. Definujme a G S(X) předpisem a((yi, • • • ,yP)) = (y2, • • • ,yP,yi)- Pak ap = id, a tedy máme homomorfismus ip : Zp —> S(X) určený předpisem ^([n]p) = a"■ Je tedy dána akce grupy Zp na X. Pro libovolné x = (yi,... ,yp) G X orbita Ox má jediný prvek, je-li y\ = • • • = yp, a právě p prvků jinak. Protože orbity tvoří rozklad množiny X, je |X| součtem několika sčítanců, z nichž každý je 1 nebo p. Přitom počet jedniček je dělitelný p a alespoň jedna jednička tam je: máme orbitu {(1,..., 1)}. Proto existuje orbita {(g,..., g)} pro nějaké g G G, g ý 1- Pak řád g je roven p a (g) je hledaná p-prvková podgrupa grupy G. První Sylowova věta Následující věta je zobecněním Cauchyho věty: Věta (Sylow). Nechť G je konečná grupa řádu n. Nechť p je prvočíslo a k g N takové, že pk \ n. Pak G obsahuje alespoň jednu podgrupu řádu pk. Důkaz provedeme indukcí vzhledem k n. Pro n = 1 věta platí (takové p neexistuje). Nechť n > 1 a pro grupy řádu menšího než n věta platí. Rozlišíme dva případy, nejprve předpokládejme, že p | |Z(G)|. Podle Cauchyho věty existuje podgrupa H C Z(G) řádu p. Pak H je normální podgrupa grupy G, faktorgrupa G/H má ^ < n prvků, a tedy pro ni platí indukční předpoklad. Protože pk^1 | j, existuje podgrupa K grupy G/H řádu \K\ = pk^1. Její vzor tt~1(K) v projekci ir : G —> G/H je podgrupa grupy G řádu pk. Pokračování důkazu první Sylowovy věty Předpokládejme naopak, že p f |Z(G)|. Užijme znovu akci p : G —> S(G) s předpisem p(a)(g) = a ■ g ■ a-1. Víme, že jednoprvkové orbity mají právě prvky z centra. Protože orbity tvoří rozklad množiny G, platí |G| = \Z(G)\ + h + ■ ■ ■ + tr, kde ři > 1.....tr > 1 jsou počty prvků v orbitách. Víme, že p | |G| a p f |Z(G)|, existuje tedy / tak, že p f ry. Protože ŕ/ = \Ox pro vhodné x g G, je ŕ/ index stabilizátoru Sx, tedy |G| = |SX| • ry. Pak p* I I Sx| a |SX| < n. Podle indukčního předpokladu má grupa Sx podgrupu H řádu pk. Protože H je také podgrupa grupy G, jsme hotovi. -Sylowské podgrupy, druhá Sylowova věta Definice. Nechť G je konečná grupa, p prvočíslo a k G N takové, že pk je největší mocnina p dělící řád grupy G, tj. \G\ = pk ■ m, přičemž p\m. Pak libovolná podgrupa grupy G mající řád pk se nazývá p-Sylowská podgrupa grupy G (někdy též Sylowova p-podgrupa). Příklad. Grupa (§3,0) řádu 6 obsahuje tři 2-Sylowské podgrupy, totiž {id, (1, 2)}, {id, (1, 3)}, {id, (2, 3)}. Obsahuje také jedinou 3-Sylowskou podgrupu, totiž {id, (1, 2, 3), (1, 3, 2)}. Věta (Sylow). Nechť G je konečná grupa, p prvočíslo a k G N takové, že \ G\ = pk • m a p \ m. Označme r počet p-Sylowských podgrup grupy G. Pak platí ► r = 1 (mod p), r | m; ► libovolná podgrupa grupy G, jejíž řád je mocnina p, je podgrupou některé p-Sylowské podgrupy grupy G; ► jestliže H, K jsou p-Sylowské podgrupy grupy G, pak existuje g G G tak, že předpis h i-> g • h • g^1 určuje izomorfismus H -> K. [První vlastnost viz [Věta 10.10, str. 51], zbytek Dummit, Foote: Abstract algebra, str. 139.] Struktura konečných komutativních grup Věta. Necht (G, •) je konečná komutativní grupa, \G\ > 1. Pak existují (ne nutně různá) prvočísla pi, .. ., ps a /q, .. ., ks g N tak, že (G,-) = (Zpíl,+)x---x(Zp,s,+). Tento rozklad grupy G na součin cyklických p-grupje určen jednoznačně až na pořadí činitelů. Zřejmě platí \ G\ = pkl ■ ■ ■ pks. [Věta 10.13. str. 52] Příklad. Užijme větu k tomu, abychom zjistili, jak mohou vypadat komutativní grupy řádu 8. Podle předchozí věty jde o to, jakými způsoby je možné napsat 8 jako součin mocnin prvočísel: 8 = 23 = 22 • 2 = 2 • 2 • 2, proto každá komutativní grupa řádu 8 je izomorfní s právě jednou z grup Zs, Z4 x Z2 a Z2 x Z2 x Z2. Zdůrazněme, že tento výčet se týká jen komutativních grup, existují i nekomutativní grupy řádu 8, například grupa symetrií čtverce D4.