Pologrupy, monoidy, grupy
Buď G množina. Uvažme libovolné zobrazení kartézské mocniny GxGdo G. O takovém zobrazení říkáme, že je to binární operace na množině G. Je-li taková binární operace pevně zadána, pak jsou-li a,b G G libovolné prvky a je-li prvek c E G obrazem uspořádané dvojice (a, b) při tomto zobrazení, píšeme to zpravidla ve tvaru c = a • b a mluvíme o binární operaci ■. Podle okolností užíváme pro označení binárních operací i jiné zavedené symboly, například +, *, o a podobně.
Je-li na množině G zadána binární operace ■, pak říkáme, že jde o grupoid a zapisujeme ho jako dvojici (G, ■).
Příklady. Dvojice (N, +), (N, •), (Z, +), (Z, -), (Z, •), (Q, +), (Q, -), (Q, •), (Q - {0},:), kde +, -, ■, : jsou obvyklé operace sčítaní, odečítání, násobení a dělení v rámci číselných množin, jsou grupoidy.
Buď A libovolná množina a buď V{A) potenční množina množiny A. Pak dvojice (V(A),\J), (V(Ä),n), (V(A), -), kde U, n a — jsou obvyklé operace sjednocení, průniku a rozdílu množin, jsou grupoidy.
Pro libovolnou množinu X jsme symbolem Xx označili množinu všech zobrazení množiny X do X a symbolem o jsme značili skládání zobrazení. Pak dvojice (Xx, o) je grupoid.
Nechť (G, ■) je grupoid. Je-li pro každá a,b,c G G splněno
a • (b • c) = (a ■ b) • c,
pak o operaci ■ říkáme, že je to asociativní operace, a o grupo-idu (G, ■) mluvíme jako o asociativním grupoidu, anebo častěji říkáme, že (G, ■) je pologrupa.
Nechť znovu (G, ■) je grupoid. Je-li pro každá a, b G G splněno
a • b = b • a, 1
pak o operaci ■ říkáme, že je to komutativní operace, a o grupo-idu (G, ■) mluvíme jako o komutativním grupoidu.
Tvrzení. Buď (G, ■) pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná di, d2, ■ ■ ■, an G G výsledek součinu prvků ai, Gt2,..., 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 ai ■ ci2 ■ • • • ■ dn.
Důkaz. Postupujeme indukcí vzhledem k n. Pro n = 1 a n = 2 není co dokazovat a pro n = 3 je tento fakt dán asociativitou operace ■. Nechť dále n > 3. Předpokládejme, že tvrzení platí pro všechny hodnoty 1,2,3,...,n — 1 a dokažme, že pak platí také pro n. Zvolme libovolné uzávorkování součinu prvků di, d2,..., dn v tomto pořadí a označme a výsledek tohoto součinu. Pak existuje k G {1, 2,3,..., n — 1} takové, že a = b • c, kde b je součin prvků di, d2,..., a c je součin prvků d^+i,..., n, obojí při jistých uzávorkováních uvedených prvků. Ovšem podle indukčního předpokladu součin prvků di, d2,..., nezávisí na způsobu uzávorkování, takže lze psát b = a\ • d, kde d je součin prvků d2,..., dfc při nějakém uzávorkování. Vzhledem k asociativitě operace ■ pak můžeme psát a = (di ■ d) • c = a\ • (d • c), kde d-c je součinem prvků d2,..., an při jistém uzávorkování. Ovšem opět podle indukčního předpokladu výsledek tohoto součinu zase nezávisí na způsobu uzávorkování. Máme tedy a = a\ • (d • c), kde prvek d-c nijak nezávisí na původně zvoleném uzávorkování součinu prvků di, d2,..., an. Tím je tvrzení dokázáno.
Podobně jednoduše lze dokázat také následující fakt.
Tvrzení. Buď (G, ■) komutativní pologrupa. Pak pro libovolné přirozené číslo n a pro libovolná di, d2,..., an G G výsledek součinu prvků di, d2,..., an nezávisí na jejich pořadí ani uzávorkování.
2
Nechť (G, ■) je grupoid. Prvek e G C se nazývá neutrální prvek nebo též jednotkový prvek grupoidu (G, ■), je-li pro každý prvek a G G splněno
e ■ a = a = a • e.
Tvrzení. V libovolném grupoidu (G, ■) existuje nejvýše jeden jednotkový prvek.
Důkaz. Nechť e, / G G jsou jednotkové prvky grupoidu (G, ■). Pak dostáváme
e = e ■ / = /,
kde první rovnost plyne z toho, že / jednotkový prvek, a druhá rovnost plyne z toho, že e je jednotkový prvek. Takže e = /.
Z uvedeného tvrzení plyne, že má-li grupoid jednotkový prvek, je tento prvek jednoznačně určen. Proto se pro něj mnohdy používá speciální symbol, zpravidla je to symbol 1.
Je-li (G, ■) pologrupa, která obsahuje jednotkový prvek 1, říkáme, že (G, ■) je monoid.
Příklady. Dvojice (N, ■), (Z,+), (Z,-), (Q,+), (Q, ■) jsou komutativní monoidy.
Buď opět A libovolná množina a buď V (A) potenční množina množiny A. Pak dvojice (V(A), U), resp. (V(A), fl) jsou komutativní monoidy, v nichž neutrálními prvky jsou podmnožiny 0, resp. A.
Znovu zopakujme, že pro libovolnou množinu X jsme symbolem Xx označili množinu všech zobrazení množiny X do X a symbolem o jsme značili skládání zobrazení. Pak dvojice (Xx, o) je monoid, neboť skládání zobrazení je asociativní operace na množině Xx a identické zobrazení idx zde hraje roli jednotkového prvku. Tento monoid obecně není komutativní.
3
Nechť (G, ■) je grupoid s jednotkovým prvkem 1. Jestliže pro některý prvek a E G existuje prvek b E 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 E G nejvýše jeden inverzní prvek.
Důkaz. Označme 1 jednotkový prvek monoidu (G, ■). Nechť b,c E G jsou inverzní prvky k danému prvku a E G, takže platí a • b = 1 = b • a a a • c = 1 = c • a. Pak máme
b = b • 1 = b • (a • c) = (b • a) • c = 1 ■ c = c,
takže b = c.
Z uvedeného tvrzení plyne, že existuje-li v monoidu (G, ■) k prvku a E G inverzní prvek, je tento prvek jediný a můžeme pro něj proto užít zvláštní označení. Zpravidla se tento inverzní prvek značí symbolem a-1.
Tvrzení. Nechť (G, ■) je monoid a nechť 1 je jeho jednotkový prvek. Nechť n je přirozené číslo a nechť a, ai, a2,..., an E G jsou libovolné invertibilní prvky monoidu (G, ■). Pak 1, a-1 a ai ■ Gt2 ■ ... ■ an jsou rovněž invertibilní prvky a platí rovnosti
i-1 = i,
(a-1)-1 = a,
Důkaz. Toto tvrzení plyne z již dokázané jednoznačnosti inverzních prvků a z faktů, že 1 je inverzním prvkem k 1, a je inverzním prvkem k a-1 a a"1 ■ ... -a^1 -a^1 je očividně inverzním prvkem k a\ • a<i • ... ■ an.
4
Nyní můžeme definovat ústřední pojem této kapitoly. 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, +), (Q - {0}, ■) jsou komutativní grupy.
Buď ještě jednou A libovolná množina a buď V (A) potenční množina množiny A. Definujeme na množině V {A) binární operaci -f- symetrické diference následujícím předpisem. Pro libovolné dvě podmnožiny B,C C A klademe
B + C = {B U C) - {B n C) = {B - C) U (C - B).
Lze se přesvědčit o tom, že tato operace je asociativní na V (A) a že dvojice (V(A),-^-) je komutativní grupa, neboť jednotkovým prvkem je zde prázdná podmnožina 0 a každá podmnožina B C A je zde inverzním prvkem sama k sobě.
Vezměme opět libovolnou množinu X a uvažujme dále libovolné bijekce / : X —>• X. Takovým bijekcím jsme v minulé kapitole říkali permutace množiny X. Množinu všech permutací množiny X jsme označili S(X). Pak skládání zobrazení o je operací též na množině S(X), takže dvojice (S(X), o) je monoid, a je to dokonce grupa, neboť pro každou permutaci / : X —>• X je inverzní zobrazení f~l : X —y X permutací, která je k ní inverzním prvkem. Uvedená grupa se nazývá grupa permutací množiny X. Jde o grupu, která obecně není komutativní.
Z posledního tvrzení této kapitoly bezprostředně plyne ještě následující fakt.
Důsledek. Nechť (G, ■) je monoid a nechť H C 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.
5