Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Matematika IV - 3. přednáška Podgrupy, homomorfismy a rozklady Michal Bulant Masarykova univerzita Fakulta informatiky 9. 3. 2011 Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo oooooo Obsah přednášky Q Podgrupy, homomorfismy a součiny Q Rozklady podle podgrup Q Normálni podgrupy Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo oooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Predmetové záložky v IS MU Podgrupy, homomorfismy a součiny oooooooooooooo Doporučené zdroje Rozklady podle podgrup ooooo Normální podgrupy oooooo • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). Podgrupy, homomorfismy a součiny oooooooooooooo Plán přednášky Rozklady podle podgrup ooooo Normálni podgrupy oooooo Q Podgrupy, homomorfismy a součiny O Rozklady podle p Podgrupy, homomorfismy a součiny •ooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Podgrupy, homomorfismy a součiny •ooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Věta Necht (G, o) grupa. Pak 0 ^ H c G je její podgrupa právě tehdy, když O Va, b G H : a o b e H; 9 Va G H : a-1 e H. Podgrupy, homomorfismy a součiny •ooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Věta Necht (G, o) grupa. Pak 0 ^ H c G je její podgrupa právě tehdy, když O Va, b G H : a o b e H; 9 Va G H : a-1 e H. Snadno se navíc vidí, že obě podmínky v předchozí větě lze shrnout do jediné: Va, b G H : a o b~x G H. Podgrupy, homomorfismy a součiny o«oooooooooooo Rozklady podle podgrup OOOOO Normálni podgrupy oooooo Příklad © Z je podgrupa aditivních grup Z,Q, R, C. O Všechny podgrupy (Z, +) jsou vyčerpány množinami mZ. © (/?+,•)<(/?*,•)■ O Množina An všech sudých permutací na n-prvkové množině je podgrupou Z„. O SL„(M) < GLn{R). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normální podgrupy oo«ooooooooooo ooooo oooooo Podgrupa generovaná množinou Jsou-li K, L podgrupy grupy G, je zřejmě i jejich průnik (nikoliv ovšem sjednocení!) podgrupou G. Totéž zřejmě dokonce platí i pro libovolný (třeba nekonečný) systém podmnožin. Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oo«ooooooooooo ooooo oooooo Podgrupa generovaná množinou Jsou-li K, L podgrupy grupy G, je zřejmě i jejich průnik (nikoliv ovšem sjednocení!) podgrupou G. Totéž zřejmě dokonce platí i pro libovolný (třeba nekonečný) systém podmnožin. Odtud plyne následující definice: Definice Je-li M libovolná podmnožina grupy G, pak (M}= f) H M. • Podobně (Zs, +) = (1) = (3) = (5) = (7). Podgrupy, homomorfismy a součiny ooo«oooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad • Z = (1). • V (Zm,+) je Zm = <[l]m)- • Podobně (Zs, +) = (1) = (3) = (5) = (7). . (Z7V) = (3) = (5) Podgrupy, homomorfismy a součiny ooo«oooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad • Z = (1). • V (Zm,+) je Zm = ([l]m). • Podobně (Z8, +) = (1) = (3) = (5) = (7). • (Z7V) = (3) = (5). • (Zg,*) není cyklická. Podgrupy, homomorfismy a součiny ooo«oooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad • Z = (1). • V (Zm,+) je Zm = ([l]m). • Podobně (Z8, +) = (1) = (3) = (5) = (7). • (Z7V) = (3) = (5). • (Zg,-) není cyklická. • D2n = (r, s). Podgrupy, homomorfismy a součiny oooo»ooooooooo Homomorfismus Rozklady podle podgrup ooooo Normálni podgrupy oooooo Definice Zobrazení f : (G, •) —> (H, o) mezi dvěmi grupami (G, •) a (H, o) se nazýva homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b G G platí f {a- b) = f{a)of{b). Povšimněme si, že násobení vlevo je uvnitř grupy G předtím, než zobrazujeme, zatímco vpravo jde o násobení v H poté, co zobrazujeme. Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H Q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f(a)"1. O obraz podgrupy K < G je podgrupa f{K) < H. □ s ■ 1 Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K < G je podgrupa f(K) < H. Q vzorem f_1(K") < G podgrupy K < H je podgrupa. □ s - ■ Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K < G je podgrupa f(K) < H. Q vzorem f_1(K") < G podgrupy K < H je podgrupa. Q je-li f zároveň bijekcí, pak i inverznízobrazení f"_1 je homomorfismus. Podgrupy, homomorfismy a součiny ooooo«oooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H Q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a)-1 Q obraz podgrupy K < G je podgrupa f(K) < H. Q vzorem f_1(K") < G podgrupy K < H je podgrupa. Q je-li f zároveň bijekcí, pak i inverznízobrazení f"_1 je homomorfismus. Q f je injektivní zobrazení právě tehdy když f~1{ej-i) = {ec}- Podgrupy, homomorfismy a součiny oooooo»ooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Definice Podgrupa, která je vzorem jednotkového prvku eeH (tj. f_1({e})) se nazývá jádro homomorfismu f a značíme ji kerf. Bijektivní homomorfismus grup G a H nazýváme izomorfismus (a značíme G = H). Poznámka Podobně jako v teorii grafů jsou i v algebře izomorfní objekty nerozlišitelné. Podgrupy, homomorfismy a součiny oooooo»ooooooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Definice Podgrupa, která je vzorem jednotkového prvku eeH (tj. f_1({e})) se nazývá jádro homomorfismu f a značíme ji kerf. Bijektivní homomorfismus grup G a H nazýváme izomorfismus (a značíme G = H). Poznámka Podobně jako v teorii grafů jsou i v algebře izomorfní objekty nerozlišitelné. Z předchozích tvrzení okamžitě vyplývá, že homomorfismus f : G —> H s triviálním jádrem je izomorfismem G na obraz f{G). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy ooooooo«oooooo ooooo oooooo Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje1. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. 1Co znamenají ty mocniny? Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy ooooooo«oooooo ooooo oooooo Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje1. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. 'Co znamenají ty mocniny? Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy ooooooo«oooooo ooooo oooooo Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje1. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Zjistit pro konkrétní cyklickou grupu generátor je obecně obtížný problém. I při znalosti generátoru g G G je ale obecně velkým problémem zjistit pro dané a e G číslo k, pro které gk = a (tzv. problém diskrétního logaritmu je základem mnoha kryptografických protokolů - EIGamal, Diffie-Hellman, DSA). 'Co znamenají ty mocniny? Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy ooooooo«oooooo ooooo oooooo Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje1. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Zjistit pro konkrétní cyklickou grupu generátor je obecně obtížný problém. I při znalosti generátoru g G G je ale obecně velkým problémem zjistit pro dané a G G číslo k, pro které gk = a (tzv. problém diskrétního logaritmu je základem mnoha kryptografických protokolů - EIGamal, Diffie-Hellman, DSA). Z definice přímo vyplývá, že každá cyklická grupa je izomorfní buď grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd (když je konečná). znamenají ty mocniny? Podgrupy, homomorfismy a s □ účiny Rozklady podle sodgrup Normálni podg rupy OOOOOOOO0OOOOO ooooo oooooo Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). Podgrupy, homomorfismy a s □ účiny Rozklady podle sodgrup Normálni podg rupy OOOOOOOO0OOOOO ooooo oooooo Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). (2) Grupa symetrií rovnostranného trojúhelníka D§ je izomorfní s grupou permutací z3. Stačí zvolit realizaci Z 3 tak, že za množinu tří prvků pro permutace vezmeme vrcholy trojúhelníka a jednotlivým symetriím přiřadíme permutace těchto vrcholů, které vyvolají. Podgrupy, homomorfismy a součiny OOOOOOOO0OOOOO Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). (2) Grupa symetrií rovnostranného trojúhelníka D§ je izomorfní s grupou permutací z3. Stačí zvolit realizaci Z 3 tak, že za množinu tří prvků pro permutace vezmeme vrcholy trojúhelníka a jednotlivým symetriím přiřadíme permutace těchto vrcholů, které vyvolají. (3) Zobrazení exp : (R, +) ->■ (M+, •) (nebo C ->■ C \ {0}) je homomorfismus aditivní grupy reálných nebo komplexních čísel na multiplikativní grupu kladných reálných čísel, resp. na multiplikativní grupu všech nenulových komplexních čísel. V případě reálných čísel jde o izomorfismus (co je jeho inverzí?). Pro komplexní čísla dostáváme netriviální jádro {2/on; k G Z}. Podgrupy, homomorfismy a součiny ooooooooo«oooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (4) Determinant matice je zobrazením, které každé matici skalám z K přiřazuje nějaký skalár z K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A ■ B) = (det A) • (det B) je tvrzením, že pro grupu G = GL(n,K) invertibilních matic je det : G —> K \ {0} multiplikativním homomorfismem grup. □ S - ■ M Podgrupy, homomorfismy a součiny ooooooooo«oooo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (4) Determinant matice je zobrazením, které každé matici skalám z K přiřazuje nějaký skalár z K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A ■ B) = (det A) • (det B) je tvrzením, že pro grupu G = GL(n,K) invertibilních matic je det : G —> K \ {0} multiplikativním homomorfismem grup. (5) Grupy zbytkových tříd (Z^, +) jsou izomorfní grupám komplexních /(-tých odmocnin z jedničky, což jsou zároveň izomorfní obrazy konečných grup otočení v rovině o celé násobky úhlu ^. (6) Multiplikativní grupa invertibilních zbytkových tříd (Zpv) je izomorfní aditivní grupě (Zp_i, +) (plyne z cykličnosti grupy -později snad dokážeme). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOO0OOO ooooo oooooo (Přímý) součin grup Definice Pro každé dvě grupy (G, •), (H,o) definujeme součin grup (G x H, *) takto: Jako množina je G x H skutečně (kartézský) součin, na kterém definujeme grupové násobení po složkách, tj. (a,x) * (b,y) = (a- b,xoy). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOO0OOO ooooo oooooo (Přímý) součin grup Definice Pro každé dvě grupy (G, •), (H,o) definujeme součin grup (G x H, *) takto: Jako množina je G x H skutečně (kartézský) součin, na kterém definujeme grupové násobení po složkách, tj. (a,x) * (b,y) = (a- b,xoy). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Zobrazení po : G x H 3 (a, x) h> a e G, pn : G x H 3 (a, x) h> x g H jsou surjektivní homomorfismy (tzv. projekce) s jádry kerpc = {(ec,x); x £ H} kerpH = {(a, en); a e G}. Podgrupy, homomorfismy a součiny ooooooooooo«oo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. Podgrupy, homomorfismy a součiny ooooooooooo«oo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. V aditivní notaci vypadá izomorfismus takto: [0W([0]2,[0]3), [l]e m> ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 m> ([1]2, [0]3) [4]6^([0]2,[2]3), [5]6 ^ ([1]2> [1]3) □ s - ■ ■* Podgrupy, homomorfismy a součiny ooooooooooo«oo Rozklady podle podgrup ooooo Normálni podgrupy oooooo Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. V aditivní notaci vypadá izomorfismus takto: [0W([0]2,[0]3), [l]e m> ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 m> ([1]2, [0]3) [4]6^([0]2,[2]3), [5]6 ^ ([1]2> [1]3) (8) Dihedrální grupa Dg (tj. grupa symetrií čtverce, (r, s\ŕ = l,s2 = l,srs = r-1} ) není izomorfní součinu Z2 x Z4, přestože mají stejný počet prvků (Dg není komutativní). □ S - ■ M Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normální podgrupy OOOOOOOOOOOO0O ooooo oooooo Čínská zbytková věta (Chinese remainder theorem) Předchozí příklad je speciálním případem tzv. Čínské zbytkové věty. Jsou-li k, m nesoudělná, pak (Zkm,+)^(Zk,+)x(Zm,+). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOO0O ooooo oooooo Čínska zbytková věta (Chinese remainder theorem) Předchozí příklad je speciálním případem tzv. Čínské zbytkové věty. Věta * Jsou-li k, m nesoudělná, pak (Zkm,+)^(Zk,+)x(Zm,+). a obecněji Věta Jsou-li m\, ítt2, • • • , m k po dvou nesoudělná, pak (ZUm., +) (Zmi, +) x (Zm2, +) x • • • x (Zmk, +). Tento izomorfismus se často s výhodou využívá k reprezentaci velkých čísel při distribuovaných výpočtech pracujících s dělitelností, kdy na každém počítači stačí pracovat s jedním (relativně malým) modulem. Podgrupy, homomorfismy a součiny OOOOOOOOOOOOO* Rozklady podle podgrup ooooo Normálni podgrupy oooooo Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). 2A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOO* ooooo oooooo Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) G (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = ai (mod mi),..., a = ak (mod rrik), což se udělá malým (ale šikovným) trikem:2 2A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOO* ooooo oooooo Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) G (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = ai (mod m\),..., a = ak (mod m^), což se udělá malým (ale šikovným) trikem:2 Pro libovolné 1 < / < k položme n; = m/rtij a protože (m,-, n,-) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u\ a v, tak, že Ujirij + Vjtij = 1, tj. Vjtij = 1 (mod mi). 2A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOO* ooooo oooooo Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m g Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) g (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a g Zm. To je ale totéž jako najít a g Z takové, že a = ai (mod m\),..., a = ak (mod m^), což se udělá malým (ale šikovným) trikem:2 Pro libovolné 1 < / < k položme n; = m/rtij a protože (m,-, n,-) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u\ a v, tak, že Ujirij + Vjtij = 1, tj. Vjtij = 1 (mod mi). Hledané a pak najdeme jako a = Y,iaivini- 2A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Podgrupy, homomorfismy a součiny oooooooooooooo Plán přednášky Rozklady podle podgrup ooooo Normálni podgrupy oooooo Q Rozklady podle podgrup Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOOO «0000 oooooo Rozklady podle podgrup Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h i> jestliže b~x ■ a e H, tj. a-1 • b e H . Je to relace ekvivalence: Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOOO «0000 oooooo Rozklady podle podgrup Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h i> jestliže b~x ■ a e H, tj. a-1 • b e H . Je to relace ekvivalence: • a-1 • a = e e H, Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup Rozklady podle podgrup •oooo Normálni podgrupy oooooo Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h í? jestliže b-1 ■ a e H, tj. a-1 • b e H . Je to relace ekvivalence: • a-1 • a = e g H, 9 je-li b'1 ■ a = h e H, potom a"1 • b = (b'1 ■ a)"1 = h'1 e H, Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup Rozklady podle podgrup •oooo Normálni podgrupy oooooo Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h í? jestliže b-1 ■ a g H, tj. a-1 • b g H . Je to relace ekvivalence: • a-1 • a = e g H, 9 je-li b'1 ■ a = h g H, potom a"1 • b = (b'1 ■ a)"1 = h'1 g H, • je-li c-1 • b g /-/ a zároveň je b-1 • a g /-/, potom c-1 • a = c-1 • i) • i)-1 • 3 E H. Podgrupy, homomorfismy a S' DUČiny Rozklady pc udle pot J grup Normální podg ;rupy oooooooooooooo o»ooo oooooo Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup o»ooo Normálni podgrupy oooooo Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Třídu příslušející prvku a značíme a ■ H (zřejmě a G a ■ H) a skutečně platí, že a-H = {ah; h £ H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup o»ooo Normálni podgrupy oooooo Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Třídu příslušející prvku a značíme a ■ H (zřejmě a G a ■ H) a skutečně platí, že a-H = {ah; h £ H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Množinu všech levých tříd rozkladu podle podgrupy H označujeme G/H. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup o»ooo Normálni podgrupy oooooo Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Třídu příslušející prvku a značíme a ■ H (zřejmě a G a ■ H) a skutečně platí, že a-H = {ah; h G H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Množinu všech levých tříd rozkladu podle podgrupy H označujeme G/H. Obdobně definujeme pravé třídy rozkladu H ■ a. Příslušná ekvivalence je: a ~ b, jestliže a ■ b~x G H. Proto H\G = {H ■ a; a G G}. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup oo«oo Normálni podgrupy oooooo Věta Pro třídy rozkladu grupy platí: Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup oo«oo Normálni podgrupy oooooo Věta Pro třídy rozkladu grupy platí: O Levé a pravé třídy rozkladu podle podgrupy H c G splývají právě tehdy když pro každé a g G, h g H platí a ■ h ■ a-1 g H. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup oo«oo Normálni podgrupy oooooo Věta Pro třídy rozkladu grupy platí: O Levé a pravé třídy rozkladu podle podgrupy H c G splývají právě tehdy když pro každé a g G, h g H platí a ■ h ■ a-1 g H. O Všechny třídy (levé i pravé) mají shodnou mohutnost jako podgrupa H. O Zobrazení a ■ H i—> H ■ a-1 zadává bijekci mezi levými a pravými třídami rozkladu G podle H. Poznámka Rozmyslete si, proč je v posledním tvrzení a a nikoliv a. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je rádu n), H jej í podgrupa. Potom □ S - ■ M Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Podgrupy, homomorfismy a s DUČiny Rozklady podle sodgrup Normálni podg rupy oooooooooooooo ooo«o oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. □ S - ■ M Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. O Je-li a g G prvek řádu k, pak k dělí n. □ S - ■ M Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. O Je-li a g G prvek řádu k, pak k dělí n. Q pro každé a g G je a" = e. □ S - ■ M Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. O Je-li a g G prvek řádu k, pak k dělí n. Q pro každé a e G je a" = e. Q je-li mohutnost grupy G prvočíslo p , pak je G izomorfní cyklické grupě Zp. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooo«o Normálni podgrupy oooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. O Je-li a g G prvek řádu k, pak k dělí n. Q pro každé a g G je a" = e. Q je-li mohutnost grupy G prvočíslo p , pak je G izomorfní cyklické grupě Zp. Druhému tvrzení se říkává Lagrangeova věta, předposlednímu malá Fermatova věta (častěji ovšem ve speciálním případě grupy (Z*, •)) Podgrupy, homomorfismy a s DUČiny Rozklady podle sodgrup Normálni podg rupy oooooooooooooo oooo» oooooo Snadnými důsledky předchozího jsou následující věty: Věta (Malá Fermatova) Pro libovolné prvočíslo p a číslo a e Z nedělitelné p platí ap_1 = 1 (mod p). Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup oooo» Normálni podgrupy oooooo Snadnými důsledky předchozího jsou následující věty: Věta (Malá Fermatova) Pro libovolné prvočíslo p a číslo a € Z nedělitelné p platí ap_1 = 1 (mod p). '-' Věta (Eulerova) Pro libovolné m G N a každé a e Z splňující (a, m) = 1 platí a^m) = 1 (mod m). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo oooooo Plán přednášky O Rozklady podle p Q Normálni podgrupy Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy •OOOOO Normálni podgrupy Podgrupy H, pro které platí, že a ■ h ■ a G H pro všechna a G G, h G H, se nazývají normální podgrupy (značíme H < G) . Snadno se nahlédne platnost následujícího Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOOO OOOOO «00000 Normálni podgrupy Podgrupy H, pro které platí, že a ■ h ■ a-1 e H pro všechna a e G, h G H, se nazývají normální podgrupy (značíme H <\ G) . Snadno se nahlédne platnost následujícího Tvrzení Podgrupa H je normální právě tehdy, když pro každé a g G p/aŕí a ■ H = H ■ a (jinými slovy: levý rozklad G podle podgrupy H je shodný s pravým rozkladem). Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy OOOOOOOOOOOOOO OOOOO «00000 Normálni podgrupy Podgrupy H, pro které platí, že a ■ h ■ a-1 e H pro všechna a e G, h G H, se nazývají normální podgrupy (značíme H <\ G) . Snadno se nahlédne platnost následujícího Tvrzení Podgrupa H je normální právě tehdy, když pro každé a e G platí a ■ H = H ■ a (jinými slovy: levý rozklad G podle podgrupy H je shodný s pravým rozkladem). Důsledek • 1 < G, G < G 9 V komutativní grupě je každá podgrupa normální. • Je-li H podgrupa konečné grupy G, kde \ H\ normální. \G\/2, pak je H Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy o»oooo Příklad • Dihedrální grupa Din má vždy normálni podgrupu izomorfní Z„. Levý (i pravý) rozklad podle této podgrupy je dvojprvková množina {Z„,s • Z„}. • (f2) = {'d, r2} je normálni podgrupa v Dg. Levý rozklad podle této podgrupy je čtyřprvková množina {{id,r2},{r,r3},{s,sr2},{sr,sr3}}. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oo«ooo Pro normální podgrupy je dobře definováno násobení na G/H vztahem (a • H) ■ (b ■ H) = (a ■ b) ■ H. Skutečně, volbou jiných reprezentantů ah, b ■ h' dostaneme opět stejný výsledek (a- h- b- h')- H = ((a • b)- (b'1 h-b) tí)-H. Věta Je-li H normálnípodgrupou G, tvoří rozklad G/H s násobením definovaným prostřednictvím reprezentantů grupu. Je-li G komutativní, je i G/H komutativní. Podgrupy, homomorfismy a součiny oooooooooooooo Rozklady podle podgrup ooooo Normálni podgrupy oo«ooo Pro normální podgrupy je dobře definováno násobení na G/H vztahem (a • H) ■ (b ■ H) = (a ■ b) ■ H. Skutečně, volbou jiných reprezentantů ah, b ■ tí dostaneme opět stejný výsledek (a • h- b- h')- H = ((a • b)- (b'1 h-b) tí)-H. Věta Je-li H normálnípodgrupou G, tvoří rozklad G/H s násobením definovaným prostřednictvím reprezentantů grupu. Je-li G komutativní, je i G/H komutativní. Příklad ríL = {na; a g Z} c Z zadává pro libovolné neN podgrupu Z a její faktorgrupou (až na izomorfismus) je aditivní grupa zbytkových tříd Z„ (přitom pro n = 1 jde o triviální grupu) . Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo ooo»oo Jednoduché (prosté) grupy Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. 3255 stran "tvrdé" matematiky Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo ooo»oo Jednoduché (prosté) grupy Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. Mezi konečnými komutativními grupami je situace skutečně jednoduchá - prostými jsou pouze grupy Zp pro prvočíselné p (podobně i každá prostá grupa lichého řádu je nutně izomorfní Zp - důkaz tohoto faktu je ale značně netriviální3). 3255 stran "tvrdé" matematiky Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo ooo»oo Jednoduché (prosté) grupy Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. Mezi konečnými komutativními grupami je situace skutečně jednoduchá - prostými jsou pouze grupy Zp pro prvočíselné p (podobně i každá prostá grupa lichého řádu je nutně izomorfní Zp - důkaz tohoto faktu je ale značně netriviální3). V nekomutativním případě je situace výrazně složitější - až v roce 1982 (samozřejmě s pomocí počítačů) se podařilo završit úsilí o úplnou klasifikaci jednoduchých grup. 3255 stran "tvrdé" matematiky Podgrupy, homomorfismy a součiny Rozklady podle podgrup Normálni podgrupy oooooooooooooo ooooo ooo»oo Jednoduché (prosté) grupy Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. Mezi konečnými komutativními grupami je situace skutečně jednoduchá - prostými jsou pouze grupy Zp pro prvočíselné p (podobně i každá prostá grupa lichého řádu je nutně izomorfní Zp - důkaz tohoto faktu je ale značně netriviální3). V nekomutativním případě je situace výrazně složitější - až v roce 1982 (samozřejmě s pomocí počítačů) se podařilo završit úsilí o úplnou klasifikaci jednoduchých grup. Například alternující grupa An (tj. podgrupa sudých permutací grupy Z„) je jednoduchá pro n > 5 , z čehož (s pomocí tzv. Galoisovy teorie) plyne nemožnost existence obecných vzorců pro kořeny polynomů stupně 5 a vyššího. 3255 stran "tvrdé" matematiky Rozklady podle podgrup ooooo Podgrupy, homomorfismy a součiny oooooooooooooo Vztah normálních podgrup a homomorfismů Normální podgrupy oooo«o Všechna jádra homomorfismů jsou normální podgrupy. Naopak, jestliže je podgrupa H c G normální, pak zobrazení (projekce na faktorgrupu) p : G ->• G/H, a h> a ■ H je surjektivní homomorfismus grup s jádrem H. Skutečně, p je dobře definované, přímo z definice násobení na G/H je vidět, že to musí být homomorfismus, který je zjevně na. Je tedy vidět, že normální podgrupy jsou právě všechna jádra homomorfismů. Podgrupy, homomorfismy a součiny oooooooooooooo Věty o izomorfismu Rozklady podle podgrup ooooo Normálni podgrupy OOOOO* Věta (první, základní) Pro libovolný homomorfismus grup f : G K je dobře definován také homomorfismus f : G/kerf -»■ K, f(a ■ H) = f(a), který je injektivní. Zejména dostáváme G/ ker f = f{G).