01ALG:Kapitola5: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
Řádka 1 088: Řádka 1 088:
 
Tedy $(\EE a\in A\supdot, b\in B\supdot)(c=ab)$.
 
Tedy $(\EE a\in A\supdot, b\in B\supdot)(c=ab)$.
 
Vezměme $\map{f\subnat}{AB}{AB\factorset A}$ a položme $f_B=f\subnat/B$.
 
Vezměme $\map{f\subnat}{AB}{AB\factorset A}$ a položme $f_B=f\subnat/B$.
Ukážeme, že $\map f_BB{AB\factorset A}$ je epimorfismus, tedy, že v každé třídě $A\supdot ab$ leží prvek z~$B$.
+
Ukážeme, že $\map {f_B}{B}{AB\factorset A}$ je epimorfismus, tedy, že v každé třídě $A\supdot ab$ leží prvek z~$B$.
 
Tedy i $a^\1ab=b$ je v~každé třídě.
 
Tedy i $a^\1ab=b$ je v~každé třídě.
 
Podlě věty o homomorfismu je $AB\factorset A\cong B\factorset{\ker f_B}$,
 
Podlě věty o homomorfismu je $AB\factorset A\cong B\factorset{\ker f_B}$,

Verze z 24. 1. 2012, 14:08

PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ALG

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ALGKarel.brinda 24. 8. 201014:49
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:48
Header editovatHlavičkový souborKarel.brinda 24. 10. 201019:54 header.tex
Kapitola0 editovatÚvodní poznámkyKarel.brinda 26. 8. 201015:03 alg_note.tex
Kapitola1 editovatTeorie množínSnilard 6. 1. 201100:37 alg_set.tex
Kapitola2 editovatRelaceKarel.brinda 25. 1. 201122:52 alg_rel.tex
Kapitola3 editovatUspořádané množinySedlam18 24. 1. 201213:18 alg_set2.tex
Kapitola4 editovatAlgebraSnilard 6. 1. 201100:59 alg_alg.tex
Kapitola5 editovatTeorie grupPitrazby 17. 2. 201202:51 alg_group.tex
Kapitola6 editovatOkruhyPitrazby 17. 2. 201203:00 alg_ring.tex
Kapitola7 editovatModuly a lineární algebryKosarvac 11. 11. 201115:50 alg_module.tex
Kapitola8 editovatTeorie svazůPitrazby 17. 2. 201214:19 alg_lattice.tex
Kapitola9 editovatPolynomy nad komutativními tělesyPitrazby 17. 2. 201214:21 alg_polynoms.tex
Kapitola10 editovatKonečná tělesaPitrazby 17. 2. 201214:24 alg_finite.tex

Zdrojový kód

%\wikiskriptum{01ALG}
 
\xxx{Teorie grup}
 
\xxxx{Grupoid. Pologrupa}
 
\define
Algebru $G=(M, \omega)$ s~binární operací $\omega$ nazýváme \defined[grupoid]{grupoid}.
Operaci $\omega$ obvykle značíme $\cdot$ a říkáme \defined[grupoid!multiplikativní]{multiplikativní grupoid},
nebo $+$ a říkáme \defined[grupoid!aditivní]{aditivní grupoid}.
 
\define
Grupoid $G=(M, \cdot)$ je asociativní neboli \defined[pologrupa]{pologrupa}, platí-li \defined[zákon!asociativní]{asociativní zákon}:
$(\AA a,b,c\in M)((ab)c=a(bc))$.
 
\def\aldotsa#1#2{a_{#1}\ldots a_{#2}}
\define
Definujeme \defined[součin!standardní]{standardní součin}:
$(a_1)=a_1$;
$(a_1 a_2)=a_1\cdot a_2$;
$(\aldotsa 1n\,a_{n+1})=(\aldotsa 1n)a_{n+1}$.
 
\lemma
Platí-li asociativní zákon, pak platí i \defined[zákon!asociativní!zobecněný]{zobecněný asociativní zákon}:
$$\bigl(\AA m,n\in\N\bigr)\bigl(\AA a_i\in M\bigr)
\bigl((\aldotsa 1m)(\aldotsa{m+1}{m+n})=(\aldotsa1{m+n})\bigr).$$
 
\proof
Důkaz provedeme matematickou indukcí podle $n$.
\begin{description}
\item[($n=1$)] Plyne z~definice standardního součinu.
\item[($n\rightarrow n+1$)]
$(\aldotsa 1m)(\aldotsa{m+1}{m+n}\, a_{m+n+1})
=(\aldotsa 1m)((\aldotsa{m+1}{m+n}) a_{m+n+1})
=\\
((\aldotsa 1m)(\aldotsa{m+1}{m+n})) a_{m+n+1}
=(\aldotsa 1{m+n}) a_{m+n+1}
=(\aldotsa 1{m+n+1})
$.
\end{description}
\QED
 
\define
Grupoid $G=(M, \cdot)$ je \defined[grupoid!komutativní]{komutativní grupoid},
 platí-li \defined[zákon!komutativní]{komutativní zákon}:
$(\AA a,b\in M)(ab=ba)$.
 
\define
$\pS n$ je množina všech permutací množiny $\widehat n$.
 
\lemma
V komutativní pologrupě platí \defined[zákon!komutativní!zobecněný]{zobecněný komutativní zákon}:
$$(\AA n\in\N)(\AA\pi\in\pS n)(\aldotsa 1n=\aldotsa{\pi(1)}{\pi(n)})$$
 
\proof
Platí, že každé $\pi\in\pS n$ je konečným složením sousedních transpozicí.
\QED
 
\define
V~pologrupě definujeme pro $a\in M$ a $n\in\Nz$ \defined[mocnina!přirozená]{přirozenou mocninu}:
$$a^n:=\underbrace{a\cdot a\cdot \cdots \cdot a}_{\text{$n$-krát}}.$$
V~aditivní pologrupě používáme označení $n\times a$.
 
\example
\begin{enumerate}
	\item $G = (\Q, \oplus), x \oplus y = \frac{x+y}{2}$ není asociativní.
	\item $(\C^{n,n}, +)$ je komutativní pologrupa.
\end{enumerate}
 
\example
\begin{enumerate}
\item \defined[pologrupy!číselné]{Číselné pologrupy}: nosičem je vždy podmnožina $\C$, operace jsou
 přirozené operace na číslech, tj. $(+)$ nebo $(\cdot)$.
 \begin{enumerate}
 \item $(\Z, +)$ je komutativní pologrupa nazývaná
  \defined[pologrupa!aditivní celých čísel]{aditivní pologrupa celých čísel}.
 \item $(\Z, \cdot)$ je komutativní pologrupa nazývaná
  \defined[pologrupa!multiplikativní celých čísel]{multiplikativní pologrupa celých čísel}.
 \item $(\N, \cdot)$ je komutativní pologrupa.
 \end{enumerate}
\item $(\Z, -)$ je grupoid.
\item Nechť $A\neq\emptyset$ a $M=\{\map fAA\}$ a $\omega=\circ$ je operace složení zorazení.
 Pak $(M, \circ)$ je pologrupa (nekomutativní) a nazývá se
  \defined[pologrupa!symetrická]{symetrická pologrupa} na $A$.
\item $(\C^{n,n}, \cdot)$ je pologrupa (nekomutativní).
\end{enumerate}
 
\define
\defined[prvek (algebra)!neutrální]{Neutrálním prvkem} grupoidu $G=(M, \cdot)$ rozumíme libovolný prvek
 $e\in M$ takový, že
$(\AA a\in M)(ea=ae=a)$.
Obyčejně značíme v~multiplikativním grupoidu $e:=1$ a nazýváme \defined[jednotka (grupoidy)]{jednotka}
 a v~aditivním $e:=0$ a nazýváme \defined[nula (grupoidy)]{nula}.
 
\lemma
Grupoid má nejvýše jeden neutrální prvek.
 
\proof
Nechť $e_1$, $e_2$ jsou neutrální prvky.
Pak $e_1=e_1e_2=e_2$.
\QED
 
\define
Nechť $G=(M, \cdot)$ je grupoid s~jednotkou.
\defined[prvek (algebra)!inverzní]{Inverzním prvkem} k~$a\in M$ je prvek $a^\1$ takový, že $a^\1a=aa^\1=1$.
 
\lemma
V~pologrupě s~jednotkou má každý prvek nejvýše jeden prvek inverzní.
 
\proof
Nechť $a_1$ a $a_2$ jsou inverzní k~$a$.
Pak $a_1=a_11=a_1(aa_2)=(a_1a)a_2=a_2$.
\QED
 
\define
Prvky, ke kterým existuje inverzní prvek, se nazývají \defined[prvek (algebra)!invertibilní]{invertibilní}
 nebo \defined[prvek (algebra)!regulární]{regulární}.
V aditivním grupoidu používáme název \defined[prvek (algebra)!opačný]{opačný prvek} a značku $-a$.
 
\define
Řekneme, že v grupoidu $G=(M,\cdot)$ \defined[grupoid!s dělením]{lze dělit}, platí-li, že
$$(\AA a,b\in M)(\EE x,y\in M)(ax=b\;\Land\;ya=b).$$
 
\define
Řekneme, že v grupoidu $G=(M,\cdot)$ \defined[grupoid!s krácením]{lze krátit}, platí-li, že
$$(\AA a,b,c\in M)\bigl((ac=bc \Lor ca=cb)\Limpl a=b\bigr).$$
 
\example
V~pologrupě $(\N,+)$ lze krátit, neboť $a+c=b+c\Limpl a=b$,
 ale nelze dělit, neboť $a+x=b$ nemá vždy řešení.
Má tedy smysl pojmy zavádět nezávisle, neboť krácení a dělení ze sebe nevyplývají.
 
\xxxx{Grupa}
 
\define
Pologrupa $G$, ve které lze jednoznačně dělit, se nazývá \defined[grupa]{grupa}.
Je-li navíc $G$ komutativní, nazývá se \defined[grupa!Abelova]{Abelova grupa}.
 
\theorem
V~libovolné grupě existuje jednotka a každý prvek má inverzní.
 
\proof
\begin{description}
 
\item[(existence jednotky)]
Víme, že $(\AA a,b)(\EE x,y)(ax=b\;\Land\;ya=b)$.
Tedy pro konkrétní $a$ existuje $e$ tak, že $ae=a$.
Ukážeme, že $e$ je jednotka.
Mějme libovolné $b\in M$.
Pak $(\EE y)(ya=b)$ a $be=(ya)e=y(ae)=ya=b$.
Tedy $e$ je univerzální pravá jednotka.
Symetricky ukážeme existenci univerzální levé jednotky $e'$.
Platí $e'=e'e=e=:1$, tedy existuje jen jedna jednotka a je pravá i levá.
 
\item[(invertibilita)]
Označme $a_P$ řešení $ax=1$ a $a_L$ řešení $ya=1$.
Pak $a_L=a_L1=a_L(aa_P)=(a_La)a_P=1a_P=a_P$.
Tedy existuje inverzní a je jeden.
 
\end{description}
\QED
 
\theorem
Nechť $G$ je pologrupa, ve které existuje pravá jednotka $e$ a libovolný prvek $a$ má zprava inverzní prvek $a^\1$
 vzhledem k~$e$.
Pak $G$ je grupa (tj. lze v~$G$ dělit).
 
\proof
$$ea=eae=eaa^\1(a^\1)^\1=ee(a^\1)^\1=e(a^\1)^\1=aa^\1(a^\1)^\1=ae=a,$$
tedy $e$ je i levou jednotkou.
\QED
 
\define
V grupě definujeme pro $a\in G^\bullet$ a pro $n\in\Z$ \defined[mocnina!celá]{celou mocninu}:
\begin{enumerate}
\item $a^n$ definované dříve;
\item $a^0:=1$;
\item $a^{-n}:=(a^\1)^n=(a^n)^\1$.
\end{enumerate}
 
V~aditivní grupě $G=(G^\bullet, +)$ používáme pro $n\geq1$ zápis $n\times a:=\underbrace{a+\cdots+a}_{\text{$n$-krát}}$.
 
\lemma
V~libovolné grupě platí $\left(a^n\right)^l=a^{nl}$,
v~Abelově grupě navíc $(ab)^n=a^nb^n$.
 
\example
\begin{enumerate}
\item $Z=(\Z; +)$ je \defined[grupa!aditivní celých čísel]{aditivní grupa celých čísel} a je Abelova.
\item $(\Q\sm\{0\},\cdot)$ je \defined[grupa!multiplikativní nenulových racionálních čísel]{%
 multiplikativní grupa nenulových racionálních čísel} a je Abelova.
\item Obdobně pro $\R\sm\{0\}$ a $\C\sm\{0\}$.
\item
 Nechť $A\neq\emptyset$, $M=\{\maptype fA{bij}A\}$.
 Pak $(M, \circ)$ je grupa nazývaná \defined[grupa!symetrická]{symetrická grupa} na $A$.
 Jednotkou je identické zobrazení a inverzním prvkem k $f$ je $f^\1$.
\item Symetrickou grupu na $\hatn n$ značíme $\pS n$.
\item $E=(\{1\}, \cdot)$ je nejmenší možná grupa nazývaná \defined[grupa!triviální]{triviální grupa}.
\item Pro $n\in\N$ a pro $k\in\hatn n$ definujeme $a_k=\cos\frac{2k\pi}n+i\sin\frac{2k\pi}n$ a nazýváme je\break
 \defined[komplexní $n$-té odmocniny z~1]{komplexní $n$-té odmocniny z~1}.
 Platí $a_ka_l=a_{k+l}$ (nebo $a_ka_l=a_{k+l-n}$ pokud $k+l>n$).
 Jednotka je $1=a_n$ a $a_k^\1=a_{n-k}$.
 Označme $\sqrt[n]1=\set{a_k}{k\in\hatn n}$.
 Pak $(\sqrt[n]1, \cdot)$ je Abelova grupa.
\item
 Nechť $V$ je vektorový prostor.
 Pak $(V, +)$ je Abelova grupa.
\end{enumerate}
 
\define
Pologrupa s~jednotkou se nazývá \defined[monoid]{monoid}.
 
\example
Monoid slov.
Nechť $\bbA\neq\emptyset$ je abeceda.
Pak $\alpha=a_1\ldots a_n$ je slovo.
Označme $\bbA^+$ množinu všech neprázdných slov, $\varepsilon$ prázdné slovo
 a $\bbA^*=\bbA^+\cup\{\varepsilon\}$ množinu všech slov.
Definujme operaci zřetězení $\circ$ tak, že $\alpha\circ\beta=a_1\ldots a_n\,b_1\ldots b_m$.
Pak $(\bbA^+, \circ)$ je pologrupa a $(\bbA^*, \circ)$ je monoid.
 
\xxxx{Podgrupa}
 
\define
Nechť $G=(M,\cdot)$ je grupa.
Řekneme, že množina $N\sse M$, $N\neq\emptyset$ je \defined[uzavřenost!v grupě]{uzavřená} v~$G$, platí-li:
$$(\AA a,b\in N)(ab^\1\in N).$$
 
\lemma
Je-li $N$ uzavřená v~$G=(M, \cdot)$, pak je $H=(N, \cdot)$ grupa.
 
\proof
Ukážeme, že $H$ splňuje základní vlastnosti grupy:
 
\begin{description}
\item[(existence jednotky)]
Vezmu libovolné pevné $a\in N$ a položím $b:=a$.
Pak vím, že $aa^\1=1\in N$.
 
\item[(invertibilita)]
K~libovolnému $b\in N$ položím $a:=1$.
Pak vím, že $1b^\1=b^\1\in N$.
 
\item[(uzavřenost vůči operaci)]
K~libovolným $a,c\in N$ položím $b:=c^\1$.
Pak vím, že $ac^\1=ab\in N$.
\end{description}
\QED
 
\define
$H$ definované v~předchozím lemmatu nazýváme \defined[podgrupa]{podgrupa} grupy $G$ a značíme $H\sg G$.
 
\lemma
$G\sg G$, $E\sg G$.
 
\define
\defined[podgrupa!netriviální]{Netriviální podgrupa} je taková $H\sg G$, že platí $H\neq G$ a $H\neq E$.
 
\theorem
Buď $G=(M,\cdot)$ grupa a pro $i\in I$ buď $H_i=(N_i,\cdot)$ systém jejích podgrup.
Potom $H:=\bigcap\limits_{i\in I}H_i=\Bigl(\bigcap\limits_{i\in I}N_i, \cdot\Bigr)\sg G$.
 
\proof
Nezbytně $1\in H_i$ tedy $H\neq\emptyset$.
$(\AA a,b\in H)(\AA i\in I)(a,b\in H_i)\Limpl (\AA a,b\in H)(ab^\1\in H_i)\Limpl ab^\1\in H$.
\QED
 
\define
Mějme $G=(M, \cdot)$ a $a\in M$.
 Pak označujeme $\anglevector a$ nejmenší podgrupu (ve smyslu inkluze) grupy $G$ obsahující $a$,
 tj. $\anglevector a=\bigcap\limits_{{H\sg G}\atop{\;a\in H,}} H$. Podgrupu $\anglevector a$ nazýváme \defined[podgrupa!cyklická]{cyklická podgrupa} grupy $G$.
 
\lemma
$\anglevector a\supdot=\set{a^k}{k\in\Z}.$
 
\proof
Je uzavřená vůči testovací podmínce, je podgrupou a je zjevně nejmenší.
\QED
 
 
\define
Nechť $G=(M, \cdot)$ je grupa, $N\sse M$ libovolná její podmnožina.
Pak definujeme \defined[podgrupa!generovaná množinou]{podgrupu generovanou $N$} jako
 $\anglevector N=\bigcap\set{H\sg G}{N\sse H\supdot}$.
Množinu $N$ nazýváme \defined[podgrupa!generátor]{generátor} $\anglevector N$.
 
\lemma
$\anglevector N\supdot=\set{a_1^{k_1}\cdots a_n^{k_n}}{n\in\Nz, a_i\in N, k_i\in\Z}=:K$.
 
\proof
Zjevně nemůže být $\anglevector N\supdot$ menší, stačí tedy ukázat, že $K$ je podgrupou:
Nechť $a=a_1^{k_1}\cdots a_n^{k_n}\in K$ a $b=b_1^{\ell_1}\cdots b_m^{\ell_m}\in K$ a potom
 $ab^\1=a_1^{k_1}\cdots a_n^{k_n}\,b_m^{-\ell_m}\cdots b_1^{-\ell_1}$.
\QED
 
\define
\begin{enumerate}
\item
 Nechť $H, K\sg G$.
 Pak definujeme \defined[součin!podgrup]{součin podgrup} $H\cdot K=\anglevector{H\supdot\cup K\supdot}$.
\item
 Nechť pro všechna $i\in I$ je $H_i\sg G$.
 Pak definujeme $\prod\limits_{i\in I}H_i=\Bigl\langle\bigcup\limits_{i\in I}H_i\supdot\Bigr\rangle$.
\end{enumerate}
 
\example
\begin{enumerate}
\item
 Nechť $S$ je množina sudých celých čísel.
 Pak $(S,+)\sg(\Z, +)$ je netriviální podgrupa.
 Ověříme uzavřenost: $(\AA a,b\in S)(a-b\in S)$, což ale zjevně platí.
\item
 $\pS n$ je grupa permutací $\hatn n$, nechť $\AM n$ je množina všech sudých permutací (přesná definice dále).
 Pak všechna $\pi,\sigma\in\AM n$ jsou složením sudého počtu transpozicí
 a inverze vznikne přečtením transpozic pozpátku.
 Tedy $(\AM n, \circ)\sg(\pS n, \circ)$, kterou nazýváme \defined[grupa!alternující]{alternující grupa}.
 
 $\abs{\pS n}=n!$; pro $n\geq 2$ je $\abs{\pA n}=n!/2$.
\item
 $(\sqrt[n]1, \cdot)\sg(\C, \cdot)$.
\end{enumerate}
 
\xxxx{Řád prvku grupy}
 
\define
Buď $G=(M,\cdot)$ grupa, $a\in M$.
\begin{enumerate}
\item
 $a$ má \defined[prvek (algebra)!řád!nekonečný]{nekonečný řád}, pokud $(\AA k,\ell\in\Z, k\neq\ell)(a^k\neq a^\ell)$.
\item
 Nemá-li $a$ nekonečný řád, pak má \defined[prvek (algebra)!řád!konečný]{konečný řád}
 a \defined[prvek (algebra)!řád]{řádem prvku} $a$ rozumíme $\min\set{r\in\N}{a^r=1}$.
\end{enumerate}
 
\lemma
Nechť $a\in G$ má řád $r$ a pro nějaké $k\in\Z$ je $a^k=1$.
Pak $r\mid k$.
 
\proof
V~celých číslech platí princip dělení se zbytkem (důkladně probereme níže):
$$(\AA k, r\in\Z, r\neq 0)(\EE \ell, R\in\Z, 0\leq R<r)(k=r\ell+R).$$
Platí $a^R=a^k(a^r)^{-\ell}=1$, tedy $R\in\N$ a $R<r$, což je spor s~tím, že $r$ je řád $a$.
Tedy $R=0$ a $r\mid k$.
\QED
 
\define
Buď $G=(M,\cdot)$ grupa.
Řekneme, že $G$ je
\begin{enumerate}
\item \defined[grupa!periodická]{periodická}/\defined[grupa!torzní]{torzní}, má-li libovolný její prvek konečný řád;
\item \defined[grupa!bez torze]{bez torze}, pokud má každý prvek různý od $1$ nekonečný řád;
\item \defined[grupa!smíšená]{smíšená} v~ostatních případech.
\end{enumerate}
 
\lemma
Libovolná konečná grupa je periodická.
 
\example Ukážeme, že nekonečné grupy mohou být periodické, bez torze i smíšené.
\begin{enumerate}
\item
Označme $G_n=(\sqrt[n]1,\cdot)$ a $M=\bigcup\limits_{n\in\N}G_n=\set{\cos2q\pi+i\sin2q\pi}{q\in\Q}$.
Pak $M$ je uzavřená v~$(\C,\cdot)$: $a,b\in M$, $a\in G_k$, $b\in G_\ell$.
$(ab^\1)^{kl}=(a^k)^\ell(b^\ell)^{-k}=1\cdot1=1$, tedy $ab^\1\in G_{k\ell}$.
Zjevně $(M, \cdot)$ je nekonečná grupa a řád prvku $a\in G_k$ je nejvýše roven $k$.
Tedy $(M, \cdot)$ je nekonečná a periodická.
\item
$(\Z,+)$ je zjevně bez torze, neboť pro $z\in\Z$ je $k\times n=0 \Lequiv z=0$.
\item
$(\C,\cdot)$ je smíšená, neboť $(M,\cdot)\sg(\C,\cdot)$ je periodická a např. číslo $2\in\C$ má nekonečný řád.
\end{enumerate}
 
\theorem (algoritmus dělení, o dělení se zbytkem)
$$(\AA k, \ell\in\Z, \ell\neq0)(\EE_1 q,r\in\Z)(k=q\ell+r \;\Land\; 0\leq r<\abs\ell).$$
 
\proof
\begin{description}
 
\ditem{existence}
Položme $q':=\intpart{\frac k{\abs\ell}}$, tedy $q'\leq\frac k{\abs\ell}<q'+1$.
Pak $q'\abs\ell\leq k<q'\abs\ell+\abs\ell$, tedy pro $r:=k-q'\abs\ell$ platí $0\leq r<\abs\ell$.
Položme $q:=q'\sgn\ell$, pak platí $q\ell+r=q'\ell\sgn\ell+r=q'\abs\ell+k-q'\abs\ell=k$.
 
\ditem{jednoznačnost}
Mějme druhou dvojici $\tilde q, \tilde r$ splňující tvrzení věty a pro spor nejprve předpokládejme,
 že $q\neq\tilde q$.
Potom $\abs{\tilde r-r}=\abs{(k-\tilde q\ell)-(k-q\ell)}=\abs{q\ell-\tilde q\ell}=
 \abs\ell\abs{q-\tilde q}\geq\abs\ell\cdot1$.
Ale $(\AA r_1,r_2\in\Z, 0\leq r_{1,2}\leq\abs\ell-1)(\abs{r_1-r_2}\leq\abs\ell-1)$, což je spor.
Tedy $q=\tilde q$ a $r=k-q\ell=k-\tilde q\ell=\tilde r$.
 
\end{description}
\QED
 
\define
\defined[největší společný dělitel]{Největší společný dělitel} $k,\ell\in\Z$ je takové $d\in\Z$, že:
\begin{enumerate}
\item $d\mid k$, $d\mid\ell$;
\item $d'\mid k \Land d'\mid\ell \Limpl d'\mid d$.
\end{enumerate}
 
\remark
Je-li číslo $d$ největší společný dělitel, pak i číslo $-d$ je největší společný dělitel.
 
\theorem
K libovolným číslům $k,\ell\in\Z$ existuje největší společný dělitel $d$ a existují $u,v\in\Z$ takové, že
$$d=uk+v\ell.$$
 
\proof
Nechť $k,\ell\neq0$.
Označme $D:=\set{uk+v\ell}{u,v\in\Z}\sse\Z$.
Množina $D$ je uzavřená na součty a $\Z$-násobky.
Definujme $d:=\min\set{x\in D}{x>0}$ a ukážeme, že je největší společný dělitel.
 
$k=dq+r$, kde $q\in\Z$ a $0\leq r<d$.
$r=k-dq$, kde $k\in D$ a $dq\in D$, tedy $r\in D$ a $r<d$, tedy musí $r=0$, jinak by $r>0\Land r<d$.
Tedy $d\mid k$ a sjeným postupem $d\mid\ell$.
 
Nechť $d'\mid k$ a $d'\mid\ell$.
Z~toho vyplývá, že $d'$ dělí všechna čísla v~$D$, tedy i $d'\mid d$.
\QED
 
\define
Nezáporný největší společný dělitel $k$ a $\ell$ budeme značit $\gcd(k,\ell)$.
Řekneme, že $k$ a $\ell$ jsou \defined[nesoudělnost]{nesoudělná}, když $\delta(k,\ell)=1$.
 
\define
\defined[násobek!nejmenší společný]{Nejmenší společný násobek} čísel $k$ a $\ell$ označujeme $\lcm(k,\ell)$
 a je to nejmenší takové $m\in\N$, že $k\divides m$ a $\ell\divides m$.
 
\xxxx{Cyklické grupy}
 
\define
Řekneme, že grupa $G$ je \defined[grupa!cyklická]{cyklická}, je-li rovna některé ze svých cyklických podgrup, tedy
$(\EE a\in G)(G=\anglevector a=\set{a^n}{n\in\Z})$.
Prvek $a$ nazýváme \defined[grupa!cyklická!generátor]{generátor} grupy $G$.
 
\lemma
\begin{enumerate}
\item Každá cyklická grupa je Abelova.
\item Každá cyklická grupa je nejvýše spočetná.
\end{enumerate}
 
\example
\begin{enumerate}
\item $Z=(\Z,+)$ je nekonečná cyklická grupa generovaná prvkem $1$ nebo $-1$:
 $$Z=(\Z,+)=\anglevector 1=\anglevector\1.$$
\item Pro každé $n\in\N$ je $\sqrt[n]1$ konečná cyklická grupa s~řádem $n$,
 generátorem je např. $a_1=\cos\frac{2\pi}n+i\sin\frac{2\pi}n$.
\end{enumerate}
 
\theorem
Libovolná podgrupa cyklické grupy je cyklická.
 
\proof
$G=\anglevector a$, $H\sg G$. Pro $H=E$ je generátorem jednotka.
Označme $p=\min\set{i\in\N}{a^i\in H}$.
Ukážeme, že $\anglevector {a^p}=H$.
\begin{description}
\item[($\sse$)]
 Zřejmé.
\item[($\supseteq$)]
 Vezměmě libovolné $x\in H$.
 Pak $(\EE q\in\Z)(x=a^q)$.
 Označme $d=\delta(p,q)=up+vq$.
 Potom $a^d=a^{up+vq}=\left(a^p\right)^u\cdot\left(a^q\right)^v\in H$.
 $p$ je nejmenší, tedy $d\geq p$, ale $d\mid p$, tedy $d\leq p$, což dohromady dává $p=d$.
 Současně $d\mid q$, tedy $q=pr$ a $a^q=\left(a^p\right)^r\in\anglevector{a^p}$.
\end{description}
\QED
 
\lemma
Nekonečná cyklická grupa $\anglevector a$ má právě 2 generátory, a to $a$ a $a^\1$.
 
\theorem
Buď $G=\anglevector a$ cyklická grupa řádu $n$ a nechť $1\leq k\leq n$.
Potom $a^k$ generuje $G$ právě tehdy, když jsou $k$ a $n$ nesoudělná.
 
\proof
\begin{description}
\item[($\Rightarrow$)]
 $G=\anglevector{a^k}$. Tedy $a=\qlb{a^k}^u$. Z~toho vyplývá, že $a^{ku-1}=1$.
 Každý generátor má řád $n$, tedy $a$ má řád $n$, tedy $ku-1=vn$, tedy $uk-vn=1$, tedy $\delta(k,n)=1$.
\item[($\Leftarrow$)]
 Z~nesoudělnosti existují $u$, $v$ tak, že $uk+vn=1$.
 Dále $a=a^1=a^{uk+vn}=\qlb{a^k}^u\qlb{a^n}^v=\qlb{a^k}^u1^v=\qlb{a^k}^u$.
 Tedy pro libovolné $x\in G$ je $x=a^r=\qlb{a^{uk}}^r$.
\end{description}
\QED
 
\define
Definujeme \defined[funkce!Eulerova]{Eulerovu funkci} $\map\phi\N\N$, kde $\phi(n)$ je počet čísel
 z~$\hatn n$ nesoudělných s $n$.
 
\lemma
$n$ je prvočíslo právě tehdy, když $\phi(n)=n-1$.
 
\xxxx{Kongruence}
 
\define
Mějme grupoid $G=(M,\cdot)$ a mějme ekvivalenci $\equiv$ na $M$.
Pak pro libovolné $x\in M$ definujeme $T_x$ jako třídu ekvivalence podle $\equiv$, která obsahuje $x$,
 tedy $x\in T_x\in M\factorset\equiv$ (korektnost je zajištěna disjunktností tříd ekvivalence).
 
\define
Buďte $G=(M,\cdot)$ grupoid a $\equiv$ ekvivalence na $G$.
Řekneme, že $\equiv$ je \defined[kongruence (grupy)]{kongruence} na $G$, platí-li, že
$$\bigl(\AA a,b,c,d\in M\bigr)\bigl((a\equiv b\Land c\equiv d)\Limpl ac\equiv bd\bigr).$$
 
\define
Buďte $G=(M,\cdot)$ grupoid a $\equiv$ kongruence na $G$.
Pak definujeme součin tříd ekvivalence $M\factorset\equiv$ jako $T_a\cdot T_b=T_{ab}$.
(Korektnost definice je zajištěna definující vlastností kongruence.)
 
\define
Buďte $G=(M,\cdot)$ grupoid a $\equiv$ kongruence na $M$.
Pak definujeme \defined[faktorgrupoid]{faktorgrupoid} $G$ jako $G\factorset\equiv:=(M\factorset\equiv, \cdot)$
 
\theorem
Buďte $G=(M,\cdot)$ grupoid a $\equiv$ kongruence na $M$.
Pak $G\factorset\equiv$
je pologrupa, resp.
je komutativní, resp.
má jednotkou,
resp. je grupa,
má-li odpovídající vlastnost i $G$.
 
\proof
Všechny body jsou obdobné, ukážeme asociativitu (pologrupa).
Nechť $T_a, T_b, T_c\in M\factorset\equiv$.
Pak $(T_a T_b)T_c=T_{ab}T_c=T_{(ab)c}=T_{a(bc)}=T_aT_{bc}=T_a(T_bT_c)$.
\QED
 
\define
Mějme $Z=(\Z,+)$ a libovolné $m\in\Z$.
Pak definujeme \defined[kongruence!modulo $m$]{kongruenci modulo $m$} (značíme $\equiv_m$) následovně:
$$a\equiv_m b\iff(\EE s\in\Z)(a-b=sm).$$
Třídy $Z\factorset{\equiv_m}$ se nazývají \defined[třídy!zbytkové]{zbytkové třídy} po dělení $m$.
Faktorgrupu $Z\factorset{\equiv_m}$ označujeme $Z_m$.
 
\lemma
Relace $\equiv_m$ je kongruence na $Z$.
 
\proof
Ukážeme, že $\equiv_m$ je ekvivalence a splňuje definiční podmínku kongruence.
\begin{description}
\ditem{reflexivita} Platí $a-a=0=0m$.
\ditem{symetrie} Nechť $a-b=sm$. Pak $b-a=-sm=(-s)m$.
\ditem{tranzitivita} Nechť $a-b=sm$ a $b-c=tm$. Pak $a-c=(a-b)+(b-c)=sm+tm=(s+t)m$.
\ditem{kongruence} Nechť $a-b=sm$ a $c-d=tm$. Pak $(a+c)-(b+d)=sm+tm=(s+t)m$.
\end{description}
\QED
 
\example
\begin{description}
\ditem{$m=0$} $a\equiv_0 b\Lequiv 0\mid a-b\Lequiv a=b$, tedy každý prvek má svou jednoprvkovou třídu.
\ditem{$m=1$} $a\equiv_1 b\Lequiv 1\mid a-b$, tedy všechny prvky leží ve stejné třídě.
\end{description}
 
\lemma
Pro $m\geq 1$ platí, že dvě celá čísla jsou v~jedné třídě $\Z\factorset{\equiv_m}$ právě tehdy,
 když dávají stejný zbytek po dělení $m$.
Tedy tříd ekvivalence podle $\equiv_m$ je $m$.
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
 $a_1, a_2\in\Z$, $a_1\EH m a_2$.
 Pak $a_1=mq_1+r_1$, $a_2=mq_2+r_2$ a $a_1-a_2=sm$.
 Odečtením prvních dvou máme $a_1-a_2=m(q_1-q_2)+(r_1-r_2)=sm$, $r_1-r_2=m(q_1-q_2-s)$, tedy $m\mid r_1-r_2$,
 ale protože $0\leq r_{1,2}<m$, je nutně $r_1=r_2$.
\ditem{$\Leftarrow$}
 Víme, že $r_1=r_2$, tedy $a_1-a_2=m(q_1-q_2)$, tedy $s=q_1-q_2$ a $a_1\equiv_m a_2$.
\ditem{$\abs{\Z\factorset{\equiv_m}}=m$}
 Toto je zjevné z předchozího.
\end{description}
\QED
 
\lemma
Faktorgrupa $Z_m$ grupy $Z = (\Z, +)$ podle $\equiv_m$ je cyklická s generátorem $T_1$, tedy $Z_m=\anglevector{T_1}$.
 
\xxxx{Homomorfismus}
 
\define
Buďte $G_1=(M_1, \cdot)$, $G_2=(M_2, \cdot)$ grupoidy.
Řekneme, že $\map h{M_1}{M_2}$ je \defined[homomorfismus (grupoidy)]{homomorfismus} grupoidů, pokud platí:
$$(\AA x,y\in M_1)\bigl(h(xy)=h(x)h(y)\bigr)$$
a budeme též značit $\map h{G_1}{G_2}$.
 
\define
Homomorfismus $h$ se nazývá:
\begin{enumerate}
\item \defined[monomorfismus (grupoidy)]{monomorfismus}, je-li prostý (injekce);
\item \defined[epimorfismus (grupoidy)]{epimorfismus}, je-li na (surjekce);
\item \defined[izomorfismus (grupoidy)]{izomorfismus}, je-li prostý a na (bijekce);
\item \defined[endomorfismus (grupoidy)]{endomorfismus}, je-li $G_1=G_2$.
\item \defined[automorfismus (grupoidy)]{automorfismus}, je-li izomorfní endomorfismus (bijekce $G\rightarrow G$).
\end{enumerate}
 
\define
Existuje-li izomorfismus $\map h{G_1}{G_2}$, nazýváme grupoidy \defined[grupoid!izomorfismus]{izomorfní}
 a značíme $G_1\cong G_2$.
 
\example
$G_1:=(\R^+, \cdot)$, $G_2:=(\R, +)$. Definujeme $\map h{G_1\supdot}{G_2\supdot}$ jako $h(x)=\ln x$.
Zjevně $h(xy)=h(x)+h(y)$, tedy $h$ je morfismus a z analýzy víme, že je bijekcí.
Tedy $G_1\cong G_2$.
 
\define
Mějme $G=(M, \cdot)$ grupu a kongruenci $\equiv$ na $G$.
Definujeme \defined[zobrazení!přirozené]{přirozené zobrazení}
 (\defined[epimorfismus (grupoidy)!přirozený]{přirozený epimorfismus}) $\map{h\subnat}{G}{G\factorset\equiv}$
 jako $h\subnat(x)=T_x$.
 
\lemma
$h\subnat$ je epimorfismus.
 
\proof
Platí $h\subnat(xy)=T_{xy}=T_xT_y=h\subnat(x)h\subnat(y)$, tedy $h$ je homomorfismus.
Současně pro každou třídu $T_x$ platí $T_x=h\subnat(x)$, tedy je na.
\QED
 
\theorem
Libovolné 2 nekonečné cyklické grupy jsou izomorfní.
Libovolné 2 cyklické grupy s~počtem prvků $n\in\N$ jsou izomorfní.
 
\proof
Mějme libovolnou $G=\anglevector a$ nekonečnou.
Ukážeme, že $G\cong Z=(\Z, +)$.
Definujeme $\map hGZ$ jako $h(a^n)=n\times1=n$.
Pak $h$ je prosté zobrazení ($m\neq n \Lequiv a^m\neq a^n$), a neboť je $G$ nekonečná, je na.
Operace $\cong$ na grupách je ekvivalencí, tedy pro libovolné $G_1$, $G_2$
 je $G_1\cong Z$ a $G_2\cong Z$, tedy $G_1\cong G_2$.
\QED
 
 
\define
Nechť $G=(M,\cdot)$ je grupoid, $N\sse M$.
Pak $H=(N,\cdot)$ nazveme \defined[podgrupoid]{podgrupoid} grupoidu $G$, pokud
 je $H$ grupoid, tedy $(\AA x,y\in H)(xy\in H)$.
Značíme $H\sg G$.
 
\lemma
Buďte $G_1$, $G_2$ grupoidy, $\map h{G_1}{G_2}$ homomorfismus.
Pak $h(G_1)\sg G_2$.
 
\theorem (o homomorfismu)
Buďte $G_1$, $G_2$ grupoidy, $\map h{G_1}{G_2}$ homomorfismus.
Pak existuje kongruence (označovaná $\equiv_h$) na $G_1$ taková, že
$h(G_1)\cong {G_1}\factorset{\equiv_h}$, kde $h(G_1)$ značí obor hodnot $h$.
 
\proof
Definujeme $\equiv_h$ jako $x\equiv_h y\Lequiv h(x)=h(y)$, tedy $\equiv_h$ je zjevně ekvivalence
 (je definovaná pomocí rovnosti)
Nechť $a\equiv_hb$ a $c\equiv_hd$.
Pak $h(ac)=h(a)h(c)=h(b)h(d)=h(bd)$, tedy $ac\equiv_h bd$ a $\equiv_h$ je kongruence.
 
Definujeme $\map g{{G_1}\factorset{\equiv_h}}{h(G_1)}$ jako $g(T_x)=h(x)$.
Definice je korektní, neboť $T_x=T_y \Lequiv h(x)=h(y)$, z~toho též vyplývá, že $g$ je prosté.
Z definice $g$ pomocí $h$ plyne, že pokryje celé $h(G_1)$, tedy je na.
Je homomorfismus, neboť $g(T_xT_y)=g(T_{xy})=h(xy)=h(x)h(y)=g(T_x)g(T_y)$.
\QED
 
\remark
Všimněme si, jak souvisí korektnost definice s~prostotou.
Pokud by bylo $T_x=T_y$ a zároveň $h(x)\neq h(y)$, pak definice není korektní.
Pokud by bylo $h(x)=h(y)$ a zároveň $T_x\neq T_y$, pak zobrazení není prosté.
 
\theorem
Nechť $\map h{G_1}{G_2}$ je homomorfismus grupoidů
a buď $g$ zobrazení definované v~důkazu předchozí věty.
Pak $h\subnat=g^\1h$.
 
\theorem
Buďte $G_1$, $G_2$ grupoidy, $\map h{G_1}{G_2}$ homomorfismus.
Je-li $G_1$ pologrupa, resp. je komutativní, resp. má jednotku, resp. je grupa,
 má tutéž vlastnost i grupoid $h(G_1)$.
 
\proof
Důkaz všech bodů je obdobný, ukážeme přenos jednotky.
Nechť $1\in G_1$, pak $h(1)$ je jednotkou v~$h(G_1)$.
Neboť pro libovolné $y\in h(G_1)$ existuje $x\in G_1$ takové, že $y=h(x)$.
Potom $yh(1)=h(x)h(1)=h(x1)=h(x)=y$. Podobně zleva.
\QED
 
\define
Buď $G=(M,\cdot)$ grupa, $A,B\sse M$. Pak definujeme \defined[součin!podmnožin]{součin podmnožin} $A\cdot B$ jako
 $A\cdot B:=\set{ab}{a\in A, b\in B}$.
(Vztah mezi součinem podmnožin a podgrup osvětlíme později.)
Je-li $B=\{b\}$, pak značíme $AB=Ab=\set{xb}{x\in A}$.
 
\define
Buď $H\sg G$ podgrupa grupy, definujeme následující 2 relace:
\begin{enumerate}
\item $a\HE Hb\Lequiv b^\1a\in H$;
\item $a\EH Hb\Lequiv ab^\1\in H$;
\end{enumerate}
 které nazýváme \defined[ekvivalence indukovaná podgrupou!levá]{levá},
 resp. \defined[ekvivalence indukovaná podgrupou!pravá]{pravá ekvivalence} indukovaná podgrupou $H$.
 
\lemma
Indukované relace jsou ekvivalence.
 
\proof
\begin{description}
\ditem{reflexivita}
 $a\HE H a\Lequiv a^\1a\in H$, ale $a^\1a=1$.
\ditem{symetrie}
 $a\HE Hb \Lequiv b^\1a\in H\supdot  \Lequiv\qlb{b^\1a}^\1=a^\1b\in H\supdot
 \Lequiv a\HE Hb$.
\ditem{tranzitivita}
 $a\HE Hb \Land b\HE Hc \Lequiv b^\1a,c^\1b\in H\supdot \Limpl c^\1bb^\1a\in H\supdot \Limpl
 c^\1a\in H\supdot \Lequiv a\HE Hc$.
\end{description}
Podobně lze ukázat totéž pro $\EH H$.
\QED
 
\example
Zvolme $b=1$. Pak $a\HE H1\Lequiv a\in H$ a současně $a\EH H1\Lequiv a\in H$,
 tedy $H$ je jedna ze tříd ekvivalence podle obou indukovaných ekvivalencí.
 
\lemma
Označme $T^L_a$ resp. $T^P_a$ třídu ekvivalence podle $\HE H$, resp. $\EH H$ obsahující $a\in G\supdot$.
Potom $T^L_a=aH\supdot$ a $T^P_a=H\supdot a$.
 
\proof
Opět lemma ukážeme pro levou ekvivalenci.
$T^L_a$ je třída $\HE H$ obsahující $a$.
Mějme libovolné $x\in G$.
Pak $x\in T^L_a \Lequiv x\HE Ha \Lequiv a^\1x\in H\supdot \Lequiv (\EE h\in H\supdot)(a^\1x=h)
 \Lequiv (\EE h\in H\supdot)(x=ah) \Lequiv x\in aH\supdot$.
\QED
 
\theorem
\begin{enumerate}
\item Libovolné 2 třídy rozkladů dle $\HE H$ či $\EH H$ jsou (množinově) ekvivalentní.
 (\uv{Každá třída má stejně prvků.})
\item Levý rozklad je (množinově) ekvivalentní s~pravým rozkladem.
 (\uv{Levých a pravých tříd je stejný počet.})
\end{enumerate}
 
\proof
\begin{enumerate}
 
\item
 Libovolné 2 levé třídy $aH\supdot$ a $bH\supdot$.
 Definujme $\map f{aH\supdot}{bH\supdot}$ jako $f(x)=ba^\1x$.
 Nechť $x=ah$, pak $f(x)=bh\in bH\supdot$ tedy definice je korektní.
 Mějme $y=bh$, pak $y=f(x) \Lequiv ba^\1x \Lequiv h=a^\1x \Lequiv x=ah\in aH\supdot$.
 Podobně dokážeme, že všechny pravé jsou ekvivalentní.
 Z~tranzitivity a z~toho, že $H\supdot$ je v~obou faktorizacích, vyplývá,
 že všechny levé třídy jsou ekvivalentní se všemi pravými.
\item 
 Definujeme $\map g{M\factorset{\HE H}}{M\factorset{\EH H}}$ jako $g(aH\supdot)=H\supdot a^\1$.
 Zjevně je na, neboť $a^\1$ projde celé $G$ právě tehdy, když $a$ projde celé $G$.
 Platí:
 $g(aH\supdot)=g(bH\supdot) \Lequiv H\supdot a^\1=H\supdot b^\1 \Lequiv a^\1\EH H b^\1
 \Lequiv a^\1b\in H\supdot \Lequiv (a^\1b)^\1=b^\1a\in H\supdot \Lequiv a\HE Hb \Lequiv aH\supdot=bH\supdot$,
 tedy $g$ je prosté (směr $\Rightarrow$) a definice je korektní (směr $\Leftarrow$).
\end{enumerate}
\QED
 
\define
Počtu rozkladových tříd podle indukovaných ekvivalencí se říká \defined[podgrupa!index]{index} podgrupy $H$.
 
\theorem (Lagrange)
Součin řádu a indexu libovolné podgrupy $H$ konečné grupy $G$ je roven řádu $G$.
 
\proof
Všechny třídy mají počet prvků, jako je řád $H$, a je jich tolik, jako je index $H$.
\QED
 
\consequence
\begin{enumerate}
\item
 Řád libovolné podgrupy konečné grupy $G$ dělí řád $G$.
\item
 Řád libovolného prvku konečné grupy $G$ dělí řád $G$.
\end{enumerate}
 
\consequence
Má-li grupa $G$ prvočíselný řád, je cyklická a nemá žádné netriviální podgrupy.
Všechny grupy s~prvočíselným řádem $p$ jsou izomorfní.
 
\proof
Grupa není triviální (má řád nejméně 2).
Vezmu $a\neq1$.
Pak řád prvku $a$ je $p$, (jednotkový řád má jen jednotka), tedy $a$ generuje $G$.
\QED
 
\theorem
Buď $G$ cyklická grupa řádu $n$ a nechť $k\mid n$.
Potom existuje právě jedna podgrupa grupy $G$ řádu $k$.
 
\proof
\begin{description}
\ditem{existence}
Nechť $a\in G$ je generátor grupy.
Položme $H:=\anglevector{a^{n/k}}$.
Pak $\qlb{a^{n/k}}^k=1$ a platí, že pokud $\qlb{a^{n/k}}^\ell=1$, tak $n\ell/k=sn$, tedy $\ell=ks$ a $\ell\geq k$.
 
\ditem{jednoznačnost}
Nechť $K\sg G$ je řádu $k$. Pak $K=\anglevector{a^\ell}$ a $\qlb{a^\ell}^k=1$ a $\ell k=sn=skn/k$
 a tedy $\ell=sd$ a $a^\ell=\qlb{a^{n/k}}^s\in H$.
Tedy $K\sg H$ a z~rovnosti počtu prvků plyne $K=H$.
\end{description}
\QED
 
\define
Buď $G$ grupa.
Řekneme, že podgrupa $H\sg G$ je \defined[podgrupa!normální]{normální}
 (\defined[podgrupa!invariantní]{invariantní}), pokud $\HE H$ a $\EH H$ splývají,
a značíme $H\nsg G$.
 
\lemma
$E\nsg G$; $G\nsg G$.
 
\proof
\begin{enumerate}
\item
$a\HE Eb\Lequiv b^\1a=1 \Lequiv a=b$; $a\EH Eb\Lequiv ab^\1=1 \Lequiv a=b$.
\item
$a\HE Gb\Lequiv b^\1a\in G$, což platí pro libovolné $a$, $b$; stejně tak pro $\EH G$.
\end{enumerate}
\QED
 
\lemma
Je-li grupa $G$ Abelova, je libovolná její podgrupa $H\sg G$ normální.
 
\theorem
Rozklad grupy $G$ je rozkladem podle kongruence právě tehdy, je-li rozkladem podle některé normální podgrupy $H\nsg G$.
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
Nechť $\equiv$ je kongruence na grupě $G=(M,\cdot)$.
Vezměme třídu $T_1$ a $a,b\in T_1$.
Pak $a\equiv1$ a $b\equiv1$, tedy $ab\equiv1$. Také $a^\1\equiv a^\1$, tedy $1\equiv a^\1$.
 
Ukážeme, že $H=(T_1,\cdot)\sg G$ je normální.
Vezměme lib. $x\in M$.
Pak $x\in T_a \Lequiv x\equiv a \Lequiv xa^\1\equiv1 \Lequiv xa^\1\in H\supdot \Lequiv (\EE h\in H\supdot)(xa^\1=h)
 \Lequiv (\EE h\in H\supdot)(x=ha) \Lequiv x\in H\supdot a$.
Budeme-li násobit $a^\1$ zleva, dostaneme $x\in aH\supdot$.
Tedy $T_a=aH\supdot=H\supdot a$, což znamená, že $H\nsg G$ a $(\equiv)=(\HE H)=(\EH H)$
 
\ditem{$\Leftarrow$}
Nechť $H\nsg G$, ukážeme, že $\EH H$ je kongruence.
Mějme $a,b,c,d\in M$ takové, že $a\EH Hb$ a $c\EH Hd$.
Potom $ac(bd)^\1=acd^\1b^\1$.
Označme $h:=cd^\1\in H\supdot$, pak existuje $h'\in H\supdot$ takové, že $ah=h'a$.
Tedy celkově dostáváme $ac(bd)^\1=ahb^\1=h'ab^\1\in h'H\supdot=H$.
\end{description}
\QED
 
\xxxx{Vnitřní automorfismy}
 
\define
Nechť $\AM G\supdot$ je množina všech automorfismů na $G$.
Pak definujme $\AM G=(\AM G\supdot,\circ)$.
 
\lemma
Nechť $G$ je grupa.
Pak $\AM G$ je grupa a $\AM G\sg \pS G$.
 
\proof
Součin (složení) 2 automorfismů je automorfismus, existuje jednotka (identita) a každý automorfismus má inverzní.
Nechť $x,y\in G\supdot$, $\alpha\in\AM G\supdot$,
 pak $\alpha^\1(xy)=\alpha^\1(\alpha(\alpha^\1(x))\alpha(\alpha^\1(y)))
 =\alpha^\1(\alpha(\alpha^\1(x)\alpha^\1(y)))=\alpha^\1(x)\alpha^\1(y)$,
 tedy inverzní je opět morfismem.
\QED
 
\lemma
Nechť $a\in M$, $\AL a(x)=axa^\1$.
Pak $\AL a$ je automorfismus.
 
\proof
\begin{description}
 
\ditem{morfismus}
Pro libovolné $x,y\in M$ platí $\AL a(x)\AL a(y)=axa^\1\,aya^\1=axya^\1=\AL a(xy)$.
 
\ditem{bijekce}
Ukážeme, že $\AL {a^\1}$ je inverzní k~$\AL a$, tj. $(\AA x\in M)(\AL {a^\1}\AL a=\AL a\AL{a^\1}=\id)$.
Pro všechna $x\in M$ platí $\qlb{\AL{a^\1}\AL a}(x)=\AL{a^\1}(axa^\1)=a^\1axa^\1a=1x1=x$,
 obdobně $\qlb{\AL a\AL{a^\1}}(x)=x$.
 
\end{description}
\QED
 
\define
Automorfismus $\alpha$ na $G$ je \defined[automorfismus!vnitřní]{vnitřní},
 právě když $(\EE a\in G\supdot)(\alpha(x)=axa^\1)$.
Takový automorfismus značíme $\alpha_a$.
 
Označme $\IM G\supdot$ množinu všech vnitřních automorfismů.
 
\lemma
$\IM G=(\IM G\supdot, \circ)\sg \AM G$ je grupa.
 
\proof
Jednotkou je $\alpha_1$, $\alpha_1(x)=1x1^\1=x$.
$(\alpha_a\alpha_b^\1)(x)=ab^\1xba^\1=(ab^\1)x(ab^\1)^\1=\alpha_{ab^\1}(x)$
\QED
 
\theorem
Podgrupa $H$ grupy $G$ je normální právě tehdy, je-li uzavřená vůči všem vnitřním automorfismům, tj.
$$H\nsg G \iff (\AA a\in G\supdot)(\AA x\in H\supdot)(\AL a(x)\in H\supdot).$$
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
Mějme $H\nsg G$ a libovolné $a\in G\supdot$ a $x\in H\supdot$.
Pak $ax\in aH\supdot=H\supdot a \Limpl (\EE h\in H\supdot)(ax=ha) \Limpl axa^\1\in H\supdot$.
\ditem{$\Leftarrow$}
Mějme libovolný $x\in aH\supdot$, tedy $x=ah=aha^\1a=\AL a(h)a$ a neboť $\AL a(h)\in H\supdot$, je $x\in aH\supdot$
a $aH\supdot \sse H\supdot a$.
Obrácenou inkluzi dokážeme obdobně, tedy $aH\supdot=H\supdot a$.
\end{description}
\QED
 
\remark
Věta dává návod, jako ověřit, že $H$ je normální.
Ale nesmíme opomenout ověřit, že $H$ vůbec je podgrupou.
 
\define
Buď $G$ grupa.
Řekneme, že $x,y\in G\supdot$ jsou \defined[konjungace]{konjungované},
 existuje-li $a\in G\supdot$ takové, že $y=\AL a(x)$.
Značíme $x\EH Ky$.
 
\lemma
Relace konjungovanosti je ekvivalence na $G$.
 
\consequence
Podgrupa $H$ grupy $G$ je normální právě tehdy, je-li sjednocením nějakých tříd konjungovaných prvků.
 
\define
Buďte $G_1$, $G_2$ grupy, $\map h{G_1}{G_2}$ homomorfismus.
\defined[homomorfismus (grupoidy)!jádro]{Jádrem} homomorfismu $h$
 rozumíme množinu $\ker h:=h^\1(\{1\})=\set{h\in G_1\supdot}{h(x)=1}$.
 
\lemma
Buďte $G_1$, $G_2$ grupy, $\map h{G_1}{G_2}$ homomorfismus.
Pak $\ker h\nsg G_1$.
 
\proof
\begin{description}
 
\ditem{je podgrupa}
Mějme libovolné $x,y\in\ker h$, tj. $h(x)=h(y)=1$.
Pak $h(xy^\1)=h(x)h(y^\1)=h(x)h(y)^\1=11^\1=1$.
 
\ditem{je uzavřená vůči automorfismům}
Nechť $a\in G_1\supdot$, $x\in\ker h$.
Pak $h(axa^\1)=h(a)h(x)h(a^\1)=h(a)h(a^\1)=h(aa^\1)=h(1)=1$.
 
\end{description}
\QED
 
\lemma
Mějme $H\nsg G$, faktorgrupu $G\factorset H$ a přirozený epimorfismus $h\subnat(x)=T_x$.
Pak $\ker h\subnat=H$.
 
\proof
$\ker h\subnat=\set{x\in G\supdot}{T_x=T_1}$, ale $T_1=H\supdot$, tedy $\ker h\subnat=H\supdot$.
\QED
 
\theorem
Normální podgrupy grupy $G$ jsou právě všechna jádra homomorfismů na $G$, tj.
$$H\nsg G \iff (\EE h, \text{$h$ je homomorfismus na $G$})(H=\ker h).$$
 
\proof
Věta shnuje předchozí 2~tvrzení.
\QED
 
\lemma
Homomorfismus $\map h{G_1}{G_2}$ je prostý právě tehdy, je-li $\ker h=\{1\}$.
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
Obrazem jednoprvkové množiny je nejvýše jednoprvková množina a
 $1$ je v~jádru pro všechny homomorfismy.
\ditem{$\Leftarrow$}
Nechť $\ker h=\{1\}$.
Mějme $x,y\in G_1$ takové, že $h(x)=h(y)$.
Pak $1=h(x)h(y^\1)=h(xy) \Limpl xy^\1\in\ker h \Limpl xy^\1=1 \Limpl x=y$.
\end{description}
\QED
 
\lemma
Nechť $\map h{G_1}{G_2}$ je homomorfismus.
Pak $a\EH{\ker h}b$ právě tehdy, je-li $h(a)=h(b)$.
 
\proof
$a\EH{\ker h}b \Lequiv ab^\1\in\ker h \Lequiv h(ab^\1)=1 \Lequiv h(a)=h(b)$.
\QED
 
\theorem (o homomorfismu pro grupy)
Nechť $\map h{G_1}{G_2}$ je homomorfismus grup.
Potom $h(G_1)\cong {G_1}\factorset{\ker h}$.
 
\proof
$h(G_1)\cong {G_1}\factorset{\equiv_h}={G_1}\factorset{\equiv_{\ker h}}$.
\QED
 
\theorem
Buď $G$ grupa a buďte $H_i\nsg G$ pro $i\in I$.
Potom $$A:=\bigcap_{i\in I} H_i\nsg G \quad\text a\quad B:=\prod_{i\in I} H_i\nsg G.$$
 
\proof
\begin{description}
\ditem{průnik}
Mějme libovolné $a\in G\supdot$ a $x\in A$.
Pak $(\AA i\in I)(x\in H\supdot) \Limpl (\AA i)(\AL a(x)\in H_i) \Limpl \AL a(x)\in A$.
 
\ditem{součin}
Mějme libovolné $a\in G\supdot$ a $x\in B$. Platí $B=\anglevector{\bigcup_I H_i\supdot}$.
Pak $x=a_1^{k_1}\cdots a_n^{k_n}$, kde $k_j\in\Z$ a $(\AA j)(\EE i_j)(a_j\in H_{j_i}\supdot)$.
Protože $H_{j_i}$ je podgrupa, je $a_i^{k_i}\in H_{j_i}\supdot$ a protože, je normální, je
 $\AL a(a_i^{k_i})\in H_{j_i}\supdot$.
A konečně $\AL a(x)=\AL a(a_1^{k_1}\cdots a_n^{k_n})=\AL a(a_1^{k_1})\cdots \AL a(a_n^{k_n})$.
Tedy každý prvek součinu je ve sjednocení podgrup, tedy je i v~produktu podgrup.
\end{description}
\QED
 
\lemma (o tečce)
Buď $G$ grupa, $A\nsg G$ a $B\sg G$.
Potom $(AB)\supdot=A\supdot B\supdot$.
 
\proof
$AB=\anglevector{A\supdot\cup B\supdot}$, ale $A\supdot B\supdot=\set{ab}{a\in A\supdot, b\in B\supdot}$.
\begin{description}
\ditem{$\sse$}
 Ukážeme, že $A\supdot B\supdot$ je uzavřená v~grupě $G$.
 Platí $A\cup B\sse A\supdot B\supdot$
 Zvolme libovolné $x,y\in A\supdot B\supdot$, $x=a_1b_1$, $y=a_2b_2$.
 Potom $xy^\1=a_1b_1(a_2b_2)^\1
  =a_1\underbrace{b_1b_2^\1a_2^\1(b_1b_2^\1)^\1}_{\AL{b_1b_2^\1}(a_2^\1)\in A\supdot}b_1b_2^\1
  =\tilde{a}\tilde{b}$, kde $\tilde a\in A\supdot$ a $\tilde b\in B\supdot$.
 Tedy $A\supdot B\supdot$ je podgrupa obsahující $A\supdot\cup B\supdot$.
 Ale $AB$ je nejmenší taková, tedy inkluze platí.
 
\ditem{$\supseteq$}
 V~$AB$ jsou všechny součiny $x_1\cdots x_n$, kde $x_i\in A\cup B$ tedy i všechny součiny tvaru $ab$.
\end{description}
\QED
 
\define
Buď $G$ grupa.
Pak $C_G:=\set{c\in G}{(\AA x\in M)(cx=xc)}$ nazveme \defined[grupa!centrum]{centrum grupy}
 (tedy centrum grupy obsahuje právě ty prvky grupy, které komutují s každým prvkem.)
 
\lemma
Buď $G$ grupa, $C_G$ její centrum. Pak:
\begin{enumerate}
\item
 je-li $G$ Abelova, je $C_G=G$;
\item
 $C_G\nsg G$;
\item
 $G\factorset{C_G}\cong \IM G$.
\end{enumerate}
 
\proof
\begin{enumerate}
\item
 V~Abelově grupě komutují každé 2 prvky.
\item
 Ukážeme, že $C_G$ je uzavřená vůči všem vnitřním automorfismům.
 Mějme libovolné $a\in G\supdot$ a $c\in C_G$.
 Pak $\AL a(c)=aca^\1=caa^\1=c\in C_G$.
\item
 Definujme $\map hG{\IM G}$ jako $h(a)=\alpha_a$, $h$ je epimorfismus.
 Pak $I_G=h(G)\cong G\factorset{\ker h}$.
 Platí $x\in\ker h\Lequiv {h(x)=\AL1=\id_G} \Lequiv (\AA y\in G\supdot)(xyx^\1=y) \Lequiv
  (\AA y\in G\supdot)(xy=yx) \Lequiv x\in C_G$, tedy $\ker h=C_G$ a $I_G\cong G\factorset{C_G}$.
\end{enumerate}
\QED
 
\theorem (o izomorfismu)
Buď $G=(M,\cdot)$ grupa, $A,B\sg G$.
Je-li $A\nsg AB$, potom $A\cap B\nsg B$ a $AB\factorset A\cong B\factorset{(A\cap B)}$.
 
\proof
Třídy $AB\factorset A$ jsou tvaru $A\supdot c$, kde $c\in (AB)\supdot=A\supdot B\supdot$.
Tedy $(\EE a\in A\supdot, b\in B\supdot)(c=ab)$.
Vezměme $\map{f\subnat}{AB}{AB\factorset A}$ a položme $f_B=f\subnat/B$.
Ukážeme, že $\map {f_B}{B}{AB\factorset A}$ je epimorfismus, tedy, že v každé třídě $A\supdot ab$ leží prvek z~$B$.
Tedy i $a^\1ab=b$ je v~každé třídě.
Podlě věty o homomorfismu je $AB\factorset A\cong B\factorset{\ker f_B}$,
 ale $\ker f_B=\set{x\in B}{f_B(x)=T_1=A}=\set{x\in B}{x\in A}=A\cap B$.
\QED
 
\define
Grupa, která nemá netriviální normální podgrupy, tj. $H\nsg G \Limpl H=G \Lor H=E$,
 se nazývá \defined[grupa!jednoduchá]{jednoduchá}.
 
\example
\begin{enumerate}
\item $E$ je jednoduchá.
\item $G$ o $p\in P$ prvcích jsou jednoduché, současně jsou cyklické, tedy Abelovy.
\end{enumerate}
 
\theorem
Buď $G\neq E$ Abelova grupa.
Potom $G$ je jednoduchá právě tehdy, má-li prvočíselný řád $p$.
 
\proof
\begin{description}
\ditem{$G$ je cyklická}
Nebyla-li by cyklická, obsahovala by netriviální podgrupu, která by byla normální,
 neboť všechny by byly normální (netriviální podgrupou by bylo libovolné $\anglevector a$, kde $a\neq1$).
\ditem{$G$ je konečná}
 Pokud není konečná, pak $G\cong Z=(\Z, +)$,
 ale např. $S=(\mathbb S, +)\nsg Z$ a $S$ odpovídá nějaké netriviální podgrupa $G$.
\ditem{neex. $1\neq q\mid p$}
Podle předházející věty existuje podgrupa $H$ řádu $q$, která je v~Abelově normální, a tedy $G$ není jednoduchá.
\end{description}
\QED
 
\xxxx{Grupy permutací}
 
\define
Buď $A$ množina a $M$ množina všech bijekcí $A\rightarrow A$.
Pak $\pS A(M,\circ)$ je grupa nazývaná \defined[grupa!symetrická]{symetrická grupa}.
Označme $\epsilon$ identitu v~$\pS A$.
 
\define
\defined[grupa!permutací]{Grupa permutací} je libovolná podgrupa symetrické grupy $\pS A$.
 
\theorem (Cayley)
Libovolná grupa je izomorfní s~nějakou grupou permutací.
 
\proof
Mějme $G=(M,\cdot)$, $a\in M$; definujeme $\map{\pi_a}MM$ jako $\pi_a(x)=ax$.
Pro libovolné $y\in M$ řešme $\pi_a(x)=ax=y$, dostaneme jedno řešení $x=a^\1y$, tedy $\pi_a$ je bijekce (permutace).
 
Definujme $\map hM{\pS M}$ jako $h(a)=\pi_a$ a ukážeme, že $h$ je homomorfismus:
Mějme $a,b,x\in M$; pak $h(ab)(x)=\pi_{ab}(x)=abx=\pi_a(bx)=\pi_a(\pi_b(x))=(\pi_a \pi_b)(x)=(h(a)h(b))(x)$.
 
Ukážeme, že je $h$ je monomorfní (prostý):
$\ker h=\set{a\in M}{h(a)=\epsilon}$, $(\AA x\in M)(\epsilon(x)=x)$, $\pi_a(x)=\epsilon(x)=x$, $a=1$.
 
Platí $G\cong h(G)\sg\pS M$. Tedy $h(G)$ je grupa permutací.
\QED
 
\remark
Cayleyova věta se dá formulovat i následovně: Libovolnou grupu lze izomorfně vnořit do symetrické grupy.
 
\remark
Pro $M=\hatn n$ se $G$ izomorfně vnoří do $\pS{\hatn n}=:\pS n$.
 
\remark
$\pi\in\pS n$ zapisované $\pi=\qlb{{1\atop p_1}{\cdots\atop\cdots}{n\atop p_n}}$ je zobrazení.
 
\example
$\pi\in\pS 8$, $\pi=\qlb{{1\atop2}{2\atop4}{3\atop5}{4\atop1}{5\atop4}{6\atop7}{7\atop6}{8\atop8}}$ lze zapsat jako
 $1\rarr2\rarr4(\rarr1); 3\rarr5(\rarr3); 6\rarr7(\rarr6); 8(\rarr8)$, ale zkráceně jako $(124)(35)(67)(8)$.
Zápis současně vyjadřuje složení cyklů a můžeme vynechat cykly s~1 prvkem.
Tedy můžeme psát $\pi=(124)(35)(67)$.
 
\define
Mějme $\pi\in\pS n$.
Pak $\pi$ je \defined[cyklus]{cyklus}, pokud $\pi=(p_1p_2...p_k)$, $1\leq k\leq n$, $p_k$ jsou různá.
Cykly jsou \defined[cyklus!nezávislost]{nezávislé}, pokud neobsahují společný prvek.
 
\lemma
Libovolná permutace lze rozepsat jako součin nezávislých cyklů.
 
\lemma
$$(k_1\cdots k_p)=(k_1k_p)(k_1k_{p-1})\cdots(k_1k_3)(k_1k_2).$$
 
\proof
Obrázkem.
\QED
 
\consequence
Transpozice generují $\pS n$.
(Každá permutace lze zapsat jako součin transpozic.)
 
\remark
Lze ukázat, že i sousední transpozice generují $\pS n$.
Dále lze ukázat, že pro jakékoli $n$ existují 2 permutace,
 které generují $\pS n$, a to např. $\tau=(12)$ a $\pi=(123\ldots n)$.
 
\theorem
Buď $n\in\N$ a $\sigma,\pi\in\pS n$,
$\sigma=(k^1_1\cdots k^1_{p_1})\cdots(k^m_1\cdots k^m_{p_m})$ je rozklad na (ne nutně nezávislé) cykly.
Potom $\AL\pi(\sigma)=(\pi(k^1_1)\cdots \pi(k^1_{p_1}))\cdots(\pi(k^m_1)\cdots \pi(k^m_{p_m}))$
 
\proof
\begin{description}
\ditem{$m=1$}
Máme $\sigma=\qlb{k_1\ldots k_p}$, označme $\sigma_\pi:=\qlb{\pi\qlb{k_1}\ldots\pi\qlb{k_p}}$,
 tedy chceme $\AL\pi\qlb\sigma=\sigma_\pi$, což, protože $\pi$ je bijekce, je ekvivalentní
 $\AL\pi\qlb\sigma\circ\pi=\sigma_\pi\circ\pi$.
 
Ukážeme, že $\qlb{\AA k\in\hatn n}\qlb{\AL\pi\qlb\sigma\qlb{\pi\qlb k}=\sigma_\pi\qlb{\pi\qlb k}}$.
To jest $\qlb{\pi\sigma\pi^\1}\qlb{\pi\qlb k}=\pi\qlb{\sigma\qlb k}?=\sigma_\pi\qlb{\pi\qlb k}$.
 
Nechť $k=k_i$, pak $\sigma\qlb k=k_{i+1}$ (položíme $k_{p+1}:=k_1$), tedy $\pi\qlb{\sigma\qlb{k}}=\pi\qlb{k_{i+1}}$.
Současně $\sigma_\pi\qlb{\pi\qlb{k_i}}=\pi\qlb{k_{i+1}}$, což jsme potřebovali.
 
Pro $k\neq k_i$ jsou obě strany rovny $\pi\qlb{k}$.
 
\ditem{$m\in\N$}
S využitím případu $m=1$ dostaneme
\begin{eqnarray*}
&\AL\pi\qlb{\qlb{k^1_1\ldots k^1_{p_1}}\ldots\qlb{k^m_1\ldots k^m_{p_m}}}=
\AL\pi\qlb{k^1_1\ldots k^1_{p_1}}\ldots\AL\pi\qlb{k^m_1\ldots k^m_{p_m}}=\\
&\qlb{\pi\qlb{k^1_1}\ldots \pi\qlb{k^1_{p_1}}}\ldots\qlb{\pi\qlb{k^m_1}\ldots \pi\qlb{k^m_{p_m}}}.
\end{eqnarray*}
 
\end{description}
\QED
 
\consequence
$(\AL\pi(\sigma))(\pi(k))=\pi(\sigma(k))$,
$\sigma=\qlb{{1\atop p_1}{\cdots\atop\cdots}{n\atop p_n}}$,
pak $\AL\pi\qlb\sigma=\qlb{{\pi\qlb1\atop \pi\qlb{p_1}}{\cdots\atop\cdots}{\pi\qlb{n}\atop \pi\qlb{p_n}}}$.
 
\lemma
Libovolná podgrupa $H$ grupy $G$, která má index 2, je normální.
(Index je počet rozkladových tříd $G\factorset H$).
 
\proof
Jedna ze tříd je $H$, druhá tedy nutně $G\sm H$.
Rozklad je tedy jednoznačný.
\QED
 
\define
Označme $\pA n$ grupu sudých permutací (ověření, že je grupa, je triviální). Pak
$\pA n$ nazýváme \defined[grupa!alternující]{alternující (pod)grupa}.
 
\consequence
$\pA n\nsg \pS n$.
 
\lemma
Nechť $A\sg B\sg G$.
Pak $A\nsg G\Limpl A\nsg B$.
 
\proof
Lze jednoduše ukázat pomocí uzavřenosti na vnitřní automorfismy.
\QED
 
\example
\begin{description}
\ditem{$n=1$} $\pA1=\pS1=E$.
\ditem{$n=2$} $\pA2=E$.
\ditem{$n\geq3$} $\pA n$ je netriviální normální podgrupa.
\ditem{$n=3$} $\pS3=\{\id, (12), (13), (23), (123), (132)\}$ a $\pA3=\{\id, (123), (132)\}$ má prvočíselný počet prvků
 a je jednoduchá.
\ditem{$n=4$} $\pA4$ má řád 12 a není jednoduchá, neboť obsahuje např. $\pp K4:=\{\id, (12)(34), (13)(24), (23)(14)\}$
 a platí $\pp K4\nsg\pA4$.
Předně je $\pp K4$ uzavřená na skládání, součin 2 se vždy zobrazí na třetí,
 např. $(12)(34)\cdot(13)(24)=(23)(14)$.
A každá permutace je sama sobě inverzní, tedy $\pp K4$ je grupa.
 
 
$\pp K4$ jsou všechny $(ij)(k\ell)$, kde tato 4 čísla jsou různá.
Ukážeme, že $\pp K4$ je uzavřená vůči vnitřním automorfismům.
$\AL\pi((ij)(k\ell))=(\pi(i)\pi(j))(\pi(k)\pi(\ell))$, ale neboť $\pi$ je bijekce,
 jsou to opět čísla $1,2,3,4$, jenom případně přeházená.
 
$\pp K4$ nazýváme \defined[grupa!Kleinova]{Kleinova grupa} (matracová grupa - podle otáčení matrace).
 
Všimněme si, že také $\pp L2:=\{\id, (12)(34)\}\nsg\pp K4$
 (má polovinu prvků, tedy index rozkladu podle $\pp L2$ je 2 a je normální).
Ale $\pp L2\not\nsg\pA4$.
\end{description}
 
\theorem
Alternující grupy $\pA n$ jsou pro $n\neq 4$ jednoduché (tedy nemají netriviální normální podgrupu).
 
\proof
Pro $n\leq3$ jsme platnost ukázali v~předchozím příkladě.
Tedy nechť $n\geq5$.
Mějme libovolnou $H\nsg\pA n$, $H\neq E$. Ukážeme, že $H=\pA n$.
Důkaz se rozpadá do 3 kroků.
\begin{description}
\ditem{v~$H$ existuje 3cykl $(u,v,w)$}
 Vezměme $\pi\in H\supdot$ takovou, která mění nejmenší co počet prvků a není identitou.
 Určitě není transpozice (ta je lichá).
 Sporem, nechť $\pi\neq(u,v,w)$.
 Pak rozklad na nezávislé cykly může vypadat následovně:
 \begin{enumerate}
 \item $\pi=(pq)(rs)\cdots$. Pak existuje páté číslo, označme jej $t$.
 \item $\pi=(pqr\cdots)\cdots$ A mění ještě nejméně 2~další čísla $s,t$.
 \end{enumerate}
 Mějme $\varrho:=(rst)\in\pA n$ sudou permutaci.
 Pak $\AL\varrho(\pi)=\varrho\pi\varrho^\1\in H\supdot$ (neboť $H$ je normální).
 V prvním případě $\AL\varrho(\pi)=(pq)(st)\cdots\neq\pi$ a ve druhém $\AL\varrho(\pi)=(pqs)\cdots\neq\pi$.
 Definujeme $\sigma:=\pi^\1(\varrho\pi\varrho^\1)\in H$ a není jednotková.
 
 Ukážeme, že $\sigma$ nechává na místě více prvků než $\pi$.
 
 (2) Mějme libovolné $k\in\hatn n$ tak, že $\pi(k)=k$. Pak $k\not\in\{p,q,r,s,t\}$ a $\varrho(k)=k$.
 Pak $\sigma(k)=k$, neboť žádná z~permutací $\pi$, $\pi^\1$, $\varrho$ a $\varrho^\1$ nemění $k$.
 Ale $\pi(p)=q$ a $\sigma(p)=p$ TODO.
 Tedy $\sigma$ mění nejméně o 1 méně čísel než $\pi$.
 
 Obdobně pro (1). Tedy $\sigma$ nechává na místě více čísel než $\pi$.
 
\ditem{je-li v~$H$ jeden 3cyklus $(u,v,w)$, jsou tam všechny 3cykly}
 Zvolme libovolný 3cyklus $(p,q,r)$.
 Položme $\pi:=({u\atop p}{v\atop q}{w\atop r}{y\atop Y}{z\atop Z})$.
 Nutně existují takové $y,z,Y,Z$, že $\pi$ je sudá, tj. $\pi\in\pA n$.
 Potom $\AL\pi((u,v,w))=(\pi(u),\pi(v),\pi(w))=(p,q,r)$ a neboť $H$ je normální, je $(p,q,r)\in H$.
 
\ditem{3cykly generují $\pA n$} Ukážeme, že součin $\pi$ 2 libovolných transpozicí lze rozložit na 3cykly.
 Je-li $\pi=(p,q)(p,r)=(prq)$ je 3cyklus.
 Je-li $\pi=(p,q)(r,s)=(p,r,s)(p,q,s)$.
 Je-li $\pi=(p,q)(p,q)=(p,q,r)(r,q,p)$ pro libovolné $r$.
 
\end{description}
\QED
 
 
\xxxx{Kartézský a direktní součin grup}
 
\define
Mějme $G_1\cldc G_n$ grupy, $G_i=(M_i,\cdot)$.
Označme $M:=M_1\times\cdots\times M_n$ a definujme operaci $\cdot$: $(a_1\cldc a_n)\cdot(b_1\cldc b_n):=(a_1b_1\cldc a_nb_n)$.
Jednotkou bude $1_M=(1\cldc1)$ a inverzním prvkem $(a_1\cldc a_n)^\1=(a_1^\1\cldc a_n^\1)$.
Grupu $G:=(M,\cdot)$ nazýváme \defined[součin!kartézský grup]{kartézský součin grup}
 a značíme $G=\mathop{\rm\times}\limits_1^n G_i$..
 
\define
Buďte $G$ grupa a $A,B\sg G$.
Řekneme, že $G$ je \defined[součin!podgrup!direktní]{direktní součin} podgrup $A,B$,
 je-li zobrazení $\map f{A\times B}G$, $f(x,y)=xy$ izomorfismem grup.
Značíme $G=A\odot B$.
 
\remark
Direktní součin lze přirozeně zobecnit na konečné i spočetné systémy podgrup.
 
\lemma
Zobrazení $f$ z~předchozí definice je homomorfismus právě tehdy, když $(\AA a\in A\supdot, b\in B\supdot)(ab=ba)$.
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
$ab=f(\anglecouple ab)=f(\anglecouple1b\anglecouple a1)=f(1,b)f(a,1)=ba$.
 
\ditem{$\Leftarrow$}
$f(\anglecouple{a_1}{b_1}\anglecouple{a_2}{b_2})=f(\anglecouple{a_1a_2}{b_1b_2})=a_1a_2b_1b_2=a_1b_1a_2b_2=f(\anglecouple{a_1}{b_1})f(\anglecouple{a_2}{b_2})$.
\end{description}
\QED
 
\lemma
Zobrazení $f$ z~předchozí definice je \uv{na} právě tehdy, když $A\supdot B\supdot=G\supdot$.
 
\proof
$A\supdot B\supdot$ je z~definice obor hodnot $f$.
\QED
 
\lemma
Je-li $f$ z~předchozí definice homomorfismus, pak je $f$ prostý právě tehdy, je-li $A\supdot\cap B\supdot=\{1\}$.
 
\proof
\begin{description}
\ditem{$\Rightarrow$}
Víme, že $\ker f=\{\anglecouple11\}$.
Nechť $c\in A\cap B$.
Pak triviálně $c\in A$ a $c^\1\in B$ a $\anglecouple c{c^\1}\in A\times B$.
A neboť $f(\anglecouple c{c^\1})=cc^\1=1$, je $\anglecouple c{c^\1}=\anglecouple11$, tedy hlavně $c=1$.
 
\ditem{$\Leftarrow$}
Nechť $A\supdot\cap B\supdot=\{1\}$.
Mějme libovolné $\anglecouple ab\in\ker f$.
Pak $f(a,b)=ab=1$, tedy $a=b^\1$ a nutně $a=b^\1\in A\supdot\cap B\supdot$ a tedy $a=b=1$.
 
\end{description}
\QED
 
\theorem
Platí $G=A\odot B$ právě tehdy, když platí:
\begin{enumerate}
\item $(\AA a\in A\supdot, b\in B\supdot)(ab=ba)$;
\item $A\supdot B\supdot=G\supdot$;
\item $A\supdot\cap B\supdot=\{1\}$.
\end{enumerate}
 
\remark
V~aditivní grupě používáme název \defined[součet!direktní]{direktní součet}.
 
\theorem
Je-li $G=A\odot B$, pak platí
\begin{enumerate}\addtocounter{enumi}{3}
\item $A\nsg G$, $B\nsg G$;
\item $AB=G$ (tedy $A$ a $B$ komutují);
\item $(\AA x\in G\supdot)(\EE_1\, a\in A\supdot, b\in B\supdot)(x=ab=ba)$.
\end{enumerate}
 
\proof
\begin{enumerate}\addtocounter{enumi}{3}
\item
Mějme $c\in G\supdot$, $x\in A$, $y\in B$ a podle (2) je $c=ab$, $a\in A\supdot$, $b\in B\supdot$.
Pak
$$\AL c(x)=cxc^\1=abxb^\1a^\1\stackrel{(1)}{=\!\!=}axbb^\1a^\1=axa^\1\in A\supdot$$
a
$$\AL c(y)=cyc^\1=a\overbrace{byb^\1}^{\in B\supdot}a^\1=byb^\1aa^\1=byb^\1\in B\supdot.$$
 
\item
Podle lemmatu o tečce je $G\supdot=A\supdot B\supdot\sse (AB)\supdot=G\supdot$, tedy $AB=G$.
 
\item
Zobrazení $f$ je bijekce, tedy existuje právě jedna dvojice $a,b$ taková, že $f(a,b)=c$.
\end{enumerate}
\QED
 
\theorem
Buď $G$ cyklická grupa řádu $p_1^{k_1}\cdots p_n^{k_n}$ -- standardní rozklad na prvočísla.
Pak $G=A_1\odot\cdots\odot A_n$, kde $A_i$ má řád $p_i$. (v roce 2010/2011 nedělal)
 
\example
Pro $Z_6=Z\factorset{\equiv_6}=(\{0,1\cldc 5\}, +)$ má řád $6=2\cdot 3$ a lze ji napsat jako $Z_6=A\oplus B$.
Platí $A\supdot=\{0,3\}$ a $B\supdot=\{0,2,4\}$.
 
\theorem
Buď $G=A\odot B$.
Pak $G\factorset A\cong B$.
 
\proof
Z věty o izomorfismu je $AB\factorset A\cong B\factorset{A\cap B}$,
ale $AB=G$, $A\cap B=E$, tedy $B\factorset E\cong B$, tedy $G\factorset A\cong B$.
\QED