Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo ooooooo ooooo Diskrétní matematika B - 6. týden Základy teorie grup Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo ooooooo ooooo Q| Motivační úvod Q Grupy Q Grupy permutací Q Grupy symetrií Q Podgrupy a homomorfismy Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo ooooooo ooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • 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). • Nathan Carter. Visual Group Theory, The Mathematical Association of America, 2009, 297 s. (Viz web). • Ask a silly question ... , Why do I need to learn this stuff? (Abstruse Goose). Motivační úvod Grupy Grupy permutací Grupy symetrií Podgrupy a homomorfismy • oooo oooooo ooooooo ooooo Chceme abstraktně pracovat s objekty a se situacemi, ve kterých je možné rovnice a • x = b vždy jednoznačně řešit (tak jako u lineárních rovnic jsou objekty a a b dány, zatímco x hledáme). Jde o tzv. teorii grup. Všimněme si, že zatím nic nevíme o povaze objektů, ani co znamená ta „tečka" v rovnici. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a homc jmorfismy 0 •ooo oooooo ooooooo ooooo • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • • monoid (G,-) je pologrupa (G,-) s jednotkovým (neutrálním) prvkem1 • grupa (G, •) je monoid, ve kterém má každý prvek inverzi • komutativní grupa (grupoid, pologrupa, monoid apod.), je taková grupa (grupoid, ...), že operace • je komutativní. Často se v případě komutativních grup setkáte rovněž s pojmem abelovská grupa. Poznámka k nejednoznačnosti terminologie (multiplikativní vs. aditivní) 1 Raděj i než jednotka používejme jednotkový prvek - důvod uvidíme později. Někdy se tomuto prvku rovněž říká jednička. Grupy permutac oooooo Grupy symetrií Podgrupy a homomorfismy ooooooo ooooo Príklad Q Přirozená čísla (s nulou) No = {0,1,2,...}, spolu s kteroukoliv z operací sčítaní a násobení jsou asociativní a komutativní pologrupa s jednotkovým prvkem, neexistují v ní ale inverzní prvky. O Celá čísla Z = {..., —2, —1, 0,1, 2,... } tvoří grupoid vůči kterékoliv z operací sčítání, odčítání, násobení. Jsou dokonce komutativní grupou vzhledem ke sčítání, jsou však jen komutativní pologrupou vůči násobení (neexistují inverze k prvkům a ^ ±1). Operace odčítání není ani asociativní (např. (5 - 3) - 2 = 0 ^ 5 - (3 - 2) = 4). Všimněte si také, že pro odečítání je nula pravý neutrální prvek, ne však levý. Dokonce v tomto případě levý neutrální prvek neexistuje. O Racionální čísla Q jsou komutativní grupou vzhledem ke sčítání (celá čísla spolu se sčítáním jsou jejich podgrupou) a nenulová racionální čísla jsou kom. grupou vůči násobení. Motivační úvod 0 Grupy oo»o Grupy permutací oooooo Grupy symetrií ooooooo Podgrupy a homomorfismy ooooo Příklad (pokračovaní) O Pro k G N, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zk = 1} je konečná grupa vůči násobení komplexních čísel. Např. pro k = 2 dostaneme grupu {—1,1} se dvěma prvky, které jsou oba samy sobě inverzí, zatímco pro k = 4 dostáváme grupu G = {1, /', —1, —/'}. O Množina Mat„ všech čtvercových matic je (nekomutativní) pologrupa vzhledem k násobení matic a komutativní grupa vzhledem ke sčítání matic. O Množina všech lineárních zobrazení Hom(\/, V) na vektorovém prostoru je pologrupa vzhledem ke skládání zobrazení a komutativní grupa vzhledem ke sčítání zobrazení. Q V obou předchozích příkladech, podmnožina invertibilních objektů uvažované (multiplikativní) pologrupy tvoří grupu. V případě matic jde o tzv. grupu invertibilních (tj. regulárních) matic, ve druhém o grupu lineárních transformací vektorového prostoru (tj. invertibilních lineárních zobrazení). Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 ooo» oooooo ooooooo ooooo Bystří studenti algebry si brzy povšimnou, že se mnohé pojmy a důkazy opakují pro různé situace. Skutečně se ukazuje, že základní pojmy a tvrzení je možné zavést a dokázat obecně pomocí univerzální algebry (příp. ještě obecněji v tzv. teorii kategorií). Pro informatiky, kteří mají za sebou funkcionální programování (příp. práci s objekty, metodami, šablonami apod.), by to možná mohl být přirozený postup, my však na to bohužel nemáme dostatek času. Pro všechny struktury (pologrupy, grupy, okruhy, tělesa, vektorové prostory, svazy, moduly atd.) lze definovat několik základních pojmů analogickým způsobem: • podstruktury • homomorfismy mezi strukturami stejného typu • součiny struktur téhož typu Motivační úvod Grupy Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO »00000 ooooooo ooooo Zpravidla grupy a pologrupy potkáváme jako množiny zobrazení na pevně dané množině M, které jsou uzavřeny vůči skládání zobrazení. Často si ale tuto skutečnost přímo neuvědomujeme. Na každé konečné množině M, s m = \ M\ G N prvky máme k dispozici mm možných definic zobrazení (každý z m prvků můžeme zobrazit na kterýkoliv v M) a všechna taková zobrazení umíme skládat. Pokud chceme, aby existovala k zobrazení a : M —> M jeho inverze a-1, musí být a bijekcí. Složením dvou bijekcí vznikne opět bijekce a proto podmnožina Sm všech bijekcí na množině M o m prvcích je grupa. Říkáme jí grupa permutací na m prvcích. Název grupa permutací přitom uvádí jinou souvislost, kdy místo bijekcí na konečné množině vnímáme permutace jako přerovnání rozlišitelných prvků. Potkávali jsme se s ní např. při studiu determinantů. V grupě permutací S3 na číslech {1,2,3} si třeba označíme jednotlivá pořadí a b c d e f d e b c f a a b c d e f b c a f d e c a b e f d d e f a b c e f d c a b f d e b c a Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oo«ooo ooooooo ooooo Všimněme si podstatného rozdílu mezi permutacemi a, b a c a dalšími třemi. Ty první tři tvoří tzv. cyklus generovaný prvkem b nebo prvkem c: b2 = c, b3 = a, c2 = b, c3 = a a samy o sobě jsou tyto tři prvky komutativní podgrupou. V ní a je neutrální prvek a b s c jsou vzájemně inverzní. Je tedy tato podgrupa stejná jako je grupa Z3 zbytkových tříd celých čísel modulo 3, resp. jako grupa třetích odmocnin z jedničky z jednoho z předchozích příkladů. Další tři prvky jsou samy sobě inverzí a každý z nich je tedy společně s neutrálním prvkem a podgrupou stejnou jako je Z2. Říkáme, že b a c jsou prvky řádu 3, zatímco prvky d, e a f jsou řádu 2. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo ooo»oo ooooooo ooooo Obdobně se chovají všechny grupy permutací Sm. Každá permutace a rozkládá množinu M na disjunktní sjednocení maximálních invariantních podmnožin Mx, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x G M a do třídy rozkladu Mx přidáváme všechny akce iterací ak(x), k = 1,2,..., dokud není ak(x) = x. Každou permutaci tak dostáváme jako složení jednodušších permutací, tzv. cyklů, které se chovají jako identická permutace vně Mx a tak jako a na Mx. Pokud přitom očíslujeme prvky v Mx jako pořadí (1,2,..., \MX\) tak aby / odpovídalo ct'(x), pak je naše permutace prostým posunutím o jednu pozici v cyklu (tj. poslední prvek je zobrazen zpátky na první). Odtud název cyklus. Zjevně přitom tyto cykly komutují, takže je jedno, v jakém pořadí z nich permutaci a složíme. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooo»o ooooooo ooooo Nejjednodušší cykly jsou jednoprvkové pevné body permutace a. Dvouprvkové (x, každou permutaci lze napsat jako složení transpozic. To, jestli potřebujeme sudý nebo lichý počet permutací, je na našich volbách nezávislé. Máme proto dobře definováno zobrazení sgn : Sm —> Z2 = {±1}, tzv. paritu permutace. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů: Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom jmorfismy 0 oooo 00000» ooooooo ooooo Věta Každá permutace konečné množiny je složením cyklů. Cyklus délky i lze vyjádřit jako složení i — 1 transpozic. Parita cyklu délky i je (—l)^-1. Parita složení permutací je součinem parit jednotlivých z nich, tzn. že zobrazení sgn převádí složení permutací a o t na součin sgn a • sgn r v komutativní grupě Z2. Motivační úvod Grupy Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO OOOOOO »000000 ooooo Uvažme ohraničený rovinný obrazec, např. rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické? Tzn. vůči kterým trasformacím (zachovávajícím velikost) jsou invariantní? Všechny symetrie pevně zvoleného útvaru budou vždy tvořit grupu (většinou pouze s jediným prvkem, identickým zobrazením). Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo o«ooooo ooooo Symetrií nacházíme několik: můžeme rotovat o tt/3 nebo můžeme zrcadlit vůči osám stran. Abychom dostali celou grupu, musíme přidat všechna složení takovýchto transformací. Víme z dřívějška, že složení dvou zrcadlení je vždy otočením. Složení takových zrcadlení v opačném pořadí dá otočení o stejný úhel, ale s opačnou orientací. V našem případě tedy zrcadlení kolem dvou různých os vygenerují postupnou opakovanou aplikací všechny symetrie, kterých bude dohromady šest. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo oo»oooo ooooo Jestliže si umístíme trojúhelník v souřadnicích jako na obrázku, bude našich šest transformací zadáno maticemi Sestavením tabulky pro násobení, tak jak jsme ji udělali pro grupu permutací S3 obdržíme právě stejný výsledek. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo ooo»ooo ooooo Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný /c-úhelník. Takové grupy symetrií se často označují jako grupy D2k a říká se jim dihedrální grupy řádu 2k (někdy též např. D(k)). Tyto grupy jsou nekomutativní pro všechny k > 3. Motivačn í úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom( jmorfismy 0 oooo oooooo oooo»oo ooooo Stejně tak lze snadno najít obrazce, které mají pouze rotační symetrie a jde tedy o komutativní grupy, které se v chemii značí jako Q. Říkáme jim cyklické grupy řádu k. K tomu postačí např. uvažovat pravidelný mnohoúhelník, u kterého nesymetricky ale pořád stejně pozměníme chování hran. Grupy symetrií grupa symetrií čtverce D% má 8 prvků (4 osové symetrie, 3 netriviální rotace a identita) a lze ji chápat jako podgrupu S4 (kam se zobrazují vrcholy?) grupa symetrií čtyřstěnu je celá S4, pokud symetrie omezíme pouze na ty, které zachovávají orientaci, dostaneme podgrupu A4 < S4 sudých permutací. Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom jmorfismy 0 oooo oooooo OOOOOO* ooooo Necht je M ohraničená množina v rovině M2. Pak grupa jejich symetrií je buď triviální nebo jedna z grup Q, D2k, s k > 1. Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom ítnorfismy 0 oooo oooooo ooooooo •OOOO Definice Je-li (A,-) grupa (případně pologrupa), pak její podmnožinu 8 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, •). Definice Zobrazení f : (G, •) —> (H, o) mezi dvěmi grupami (G, •) a (/7, o) se nazývá homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b £ 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. Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom ítnorfismy 0 oooo oooooo ooooooo o»ooo 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 e^ G G je neutrální prvek v H O obraz inverze k prvku je inverzí obrazu, tj. f(a^1) = f(a)^1 Q obraz podgrupy K c G je podgrupa f (K) c H. 0 vzorem f~1(K) c G podgrupy K c H je podgrupa. 0 je-li f zároveň bijekcí, pak i inverznízobrazení f:_1 je homomorfismus. O f je injektivní zobrazení právě tehdy, když f^1(en) = {sg}- Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom ítnorfismy 0 oooo oooooo ooooooo oo»oo Definice Podgrupa, která je vzorem jednotkového prvku e £ H (tj. f~1(e)) se nazývá jádro homomorfismu f a značíme ji ker f. Bijektivní homomorfismus grup G a H nazýváme izomorfismus (a značíme G 2é H). 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). Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom ítnorfismy 0 oooo oooooo ooooooo ooo»o Příklad (1) Pro každou grupu permutací G = Sn jsme definovali zobrazení sgn : (S„, o) —y (Z2, +) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (S„,o) a (Z2,+) . Jádrem tohoto homomorfismu jsou permutace se sudou paritou. (2) Grupa symetrií rovnostranného trojúhelníka D§ je izomorfní s grupou permutací S3. Stačí zvolit realizaci S3 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 ->• R+ (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 {2kiri; k G Z}. Motivačn úvod Grupy Grupy permutací Grupy symetrií Podgrupy a hom ítnorfismy 0 oooo oooooo ooooooo OOOO* Příklad (4) Determinant matice je zobrazením, které každé matici skalárů z K přiřazuje nějaký skalár z K (pracovali jsme sK = Z,Q,l, C). Cauchyova věta o determinantu součinu čtvercových matic det(/4 • B) = (det/4) • (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 /c-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 (Zp,-) je izomorfní aditivní grupě (Zp_i, +) (plyne mj. z věty o existenci primitivního kořene).