Matematika IV - 1. přednáška Základy teorie grup Michal Bulant Masarykova univerzita Fakulta informatiky 22. 2. 2010 □ S Obsah přednášky Motivační úvod Grupy - homomorfismy a součiny Grupy permutací n S - = -E -00*0 Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU □ s 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 Plán přednášky Motivační úvod Grupy - homomorfismy a součiny Grut n S - = -E -00*0 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. Plán přednášky íční úvod Grupy - homomorfismy a součiny Grut n S - = -E -00*0 • grupoid (G, •) je množina G s binární operací □ s - = ■€. -o<\(y • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací □ s - • 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ěji než jednotka používejme jednotkový prvek - důvod uvidíme později. Někdy se tomuto prvku rovněž říká jednička.< c • 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 • 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 • 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 • 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 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í). 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. 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 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 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 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. 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. Příklad 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. 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 7^ 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. Příklad 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. 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 7^ 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. Příklad 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. 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 7^ 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. 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í. □ S Příklad (pokračování) Pro IteN, množina všech k-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, —/}. Příklad (pokračování) Pro IteN, množina všech k-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, —/}. Příklad (pokračování) Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zfc = 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, —/}. 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. Příklad (pokračování) Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zfc = 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, —/}. 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. Příklad (pokračování) Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zfc = 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, —/}. 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. 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í. Příklad (pokračování) Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zfc = 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, —/}. 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. 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í. Příklad (pokračování) Pro IteN, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zfc = 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, —/}. 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. 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í. 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í). Příklad Pro k G N, množina všech k-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, —/}. Příklad Pro k G N, množina všech /(-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, —/}. 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. Příklad Pro k G N, množina všech /(-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, —/}. 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. 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í. Příklad Pro k G N, množina všech /(-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, —/}. 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. 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í. V obou předchozích příkladech, podmnožina invertibilních objektů uvažované pologrupy tvoří grupu. V případě matic jde o tzv. grupu invertibilních matic, ve druhém o grupu lineárních transformací vektorového prostoru (tj. invertibilních lineárních zobrazení). ^0 0,0- Plán přednášky íční úvod Grupy - homomorfismy a součiny Grupy permutací n S - = -E -00*0 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\ 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. 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\ 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 Zm všech bijekcí na množině Mom 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ů. Název grupa permutaci přitom uvadi jmou 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,1,2), d = (1,3,2), e = (3,2,1), f = (2,1,3). Skládání našich permutací je pak zadáno tabulkou a b c d e f a a b c d e f b b c a f d e c c a b e f d d d e f a b c e e f d c a b f f d e b c a 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ů. 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. 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. 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. 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ů. Skutečnost, jestli potřebujeme sudý nebo lichý počet permutací je na našich volbách nezávislá. Nejjednodušší cykly jsou jednoprvkové pevne body permutace a. Dvouprvkové (x, každou permutaci napsat jako složení transpozic sousedních prvků. Skutečnost, jestli potřebujeme sudý nebo lichý počet permutací je na našich volbách nezávislá. Máme proto definováno dobře zobrazení sgn : Zm —> Z2 = {±1}, tzv. paritu permutace. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů: 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.