Grupa¶

Operácia¶

Skôr než sa dostaneme k pojmu binárna operácia, je dobré si ujasniť, čo v matematike znamená slovo operácia.

V bežnej (stredoškolskej) matematike pod operáciou rozumieme napríklad: - sčítanie: $a + b$, - odčítanie: $a - b$, - násobenie: $a \cdot b$, - delenie: $a / b$.

Tieto operácie: - berú nejaké vstupy (čísla), - vykonajú s nimi presné pravidlo, - vrátia výsledok.

V abstraktnej algebre sa snažíme tieto známe operácie zovšeobecniť a popísať ich bez ohľadu na to, či ide o čísla, vektory, matice alebo iné objekty.

Binárna operácia¶

Binárna operácia

Binárna operácia na množine $G$ je zobrazenie

\[ \circ : G \times G \to G \]

ktoré každým dvom prvkom $a, b \in G$ priradí práve jeden prvok z množiny $G$.

Čo presne znamená „binárna“¶

Slovo binárna znamená: - operácia pracuje presne s dvoma prvkami.

Porovnanie: - unárna operácia – pracuje s jedným prvkom (napr. $a \mapsto -a$), - binárna operácia – pracuje s dvoma prvkami (napr. $a + b$), - ternárna operácia – pracovala by s troma prvkami (v algebre sa skoro nepoužíva).

Takže: - $+$, $−$, $\cdot$, $/$ sú binárne operácie, - „zmena znamienka“ $a \mapsto -a$ nie je binárna, ale unárna.

Rozdiel medzi „klasickou“ a binárnou operáciou¶

V skutočnosti neexistuje rozdiel v princípe, rozdiel je len v presnosti zápisu.

Bežná matematika	Abstraktná algebra
„sčítanie čísel“	binárna operácia
„násobenie čísel“	binárna operácia
„$+$“	$\circ$
konkrétne čísla	ľubovoľné prvky množiny

V abstraktnej algebre: - nás nezaujíma, či ide o čísla, - zaujíma nás len to, ako sa prvky kombinujú.

Preto používame všeobecný symbol $\circ$, aby sme neboli viazaní na konkrétnu operáciu.

Prečo je dôležité $G \times G \to G$¶

Zápis [ \circ : G \times G \to G ] hovorí tri kľúčové veci:

Vstup sú dva prvky z $G$ $G \times G$ znamená „všetky usporiadané dvojice $(a, b)$“.
Výstup je jeden prvok Operácia dáva presne jeden výsledok.
Výsledok nesmie opustiť množinu Toto sa nazýva uzavretosť.

Uzavretosť – typická pasca¶

Uzavretosť

Ak výsledok operácie nepatrí späť do množiny, nejde o binárnu operáciu na tejto množine.

Príklady: - $+$ na $\mathbb{Z}$: $2 + 3 = 5 \in \mathbb{Z}$ → OK - $/$ na $\mathbb{Z}$: $1 / 2 \notin \mathbb{Z}$ → NIE JE binárna operácia na $\mathbb{Z}$

Grupa – myšlienka¶

Než dáme presnú definíciu, intuícia:

Grupa je množina prvkov, kde sa dajú prvky „spájať“ operáciou tak, že: - poradie zátvoriek nehrá rolu, - existuje „nič nerobiaci“ prvok, - každý prvok má svoj „opak“.

Definícia grupy¶

Grupa

Nech $G$ je neprázdna množina a $\circ$ binárna operácia na $G$. Dvojica $(G, \circ)$ sa nazýva grupa, ak platia:

Asociativita
Existencia neutrálneho prvku
Existencia inverzného prvku

1. Asociativita¶

Asociativita

Operácia $\circ$ je asociatívna, ak pre všetky $a, b, c \in G$ platí

\[ (a \circ b) \circ c = a \circ (b \circ c) \]

Čo to znamená slovami¶

Nezáleží na tom, ako prvky zoskupíme.

Pozor: - asociativita nie je to isté ako komutativita, - poradie prvkov nemeníme, len zátvorky.

Príklady: - sčítanie: $(2+3)+4 = 2+(3+4)$, - násobenie: $(2\cdot3)\cdot4 = 2\cdot(3\cdot4)$, - odčítanie: $(5-3)-1 \neq 5-(3-1)$ → nie je asociatívne.

2. Neutrálny prvok¶

Neutrálny prvok

Prvok $e \in G$ sa nazýva neutrálny prvok, ak pre všetky $a \in G$ platí

\[ a \circ e = e \circ a = a \]

Intuícia¶

Neutrálny prvok: - nemení hodnotu, - správa sa ako „0“ alebo „1“ podľa typu operácie.

Príklady: - pri sčítaní: $0$, - pri násobení: $1$.

3. Inverzný prvok¶

Inverzný prvok

Prvok $a' \in G$ je inverzný k $a \in G$, ak platí

\[ a \circ a' = a' \circ a = e \]

Intuícia¶

Inverzný prvok je taký, ktorý: - „zruší“ pôvodný prvok, - vráti nás späť k neutrálnemu prvku.

Príklady: - pri sčítaní: $a' = -a$, - pri násobení: $a' = \frac{1}{a}$, ak $a \neq 0$.

Príklady grúp¶

Kladné racionálne čísla s násobením¶

($\mathbb{Q}^+, \cdot$)

množina: $\mathbb{Q}^+$,
operácia: násobenie.
asociativita: platí,
neutrálny prvok: $1$,
inverzný prvok: $\frac{1}{q}$.

Preto $(\mathbb{Q}^+, \cdot)$ je grupa.

Celé čísla so sčítaním¶

($\mathbb{Z}, +$)

množina: $\mathbb{Z}$,
operácia: sčítanie.
asociativita: platí,
neutrálny prvok: $0$,
inverzný prvok: $-a$.

Preto $(\mathbb{Z}, +)$ je grupa.

Príklady známych grúp¶

Najprv si uveďme niekoľko príkladov štruktúr, ktoré sú grupami:

$(\mathbb{R}^+, \cdot)$ — kladné reálne čísla s násobením,
$(\mathbb{Q}, +)$ — racionálne čísla so sčítaním,
$(\mathbb{R}, +)$ — reálne čísla so sčítaním.

Tieto príklady ukazujú, že: - jedna množina môže tvoriť grupu s rôznymi operáciami, - operácia je rovnako dôležitá ako samotná množina.

Zvyškové triedy modulo $m$¶

Intuícia pojmu „modulo“¶

V bežnom živote sa s pojmom modulo stretávame napríklad: - hodiny na ciferníku (po 12 nasleduje opäť 1), - dni v týždni, - zvyšok po delení.

Napríklad: - $7 \equiv 2 \pmod{5}$, pretože po delení 5 zostane zvyšok 2, - $12 \equiv 0 \pmod{6}$.

Množina zvyškových tried¶

Zvyškové triedy modulo $m$

Nech $m \in \mathbb{N}$, $m \ge 2$. Množinu zvyškových tried modulo $m$ označujeme

\[ \mathbb{Z}_m = \{0, 1, 2, \dots, m-1\}. \]

Vysvetlenie¶

Neberieme všetky celé čísla, iba ich zvyšky po delení $m$.
Každé celé číslo patrí do presne jednej triedy.

Príklad: - pre $m = 5$:

$$ \mathbb{Z}_5 = {0,1,2,3,4} $$

Operácia sčítania modulo $m$¶

Sčítanie modulo $m$

Pre $a, b \in \mathbb{Z}$ definujeme

\[ a \oplus b = (a + b) \bmod m \]

Výsledkom je vždy prvok z množiny $\mathbb{Z}_m$.

Čo znamená „$\bmod m$“¶

najprv normálne sčítame,
potom vezmeme zvyšok po delení $m$.

Príklady pre $m = 5$: - $2 + 3 = 5 \Rightarrow 5 \bmod 5 = 0$, - $3 + 4 = 7 \Rightarrow 7 \bmod 5 = 2$.

Grupa $(\mathbb{Z}_m, +)$¶

Grupa zvyškových tried

Dvojica $(\mathbb{Z}_m, +)$ je grupa.

Overenie podmienok grupy¶

Uzavretosť Súčet dvoch zvyškov je opäť zvyšok modulo $m$.
Asociativita Sčítanie modulo $m$ je asociatívne, pretože obyčajné sčítanie je asociatívne.
Neutrálny prvok Neutrálnym prvkom je $0$.
Inverzný prvok Inverzným prvkom k $a \in \mathbb{Z}_m$ je

$$ a' = m - a \quad (\text{mod } m) $$

Napríklad v $\mathbb{Z}_5$: - inverz k $1$ je $4$, - inverz k $2$ je $3$.

Cayleyho tabuľka (operačná tabuľka)¶

Cayleyho tabuľka

Tabuľka, ktorá zobrazuje výsledky operácie medzi všetkými dvojicami prvkov množiny.

Príklad: sčítanie modulo 6¶

+	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

Ako tabuľku čítať¶

riadok = prvý sčítanec,
stĺpec = druhý sčítanec,
bunka = výsledok operácie modulo $m$.

Množina $\mathbb{Z}_m^\*$¶

Multiplikatívna množina modulo $m$

Označme

\[ \mathbb{Z}_m^\* = \{a \in \mathbb{Z}_m \mid \exists a^{-1} \text{ modulo } m\} \]

Intuícia¶

Nie každý prvok má násobkový inverz modulo $m$.

Príklad: - v $\mathbb{Z}_6$: - $2$ nemá inverz (nedá sa dostať $1$), - $5$ inverz má.

Príklad: $\mathbb{Z}_5^\*$¶

\[ \mathbb{Z}_5^\* = \{1,2,3,4\} \]

Tabuľka násobenia modulo 5¶

·	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Záver¶

Každý prvok má inverz,
preto $(\mathbb{Z}_5^\*, \cdot)$ je grupa.

Príklad: $\mathbb{Z}_7^\*$¶

\[ \mathbb{Z}_7^\* = \{1,2,3,4,5,6\} \]

Aj tu má každý prvok inverz, takže ide o grupu.

Dôležité upozornenie¶

Nie každé $\mathbb{Z}_m^\*$ je grupa

$(\mathbb{Z}_m^\*, \cdot)$ je grupa iba vtedy, keď má každý prvok inverz modulo $m$.

Typicky: - ak je $m$ prvočíslo → áno, - ak je $m$ zložené → nie vždy.

Jedinečnosť prvkov v grupe¶

Veta: Neutrálny prvok je jedinečný¶

Jedinečnosť neutrálneho prvku

V každej grupe existuje práve jeden neutrálny prvok.

Dôkaz

Predpokladajme, že v grupe existujú dva neutrálne prvky $e_1$ a $e_2$.

Keďže $e_1$ je neutrálny prvok, platí:

\[ e_1 \circ e_2 = e_2 \]

Zároveň, keďže $e_2$ je neutrálny prvok, platí:

\[ e_1 \circ e_2 = e_1 \]

Z oboch rovností dostávame:

\[ e_1 = e_2 \]

Preto neutrálny prvok v grupe existuje len jeden.

Poznámka

Tento dôkaz využíva iba definíciu neutrálneho prvku, nič viac o grupe nepotrebujeme.

Veta: Inverzný prvok je jedinečný¶

Jedinečnosť inverzného prvku

Ku každému prvku $g \in G$ existuje práve jeden inverzný prvok.

Dôkaz

Nech $g \in G$ a nech $\tilde{g}_1$ a $\tilde{g}_2$ sú inverzné prvky k $g$. Potom platí:

\[ g \circ \tilde{g}_1 = e \quad \text{a} \quad g \circ \tilde{g}_2 = e \]

Vynásobíme obe rovnosti zľava prvkom $\tilde{g}_2$:

\[ \tilde{g}_2 \circ (g \circ \tilde{g}_1) = \tilde{g}_2 \circ (g \circ \tilde{g}_2) \]

Použijeme asociativitu:

\[ (\tilde{g}_2 \circ g) \circ \tilde{g}_1 = (\tilde{g}_2 \circ g) \circ \tilde{g}_2 \]

Keďže $\tilde{g}_2$ je inverzný k $g$, platí:

\[ e \circ \tilde{g}_1 = e \circ \tilde{g}_2 \]

A keďže neutrálny prvok nič nemení:

\[ \tilde{g}_1 = \tilde{g}_2 \]

Inverzný prvok je teda jedinečný.

Poznámka

Preto používame jednoznačný zápis $g^{-1}$.

Veta: Inverz súčinu dvoch prvkov¶

Inverz súčinu

Nech $g_1, g_2 \in G$. Potom platí:

\[ (g_1 \circ g_2)^{-1} = g_2^{-1} \circ g_1^{-1} \]

Dôkaz

Overíme, že prvok $g_2^{-1} \circ g_1^{-1}$ je inverzný k $g_1 \circ g_2$.

Najprv sprava:

\[ (g_1 \circ g_2) \circ (g_2^{-1} \circ g_1^{-1}) \]

Asociativitou dostaneme:

\[ g_1 \circ (g_2 \circ g_2^{-1}) \circ g_1^{-1} \]

Keďže $g_2 \circ g_2^{-1} = e$, platí:

\[ g_1 \circ e \circ g_1^{-1} \]

A teda:

\[ e \]

Podobne vieme overiť aj opačné poradie, takže prvok $g_2^{-1} \circ g_1^{-1}$ je skutočne inverzný.

Častá chyba

Vo všeobecnej grupe neplatí:

\[ (g_1 \circ g_2)^{-1} = g_1^{-1} \circ g_2^{-1} \]

Poradie sa musí otočiť.

Inverz súčinu viacerých prvkov¶

Všeobecný tvar

Pre $g_1, g_2, \dots, g_n \in G$ platí:

\[ (g_1 \circ g_2 \circ \dots \circ g_n)^{-1} = g_n^{-1} \circ \dots \circ g_2^{-1} \circ g_1^{-1} \]

Poznámka

Inverz vzniká vždy tak, že: - otočíme poradie, - zoberieme inverz každého prvku.

Zhrnutie kapitoly: Grupa¶

Operácia je presné pravidlo, ktoré z daných vstupov vytvorí výstup. V abstraktnej algebre sa nezameriavame na konkrétne čísla, ale na spôsob kombinovania prvkov.
Binárna operácia na množine $G$ je zobrazenie

$$ \circ : G \times G \to G $$

ktoré: - pracuje s dvoma prvkami, - dáva práve jeden výsledok, - je uzavretá (výsledok zostáva v množine $G$).

Uzavretosť je kľúčová: ak výsledok operácie nepatrí späť do množiny, nejde o binárnu operáciu na tejto množine.

Grupa je dvojica $(G,\circ)$, kde:
$G$ je neprázdna množina,
$\circ$ je binárna operácia na $G$,
platia tri podmienky:
1. Asociativita
$$ (a \circ b)\circ c = a \circ (b \circ c) $$
1. Existencia neutrálneho prvku existuje $e$, že
$$ a \circ e = e \circ a = a $$
1. Existencia inverzného prvku ku každému $a$ existuje $a'$, že
$$ a \circ a' = a' \circ a = e $$
Asociativita sa týka iba zátvoriek, nie poradia prvkov (nezamieňať s komutativitou).
Neutrálny prvok:
nemení ostatné prvky,
je v grupe jedinečný.
Inverzný prvok:
„ruší“ daný prvok,
je ku každému prvku práve jeden,
zapisujeme ho ako $a^{-1}$.

Platí vzorec pre inverz súčinu:

$$ (g_1 \circ g_2)^{-1} = g_2^{-1} \circ g_1^{-1} $$

a všeobecne sa pri inverzii: - otáča poradie, - berie sa inverz každého prvku.

Zvyškové triedy modulo $m$:

$$ \mathbb{Z}_m = {0,1,2,\dots,m-1} $$

predstavujú triedy čísel s rovnakým zvyškom po delení $m$.

Sčítanie modulo $m$ robí z $\mathbb{Z}_m$ grupu:
neutrálny prvok je $0$,
inverz k $a$ je $m-a$ (mod $m$).
Cayleyho tabuľka prehľadne zobrazuje výsledky operácie medzi všetkými prvkami množiny.
Multiplikatívna množina $\mathbb{Z}_m^\*$ obsahuje len tie prvky, ktoré majú inverz modulo $m$.
Ak je $m$ prvočíslo, $(\mathbb{Z}_m^\*, \cdot)$ je grupa.
Ak je $m$ zložené, nie každý prvok má inverz → nemusí ísť o grupu.

Jedna veta na zapamätanie¶

Grupa je množina, kde vieme prvky spájať asociatívne, máme „nič nerobiaci“ prvok a ku každému prvku existuje presný opak.

Grupa¶

Operácia¶

Binárna operácia¶

Čo presne znamená „binárna“¶

Rozdiel medzi „klasickou“ a binárnou operáciou¶

Prečo je dôležité \(G \times G \to G\)¶

Uzavretosť – typická pasca¶

Grupa – myšlienka¶

Definícia grupy¶

1. Asociativita¶

Čo to znamená slovami¶

2. Neutrálny prvok¶

Intuícia¶

3. Inverzný prvok¶

Intuícia¶

Príklady grúp¶

Kladné racionálne čísla s násobením¶

Celé čísla so sčítaním¶

Príklady známych grúp¶

Zvyškové triedy modulo \(m\)¶

Intuícia pojmu „modulo“¶

Množina zvyškových tried¶

Vysvetlenie¶

Operácia sčítania modulo \(m\)¶

Čo znamená „\(\bmod m\)“¶

Grupa \((\mathbb{Z}_m, +)\)¶

Overenie podmienok grupy¶

Cayleyho tabuľka (operačná tabuľka)¶

Príklad: sčítanie modulo 6¶

Ako tabuľku čítať¶

Množina \(\mathbb{Z}_m^\*\)¶

Intuícia¶

Príklad: \(\mathbb{Z}_5^\*\)¶

Tabuľka násobenia modulo 5¶

Záver¶

Príklad: \(\mathbb{Z}_7^\*\)¶

Dôležité upozornenie¶

Jedinečnosť prvkov v grupe¶

Veta: Neutrálny prvok je jedinečný¶

Veta: Inverzný prvok je jedinečný¶

Veta: Inverz súčinu dvoch prvkov¶

Inverz súčinu viacerých prvkov¶

Zhrnutie kapitoly: Grupa¶

Jedna veta na zapamätanie¶