Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Matematika IV - 1. přednáška Základy teorie grup Michal Bulant Masarykova univerzita Fakulta informatiky 23. 2. 2011 Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Obsah přednášky Q Motivační úvod Q Grupy - homomorfismy a součiny Q Grupy permutací Q Grupy symetrií Q Podgrupy a homomorfismy Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. 9 Předmětové záložky v IS MU Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. 9 Předmětové záložky v IS MU 9 Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). • P. Horák, Základy matematiky, http://www.math.muni.cz/~horak/09p_zm_skripta.pdf Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Plán přednášky Q Motivační úvod Grupy symetrii 0 Podgrupy a homomorfisn Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy • oooo oooooo oooooo 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 jsou 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Plán přednášky Q Motivační úvod Q Grupy - homomorfismy a součiny Q Grupy permutací Q Grupy symetrií O Podgrupy a homomorfismy • pejsdo jujemq s f) emzouiu sf (• '£)) pjodmS • OOOOOO OOOOOO ooo» 0 íluoluolj e ÄdnjSpoj juisluXs Ädm^ pe^ni ujed Ädm^ Äupnc is e ÄLUSi^JO luoluolj - Adm^ poAn j uoea!!0|/\| Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • 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 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, c Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • 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 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, c Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • 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. 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, c Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • 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. 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, c Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o «ooo oooooo oooooo • 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, c Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o o»oo oooooo oooooo Příliš stručná exkurze do univerzální algebry 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í). Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o o»oo oooooo oooooo Příliš stručná exkurze do univerzální algebry 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ácí 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. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o o»oo oooooo oooooo Příliš stručná exkurze do univerzální algebry 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ácí 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, svazy, atd.) lze definovat několik základních pojmů analogickým způsobem: • podstruktury Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o o»oo oooooo oooooo Příliš stručná exkurze do univerzální algebry 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ácí 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, svazy, atd.) lze definovat několik základních pojmů analogickým způsobem: • podstruktury • homomorfismy mezi strukturami stejného typu Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o o»oo oooooo oooooo Příliš stručná exkurze do univerzální algebry 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ácí 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, svazy, 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oo«o oooooo oooooo Příklad O Přirozená čísla (s nulou) No = {0,1,2,...}, spolu s kteroukoliv z operací sčítání a násobení jsou asociativní a komutativní pologrupa s jednotkovým prvkem, neexistují v ní ale inverzní prvky. Motivačn ' úvod Grupy - homon lorfismy a s Dučiny Grupy perrr u tací Grupy symetrií Podgrupy a homomorfismy 0 oo«o oooooo OOOOOO Příklad O Přirozená čísla (s nulou) No = {0,1,2,...}, spolu s kteroukoliv z operací sčítání a násobení jsou asociativní a komutativní pologrupa s jednotkovým prvkem, neexistují v ní ale inverzní prvky. Q 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. Motivačn ' úvod Grupy - hornom orfismy a s Dučiny Grupy pern u tací Grupy symetrií Podgrupy a homomorfismy 0 oo«o oooooo OOOOOO Příklad O Přirozená čísla (s nulou) No = {0,1,2,...}, spolu s kteroukoliv z operací sčítání a násobení jsou asociativní a komutativní pologrupa s jednotkovým prvkem, neexistují v ní ale inverzní prvky. Q 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 grupou vůči násobení. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o ooo» oooooo oooooo Příklad (pokračování) O Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z £ 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 O. o- Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o ooo» oooooo oooooo Příklad (pokračování) O Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z £ 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 Matn všech čtvercových matic je (nekomutativní) pologrupa vzhledem k násobení matic a komutativní grupa vzhledem ke sčítání matic. 'o O. o- Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o ooo» oooooo oooooo Příklad (pokračování) O Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z £ 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 Matn 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í. 'o O. o- Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o ooo» oooooo oooooo Příklad (pokračování) O Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z £ 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í. O 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Plán přednášky Q Motivační úvod Q Grupy - homomorfismy a součiny Q Grupy permutací Q Grupy symetrií O Podgrupy a homomorfismy Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO »00000 oooooo Grupy permutací 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\ e 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. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO »00000 oooooo Grupy permutací 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\ e 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 Zm všech bijekcí na množině M o m prvcích je grupa. Říkáme jí grupa permutací na m prvcích. Motivačn ľ úvod Grupy - hornom orfismy a s< Dučiny Grupy perrr i u tací Grupy symetrií Podgrupy a hom< )morfismy 0 OOOO o«oooo OOOOOO 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ů. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo o«oooo oooooo 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í Z 3 na číslech {1,2,3} si třeba označíme jednotlivá pořadí a = (1,2,3), b = (2,3,1), c = (3,l,2), d = (1,3,2), e = (3,2,l), f = (2,1,3). Skládání našich permutací je pak zadáno tabulkou 3 b c d e f a b c d e f 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 □ s - ■ Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oo»ooo oooooo 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 jednotka, 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ů. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oo»ooo oooooo 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 jednotka, 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 jednotkou 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo ooo«oo oooooo Obdobně se chovají všechny grupy permutací Zm. 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í uk(x), k = 1, 2,..., dokud není ak(x) = x. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo ooo«oo oooooo Obdobně se chovají všechny grupy permutací Zm. 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í uk(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. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo ooo«oo oooooo Obdobně se chovají všechny grupy permutací Zm. 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í uk(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 každou permutaci napsat jako složení transpozic sousedních prvků. To, jestli potřebujeme sudý nebo lichý počet permutací, je na našich volbách nezávislé. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooo»o oooooo Nejjednodušší cykly jsou jednoprvkové pevné body permutace a. Dvouprvkové (x, každou permutaci napsat jako složení transpozic sousedních prvků. 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 : Zm —> Z2 = {±1}, tzv. paritu permutace. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů: Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO 00000« oooooo Každá permutace konečné množiny je složením cyklů. Cyklus délky £ lze vyjádřit jako složení £ — 1 transpozic. Parita cyklu délky £ 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Plán přednášky Q Motivační úvod Q Grupy - homomorfismy a součiny Q Grupy permutací Q Grupy symetrií O Podgrupy a homomorfismy Motivačn ľ úvod Grupy - hornom orfismy a s< Dučiny Grupy pern i u tací Grupy symetrií Podgrupy a homomorfismy 0 OOOO oooooo •ooooo Uvažme ohraničený rovinný obrazec, např. rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické? Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO OOOOOO »00000 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooooo o«oooo symetrie rovnostranného trojúhelníku Symetrií nacházíme několik: můžeme rotovat o 7r/3 nebo můžeme zrcadlit vůči osám stran. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooooo o«oooo symetrie rovnostranného trojúhelníku 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ý bude dohromady šest. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oo»ooo 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í Z 3 obdržíme právě stejný výsledek. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooooo ooo«oo Dihedrální grupy Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný /(-úhelník. Takové grupy symetrií se často označují jako grupy Dik a říká se jim dihedrální grupy řádu 2k (někdy též např D(k)). Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooooo ooo«oo Dihedrální grupy Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný /(-úhelník. Takové grupy symetrií se často označují jako grupy Dik 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 - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooo»o Cyklické grupy 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 Ck- Ří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. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O OOOO OOOOOO 00000« Klasifikace symetrií Věta Nechi je M ohraničená množina v rovině R2. Pak grupa jejich symetrií je buď triviální nebo jedna z grup Ck, Dik, s k > 1. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Plán přednášky Q Motivační úvod Q Grupy - homomorfismy a součiny Q Grupy permutací Q Grupy symetrií Q Podgrupy a homomorfismy Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Podpologrupy a podgrupy Definice Je-li (A, •) grupa (případně 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, •). Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Podpologrupy a podgrupy Definice Je-li (A, •) grupa (případně 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, •). Definice Zobrazení f : (G, •) —> (H, o) mezi dvěmi grupami (G, •) a (/-/, o) se nazývá 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. n Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K C G je podgrupa f (K) C H. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K C G je podgrupa f (K) C H. Q vzorem f_1(K") C G podgrupy K C H je podgrupa. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K C G je podgrupa f (K) C H. Q vzorem f_1(K") C G podgrupy K C H je podgrupa. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Q obraz podgrupy K C G je podgrupa f (K) C H. Q vzorem f_1(K") C G podgrupy K C H je podgrupa. Q je-li f zároveň bijekcí, pak i inverznízobrazení f"_1 je homomorfismus. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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 jednotky ec G G je jednotka v H Q 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. Q vzorem f_1(K") C G podgrupy K C 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}- Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Definice Podgrupa, která je vzorem jednotkového prvku e 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 H). Poznámka Podobně jako v teorii grafů jsou i v algebře izomorfní objekty nerozlišitelné. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo Definice Podgrupa, která je vzorem jednotkového prvku e 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 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). Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy o oooo oooooo oooooo Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : rXn>°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup ŕXn,o) a (Z2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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,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í 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í. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo 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,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í 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 —> 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 {2/on; k G Z}. Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo 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 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 - ■ ■O O. o- Motivační úvod Grupy - homomorfismy a součiny Grupy permutací Grupy symetrií Podgrupy a homomorfismy O oooo oooooo oooooo 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 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 k-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).