Pologrupy, monoidy, grupy Jan Paseka Masarykova univerzita Brno Pologrupy, monoidy, grupy ­ p.1/32 Abstrakt V této kapitole se budeme zabývat jistými speciálními typy zobrazení, které se nazývají operace. Pologrupy, monoidy, grupy ­ p.2/32 Abstrakt V této kapitole se budeme zabývat jistými speciálními typy zobrazení, které se nazývají operace. Pojem operace vznikl zobecněním pojmů běžně známých ze střední školy, jako jsou například násobení přirozených čísel nebo odečítání celých čísel, atd. Pologrupy, monoidy, grupy ­ p.2/32 Abstrakt V této kapitole se budeme zabývat jistými speciálními typy zobrazení, které se nazývají operace. Pojem operace vznikl zobecněním pojmů běžně známých ze střední školy, jako jsou například násobení přirozených čísel nebo odečítání celých čísel, atd. Vidíme, že v těchto případech je vždy libovolné uspořádané dvojici čísel z jisté množiny přiřazeno jediné, přesně určené číslo z téže množiny. Pologrupy, monoidy, grupy ­ p.2/32 Obsah přednášky Operace, grupoid. n ­ ární operace. Asociativní operace, pologrupa. Komutativní zákon. Pologrupy, monoidy, grupy ­ p.3/32 Obsah přednášky Operace, grupoid. n ­ ární operace. Asociativní operace, pologrupa. Komutativní zákon. Monoid. Invertibilní a inverzní prvek. Grupa. Pologrupy, monoidy, grupy ­ p.3/32 Grupoid Definice. Necht' G je neprázdná množina. Pak libovolné zobrazení G × G - G se nazývá operace na množině G. Pologrupy, monoidy, grupy ­ p.4/32 Grupoid Definice. Necht' G je neprázdná množina. Pak libovolné zobrazení G × G - G se nazývá operace na množině G. Je ­ li při tomto zobrazení uspořádané dvojici (a, b) G přiřazen prvek c G, pak budeme obvykle psát a b = c a hovořit o operaci (čti "tečka") . Množina G spolu s operací se nazývá grupoid a označuje se symbolem (G, ) . Pologrupy, monoidy, grupy ­ p.4/32 Grupoid Definice. Necht' G je neprázdná množina. Pak libovolné zobrazení G × G - G se nazývá operace na množině G. Je ­ li při tomto zobrazení uspořádané dvojici (a, b) G přiřazen prvek c G, pak budeme obvykle psát a b = c a hovořit o operaci (čti "tečka") . Množina G spolu s operací se nazývá grupoid a označuje se symbolem (G, ) . Pologrupy, monoidy, grupy ­ p.4/32 Označení I Poznámka. 1. Pro označování operace na množině G se ukazuje jako nepraktické používat písmena a symboliku zavedenou v kapitole o zobrazeních. Vhodnější je používat speciálních symbolů. Nejčastěji to budou: Pologrupy, monoidy, grupy ­ p.5/32 Označení I Poznámka. 1. Pro označování operace na množině G se ukazuje jako nepraktické používat písmena a symboliku zavedenou v kapitole o zobrazeních. Vhodnější je používat speciálních symbolů. Nejčastěji to budou: ­ symbol (tzv. multiplikativní symbolika), který budeme číst "krát" a budeme hovořit o operaci "násobení". Je ­ li a b = c , pak prvek c budeme nazývat součinem prvků a, b (v tomto pořadí). Pologrupy, monoidy, grupy ­ p.5/32 Označení II ­ symbol + (tzv. aditivní symbolika), který budme číst "plus" a budeme hovořit o operaci "sečítání". Je ­ li a + b = c, pak prvek c budeme nazývat součtem prvků a, b (v tomto pořadí). Pologrupy, monoidy, grupy ­ p.6/32 Označení II ­ symbol + (tzv. aditivní symbolika), který budme číst "plus" a budeme hovořit o operaci "sečítání". Je ­ li a + b = c, pak prvek c budeme nazývat součtem prvků a, b (v tomto pořadí). Výše zavedené symboly nebo + samozřejmě nemají nic společného s násobením nebo sčítá- ním čísel. Pro označování operací na množině budeme podle potřeby používat i jiné symboly, na- příklad , atd. Pologrupy, monoidy, grupy ­ p.6/32 Nosná množina grupoidu 2. Z předchozí definice plyne, že grupoid (G, ) je uspořádaná dvojice, sestávající z množiny G (která se též nazývá nosná množina grupoidu) a z operace na množině G. Pologrupy, monoidy, grupy ­ p.7/32 Nosná množina grupoidu 2. Z předchozí definice plyne, že grupoid (G, ) je uspořádaná dvojice, sestávající z množiny G (která se též nazývá nosná množina grupoidu) a z operace na množině G. Rovnost dvou grupoidů znamená tedy rovnost nosných množin a současně rovnost příslušných operací . Pologrupy, monoidy, grupy ­ p.7/32 n ­ ární operace I "n ­ ární operace" na množině G, pro libovolné přirozené n, což je libovolné zobrazení G × G × × G (n ­ krát) - G. Pologrupy, monoidy, grupy ­ p.8/32 n ­ ární operace I "n ­ ární operace" na množině G, pro libovolné přirozené n, což je libovolné zobrazení G × G × × G (n ­ krát) - G. Je to předpis, který každé uspořádané n ­ tici prvků z G přiřazuje jediný prvek z G. Pologrupy, monoidy, grupy ­ p.8/32 n ­ ární operace I "n ­ ární operace" na množině G, pro libovolné přirozené n, což je libovolné zobrazení G × G × × G (n ­ krát) - G. Je to předpis, který každé uspořádané n ­ tici prvků z G přiřazuje jediný prvek z G. Příkladem n ­ ární operace na množině reálných čísel R je třeba operace max (x1, x2, . . . , xn), která každé uspořádané n ­ tici reálných čísel přiřazuje to číslo, které je z nich maximální. Pologrupy, monoidy, grupy ­ p.8/32 n ­ ární operace II Pro n = 1, resp. n = 2, resp. n = 3 se pak užívá názvů unární operace, resp. binární operace, resp. ternární operace. Pologrupy, monoidy, grupy ­ p.9/32 n ­ ární operace II Pro n = 1, resp. n = 2, resp. n = 3 se pak užívá názvů unární operace, resp. binární operace, resp. ternární operace. Unární operace na G není nic jiného, než libovolné zobrazení G - G. Pologrupy, monoidy, grupy ­ p.9/32 n ­ ární operace II Pro n = 1, resp. n = 2, resp. n = 3 se pak užívá názvů unární operace, resp. binární operace, resp. ternární operace. Unární operace na G není nic jiného, než libovolné zobrazení G - G. Binární operace je pak operací v našem slova smyslu, definovanou výše. Pologrupy, monoidy, grupy ­ p.9/32 Příklady I 1. Uvažme množinu Z všech celých čísel. Pak obyčejné násobení čísel je zřejmě operací na množině Z . Tedy (Z, ) je grupoid. Pologrupy, monoidy, grupy ­ p.10/32 Příklady I 1. Uvažme množinu Z všech celých čísel. Pak obyčejné násobení čísel je zřejmě operací na množině Z . Tedy (Z, ) je grupoid. Podobně dostáváme grupoidy (Z, +) , resp. (Z, -) , kde + , resp. - značí obyčejné sčítání, resp. obyčejné odečítání celých čísel. Pologrupy, monoidy, grupy ­ p.10/32 Příklady I 1. Uvažme množinu Z všech celých čísel. Pak obyčejné násobení čísel je zřejmě operací na množině Z . Tedy (Z, ) je grupoid. Podobně dostáváme grupoidy (Z, +) , resp. (Z, -) , kde + , resp. - značí obyčejné sčítání, resp. obyčejné odečítání celých čísel. Je jasné, že se jedná o různé grupoidy, i když nosná množina je ve všech třech případech stejná. Pologrupy, monoidy, grupy ­ p.10/32 Příklady II 2. Vezmeme ­ li množinu N všech přirozených čísel, pak obyčejné odečítání čísel není operací na N, protože například pro přirozená čísla 2, 3 je 2 - 3 N, tzn. nejedná se o zobrazení N × N - N . Pologrupy, monoidy, grupy ­ p.11/32 Příklady II 2. Vezmeme ­ li množinu N všech přirozených čísel, pak obyčejné odečítání čísel není operací na N, protože například pro přirozená čísla 2, 3 je 2 - 3 N, tzn. nejedná se o zobrazení N × N - N . Dále například obyčejné dělení čísel není operací na množině R všech reálných čísel. Pologrupy, monoidy, grupy ­ p.11/32 Příklady III 3. Necht' A je libovolná množina. Pak sjednocení, průnik a rozdíl dvou podmnožin množiny A je opět (jednoznačně určená) podmnožina v A. Pologrupy, monoidy, grupy ­ p.12/32 Příklady III 3. Necht' A je libovolná množina. Pak sjednocení, průnik a rozdíl dvou podmnožin množiny A je opět (jednoznačně určená) podmnožina v A. Tedy sjednocení, průnik a rozdíl množin jsou operace na množině 2A (tj. na systému všech podmnožin množiny A). Pologrupy, monoidy, grupy ­ p.12/32 Příklady III 3. Necht' A je libovolná množina. Pak sjednocení, průnik a rozdíl dvou podmnožin množiny A je opět (jednoznačně určená) podmnožina v A. Tedy sjednocení, průnik a rozdíl množin jsou operace na množině 2A (tj. na systému všech podmnožin množiny A). Dostáváme tak grupoidy ( 2A , ) , resp. ( 2A , ) , resp. ( 2A , - ) . Pologrupy, monoidy, grupy ­ p.12/32 Příklady IV 4. Necht' A je libovolná neprázdná množina. Symbolem AA , jak víme, označujeme systém všech zobrazení množiny A do množiny A . Pologrupy, monoidy, grupy ­ p.13/32 Příklady IV 4. Necht' A je libovolná neprázdná množina. Symbolem AA , jak víme, označujeme systém všech zobrazení množiny A do množiny A . Pro f, g AA je zřejmě složené zobrazení g f opět zobrazením A - A, tzn. jinak řečeno g f AA . Pologrupy, monoidy, grupy ­ p.13/32 Příklady IV 4. Necht' A je libovolná neprázdná množina. Symbolem AA , jak víme, označujeme systém všech zobrazení množiny A do množiny A . Pro f, g AA je zřejmě složené zobrazení g f opět zobrazením A - A, tzn. jinak řečeno g f AA . Skládání zobrazení je tedy operací na množině AA a (AA , ) je pak grupoid. Pologrupy, monoidy, grupy ­ p.13/32 Zadávání operace Operace na množině G je zobrazení G × G - G. Pologrupy, monoidy, grupy ­ p.14/32 Zadávání operace Operace na množině G je zobrazení G × G - G. Je to tedy předpis, který každé uspořádané dvojici prvků z G přiřadí jediný prvek z G. Pologrupy, monoidy, grupy ­ p.14/32 Zadávání operace Operace na množině G je zobrazení G × G - G. Je to tedy předpis, který každé uspořádané dvojici prvků z G přiřadí jediný prvek z G. Pokud je však množina G konečná, pak je výhodné zadávat operaci na G pomocí tabulky. Pologrupy, monoidy, grupy ­ p.14/32 Příklad V 5. Na množině G = {a, b, c, d} definujeme operaci tabulkou : a b c d a b a b c b a b c d c b c a c d a d a d Pologrupy, monoidy, grupy ­ p.15/32 Příklad V 5. Na množině G = {a, b, c, d} definujeme operaci tabulkou : a b c d a b a b c b a b c d c b c a c d a d a d Potom (G, ) je grupoid, při- čemž například platí: ad = c , d a = a atd. Pologrupy, monoidy, grupy ­ p.15/32 Vlastnosti grupoidů I Necht' (G, ) je grupoid. Pologrupy, monoidy, grupy ­ p.16/32 Vlastnosti grupoidů I Necht' (G, ) je grupoid. Je-li pro každá a, b, c G splněno a (b c) = (a b) c, pak o operaci říkáme, že je to asociativní operace, a o grupoidu (G, ) mluvíme jako o asociativním grupoidu, anebo častěji říkáme, že (G, ) je pologrupa. Pologrupy, monoidy, grupy ­ p.16/32 Vlastnosti grupoidů II Necht' (G, ) je grupoid. Pologrupy, monoidy, grupy ­ p.17/32 Vlastnosti grupoidů II Necht' (G, ) je grupoid. Je-li pro každá a, b G splněno a b = b a, pak o operaci říkáme, že je to komutativní operace, a o grupoidu (G, ) mluvíme jako o komutativním grupoidu. Pologrupy, monoidy, grupy ­ p.17/32 Vlastnosti grupoidů III Tvrzení. Bud' (G, ) pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná a1, a2, . . . , an G výsledek součinu prvků a1, a2, . . . , an v dané pologrupě v uvedeném pořadí nezávisí na jejich uzávorkování. Pologrupy, monoidy, grupy ­ p.18/32 Vlastnosti grupoidů III Tvrzení. Bud' (G, ) pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná a1, a2, . . . , an G výsledek součinu prvků a1, a2, . . . , an v dané pologrupě v uvedeném pořadí nezávisí na jejich uzávorkování. Poznámka. Proto pak takový součin zapisujeme ve tvaru a1 a2 . . . an. Pologrupy, monoidy, grupy ­ p.18/32 Vlastnosti grupoidů IV Tvrzení. Bud' (G, ) komutativní pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná a1, a2, . . . , an G výsledek součinu prvků a1, a2, . . . , an nezávisí na jejich pořadí ani uzávorkování. Pologrupy, monoidy, grupy ­ p.19/32 Vlastnosti grupoidů IV Tvrzení. Bud' (G, ) komutativní pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná a1, a2, . . . , an G výsledek součinu prvků a1, a2, . . . , an nezávisí na jejich pořadí ani uzávorkování. Necht' (G, ) je grupoid. Prvek e G se nazývá neutrální prvek nebo též jednotkový prvek grupoidu (G, ), je-li pro každý prvek a G splněno e a = a = a e. Pologrupy, monoidy, grupy ­ p.19/32 Příklady VI a) Grupoidy (Z, ) , (Z, +) , (2A , ) , (2A , ) jsou asociativní i komutativní, jednotkový prvek je po řadě 1, 0, a A. Pologrupy, monoidy, grupy ­ p.20/32 Příklady VI a) Grupoidy (Z, ) , (Z, +) , (2A , ) , (2A , ) jsou asociativní i komutativní, jednotkový prvek je po řadě 1, 0, a A. b) Grupoid (Z, -) a grupoid (G, ) z příkladu V není asociativní a není komutativní. První grupoid nemá jednotkový prvek, u druhého je jednotkovým prvkem prvek b. Pologrupy, monoidy, grupy ­ p.20/32 Příklady VI c) Grupoid (2A , -) je asociativní i komutativní v případě, že A = ; je ­ li A = , pak (2A , -) není asociativní ani komutativní. Grupoid nemá jednotkový prvek. Pologrupy, monoidy, grupy ­ p.21/32 Příklady VI c) Grupoid (2A , -) je asociativní i komutativní v případě, že A = ; je ­ li A = , pak (2A , -) není asociativní ani komutativní. Grupoid nemá jednotkový prvek. d) Grupoid (AA , ) je vždy asociativní; komutativní je tento grupoid pouze v případě, že množina A je jednoprvková. Jednotkový prvek je identické zobrazení. Pologrupy, monoidy, grupy ­ p.21/32 Jednotkový prvek, monoid Tvrzení. V libovolném grupoidu (G, ) existuje nejvýše jeden jednotkový prvek. Pologrupy, monoidy, grupy ­ p.22/32 Jednotkový prvek, monoid Tvrzení. V libovolném grupoidu (G, ) existuje nejvýše jeden jednotkový prvek. Z uvedeného tvrzení plyne, že má-li grupoid jednotkový prvek, je tento prvek jednoznačně určen. Proto se zpravidla značí symbolem 1. Pologrupy, monoidy, grupy ­ p.22/32 Jednotkový prvek, monoid Tvrzení. V libovolném grupoidu (G, ) existuje nejvýše jeden jednotkový prvek. Z uvedeného tvrzení plyne, že má-li grupoid jednotkový prvek, je tento prvek jednoznačně určen. Proto se zpravidla značí symbolem 1. Je-li (G, ) pologrupa, která obsahuje jednotkový prvek 1, říkáme, že (G, ) je monoid. Pologrupy, monoidy, grupy ­ p.22/32 Invertibilní a inverzní prvek Necht' (G, ) je grupoid s jednotkovým prvkem 1. Jestliže pro některý prvek a G existuje prvek b G takový, že platí a b = 1 = b a, pak prvek a se nazývá invertibilní prvek grupoidu (G, ) a prvek b se nazývá inverzní prvek k prvku a v tomto grupoidu. Pologrupy, monoidy, grupy ­ p.23/32 Invertibilní a inverzní prvek Necht' (G, ) je grupoid s jednotkovým prvkem 1. Jestliže pro některý prvek a G existuje prvek b G takový, že platí a b = 1 = b a, pak prvek a se nazývá invertibilní prvek grupoidu (G, ) a prvek b se nazývá inverzní prvek k prvku a v tomto grupoidu. Tvrzení. V libovolném monoidu (G, ) existuje ke každému prvku a G nejvýše jeden inverzní pr- vek. Pologrupy, monoidy, grupy ­ p.23/32 Počítání s invertibilními prvky Existuje-li v monoidu (G, ) k prvku a G inverzní prvek, je tento prvek jediný a zpravidla se značí symbolem a-1 . Pologrupy, monoidy, grupy ­ p.24/32 Počítání s invertibilními prvky Existuje-li v monoidu (G, ) k prvku a G inverzní prvek, je tento prvek jediný a zpravidla se značí symbolem a-1 . Tvrzení. Necht' (G, ) je monoid a necht' 1 je jeho jednotkový prvek. Necht' n je přirozené číslo a necht' a, a1, a2, . . . , an G jsou libovolné invertibilní prvky monoidu (G, ). Pak 1, a-1 a a1 a2 . . . an jsou rovněž invertibilní prvky a platí rovnosti 1-1 = 1, (a-1 )-1 = a, (a1 a2 . . . an)-1 = a-1 n . . . a-1 2 a-1 1 . Pologrupy, monoidy, grupy ­ p.24/32 Grupa Monoid (G, ), v němž ke každému prvku existuje prvek inverzní, to znamená monoid, jehož všechny prvky jsou invertibilní, se nazývá grupa. Pologrupy, monoidy, grupy ­ p.25/32 Grupa Monoid (G, ), v němž ke každému prvku existuje prvek inverzní, to znamená monoid, jehož všechny prvky jsou invertibilní, se nazývá grupa. Příklady. Dvojice (Z, +), (Q, +), (R, +), (C, +), (Q-{0}, ), (R-{0}, ), (C-{0}, ) jsou komutativní grupy. Pologrupy, monoidy, grupy ­ p.25/32 Příklady grup I Bud' A libovolná množina a bud' P(A) potenční množina množiny A. Pologrupy, monoidy, grupy ­ p.26/32 Příklady grup I Bud' A libovolná množina a bud' P(A) potenční množina množiny A. Definujeme na množině P(A) binární operaci ÷ symetrické diference následujícím předpisem. Pro libovolné dvě podmnožiny B, C A klademe B ÷ C = (B C) - (B C) = (B - C) (C - B). Pologrupy, monoidy, grupy ­ p.26/32 Příklady grup I Bud' A libovolná množina a bud' P(A) potenční množina množiny A. Definujeme na množině P(A) binární operaci ÷ symetrické diference následujícím předpisem. Pro libovolné dvě podmnožiny B, C A klademe B ÷ C = (B C) - (B C) = (B - C) (C - B). Tato operace je asociativní na P(A), (P(A), ÷) je komutativní grupa, nebot' jednotkovým prvkem je zde prázdná podmnožina a každá podmnožina B A je zde inverzním prvkem sama k sobě. Pologrupy, monoidy, grupy ­ p.26/32 Příklady grup II Vezměme opět libovolnou množinu X a uvažujme dále libovolné bijekce f : X X (permutace množiny X). Pologrupy, monoidy, grupy ­ p.27/32 Příklady grup II Vezměme opět libovolnou množinu X a uvažujme dále libovolné bijekce f : X X (permutace množiny X). Skládání zobrazení je operací též na množině S(X) všech permutací, takže dvojice (S(X), ) je monoid, a je to dokonce grupa, nebot' pro každou permutaci f : X X je inverzní zobrazení f-1 : X X permutací, která je k ní inverzním prvkem. Pologrupy, monoidy, grupy ­ p.27/32 Příklady grup II Vezměme opět libovolnou množinu X a uvažujme dále libovolné bijekce f : X X (permutace množiny X). Skládání zobrazení je operací též na množině S(X) všech permutací, takže dvojice (S(X), ) je monoid, a je to dokonce grupa, nebot' pro každou permutaci f : X X je inverzní zobrazení f-1 : X X permutací, která je k ní inverzním prvkem. Uvedená grupa se nazývá grupa permutací množiny X. Obecně není komutativní. Pologrupy, monoidy, grupy ­ p.27/32 Grupa invertibilních prvků monoidu Důsledek. Necht' (G, ) je monoid a necht' H G je množina všech invertibilních prvků monoidu (G, ). Pak množina H je uzavřená vzhledem k operaci , čili tato operace je operací i na množině H, a přitom dvojice (H, ) je grupa. Pologrupy, monoidy, grupy ­ p.28/32 Grupa S3 Prvky množiny S3, t. j. permutace množiny {1, 2, 3}, si můžeme představit jako symetrie rovnostranného trojúhelníka s vrcholy označenými čísly 1, 2, 3. Označme si identickou permutaci této množiny jako , otočení kolem těžiště trojúhelníka proti směru resp. ve směru hodinových ručiček o uhel /3 jako resp. -1 , a osovou souměrnost podle osy procházející i-tým vrcholem a středem protilehlé strany jako i, pro i = 1, 2, 3. Pologrupy, monoidy, grupy ­ p.29/32 Grupa S3 Množina permutací S3 se bude skládat z permutací = 1 2 3 1 2 3 , = 1 2 3 2 3 1 , -1 = 1 2 3 3 1 2 , 1 = 1 2 3 1 3 2 , 2 = 1 2 3 3 2 1 , 3 = 1 2 3 2 1 3 . Pologrupy, monoidy, grupy ­ p.30/32 Grupa S3 1 2 3 -1 3 2 1 Pologrupy, monoidy, grupy ­ p.31/32 Grupa S3 Multiplikativní tabulka binární operace na množině S3 má následující tvar: -1 1 2 3 -1 1 2 3 -1 3 1 2 -1 -1 2 3 1 1 1 2 3 -1 2 2 3 1 -1 3 3 1 2 -1 Pologrupy, monoidy, grupy ­ p.32/32