 \documentclass{amsart}

\usepackage[utf8]{inputenc}
\usepackage[IL2]{fontenc}
\usepackage[czech]{babel}
\usepackage{amsmath,amssymb}
\usepackage{comment}

\usepackage{tikz}

\usepackage{graphics,graphicx}
\usepackage{pstricks,pst-node,pst-tree}

\usepackage[unicode]{hyperref}



\newtheorem{theorem}{Věta}[section]
\newtheorem{pozn}[theorem]{Poznámka}
\newtheorem{dusl}[theorem]{Důsledek}
\newtheorem{prikl}[theorem]{Příklad}
\newtheorem{fakt}[theorem]{Fakt}

\theoremstyle{definition}
\newtheorem*{definice}{Definice}
\newtheorem*{znac}{Značení}

\newtheorem*{tvrz}{Tvrzení}
\newtheorem*{lemma}{Lemma}

\def\NSD{\mathop{\rm GCD}}
\def\nsn{\mathop{\rm lcm}}
\def\sgn{\mathop{\rm sgn}}
\def\A{\mathop{\mathcal A}}
\def\B{\mathop{\mathcal B}}

\DeclareMathOperator{\N}{\mathbb N}
\DeclareMathOperator{\Z}{\mathbb Z}
\DeclareMathOperator{\Q}{\mathbb Q}

%\let\NSD=\gcd

%\newcommand{\sgn}{{\rm sgn}}
\newcommand{\md}{{\rm mod\ }}
\newcommand{\dv}{{\rm div\ }}
\newcommand{\Ker}{{\rm Ker}}
\newcommand{\rmod}{{\rm rmod}}
\newcommand{\lmod}{{\rm lmod}}
\newcommand{\Id}{{\rm Id}}
\newcommand{\id}{{\rm id}}
%\DeclareMathOperator{\st}{deg}
\let\st=\deg

\begin{document}

\date{\today}
\title{Algebra I pro informatiky}
%\author{Jan Žemlička}



\maketitle

\tableofcontents


\section{Předmět(y) zkoumání}



Pod názvem algebra se po dlouhou dobu rozuměla nauka o řešení rovnic, což dosvěd\-čuje i etymologie
tohoto slova; termínem al-džabr označuje Muhammad Ibn Músá al-Chórezmí (kolem 780 – kolem 850)  ve svém
{\it Algebraickém traktátu} úpravu odpovídající přičtení výrazu k oběma stranám rovnice. Ač je al-Chórezmí
často nazýván Otcem algebry a stal se neplánovaným autorem pojmenování
celé matematické disciplíny (a také pojmu algoritmus skrze přízvisko al-Chorézmí, které označuje jeho rodiště Chorézm, dnešní uzbeckou Chívu),
algebraické úvahy a postupy jsou mnohem staršího data. Zmiňme alespoň teorii čísel,
pěstovanou už v antickém starověku, například Eukleidův algoritmus je stále velmi užitečný nástroj, jehož
algebraická povaha je mimo vší pochybnost. 

V současném pojetí algebry už netvoří otázka řešení polynomiálních rovnic, jak bychom měli předmět
starověké, středověké a raně novověké algebry upřesnit, centrální roli.
Přesto lze mnoho algebraických problémů rovnicovým jazykem vy\-jádřit
a například otázka obtížnosti nalezení řešení kvadratických
či kubických rovnic je zajímavá nejen pro současnou algebru, nýbrž i pro kryptologii.
V algebře se podobně jako v celé matematice zásadně změnil jazyk. Symbolický zápis
umožňuje přesnější a jasnější formulace starých otázek a přirozeně nabízí otázky nové.
Obdobně se zásadně změnila míra abstrakce algebraických úvah. Zatímco v {\it klasické algebře}
se matematici zabývali vždy zcela konkrétní algebraickou strukturou, jakou představují přirozená čísla
se sčítáním a násobením, celá či racionální čísla se sčítáním, násobením, odčítáním, popřípadě dělením
nebo reálná či komplexní čísla v kontextu otázek vyjádřených obvyklými operacemi,  v takzvané {\it moderní
algebře} už v centru pozornosti stojí obecný, obvykle axiomaticky popsaný algebraický objekt. 
My se budeme pochopitelně věnovat základním konceptům moderní algebry s přihlédnutím
k historickým souvislostem a postoji studenta informatiky, pro nějž je realitou jen velmi
omezený sortiment konkrétních algebraických struktur, což je postoj přirozeně blízký klasické
algebře.

Velmi zhruba vyjádřeno se tedy moderní algebra věnuje zkoumání množin opatře\-ných jistým systémem operací.
Předmětem zájmu jsou ovšem nejen strukturní vlastnosti takové množiny popsané podmínkami, které 
pomocí operací umíme vyjádřit, nýbrž i vlastnostmi ,,vyšších řádů'', například vlastnosti systémů různých množin
s podobnými systémy operací či  tříd takových množin.
Tento text si přitom klade za cíl seznámit studenty informatiky s nejzákladnějšími
pojmy, koncepty a v neposlední řadě i konkrétními objekty, které jsou předmětem zkoumání současné algebry. 
Výběr a uspořádání teorie, kterou zde prezentujeme, je zvolen s ohledem na tři základní hlediska.
Jak už bylo zmíněno, především se snažíme navázat na koncepty a způsoby uvažování, které
jsou pro studenta informatiky přirozené, dále se v rámci velmi omezeného
prostoru pokoušíme demonstrovat několik elementárních algebraických
výsledků, které jsou užitečné v informatických aplikacích a konečně
za nepominutelný považujeme přístup, který můžeme nepříliš přesně označit jako
kontextuální, a jímž míníme seznámení studenta s terminologickými a historickými
kontexty současné algebry.

Dříve než se začneme systematicky zabývat 
abstraktními úvahami o algebraic\-kých objektech, uvedeme několik motivačních příkladů, které by nám pomohly usnadnit
porozumění důvodům (ať už praktickým tak historickým), proč
právě tu či onu vlastnost sledujeme.

Nejprve se domluvme, že {\it binární operací} na neprázdné množině $A$ budeme rozumět 
libovolné zobrazení $A^2=A\times A\to A$ (obvykle ji budeme zapisovat centrálně),
{\it unární operace} na $A$ bude jakékoli zobrazení $A\to A$ a {\it nulární operace}  
bude zobrazení kartézské mocniny $A^0$, která sestává právě z jediné prázdné posloupnosti,
do množiny $A$,  můžeme ji proto chápat jako vybrání prvku z množiny $A$, právě toho, na nějž se
zobrazí jednoprvková množina $A^0$ (obvykle se nulární operace s tímto vyznačeným prvkem ztotožňuje).

Můžeme si poněkud předčasně dovolit i zcela obecnou definici operace:

\begin{definice} Pro každé celé $n\ge 0$ nazveme {\it $n$-ární operací na množině $A$}
každé zobrazení $A^n\to A$ (číslo $n$ budeme nazývat {\it aritou} nebo {\it četností}
operace).
\end{definice}


\begin{prikl}\label{0.1} \rm Uvažujme množinu celých čísel $\Z$ a na ní obvyklé
operace sčítání $+$ a násobení $\cdot$. Pro libovolné
přirozené číslo $n$ položme $n\Z=\{n\cdot z|\ z\in \Z\}$.
Nyní si můžeme všimnout, že je množina $n\Z$ ,,uzavřená" na obě
uvažované operace, tj. pro každou dvojici $a,b\in n\Z$ platí,
že $a+b, a\cdot b \in n\Z$, tedy operace $+$ a $\cdot$ můžeme uvažovat
také omezeně na množině $n\Z$. Ačkoli pro žádné $n>1$ množiny 
$n\Z$ a $\Z$ nesplývají, nelze pomocí vlastností
operace $+$ obě množiny odlišit (tj. mají stejné ,,algebraické" vlastnosti
vzhledem ke sčítání),
což ozřejmíme, zavedeme-li zobrazení $f_n: \Z\to n\Z$
předpisem $f_n(k)=kn$. Zjevně se jedná o bijekci, která navíc splňuje
podmínku $f_n(a+b)=f_n(a)+f_n(b)$. 

Poznamenejme, že taková vlastnost zobrazení není nijak samozřejmá,
například vzhledem k operaci násobení $f_n$ obdobnou podmínku nesplňuje.
Uvážíme-li navíc podmínku
,,existuje prvek $e$ tak, že pro všechny prvky $a$ platí $a\cdot e=a$", 
pak je tato podmínka na množině $\Z$ splněna pro $e=1$, zatímco
na množině $n\Z$ zjevně neplatí.
\end{prikl}

V souladu se značením zavedeným na kurzu lineární algebry
položme $\Z_n=\{0,1,\dots,n-1\}$ pro nějaké celé číslo $n>1$.

\begin{pozn} Pro každé $a$ celé a $b$ kladné existují jednoznačně určená čísla $q\in\Z$ a $r\in\Z_b$, pro která $a=qb+r$. 
\end{pozn}
\begin{proof} Pro $a\ge0$ existenci $q\in\Z$ a $r\in\Z_b$ dokazuje
školský algoritmus dělení se zbytkem (opírající se o fakt, že každé celé číslo lze zapsat v dekadickém zápisu). Pro $a<0$ najdeme algoritmem $p\in\Z$ a $z\in\Z_b$, pro která $-a=pb+z$
$-a$ a $b$. Hledaným podílem je $-q$ a zbytkem $0$, pokud $z=0$,
nebo podíl je  $-q-1$ a zbytek $b-r$, pokud $z>0$.

Nechť $a=qb+r=q'b+r'$ pro $q,q'\in\Z$ a $r,r'\in\Z_b$ a předpokládejme,
že například $r\ge r'$. Pak $0\le r-r'=(q'-q)b<b$, proto $q=q'$ a tudíž $r=r'$, čímž jsme dokázali jednoznačnost volby  $q\in\Z$ a $r\in\Z_b$.
\end{proof}

Nadále budeme používat značení $(a)\dv b$ pro celočíselný podíl a 
$(a)\md b$ pro zbytek, tj. pro hodnoty jednoznačně zajištěné předchozí poznámkou.

\begin{prikl}\label{0.2} \rm 
Zaveďme na množině $\Z_n$ operace  $+$ a $\cdot$
předpisem $a+b=(a+b)\md n$ a $a\cdot b=(a\cdot b)\md n$, kde
$\md n$ znamená zbytek po celočíselném dělení hodnotou $n$ a v závorce uvažujeme
vždy obvyklé sčítání a násobení celých čísel. Konečně definujme zobrazení
$F_n:\Z\to\Z_n$ předpisem $F_n(k)=(k)\md n$.
Všimněme si, že tentokrát zobrazení $F$ sice není bijekce, ale 
obě operace sčítání a násobení ,,převádí" na nově zavedené $+$ a $\cdot$,
tedy $F_n(a+b)=F_n(a)+F_n(b)$ i $F_n(a\cdot b)=F_n(a)\cdot F_n(b)$.
\end{prikl}

\begin{definice} 
Máme-li binární operaci $*$ na množině $A$, nějakou podmnožinu $U$ 
množi\-ny $A$ a binární operaci $\circ$ na množině $B$.
Řekneme, že $U$ je {\it uzavřená} na operaci $*$, jestliže
pro všechna $x,y\in U$ platí, že $x*y\in U$, a
zobrazení $f:A\to B$ nazveme {\it slučitelné} s operacemi $*$ a $\circ$
je-li pro všechna $x,y\in A$ splněna rovnost $f(x*y)=f(x)\circ f(y)$.
\end{definice}

Všimněme si, že zobrazení $f_n$ z \ref{0.1} je slučitelné s operacemi $+$ a není
slučitelné s operacemi $\cdot$, zatímco zobrazení $F_n$ z \ref{0.2}
je slučitelné s oběma páry operací $+$ i $\cdot$. Navíc množina
$n\Z$ je uzavřená na operace $+$ i $\cdot$.


Na dvou známých příkladech si ilustrujme, že jsou uvedené pojmy základním stavebním kamenem algebry:

\begin{prikl}\label{0.2p} \rm 
(1) Podprostor vektorového prostoru je zjevně podmnožinou uzavře\-nou na (vektorové) sčítání
a lineární zobrazení jsou se sčítáním slučitelná. Navíc uvažuje\-me-li násobení skalárem
pro každý skalár $a$ jako unární operaci, pak je podprostor uzavřený na všechny takto definované 
unární operace.

%(2)  Na množině $M(X)$ všech slov, tj. všech konečných posloupností písmen z množiny $X$ uvažujme  binární operaci skládání $\cdot$:  
%\[ x_1\dots x_n\ \cdot\ y_1\dots y_m = x_1\dots x_n\ y_1\dots y_m. \]
%Zvolme $x\in X$ a $s\in M(X)$. Je-li $f_x:M(X)\to M(X)$ zobrazení, které z každého slova vypustí všechna písmena $x$ a $f_s:M(X)\to M(X)$ zobrazení, které každé písmeno $x$ nahradí slovem $s$, snadno nahlédneme, že jde o zobrazení slučitelná s operací $\cdot$.

(2) Uvážíme na množině $\{0,1\}$ Booleovské operace $\land$, $\lor$ a XOR, zapsat si je můžeme tabulkami:
\[
\begin{tabular}{c|rp{2mm}}
$\land$ & \bf 0 & \bf 1 \\
\hline
\bf 0 & 0 & 0 \\
\bf 1 & 0 & 1 
\end{tabular}
\ \ \ \ 
\begin{tabular}{c|rp{2mm}}
$\lor$ & \bf 0 & \bf 1 \\
\hline
\bf 0 & 0 & 1 \\
\bf 1 & 1 & 1 
\end{tabular}
\ \ \ \ 
\begin{tabular}{c|rp{2mm}}
XOR & \bf 0 & \bf 1 \\
\hline
\bf 0 & 0 & 1 \\
\bf 1 & 1 & 0 
\end{tabular}
\]
Vezmeme-li bijekci $b(0)=1$, $b(1)=0$, pak z tabulky operací vidíme, že je $b$ slučitelná s operacemi $\land$ a $\lor$
v obou možných pořadí operací, nikoli ovšem s operacemi $\land$ a $\land$ respektive $\lor$ a $\lor$.
Podobně z tabulky operace XOR nahlédneme, že $b$ s operacemi 
$\land$ a XOR ani $\lor$ a XOR (v žádném pořadí) slučitelná není.
\end{prikl}

\vskip 1cm

\section{Základy elementární teorie čísel}

V této kapitole připomeneme a korektně dokážeme několik jednoduchých poznatků z teorie čísel, konkrétně Eukleidův algoritmus, Základní větu aritmetiky a Čínskou větu o zbytcích. Poslouží nám nejen jako motivace zkoumání obecných algebraických vlastností (slučitelnost ekvivalence s operací), nýbrž i jako užitečný nástroj, jenž budeme potřebovat v následujících
kapitolách.

Jsou-li $a,b$ dvě celá čísla, budeme fakt, že číslo $a$ dělí $b$,  značit $a/b$ a symbolem
$\NSD(a,b)$ budeme rozumět {\it největší společný dělitel} čísel $a$ a $b$, tedy nezáporné číslo $d$, které je  společným dělitelem  čísel $a$ a $b$
($d/a,b$) a které je děleno všemi společnými děliteli čísel $a$ a $b$ ($c/a,b \Rightarrow c/d$).
Podobně $\nsn(a,b)$ bude označovat {\it nejmenší společný násobek} čísel $a$ a $b$, tedy nezáporné číslo $n$, které je  společným násobkem  čísel $a$ a $b$
($a,b/n$) a které je děleno všemi společnými děliteli čísel $a$ a $b$ ($a,b/m \Rightarrow n/m$).
Konečně přirozené číslo $p$ nazveme prvočíslem, jestliže pro každá celá $a, b$ platí implikace $p=a\cdot b\Rightarrow a=\pm1$ nebo $b=\pm1$.


Připomeňme nejprve rozšířený Eukleidův algoritmus hledání největšího společné\-ho dělitele čísel $a$ a $a$:

\vskip 3mm
{\tt
VSTUP: $a,b\in \N$, $a\ge b$ 

VÝSTUP: $\NSD(a,b), x,y\in \Z$, pro které $\NSD(a,b)=x\cdot a + y\cdot b$
\begin{enumerate}
\item[0.] $i:=1$, $(a_0,a_1):=(a,b)$; $(x_0,x_1):=(1,0)$; $(y_0,y_1):=(0,1)$;
\item[1.] while$(a_i>0)$ do

$\{a_{i+1}: = (a_{i-1})\md a_i$; $q_{i}: = (a_{i-1})\dv a_i$;\ $\%$tj. $a_{i-1} = q_ia_i + a_{i+1}$ 

$x_{i+1}:=x_{i-1}-x_i\cdot q_i$; $y_{i+1}:=y_{i-1}-y_i\cdot q_i$; $i:=i+1;\}$

\item[2.] return $a_{i-1}, x_{i-1},y_{i-1}$.
\end{enumerate}
}
\vskip 3mm

\begin{pozn}\label{EA} Eukleidův algoritmus pracuje správně, tedy pro $a,b\in \N$ najde největší společný dělitel 
a pro $x,y\in \Z$ na jeho výstupu platí, že $\NSD(a,b)=x\cdot a + y\cdot b$.
\end{pozn}
\begin{proof} Využijeme značení algoritmu 
a poznamenejme, že vypočítaná hodnota $a_{i+1}$ je vždy menší než předchozí $a_i$,
proto while-cyklus v algoritmu skončí.

Nyní zvolíme index $n$ tak, že $a_n>0$ a $a_{n+1}=0$.
Všimněme si, že $a_n = \NSD(a_{n-1}, a_n)$, protože $a_n/a_{n-1}$.

Označíme $\mathcal D(u,v)=\{c\in \mathbb Z|\ c/u, c/v\}$ pro každé $u,v$ množinu všech jejich společných dělitelů a
ukážeme pro každé $i=1,\dots, n-1$, že množina všech dělitelů dvojice
$a_i, a_{i+1}$ je stejná jako množina všech dělitelů dvojice $a_{i-1}, a_i$, tedy že 
\[
\mathcal D(a_i, a_{i+1}) = \mathcal D(a_{i-1}, a_i).
\]
Využijeme při tom vztahů $a_{i-1}=a_{i+1} + q_i\cdot a_i$ a $a_{i+1}=a_{i-1} - q_i\cdot a_i$:
\[
c /a_{i-1}, a_i \Rightarrow c/a_{i+1}=a_{i-1} - q_i\cdot a_i,
\]
\[
d / a_i, a_{i+1} \Rightarrow d/a_{i-1}=a_{i-1} + q_i\cdot a_i.
\]
Protože $a_n$ je největší společný dělitel prvků $a_n$ a $a_{n-1}$
a 
\[
\mathcal D(a_{n-1},a_n) = \mathcal D(a_{n-2}, a_{n-1})=\dots =\mathcal D(a_{0}, a_{1}),
\]
platí, že $a_n\in \mathcal D(a_{i-1}, a_i)$ a navíc $d/ a_n$ pro každé $d\in \mathcal D(a_{i-1}, a_i)$,
tedy 
\[
a_n =\NSD(a_n, a_{n-1})=\NSD(a_{n-1}, a_{n-2})=\dots =\NSD(a_0, a_1).
\]

Nakonec ověříme indukcí podle $i$ platnost tvrzení $a_{i}=x_i\cdot a_0 + y_i\cdot a_1$,
které potřebujeme dokázat pro $i=n$.
Zřejmě tvrzení platí pro $i=0$ a $i=1$ a předpoklá\-dejme, že tvrzení platí pro $i$ a $i-1$, tedy 
$a_{i}=x_i\cdot a_0 + y_i\cdot a_1$ a $a_{i-1}=x_{i-1}\cdot a_0 + y_{i-1}\cdot a_1$.
Dokážeme rovnost pro $i+1$ dosazením za $a_{i}$ a $a_{i-1}$ do vztahu:
\[
a_{i+1}= a_{i-1} - a_i\cdot q_i= 
(x_{i-1}\cdot a_0 + y_{i-1}\cdot a_1) - (x_i\cdot a_0 + y_i\cdot a_1)\cdot q_i =
\]
\[
= (x_{i-1}-x_i\cdot q_i)\cdot a_0 + (y_{i-1}-y_i\cdot q_i)\cdot a_1
= x_{i+1}\cdot a_0 + y_{i+1}\cdot a_1,
\]
čímž jsme dokončili důkaz.
\end{proof}

Poznamenejme, že čísla $x$ a $y$ na výstupu Eukleidova algoritmu se nazývají {\it Bezoutovy koeficienty} a že není těžké dokázat omezení na jejich velikost $|x|\le \frac{b}{2}$ a $|y|\le \frac{b}{2}$, pokud $a, b>1$.

Nyní už je snadné dokázat jednoznačnost prvočíselného rozkladu.

\begin{theorem}[Základní věta aritmetiky]\label{zva} Každé přirozené číslo větší než jedna lze až na pořadí jednoznačně rozložit na součin prvočísel.
\end{theorem}
\begin{proof} Nejprve si uvědomíme, že lze každé přirozené číslo $n > 1$ napsat jako součin prvočísel, což můžeme
snadno dokázat indukcí podle $n$. Číslo $2$ je zřejmě prvočíslo. 
Pokud $n$ není prvočíslo, existují taková přirozená čísla $k,\ l < n$, že $n = k\cdot l$. Obě jsou samozřejmě větší
než jedna a podle indukčního předpokladu máme prvočíselný rozklad čísel 
$k = p_1\cdot\ldots\cdot p_r$ a $l = q_1\cdot\ldots\cdot q_s$. 
Tedy číslo $n$ je součinem prvočísel $p_1\cdot\ldots\cdot p_r\cdot q_1\cdot\ldots\cdot q_s$.

Dříve než ověříme jednoznačnost prvočíselného rozkladu,
dokážeme technické
\begin{lemma} Nechť $p$ je prvočíslo a $a,b,a_1, a_2,\dots, a_k\in \N$. Pak platí
\begin{enumerate}
\item  $p/a\cdot b$ $\Rightarrow$ $p/a$ nebo $p/b$,
\item  $p/a_1a_2\dots a_k$ $\Rightarrow$ $\exists i$, že $p/a_i$. 
\end{enumerate}
\end{lemma}
(1) Předpokládejme, že  $p/a\cdot b$ a  $p$ nedělí $a$.
Protože $p$ má pouze dělitele $\pm1$ a $\pm p$, vidíme, že  $\NSD(p,a)=1$, 
a proto podle \ref{EA} existují taková celá $x$ a $y$, že $1=a\cdot x+p\cdot y$. Přenásobením této rovnosti hodnotou $b$ dostaneme $b=abx+pby$, a
protože $p$ dělí oba sčítance vpravo, platí také, že $p/b$.

(2) Dokážeme indukcí podle $k$. Pro $k=1$ je tvrzení triviální.
Předpokládáme-li, že $p/a_1a_2\dots a_k=a_1\cdot(a_2\dots a_k)$, pak 
podle (1) buď $p/a_1$ a jsme hotovi nebo $p/a_2a_3\dots a_k$ a závěr plyne z indukčního předpokladu.

Nyní indukcí provedeme důkaz jednoznačnosti prvočíselného rozkladu čísla $n$. Indukčním předpokladem zde
bude tvrzení, že je prvočíselný rozklad určen jednoznačně až na pořadí pro všechna čísla menší než $n$.

Je-li $n$ prvočíslo (speciálně $n = 2$),
obsahuje prvočíselný rozklad jediné prvočíslo a je tedy zřejmě určen jednoznačně. Platí-li tvrzení pro všechna $k < n$ 
a $n = p_1\cdot\ldots\cdot p_r = q_1\cdot\ldots\cdot p_s$ jsou dva prvočíselné rozklady,
potom podle tvrzení Lemmatu existuje takové $j$, že $p_1 / q_j$. 
Bez újmy na obecnosti můžeme předpokládat, že $j=1$. Protože $p_1$ i $q_1$
jsou prvočísla, máme $p_1=q_1$. Nyní stačí použít indukční předpoklad pro 
$p_2\cdot\ldots\cdot p_r = q_2\cdot\ldots\cdot p_s<n$. 
\end{proof}


\begin{dusl} Pro každá přirozená $a,b$ existuje jednoznačně určený
$\NSD(a,b)$ a $\nsn(a,b)$ a platí, že $\nsn(a,b)=\frac{a\cdot b}{\NSD(a,b)}$ .
\end{dusl}
\begin{proof}  Snadno díky jednoznačnosti prvočíselného rozkladu zaručeného Větou \ref{zva}
ověříme bezprostředně z definice, že pro $a=\prod p_i^{\alpha_i}$, $b=\prod p_i^{\beta_i}$
\[
\NSD(a,b)=\prod p_i^{\min(\alpha_i, \beta_i)}\text{ a }\nsn(a,b)=\prod p_i^{\max(\alpha_i, \beta_i)}.
\]
Navíc každé dva $\NSD(a,b)$ (respektive $\nsn(a,b)$) se podle definice vzájemně dělí, tedy jsou stejné.
\end{proof}

Nyní si všimneme, že počítání v  množině $\Z_n$ s operacemi modulo
$n$ lze  ,,algebraicky" přesně reprezentovat
pomocí počítání v menších množinách $\Z_{n_i}$, což
je pozorování významné  pro výpočty pracující s velkými celými čísly.

Nejprve zavedeme součinové operace.
Pro kladná celá čísla 
$n_1,\dots,n_k $, 
definujme na kartézském součinu $\prod_{i=1}^k \Z_{n_i}$
po složkách (součinové) operace $+$, $-$ a $\cdot$:
\[(a_1,a_2,\dots,a_k)+(b_1,b_2,\dots,b_k) = (a_1+b_1,a_2+b_2,\dots,a_k+b_k),
\]
%\[(a_1,a_2,\dots,a_k)-(b_1,b_2,\dots,b_k) = (a_1-b_1,a_2-b_2,\dots,a_k-b_k),\]
\[(a_1,a_2,\dots,a_k)\cdot(b_1,b_2,\dots,b_k) = (a_1\cdot b_1,a_2\cdot b_2,\dots,a_k\cdot b_k),
\]
kde odčítání ve složkách definujeme rovněž modulo $n_i$.
 

\begin{prikl}\label{0.4} \rm Uvažujme kladná celá čísla 
$n_1,\dots,n_k $, položme $n=n_1\cdot\dots\cdot n_k$ a
definujme zobrazení
\[
G:\Z\to\mathbf \prod_{i=1}^k \Z_{n_i} \text{\ \  předpisem \ \ }
G(a)=((a)\md n_1,\dots, (a)\md n_k)
\]
a stejným předpisem zavedeme i zobrazení
$H:\Z_n\to\mathbf \prod_{i=1}^k \Z_{n_i}$.
Všimněme si, že obě zobrazení jsou slučitelná s operacemi $+$
%, operacemi $-$ 
i operacemi $\cdot$.
\end{prikl}

Ve výše zavedené notaci vyslovíme klasické tvrzení:

\begin{theorem}[Čínská věta o zbytcích]\label{CRT} Nechť $n_1, n_2, \dots, n_k $ jsou
 kladná
celá čísla a $n=n_1\cdot n_2\cdot\dots\cdot n_k$. Potom je zobrazení $H$ z \ref{0.4} slučitelné s operacemi $+$ a $\cdot$.
Navíc $H$ je bijekce, právě když jsou čísla $n_1, n_2, \dots, n_k $ po dvou nesoudělná.
\end{theorem}
\begin{proof}  V Příkladu \ref{0.4} jsme si uvědomili, že je $f$ zobrazení slučitelné s oběma operacemi. Zbývá dokázat ekvivalenci.

Nejprve dokážeme zpětnou implikaci. Nechť jsou čísla $n_1, n_2, \dots, n_k $ po dvou nesoudělná. Ukážeme, že je $H$ bijekce. Protože jsou $\Z_n$ a $\prod_{i=1}^k\Z_{n_i}$
stejně velké konečné množiny, stačí ověřit, že je $f$ prosté. Nechť pro $a\le b\in\Z_n$ platí,
že $H(a)=H(b)$. Potom $H(b-a)=0$, tedy $n_i/b-a$ pro všechna $i=1,\dots,k$. Protože 
jsou $n_i$ po dvou nesoudělná dostáváme z Věty \ref{zva} $n/b-a$. Protože ovšem $0\le b-a\le n-1$, máme $b=a$.

Přímou implikaci dokážeme nepřímo. Nechť existují indexy $i\ne j$, pro něž $c=\NSD(n_i,n_j)>1$.
Potom $\frac{n}{c}\in\Z_n\setminus\{0\}$ a pro všechna $r=1,\dots,k$ platí, že $n_r/\frac{n}{c}$.
To znamená, že $H(0)=(0,\dots,0)=H(\frac{n}{c})$, tedy $H$ není prosté.
\end{proof}

Uvedený důkaz Čínské věty o zbytcích není konstruktivní, tedy nám neposkytuje algoritmus k nalezení vzoru nějakého prvku
v zobrazení $H$.
Zavedeme proto relaci kongruence, která nám spolu Eukleidovým algoritmem
umožní efektivně počítat vzory zobrazení $H$.

{\it Relací na množině $A$} rozumíme libovolnou podmnožinu $\rho$ množiny $A\times A$ a 
označme $ \equiv\ (\md n)$ relaci {\it kongruence} na množině celých čísel 
$\Z$ danou předpisem $a\equiv b \ (\md n)\leftrightarrow n/(a-b)$. 

Dále připomeňme, že obecná relace $\rho$ je


- {\it reflexivní}, jestliže $(a,a)\in\rho$ pro každé $a\in A$,

- {\it symetrická}, platí-li pro každé $a,b\in A$ implikace 
$(a,b)\in \rho$ $\Rightarrow$ $(b,a)\in \rho$,


- {\it tranzitivní}, platí-li pro každé $a,b,c\in A$ implikace 
$(a,b), (b,c)\in \rho$ $\Rightarrow$ $(a,c)\in \rho$,

- {\it ekvivalence}, je-li reflexivní, symetrická a tranzitivní relace.

Připomeňme, že na každé množině $A$ máme k dispozici dvě tzv. {\it triviální} ekvivalence $\id=\{(a,a)\mid a\in A\}$, $A\times A$ je tzv. {\it triviální}, navíc zobrazení $f:A\to B$ určuje ekvivalenci $\ker f=\{(x,y)\in A\times A|\ f(x)=f(y)\}$ (tzv. {\it jádro zobrazení}). 


Dříve než začneme používat termín kongruence v mnohem obecnějším významu, všimněme si 
některých jejich (zjevně algebraických) vlastností:

\begin{pozn}\label{kong-Z} Nechť $k,n\in\N$ a $n>1$. Pak je $\equiv (\md n)$ ekvivalence na $\Z$ a pro každé $a,b,c,d\in\Z$ platí:
\begin{enumerate}
\item jestliže $a\equiv b \ (\md n)$ a $c\equiv d \ (\md n)$, pak $a+c\equiv b+d \ (\md n)$, 
$a-c\equiv b-d \ (\md n)$, $a\cdot c\equiv b\cdot d \ (\md n)$ a $a^k\equiv b^k \ (\md n)$,
\item jestliže $c\ne 0$, pak $a\equiv b \ (\md n)$, právě když $a\cdot c\equiv b\cdot c \ (\md cn)$,
\item jestliže $\NSD(c,n)=1$, pak $a\equiv b \ (\md n)$, právě když $a\cdot c\equiv b\cdot c \ (\md n)$.
\end{enumerate}
\end{pozn}
\begin{proof} $\equiv (\md n)$ tvoří ekvivalenci například proto, že
jde o ekvivalenci $\ker F_n$ pro $F_n$ z \ref{0.2}.

(1) Předpokládáme-li, že $n/(a-b), (c-d)$, pak 
\[ n/(a-b)+(c-d)=(a+c)-(b+d),\] 
\[
n/(a-b)-(c-d)=(a-c)-(b-d),
\] 
\[
n/(a-b)\cdot c + b\cdot(c-d)=(a\cdot c)-(b\cdot d)
\]
a poslední kongruenci dostaneme indukčním použitím předchozí pro $a=c$ a $b=d$.

(2) $a\equiv b \ (\md n) \Leftrightarrow n/(a-b) \Leftrightarrow  nc/(ac-bc) \Leftrightarrow a c\equiv b c \ (\md cn)$.

(3) Přímá implikace plyne okamžitě z (1), protože $c\equiv c\ (\md n)$. Jakmile $n/ac-bc=(a-b)c$ a $c$ a $n$ jsou nesoudělná čísla, pak nutně $n/(a-b)$ díky Větě \ref{zva}.
\end{proof}


\begin{definice} Uvažujme na množině $A$ binární operaci $*$ a ekvivalenci
$\sim$. Řekneme, že $\sim$ je {\it slučitelná s operací $*$}, jestliže 
pro všechny takové prvky $a_1,a_2, b_1, b_2\in A$, pro něž $a_1\sim b_1$
a $a_2\sim b_2$ platí, že $(a_1*a_2)\sim (b_1*b_2)$.
\end{definice}

V Poznámce \ref{kong-Z} jsme tedy zjistili, že je kongruence $\equiv (\md n)$ slučitelná s~přiro\-zenými operacemi $+$, $-$ a $\cdot$ na celých číslech.

\begin{prikl}\label{Garner} \rm 
Podle Čínské věty o zbytcích existuje právě jedno $x\in\Z_{35}$ splňující kongruence $x\equiv 2 \ (\md 5)$ a $x\equiv 3 \ (\md 7)$,
pokusíme se ho spočítat. 
Nejprve si všimneme, že z první kongruence plyne, že $x=5y+2$ pro vhodná $y\in \Z$ a toto vyjádření dosadíme do druhé 
kongruence a pomocí Poznámky \ref{kong-Z} budeme kongruenci upravovat ekvivalentními úpravami: 
\[5y+2\equiv 3 \ (\md 7) \Leftrightarrow 5y\equiv 1 \ (\md 7) \Leftrightarrow 3\cdot5y\equiv 3\cdot1 \ (\md 7) \Leftrightarrow y\equiv 3 \ (\md 7). \]
Poznamenejme, že jsme v posledním kroku využili toho, že umíme (obecně díky Eukleidovu algoritmu) najít ,,inverz modulo 7" k číslu $5$, jímž je $3$). Hledaným řešením je tedy $x=5\cdot3+2=17$.
\end{prikl}




\vskip 1cm

\section{Asociativní binární operace}

Zkusíme se nyní oprostit od konkrétní algebraické struktury a uvážíme sice
obecnou avšak velmi jednoduchou situaci množiny opatřené asociativní binární operací.
Hlavním výsledkem této kapitoly bude kromě příkladů řady struktur, které takovou podmínku splňují,
především pozorování, že množina s asociativní operací je jistým způsobem
velmi blízko mnohem silnějšímu pojmu grupa (Poznámka~\ref{1.6}), který jako jeden ze základních pojmů moderní algebry také
zavedeme. 




\begin{definice} Uvažujme binární operací $*$ na množině $A$.
{\it Neutrálním prvkem} operace $*$ rozumíme
takový prvek $e\in A$, že $g*e=g=e*g$ pro všechna $g\in A$.
\end{definice}

Všimněme si, že v jedné množině
nemohou být pro stejnou operaci dva různé neutrální prvky:

\begin{pozn} Každá binární operace má nejvýše jeden neutrální prvek.
\end{pozn}
\begin{proof} Jsou-li $e,f$ dva neutrální prvky, pak $e = e*f = f$.
\end{proof}

Než se omezíme na zkoumání asociativních operací, učiníme zcela obecné pozorování o neutrálních prvcích.

\begin{definice} Nechť  $\cdot$ je binární operace na množině $S$ a $e$ je její neutrální
prvek. Řekneme, že prvek $s\in S$ je
{\it invertibilní}, jestliže existuje takový prvek $s^{-1}\in S$, pro který
$s^{-1}\cdot s = s\cdot s^{-1}=e$. Prvek $s^{-1}$ nazveme {\it inverzním prvkem} k prvku $s$.
\end{definice}


Množině $G$ s binární operací $\cdot$ budeme říkat {\it grupoid}
(a budeme psát $G(\cdot)$). O grupoidu $G(\cdot)$ řekneme, že je:
\begin{enumerate}
\item[-] {\it pologrupa}, je-li operace $\cdot$ {\it asociativní},
tj. pro všechna $x,y,z\in G$ platí rovnost $x\cdot(y\cdot z)=(x\cdot y)\cdot z$
\item[-] {\it monoid}, je-li operace $\cdot$ asociativní a v $G$ leží její neutrální prvek,
\item[-] {\it grupa}, je-li $G(\cdot)$ monoid, jehož každý prvek je invertibilní,
\item[-] {\it komutativní grupa} (nebo {\it abelovská grupa}), je-li $G(\cdot)$ grupa a $\cdot$ je {\it komutativní}, tj. pro všechna $x,y\in G$ platí rovnost $x\cdot y=y\cdot x$.
\end{enumerate}


V Příkladu \ref{0.1} jsme připomněli asociativní a komutativní operace
$+$ a $\cdot$ na množině celých čísel (a v Příkladech \ref{0.2} a \ref{0.4} jsme
si uvědomili, že asociativitu i komutativitu splňují jimi indukované operace na
množinách $\Z_n$). Jistě zde není třeba opakovat, jak vypadají odpovídající
neutrální a invertibilní prvky. Uveďme ještě několik dobře známých, ač méně elementárních
příkladů asociativních binárních operací.

\begin{prikl}\label{pologrupy}\rm  Nechť $n>1$ je přirozené číslo, $X$ neprázdná množina.

(1) Definujeme na $X$
binární operaci $\ast$ předpisem $x\ast y = x$, je operace $\ast$ asociativní, tedy $X(*)$ je pologrupa.
Je-li $X$  aspoň dvouprvková, pak $X$ neobsahuje žádný neutrální prvek, tudíž nejde o monoid, přestože každý prvek $X$
splňuje první z rovností, kterou je neutrální prvek definován.
V definici neutrálního prvku se tedy nemůžeme omezit jen
na jednu ze dvou rovností.

(2)  Nechť $M(X)$ je množina všech slov, tj. všech konečných posloupností písmen z množiny $X$, uvažujme  binární operaci skládání $\cdot$:  
\[ 
x_1\dots x_n\ \cdot\ y_1\dots y_m = x_1\dots x_n\ y_1\dots y_m.
\]
a označme $\epsilon$ prázdné slovo. 
Snadno nahlédneme, že je operace $\cdot$ asociativní (je-li $X$ aspoň dvouprvková
množina, pak operace není komutativní)
a platí, že $\epsilon\cdot s = s\cdot \epsilon = s$ pro každé $s\in M(X)$, tedy $M(X)(\cdot)$ je tzv. {\it slovní} monoid.

(3) Označme $T(X)$ množinu všech zobrazení
množiny $X$ do sebe. Potom $T(X)(\circ)$ tvoří (s operací skládání $\circ$) (tzv. {\it transformační}) monoid, kde identické zobrazení $\Id$ představuje neutrální prvek.

Uvažíme-li v transformačním monoidu $T(\Z)$ transformace $\alpha,\beta$ dané předpisy $\alpha(k)=2k$ a $\beta(k)=[\frac{k}{2}]$, pak platí, že $\beta\alpha = \Id$  a $\alpha\beta \ne \Id$. 
Prvky $\alpha$ a $\beta$ tedy splňují právě jednu z definitorických
rovností invertibilního prvku, ačkoli se zjevně o invertibilní prvky nejedná. Snadno nahlédneme, že invertibilní transformace jsou právě bijekce.


(4) Čtvercové matice $M_n(T)$ nad tělesem $T$ stupně $n$ spolu s násobením tvoří monoid 
$M_n(T)(\cdot)$ s neutrálním prvkem tvořeným jednotkovou maticí.

(5) $\Z_n(\cdot)$ je konečný komutativní monoid s neutrálním prvkem 1.
\end{prikl}

Do konce této kapitoly budeme nadále  označovat neutrální prvek 
obecné binární operace $\cdot$ symbolem $e$. Zároveň poznamenejme, že je obvyklé značit
neutrální prvek multiplikativní operace (tj. $\cdot$) symbolem $1$ a 
neutrální prvek aditivní operace (tj. $+$) symbolem $0$ (a my se tohoto úzu budeme
později také držet).

Následující dvě tvrzení známe z kontextu počítání se čtvercovými maticemi.

\begin{pozn}\label{1.4} Buď $S(\cdot)$ monoid a $a,b,c\in S$. Platí-li,
že $a\cdot b=c\cdot a=e$, potom $b=c$ je jednoznačně určený inverzní prvek k  prvku
$a$.
\end{pozn}
\begin{proof} S využitím asociativity spočítejme:
\[c = c\cdot e = c\cdot (a\cdot b)=(c\cdot a)\cdot b = e\cdot b=b,\]
odkud vidíme nejen rovnost $b=c$, ale i jednoznačnost, neboť dva prvky inverzní k $a$ splňují podmínku předpokladu.
\end{proof}

Nyní víme, že je inverz k invertibilnímu prvku $a$ v monoidu určen 
jednoznačně, budeme ho tedy značit $a^{-1}$. Množinu všech invertibilních prvků  monoidu $S(\cdot)$ označíme $S^*$.


\begin{pozn}\label{1.6}  Nechť $S(\cdot)$ je monoid. Jestliže $s,t\in S^*$, pak $s\cdot t$ a  $s^{-1}$ jsou také invertibilní prvky $S$ a platí, že $(s\cdot t)^{-1}=t^{-1}\cdot s^{-1}$ a $(s^{-1})^{-1}=s$. Označíme-li $\cdot_{S^*}$ restrikci
$\cdot|_{S^*\times S^*}$ operace $\cdot$ na množinu $S^*\times S^*$,
pak $S^*(\cdot_{S^*})$ je grupa.
\end{pozn}
\begin{proof} Protože $s\cdot s^{-1} = s^{-1}\cdot s=e$, je zřejmě $s^{-1}$ invertibilní a díky \ref{1.4} máme $(s^{-1})^{-1}=s$. Nyní stačí dokázat, že je prvek
$t^{-1}\cdot s^{-1}$ inverzní k $s\cdot t$:
\[
(s\cdot t)\cdot(t^{-1}\cdot s^{-1}) = s\cdot(t\cdot t^{-1})\cdot s^{-1} = 
s\cdot e\cdot s^{-1} = s\cdot s^{-1} = e
\]
a symetricky 
\[
(t^{-1}\cdot s^{-1})\cdot(s\cdot t) = t^{-1}\cdot (s^{-1}\cdot s)\cdot t = 
t^{-1}\cdot e\cdot t = t^{-1}\cdot  t = e.
\]
Dokázali jsme, že je množina $S^*$  uzavřená
na operaci $\cdot$ i na inverzní prvky, protože $e\cdot e =e$, vidíme, že $e\in S^*$, tedy $S^*(\cdot)$ je grupa.
\end{proof}

Grupu invertibilních prvků monoidu $S(\cdot)$ z Poznámky~\ref{1.6} budeme značit $S^*(\cdot)$.

Podívejme se na grupy invertibilních prvků monoidů z Příkladu~\ref{pologrupy}:

\begin{prikl}\label{1.8}\rm Nechť $n>1$ je přirozené číslo a $X$ neprázdná množina a $T$ těleso.

(1)
Grupa invertibilních prvků 
 $M(X)(\cdot)$ obsahuje pouze neutrální prvek $\epsilon$.

(2) Grupu invertibilních prvků transformačního monoidu
$T(X)(\circ)$ tvoří právě všechny bijekce
$S(X)$ na množině $X$ (mluvíme o {\it symetrické grupě} nebo grupě permutací). Poznamenejme, že grupa permutací na množině  $\{1,\dots,n\}$ se obvykle značí $S_n(\circ)$.

(3)  Grupu invertibilních prvků monoidu čtvercových matic $M_n(T)(\cdot)$ stupně $n$
tvoří právě všechny regulární matice stupně $n$ (značíme je $GL_n(T)$).

(4) Ukážeme, že $\Z_n^*(\cdot)=\{a\in \Z_n|\ \NSD(a,n)=1\}$. Jestliže $a\in\Z_n^*$, existují $x\in \Z_n$ a $y\in \Z$, pro něž $ax+by=1$. Je-li $s$ společný dělitel čísel
$a$, $n$, pak $s/(ax+ny)=1$, proto $\NSD(a,n)=1$. Nechť naopak $\NSD(a,n)=1$, potom díky Euklidovu algoritmu existují $x\in \Z$ a
 $y\in \Z$, pro které $ax+ny=1$,
proto $a^{-1}=x\md n$. To znamená, že  $a\in\Z_n^*$. 
\end{prikl}  





\vskip 1cm

\section{Grupy, podgrupy a homomorfismy}

Nyní zaměříme svou pozornost na obecné grupy.
Nejprve učiníme soubor obecných pozorování o jejich algebraicky významných podmnožinách, kterým budeme říkat podgrupy a algebraicky významných zobrazeních mezi grupami, jež budeme nazývat homomorfismy. Poté si prohlédneme ekvivalence na obecných grupách, které zcela pří\-močaře zobecňují pojem
kongruence na celých číslech.
Jako důsledek souboru elementár\-ních technických pozorování
o těchto ekvivalencích dostaneme pro úvahy o podgrupách velmi užitečnou
Lagrangeovu větu, která svazuje dělitelností velikost grupy a její podgrupy.

Podobně jako v předchozí kapitole budeme neutrální prvek obecné multiplikativně zapsané
grupy $G(\cdot)$ označovat symbolem $e$ a inverzní prvek k prvku $g$ symbolem $g^{-1}$.


\begin{definice} {\it Podgrupou} grupy $G(\cdot)$
budeme rozumět každou podmnožinu $H$ množiny $G$, která je uzavřená na 
$\cdot$, obsahuje prvek $e$ a pro jejíž každý prvek $h\in H$ platí, že $h^{-1}\in H$.
{\it Normální podgrupa} je podgrupa $H$ grupy $G$ splňující navíc podmínku
$g\cdot h\cdot g^{-1}\in H$ pro každé $g\in G$ a $h\in H$.
Je-li $H$ podgrupa $G(\cdot)$, definujme na $G$ relace
$\rmod\ H$ a $\lmod\ H$: 
\[(a,b)\in \rmod\ H \Leftrightarrow a\cdot b^{-1}\in H\]
\[(a,b)\in \lmod\ H\Leftrightarrow a^{-1}\cdot b\in H\]
\end{definice}

Protože podle \ref{1.6} pro každý prvek $g$ grupy $G(\cdot)$ platí, že $(g^{-1})^{-1}=g$ , mohli jsme normální podgrupu $H$ také ekvivalentně definovat
také symetrickou podmínkou $g^{-1}\cdot h\cdot g\in H$ pro každé $g\in G$ a $h\in H$.

\begin{pozn}\label{1.9} Nechť $G(\cdot)$ je grupa, $H$ a $H_i$, $i\in I$ její podgrupy.
\begin{enumerate}
\item[(1)] $H(\cdot)$ tvoří s operací omezenou na množinu $H$ opět grupu,
\item[(2)] $\bigcap_{i\in I}H_i$ je podgrupa grupy $G(\cdot)$,
\item[(3)] jsou-li všechny podgrupy $H_i$ normální, pak je i podgrupa $\bigcap_{i\in I}H_i$ 
normální,
\item[(4)] je-li $G(\cdot)$ komutativní grupa, pak je podgrupa $H$ vždy normální.
\item[(5)] $\rmod\ H$ i $\lmod\ H$ jsou ekvivalence na $G$, 
\item[(6)] $\rmod\ H =\lmod\ H$, právě když je $H$ normální podgrupa $G(\cdot)$,
\item[(7)] je-li $H$ normální, pak je  $\rmod\ H$ slučitelná s operací $\cdot$.
\end{enumerate}
\end{pozn}
\begin{proof} (1) Plyne okamžitě z definice podgrupy a vlastností operace $\cdot$ na $G$
(srovnej s důkazem \ref{1.6}).

(2) $e\in H_i$ pro všechna $i\in I$ podle,
tedy $e\in\bigcap_{i\in I}H_i$.
Zvolme libovolně $a,b\in\bigcap_{i\in I}H_i$. Potom $a\cdot b\in H_i$ pro každé
$i\in I$ díky uzavřenosti $H_i$ na operaci $\cdot$, tedy 
$a\cdot b\in \bigcap_{i\in I}H_i$. Podobně podle definice $a^{-1}\in H_i$ pro každé
$i\in I$, proto $a^{-1}\in \bigcap_{i\in I}H_i$.

(3) Zvolme $h\in\bigcap_{i\in I}H_i$ a $g\in G$. Pak $g\cdot h\cdot g^{-1} \in H_i$
pro všechna $i\in I$, a tudíž $g\cdot h\cdot g^{-1} \in \bigcap_{i\in I}H_i$.

(4) Díky komutativitě binární operace platí pro každé 
$g\in G$ a $h\in H$, že $g\cdot h\cdot g^{-1}= g\cdot g^{-1}\cdot h = h\in H$.

(5) Dokážeme jen, že je $\rmod\ H$ ekvivalence, pro $\lmod\ H$ bude důkaz symetrický.
Podgrupa $H$ obsahuje neutrální prvek $e$, proto pro každé $a\in G$ máme
$a\cdot a^{-1}=e\in H$, tedy $(a,a)\in \rmod\ H$. Předpokládáme-li, že
$(a,b)\in \rmod\ H$, pak $a\cdot b^{-1}\in H$, proto i 
$b\cdot a^{-1}=(a\cdot b^{-1})^{-1}\in H$ (podle \ref{1.4} a \ref{1.6}), tudíž
$(b,a)\in \rmod\ H$. Nyní předpokládejme, že $(a,b), (b,c)\in \rmod\ H$,
což podle definice naší relace znamená, že $a\cdot b^{-1}, b\cdot c^{-1}\in H$.
Z uzavřenosti $H$ na binární operaci plyne, že 
$(a\cdot b^{-1})\cdot (b\cdot c^{-1})\in H$, tedy 
$a\cdot c^{-1} = a\cdot b^{-1}\cdot b\cdot c^{-1}\in H$
a $(a,c)\in \rmod\ H$. Tím jsme ověřili, že je relace $\rmod\ H$ reflexivní, symetrická
a tranzitivní.

(6) 
Předpokládejme, že $\rmod\ H =\lmod\ H$ a zvolme $h\in H$ a $g\in G$.
Potom $(g\cdot h)^{-1}\cdot g= h^{-1}\cdot g^{-1}\cdot g = h^{-1}\in H$, 
tedy $(g\cdot h,g)\in \lmod\ H = \rmod\ H$. Z definice $\rmod\ H$ dostaneme
$g\cdot h\cdot g^{-1}\in H$.


Nyní předpokládejme, že je $H$ normální podgrupa grupy $G(\cdot)$.
Zvolíme-li $(a,b)\in \rmod\ H$, víme, že $a\cdot b^{-1}\in H$.
Podle definice normální podgrupy 
$b^{-1}\cdot a =b^{-1}\cdot a\cdot b^{-1} \cdot (b^{-1})^{-1}\in H$,
tedy $(b,a)\in \lmod\ H$ a díky (1) $(a,b)\in \lmod\ H$, čímž
jsme ověřili, že $\rmod\ H \subseteq \lmod\ H$. Symetrický argument
dokazuje obrácenou implikaci.

(7) Zvolme $(a_0,b_0), (a_1,b_1)\in \rmod\ H$, tj.
$a_0\cdot b_0^{-1}$ i $a_1\cdot b_1^{-1}$ jsou prvky $H$. 
Nyní použijeme normalitu $H$, abychom
dostali, že $b_0^{-1}\cdot a_0=b_0^{-1}\cdot (a_0\cdot b_0^{-1})\cdot b_0\in H$.
Uzavřenost $H$ na $\cdot$ zaručuje, že 
$b_0^{-1}\cdot a_0 \cdot a_1\cdot b_1^{-1}\in H$ a dalším využitím normality získáme
$ a_0 \cdot a_1\cdot (b_0\cdot b_1)^{-1}=
b_0\cdot(b_0^{-1}\cdot a_0 \cdot a_1\cdot b_1^{-1})\cdot b_0^{-1}\in H$, tedy
$(a_0\cdot a_1,b_0\cdot b_1)\in \rho$, čímž jsme ověřili slučitelnost 
ekvivalence $\rmod\ H$ s s operací $\cdot$.
\end{proof}

Vedle obecných příkladů největší a nejmenší podgrupy nejprve nahlédneme, jak vypadají všechny podgrupy grupy celých čísel.

\begin{prikl}\label{1.10}\rm 
(1) Všimněme si, že v každé grupě $G(\cdot)$ tvoří množiny $\{e\}$ a $G$
(tzv. {\it triviální}) příklady normálních podgrup.

(2) Uvažujeme-li komutativní grupu celých čísel $\Z(+)$ (s neutrálním
prvkem $0$ a inverzními prvky značenými standardně symbolem $-$),
potom množiny tvaru $n\Z=\{n\cdot z|\ z\in \Z\}$ jsou pro
každé nezáporné celé $n$ podgrupou grupy $\Z(+)$ (viz~\ref{0.1}).
Naopak, uvažujme libovolnou nenulovou podgrupu $P$ grupy $\Z(+)$.
Protože $P$ obsahuje nějaký nenulový prvek a s každým $a\in P$ je i $-a\in P$,
leží v $P$ jistě nějaký kladný prvek a my můžeme zvolit nejmenší kladné
číslo obsažené v $P$, označme ho $n$. Ukažme, že nutně $P=n\Z$. 
Indukcí díky uzavřenosti
$P$ na sčítání nahlédneme, že $2n=n+n\in P$, $3n\in P$, \dots, $kn\in P$, \dots, 
pro každé přirozené $k$. Protože $-n\in P$, dostaneme stejným argumentem, že
$n\Z\subseteq P$. Nyní zvolme libovolně $a\in P$. Potom vydělíme se zbytkem
číslo $a$ číslem $n$, t.j. najdeme celé $q$ a nezáporné celé $z< n$, pro která
$a=qn+z$. Z uzavřenosti $P$ na $+$ použité pro prvky $a,-qn\in P$ plyne, že $z=a+(-qn)\in P$,
a z minimality volby $n$ dostáváme, že $z=0$, tedy $n\Z= P$.
\end{prikl}


\begin{definice}
Zobrazení $\varphi:G\to H$ grup $G(\cdot)$ a $H(\cdot)$ slučitelné s jejich binárními operacemi 
se nazývá (grupový) {\it homomorfismus}. Bijektivní homomorfismus budeme nazývat 
{\it izomorfismus}.
Podmnožině $\Ker \varphi=\{g\in G|\ \varphi(g)=e\}$
i relaci $\ker \varphi=\{(g_1,g_2)\in G\times G|\ \varphi(g_1)=\varphi(g_2)\}$ budeme říkat
{\it jádro homomorfismu}.
Jestliže mezi dvěma grupami $G_1$ a $G_2$ existuje izomorfismus, říkáme,
že $G_1$ a $G_2$ jsou {\it izomorfní} a píšeme $G_1\cong G_2$.
\end{definice}

Je-li $\varphi:G\to H$ zobrazení, $A\subseteq G$ a ,  připomeňme, že obrazem $\varphi(A)$ podmnožiny
$A\subseteq G$ rozumíme podmnožinu $\{\varphi(a)\mid a\in A\}$ množiny $H$ a úplným vzorem $\varphi^{-1}(B)$ podmnožiny
$B\subseteq H$ rozumíme podmnožinu $\{g\in G|\ \exists b\in B: \varphi(g)=b\}$ množiny $H$.
Všimněme si, že symbol $\varphi^{-1}(B)$ má dobrý význam i v případě, že zobrazení $\varphi$ není bijekce, a tedy nemáme k dispozici
inverzní zobrazení. Je-li $\varphi:G\to H$ grupový homomorfismus, pak si dále všimneme, že $\varphi^{-1}(\{e\})=\Ker \varphi$
a že $\varphi(\Ker \varphi)=\{e\}$.




\begin{pozn}\label{1.17} Nechť $G_1(\cdot)$,  $G_2(\cdot)$ a $G_3(\cdot)$ jsou grupy a
$\varphi:G_1\to G_2$ a $\psi:G_2\to G_3$ jsou homomorfismy. 
\begin{enumerate}
\item[(1)] $\varphi(e)=e$ a $\varphi(a^{-1})=(\varphi(a))^{-1}$ pro každé $a\in G$,
\item[(2)] $\psi\varphi$ je homomorfismus,
\item[(3)] je-li $\varphi$ bijekce, pak $\varphi^{-1}$ je izomorfismus,
\item[(4)] obraz $\psi(H)$ je podgrupa $G_3(\cdot)$ a úplný vzor $\varphi^{-1}(H)$
je podgrupa $G_1(\cdot)$ pro každou podgrupu $H$ grupy $G_2(\cdot)$,
\item[(5)] $\Ker \varphi$ je normální podgrupa $G_1(\cdot)$ a $\ker \varphi = \rmod\ \Ker \varphi = \lmod\ \Ker \varphi$,
\item[(6)] $\varphi$ je prostý homomorfismus, právě když $\Ker \varphi=\{e\}$ a to nastává, právě když $\ker \varphi=\id$.
\end{enumerate}
\end{pozn}
\begin{proof} (1)  Protože $\varphi(e)=\varphi(e\cdot e)=\varphi(e)\cdot \varphi(e)$, stačí rovnost
$\varphi(e)=\varphi(e)\cdot \varphi(e)$ přenásobit prvkem $\varphi(e)^{-1}$, abychom dostali
\[
e=\varphi(e)\cdot \varphi(e)^{-1}=\varphi(e)\cdot \varphi(e)\cdot \varphi(e)^{-1} =\varphi(e).
\]
Dále $e=\varphi(e)= \varphi(a^{-1}\cdot a) = \varphi(a^{-1})\cdot \varphi(a)$ a podobně
$e=\varphi(a)\cdot \varphi(a^{-1})$, proto $\varphi(a^{-1})=(\varphi(a))^{-1}$.

(2) Je-li $a,b \in G_1$, pak 
$\psi\varphi(a\cdot b)= \psi(\varphi(a)\cdot \varphi(b))= \psi(\varphi(a))\cdot \psi(\varphi(b))$.

(3) Stačí ověřit, že $\varphi^{-1}$ je homomorfismus. Zvolíme-li $c,d \in G_2$,
potom 
\[
\varphi(\varphi^{-1}(c)\cdot \varphi^{-1}(d)) = c\cdot d,\ \ \text{proto}\ \ \varphi^{-1}(c)\cdot \varphi^{-1}(d) = \varphi^{-1}(c\cdot d).
\]

(4) Nejprve ukážeme, že je $\psi(H)$ podgrupa $G_3(\cdot)$. 
Podle (1) je $e=\psi(e)\in \psi(H)$. Vezměme  $u,v \in \psi(H)$, tj. existují
$c,d \in H$, pro která $\psi(c)=u$ a $\psi(d)=v$. Protože $c\cdot d,\ c^{-1} \in H$,
dostáváme přímo z definice, že
\[
u\cdot v = \psi(c)\cdot \psi(d)= \psi(c\cdot d)\in \psi(H),
\] 
a $u^{-1} = \psi(c)^{-1} = \psi(c^{-1})\in \psi(H)$ podle (1).

Poznamenejme, že $e\in \varphi^{-1}(H)$ a zvolme
$a,b\in \varphi^{-1}(H)$, tj. $\varphi(a),\varphi(b)\in H$. Potom opět
$\varphi(a)\cdot \varphi(b)= \varphi(a\cdot b)\in H$, 
a $\varphi(a^{-1}) = \varphi(a)^{-1}\in H$, tedy $a\cdot b,\ a^{-1}\in \varphi^{-1}(H)$, proto je
$\varphi^{-1}(H)$ podgrupa.

(5) Protože $\{e\}$ je podgrupa $G_2(\cdot)$ a $\Ker \varphi=\varphi^{-1}(\{e\})$, je
$\Ker \varphi$ podgrupa podle (4). Vezmeme-li libovolné $g\in G_1$ a $h\in \Ker \varphi$, potom
\[
\varphi(g\cdot h\cdot g^{-1})=\varphi(g)\cdot \varphi(h)\cdot \varphi(g^{-1})=\varphi(g)\cdot e\cdot \varphi(g)^{-1} = e,
\]
tedy $g\cdot h\cdot g^{-1}\in\Ker \varphi$.
Zbývá si uvědomit, že 
$\varphi(a)=\varphi(b) \Leftrightarrow \varphi(a)\cdot \varphi(b)^{-1}=e\Leftrightarrow \varphi(a\cdot b^{-1})=e
\Leftrightarrow  a\cdot b^{-1}\in\Ker \varphi$.

(6) Je-li $\varphi$ prosté, pak existuje jediný vzor jednotky, tedy $\Ker \varphi=\{e\}$ a jestliže $\ker \varphi=\id$, pak je zřejmě $\varphi$ prosté.
Konečně, jestliže $\Ker \varphi=\{e\}$, potom $\ker \varphi = \rmod\ \Ker \varphi=\rmod\ \{e\}=\id$ podle (5).
\end{proof}




\begin{prikl}\rm 
(1) Identita na libovolné grupě $G(\cdot)$ a zobrazení, které
jakémukoli prvku grupy přiřadí neutrální prvek jiné grupy, představují
triviální příklady homomorfismů.
 
(2) Je-li $\varphi:U\to V$ lineární zobrazení dvou vektorových prostorů nad týmž tělesem se sčítáním vektorů označeným symbolem $+$, pak je 
$\varphi$ homomorfismus aditivních grup $U(+)$ a $V(+)$.

(3) V rámci kurzu lineární algebry bylo dokázáno, že znaménko součinu permutací je rovno součinu jejich znamének,
tedy, že $\sgn: S_n\to \{1,-1\}$ je homomorfismus grupy permutací $S_n(\circ)$ do dvouprvkové grupy $\{1,-1\}(\cdot)$.
Podle \ref{1.17}(5) je $\Ker\ \sgn=A_n$ je normální podgrupa grupy $S_n(\circ)$.
Navíc lze (elementárními prostředky) dokázat, že grupa $S_n(\circ)$ neobsahuje
pro $n\ne 4$ jiné normální podgrupy než $\{\Id\}$, $S_n$ a $A_n$
(v případě $S_4$ se vyskytuje ještě jedna tzv. Kleinova normální podgrupa $K=\{\Id, (12)(34), (13)(24), (14)(23)\}$).
Všimneme si, že například podgrupy $T=\{\Id, (12)\}$ grupy $S_3$
není normální ($(13)\circ(12)\circ(13)^{-1}=(23)\not\in T$).

(4) V lineární algebře se dále dokazuje, že determinant $\det$ je homomorfismus z grupy regulárních matice 
$n\times n$ nad tělesem $T$ do multiplikativní grupy tělesa $T\setminus\{0\}(\cdot)$, snadno nahlédneme, že i druhá mocnina determinantu $\det^2$ je homomorfismus stejných grup, tedy 
$\Ker\ \det=\{\mathbf A\in GL_n(T)\mid\det(\mathbf A)=1 \}$
a $\Ker\ \det^2=\{\mathbf A\in GL_n(T)\mid\det(\mathbf A)=\pm 1 \}$ jsou díky \ref{1.17}(5) normální podgrupy grupy $GL_n(T)(\cdot)$.
%Uvažujme pro každé $k\in Z_n$ na grupě $Z_n(+)$ zobrazení $\mu_k:Z_n\to Z_n$ dané předpisem $\mu_k(a)=(k\cdot a)\md n$. Potom se jedná opět o grupový homomorfismus.
\end{prikl}



 Nechť $H$ a $K$ jsou dvě podmnožiny grupy $G(\cdot)$
a $g\in G$. Označme množiny $H\cdot K=\{h\cdot k|\ h\in H,\ k\in K\}$,
$gH=\{g\}H$ a $Hg=H\{g\}$. 
V případě grup s operací $\cdot$ budeme často psát $hk$ místo $h\cdot k$ a  $HK$ místo $H\cdot K$.






\begin{pozn}\label{1.12} Nechť $G(\cdot)$ je grupa a $H$ její podgrupa.
Potom platí: 
\begin{enumerate}
\item[(1)] $(a,b)\in \rmod\ H \Leftrightarrow (a^{-1},b^{-1})\in \lmod\ H$ pro každé $a,b\in G$,
\item[(2)] $|G/\rmod\ H| = |G/\lmod\ H|$,
\item[(3)] $[a]_{\rmod\ H} = Ha$ a $[a]_{\lmod\ H} = aH$ pro každé $a\in G$,
\item[(4)] $|[a]_{\rmod\ H}| = |[a]_{\lmod\ H}|= |H|$ pro každé $a\in G$.
\end{enumerate}
\end{pozn}
\begin{proof} (1) Díky \ref{1.6} máme rovnost $a\cdot b^{-1} =(a^{-1})^{-1}\cdot b^{-1}$, proto
$a\cdot b^{-1}\in H \Leftrightarrow (a^{-1})^{-1}\cdot b^{-1}\in H$, čímž jsme
dokončili důkaz.

(2) Podle (1) je zobrazení
$[a]_{\rmod\ H}\to [a^{-1}]_{\lmod\ H}$ korektně definovanou bijekcí, tedy faktorové
množiny $G/\rmod\ H$ a $G/\lmod\ H$ mají stejně prvků.

(3) Opět se budeme věnovat jen ekvivalenci $\rmod\ H$. Použijeme definici
rozkladové třídy:
\[
[a]_{\rmod\ H}=\{b\in G|\ (a,b)\in \rmod\ H\} =
\{b\in G|\ \exists h\in H:\  a\cdot b^{-1}=h\} =
\]
\[
=\{ b \in G|\ \exists h\in H:\  b=h^{-1}\cdot a\} = 
\{ b \in G|\ \exists h'\in H:\  b=h'\cdot a\} = 
Ha.
\]

(4) Definujme zobrazení $b: H \to Ha$ (resp. $H \to aH$) předpisem
$b(h) = h\cdot a$ (resp. $b(h) = a\cdot h$). Zřejmě jde o zobrazení
na $Ha$ (resp. na $aH$) a předpokládejme, že $b(h_0)=b(h_1)$, tedy 
$h_0\cdot a=h_1\cdot a$. Tuto rovnost zprava (resp. zleva)
přenásobíme hodnotou $a^{-1}$, abychom dostali 
$h_0=h_0\cdot a\cdot a^{-1}=h_1\cdot a\cdot a^{-1} = h_1$. Tedy $b$ je bijekce
a všechny množiny $H$, $aH$, $Ha$ mají stejný počet prvků. Nyní zbývá použít (3).
\end{proof}


\begin{definice} Buď $H$ podgrupa grupy $G(\cdot)$.
Potom číslu $[G:H]=|G/\rmod\ H|$ ($=|G/\lmod\ H|$ podle \ref{1.12}) budeme říkat
{\it index podgrupy} $H$ v grupě $G$ a velikosti $|G|$ množiny $G$ budeme říkat 
{\it řád grupy} $G$.
\end{definice}

\begin{theorem}[Lagrange]\label{Lagrange} Je-li $H$ podgrupa grupy $G(\cdot)$,
pak $|G|=[G:H]\cdot|H|$.
\end{theorem}
\begin{proof} Podle \ref{1.9}(5) je $\rmod\ H$ ekvivalence, proto 
$G=\dot{\bigcup}_{A\in G/\rmod\ H}A$, kde sjednocujeme disjunktní množiny.
Využijeme-li dále poznatek \ref{1.12}(4), který
říká, že všechny ekvivalenční třídy mají počet prvků stejný jako množina $H$,
pak dostáváme
\[
|G|=|{\bigcup^\circ}_{A\in G/\rmod\ H}A| = \sum_{A\in G/\rmod\ H}|A|
= \sum_{A\in G/\rmod\ H}|H| = [G:H]\cdot|H|.
\]
\end{proof}

\begin{dusl}\label{DuslLagrange} Je-li $G(\cdot)$ konečná grupa, potom řád každé její podgrupy dělí řád grupy $G$.\end{dusl}

\begin{prikl}\rm Z předchozího důsledku okamžitě plynou následující pozorování:

(1) Grupa prvočíselného řádu obsahuje jen triviální podgrupy, tedy $G$ a $\{e\}$.

(2) Protože $|S_{10}|=10!$ a $11$ nedělí $10!$, permutační grupa  řádu $S_{10}(\circ)$
neobsahuje žádnou podgrupu řádu 11.

(3) Jsou-li $H$ a $K$ dvě konečné podgrupy nějaké grupy $G(\cdot)$ a platí-li, že jsou řády $H$ a $K$
nesoudělné, pak $H\cap K=\{1\}$.
\end{prikl}

%Nakonec učiníme početně užitečné pozorování, že výsledkem součin dvou normálních podgrup grupy je nejmenší normální podgrupa, která obě obsahuje.

%\begin{prikl}\label{1.11}\rm (1) Mějme dvě normální podgrupy $H$ a $K$ grupy $G(\cdot)$. Pak pro každé $h_0\in H$ a $k\in K$ existuje $h_1\in H$, pro které $k\cdot h_0\cdot k^{-1}=h_1$, tedy $k\cdot h_0=h_1 \cdot k$ a $KH\subseteq HK$. Symetrický argument dokazuje i obrácenou inkluzi, proto $KH=HK$. Nyní snadno nahlédneme, že je součin $HK$ rovněž podgrupou $G(\cdot)$: zřejmě $e=e\cdot e \in HK$ a zvolíme-li $h_0,h_1\in H$ a $k_0,k_1\in K$, potom $(h_0\cdot k_0)^{-1}=k_0^{-1}\cdot h_0^{-1}\in KH=HK$ a dále existuje takové $h_2\in H$, že $k_0\cdot h_1 = h_2\cdot k_0$, proto $h_0\cdot k_0\cdot h_1\cdot k_1=h_0\cdot h_2\cdot k_0\cdot k_1\in HK$. Konečně vezmeme-li libovolné prvky $g\in G$, $h\in H$ a $k\in K$, pak platí $g\cdot h \cdot k \cdot g^{-1} = (g\cdot h \cdot g^{-1})\cdot (g \cdot  k \cdot g^{-1})\in HK$ díky předpokládané normalitě obou podgrup. Vidíme, že ,,součin" normálních podgrup (například tedy součin libovolných podgrup komutativní grupy) dává opět normální podgrupu. Poznamenejme, že součin podgrup, které normální nejsou, vůbec nemusí být podgrupou (stačí uvážit například podgrupy $H=\{Id, (12)\}$ a $K=\{Id, (13)\}$ grupy $S_3$).

%(2) Uvažujeme-li komutativní grupu $A(+)$ a $H$, $K$ její podgrupy, pak $H+K=\{h+ k|\ h\in H,\ k\in K\}$ je podle předchozího pozorování opět podgrupa. Speciálně, vezmeme-li grupu celých čísel $\Z(+)$, pak $30\Z+54\Z=\{30x+ 54y|\ x,y\in \Z\}=\NSD(30,54)\Z=6\Z$. Všimněme si také, že $30\Z \cap 54\Z=\{z\in \Z|\ 30/z , 54/z\}=\nsn(30,54)\Z=270\Z$. 
%\end{prikl}
 


%\section{Faktorové grupy a izomorfismy grup}

%V této kapitole se seznámíme s homomorfismy, tedy se zobrazeními grup, které budou s to přenášet některé jejich vlastnosti. Mimořádné místo mezi homomorfismy zaujímají bijektivní homomorfismy, jimž budeme říkat izomorfismy. 
%Vezmeme-li si například pro grupu $H=\{\id,(12)\}$ grupy permutací $S_3(\circ)$, která není normální, ekvivalence $\rmod H$ podle předchozí věty není slučitelná s operací $\circ$ a podle \ref{1.12}(4) platí $\rmod H\ne \lmod H$. 





\vskip 1cm

\section{Klasifikace cyklických grup}

V následující kapitole omezíme záběr našeho zkoumání na grupy, které jsou určeny
jediným prvkem a obvykle se nazývají {\it cyklické}. Nejen, že záhy nahlédneme, že jsou
nutně komutativní, ale ukážeme, že jich je málo a že je všechny už známe, konkrétně,
že jsou izomorfní některé z grup $\Z(+)$ a $\Z_n(+)$ pro $n\in \N$. S využitím 
dělitelnosti se proto ukáže, že víme dost o jejich struktuře.


Nejprve ovšem připomeňme, že podle \ref{1.9}(2) je průnik libovolného systému podgrup zase
podgrupou. Uvážíme-li grupu $G(\cdot)$ a podmnožinu $X\subseteq G$,
pak průnik všech podgrup $G(\cdot)$ obsahujících $X$ je rovněž podgrupou
obsahující $X$, označme ho $\langle X\rangle$, zjevně se jedná o nejmenší
takovou podgrupu vzhledem k inkluzi. Speciálně budeme psát $\langle g\rangle$
místo $\langle \{g\}\rangle$, je-li $g\in G$.

\begin{definice} Buď $G(\cdot)$ grupa a $X\subseteq G$.
Podgrupu $\langle X\rangle$ nazveme podgrupu $G(\cdot)$ {\it generovanou}
množinou $X$.
Řekneme, že $G(\cdot)$ je {\it cyklická grupa}, existuje-li takový prvek $g\in G$, že
$\langle g\rangle = G$.
\end{definice}


\begin{prikl}\label{2.0} \rm (1) $\Z(+)$ je cyklická grupa, kde 
$\Z =\langle 1\rangle =\langle -1\rangle$.

(2) $\Z_n(+)$ je pro každé přirozené $n$ cyklická grupa s operacemi
definovanými modulo $n$, kde $\Z_n =\langle a\rangle$, právě když  $\NSD(a,n)=1$.
Jestliže $\Z_n =\langle a\rangle$, potom $1\in \langle a\rangle$, a proto existuje $x\in\N$, pro které
$a\cdot x\equiv 1\ (\md n)$. To znamená, že $a\cdot x+ n\cdot y = 1$ pro vhodné celé $y$, a protože
$\NSD(a,n)$ dělí levou stranu rovnosti, musí dělit i jedničku a proto $\NSD(a,n)=1$.

Naopak, předpokládáme-li, že $\NSD(a,n)=1$, potom díky Eukleidovu algoritmu (\ref{EA}) existují 
$x\in\Z_n$ a celé $y$, pro něž $a\cdot x+ n\cdot y=1$.
Proto $(a\cdot x)\md n=1$, tudíž $1\in a\Z_n$ a $\Z_n= \langle a\rangle$.
\end{prikl}


Nechť $G(\cdot)$ je grupa $a\in G$. Definujme indukcí:
\begin{enumerate}
\item[ ] $a^0 = e$, 
\item[ ] $a^n = a^{n-1}\cdot a$ pro každé $n>0$,
\item[ ] $a^n = (a^{-1})^{|n|}$ pro každé $n<0$.
\end{enumerate}

Poznamenejme, že pro ,,aditivně" zapsané grupy $A(+)$ označujeme neutrální prvek 
$0$. Proto pro $a\in G$ značíme  $-a$ opačný prvek a dále
$0\cdot a=0$,  $n\cdot a=(n-1)\cdot a+ a$ pro $n>0$ a $n\cdot a=|n|\cdot (-a)$  pro $n<0$.

\begin{pozn}\label{2.1} Nechť $G(\cdot)$ je grupa a $a\in G$.
Zobrazení $\phi: \Z\to G$ dané předpisem $\phi(n)=a^n$
je homomorfismus grup $\Z(+)$ a $G(\cdot)$
a $\phi(\Z)=\langle a\rangle =\{a^n|\ n\in \Z\}$. 
\end{pozn}
\begin{proof} Potřebujeme pro každou dvojici $m,n\in \Z$ ověřit, že
$\phi(n+m)=a^{n+m}=a^n\cdot a^m = \phi(n)\cdot \phi(m)$.
Přitom $a^{n+m}=a^n\cdot a^m$ zjevně platí pro obě nezáporná a obě záporná $m,n$.
Je-li $n$ záporné a $m+n$ nezáporné, pak
$a^n\cdot a^m=(a^{-1})^{-n}\cdot a^m = a^{n+m}$.
Podobně pro $n$ záporné, $m$ kladné a $m+n$ záporné máme
$a^n\cdot a^m=(a^{-1})^{-n}\cdot a^m = (a^{-1})^{-n-m}=a^{n+m}$.

Závěrem poznamenejme, že $\phi(\Z)$ je právě tvaru $\phi(\Z)=\{a^n|\ n\in \Z\}$, a proto se jedná o nejmenší podgrupu $G(\cdot)$ obsahující $a$.
\end{proof}

V následujícím pozorování shrňme užitečné početní vlastnosti exponentů.

\begin{dusl}\label{2.2} Nechť $G(\cdot)$ je grupa a $a\in G$. Potom pro každé $n, m\in \Z$ platí, že $a^{-n}=(a^n)^{-1}$ a $(a^n)^m=a^{nm}$. 
\end{dusl}

Pro práci s jednotlivými prvky grupy je užitečné zavést následující terminologii.

\begin{definice}
{\it Řádem prvku} $g$ grupy $G(\cdot)$ rozumíme právě řád cyklické podgrupy $\langle g\rangle$
a {\it exponentem prvku} $g$ rozumíme každé přirozené číslo $n$, pro které platí $g^n=1$.
\end{definice}

Z Důsledky~\ref{DuslLagrange} okamžitě dostáváme pozorování, že
v konečné grupě řád prvku dělí řád grupy. Následující popis řádu prvku
využijeme v následující klasifikaci obecných cyklických grup.

\begin{pozn}\label{ord} Řád prvku $g$ grupy $G(\cdot)$ je nejmenší kladné číslo $k$, pro něž $g^k=e$ nebo $\infty$ v případě, že takové $k$ neexistuje. Navíc, je-li řád $g$ konečný, pak dělí každý exponent $g$.
\end{pozn}
\begin{proof} Nechť existuje kladné číslo $k$, pro něž $g^k=e$.
Označíme-li $q:=(n)\dv k$ a $r:=(n)\dv k$ pro libovolné celé $n$, pak
z \ref{2.1} a \ref{2.2} dostáváme
\[
g^n=g^{qk+r}=(g^k)^q\cdot g^r= e^q\cdot g^r = g^r,
\]
a proto $\langle g\rangle=\{g^i|\ i\in\Z_k\}$. Zvolíme-li $k$ minimální možné, pak pro $0\le 0i<j<k$ platí, že $g^i\ne g^j$, neboť $g^{j-i}\ne e$. To znamená, že $|\langle g\rangle|=k$ a nejmenší kladný exponent je dělitelem ostatních exponentů.

Pokud neexistuje žádný kladný exponent, pak pro každou dvojici $i<j$ ze stejného důvodu platí, že $g^i\ne g^j$, tudíž je řád prvku $g$ nekonečný.
\end{proof}



\begin{theorem}\label{2.4} Buď $G(\cdot)$ cyklická grupa.
\begin{enumerate}
\item[(1)] Je-li $G$ nekonečná, pak $G(\cdot)\cong \Z(+)$.
\item[(2)] Je-li $n=|G|$ konečné, pak $G(\cdot)\cong \Z_n(+)$.
\end{enumerate}
\end{theorem}
\begin{proof} Vezměme nějaký generátor $g$ cyklické grupy $G(\cdot)$, tedy
$\langle g\rangle = G$. Je-li řád $|G|=|\langle g\rangle|$ nekonečný,  definujme zobrazení 
$\phi: \Z\to G$ předpisem $\phi(j)=g^j$. Potom jde podle \ref{2.1} o homomorfismus na celé $G$, pro který $\Ker\phi=\{0\}$ díky Poznámce~\ref{ord} a tudíž je podle Poznámky~\ref{1.17}(6) $\phi$ prostý.

Nechť $n=|G|=|\langle g\rangle|$ je konečný řád.
Pak je zobrazení $\phi: \Z_n\to G$ dané předpisem $\phi(j)=g^j$ bijekce
a platí, že
\[
\phi((x+y)\md n)=g^{(x+y)\md n}=
g^{(x+y)\md n}\cdot g^{n(x+y)\dv n}=g^{x}\cdot g^y =\phi(x)\cdot \phi(y),
\]
tedy jde o homomorfismus.
\end{proof}

Předchozí kritérium nám usnadní důkaz následující vlastnosti cyklických grup.

\begin{dusl}\label{2.5} Každá podgrupa cyklické grupy je opět cyklická.
\end{dusl}
\begin{proof} 
Díky \ref{2.4} stačí tvrzení o podgrupách dokázat pro grupy $\Z(+)$ a
$\Z_n(+)$. Nejprve ho dokažme pro grupu $\Z(+)$. 
V \ref{1.10}(2) jsme ověřili, že $\Z(+)$ jiné podgrupy než podgrupy
tvaru $n\Z$ neobsahuje. Přitom $\langle n\rangle =n\Z$ je cyklická
grupa, čímž je tvrzení ověřeno.

Nyní využijeme homomorfismu $F_n:\Z\to \Z_n$ z \ref{0.1}.
Zvolíme-li podgrupu $H$ grupy $\mathbf{Z}_n(+)$, pak $F_n^{-1}(H)$ je podle
předchozí úvahy a \ref{1.17}(5) cyklická podgrupa $\Z$, tedy
$H=F_n(F_n^{-1}(H))$ je cyklická podgrupa $\Z_n(+)$.
\end{proof}

Na závěr si všimněme, že pro každé přirozené $k$  značíme
$k\Z=\{kz|\ z\in \Z\}$, a proto jde podle Poznámky~\ref{2.1} o nejmenší podgrupu grupy $\Z(+)$, obsahující $k$, tedy $\langle k\rangle=k\Z$. 
Podobně pro každé $k\in\Z_n$ platí, že  $k\Z_n=\langle k\rangle=\{k\cdot z|\ z\in \Z_n\}$.


%Snadno nahlédneme, že je-li $g$ generátor cyklické grupy $G(\cdot)$,pak $[g]_H$ je generátor její faktorové grupy $G/H(\cdot)$.

%Na závěr kapitoly dokážeme užitečný vzoreček na výpočet Eulerovy funkce, která určuje právě počet generátorů konečných cyklických grup.



\vskip 1cm
\section{Cyklické grupy v kryptografii}


Teorie prezentovaná v předchozích kapitolách má několik užitečných kryptografických
aplikací založených na jednoduchém pozorování, že je obvykle mnohem snazší v grupě mocnit, než ze známé mocniny
určovat její základ či exponent. Dříve než se k popisu protokolu založeného na obtížnosti odmocňování
(RSA v Příkladu~\ref{RSA}) a protokolů, které se opírají o obtížnost diskrétního logaritmu (Příkladu~\ref{dl}) dostaneme,
učiníme pozorování o struktuře uspořádané množiny podgrup koneč\-né cyklické grupy (Poznámka~\ref{2.8}),
počtu generátorů cyklické grupy pomocí Eulerovy funkce (Věta~\ref{phi})
a o řádu prvků obecné grupy, které je známo pod názvem Eulerova věta (Věta~\ref{MFT}).




\begin{pozn}\label{2.8} Nechť $k,n$ jsou taková přirozená číslá, že $k>1$ a $k/n$. Pak $\langle \frac{n}{k} \rangle$ je jediná podgrupa grupy $\Z_n(+)$ řádu $k$ a 
pro každé $a\in\Z_n\setminus\{0\}$ platí, že $\langle a\rangle=\langle \frac{n}{k}\rangle$, právě když $\frac{n}{k}=\NSD(a,n)$.
\end{pozn}
\begin{proof} Nejprve zvolme libovolný dělitel $d$ čísla $n$ menší než $n$. Pak snadno nahlédneme, že
$\langle d \rangle = \{0, d, 2d, \dots, (\frac{n}{d}-1)d\}$ je podgrupa řádu $\frac{n}{d}$.
Pro volbu $d=\frac{n}{k}$ je podgrupa $\langle \frac{n}{k}\rangle$ řádu $k$. 

Položíme-li $d:=\NSD(a,n)$ pro nějaké $a\in\Z_n\setminus\{0\}$, pak 
je $d$ dělitel $n$ a ukážeme, že $\langle a\rangle=\langle d\rangle$.
Eukleidův algoritmus nám zaručuje existenci čísla
$x\in\Z_n$ a celého $y$, pro něž $a\cdot x+ n\cdot y=d$, z čehož plyne, že
$(a\cdot x)\md n=d$. Proto $d\in \langle a\rangle=$, a tudíž $\langle d\rangle\subseteq \langle a\rangle$. 
Naopak, protože $d/a$, dostáváme, že $a\in \langle d\rangle$, proto $\langle a\rangle\subseteq \langle d\rangle$,
čímž jsme dokončili důkaz rovnosti $\langle a\rangle=\langle d\rangle$.

Dokázali jsme, že pro každý dělitel $k$ čísla $n$ větší než $1$ máme jedinou podgrupu tvaru $\langle \frac{n}{k}\rangle$
a pro $a\in\Z_n\setminus\{0\}$ máme $\langle a\rangle=\langle \NSD(a,n)\rangle$. Ze zřejmého faktu, že $\NSD(a,n)$ dělí $n$,
plyne platnost závěrečné ekvivalence.
\end{proof}

Poznamenejme, že $\langle 0 \rangle=\{0\}$ je jediná podgrupa grupy $\Z_n(+)$ řádu 1, a 
s využitím klasifikační Věty~\ref{2.4} vidíme, že pro každý dělitel $k$ řádu konečné cyklické grupy, existuje právě jedna
její podgrupa grupy řádu $k$. Protože podle Lagrangeovy věty řád podgrupy dělí řád grupy, máme kompletně popsánu strukturu
podgrup konečných cyklických grup.

\begin{definice} {\it Eulerovou funkcí}  nazveme zobrazení $\varphi: \N\to \N$ dané předpisem
\[\varphi(n)=|\Z_n^*|=|\{k\in\Z_n|\ \NSD(k,n)=1\}|.\]
\end{definice}

Rovnost v definici jsme nahlédli v Příkladu~\ref{1.8}(4) a v Příkladu~\ref{2.0}(2) jsme ukázali, že hodnota Eulerovy funkce $\varphi(n)$ udává počet generátorů cyklické grupy řádu $n$.
Následují věta nám nám při znalosti prvočíselného rozkladu čísla $n$ umožní spočítat hodnotu $\varphi(n)$, tedy počet generátorů
jakékoli cyklické grupy řádu $n$.

\begin{theorem}\label{phi} Buď $p_1<p_2<\dots<p_k$ prvočísla a $r_1,r_2,\dots,r_k$
kladná celá čísla. Potom 
$\varphi(\prod_{i=1}^k p_i^{r_i}) =
\prod_{i=1}^k \varphi(p_i^{r_i}) = 
\prod_{i=1}^k (p_i-1)p_i^{r_i-1}$.
\end{theorem}
\begin{proof} 
Nejprve pro libovolné prvočíslo $p$ a kladné celé číslo $r$ spočítáme, že $\varphi(p^k)=(p-1)\cdot p^{k-1}$.
Číslo menší než $p^k$ je soudělné s $p^k$ právě tehdy, když je násobkem čísla $p$.
Protože nezáporných násobků čísla $p$ menších než $p^k$ je zřejmě právě $p^{k-1}$, dostáváme,
že kladných čísel nesoudělných s $p^k$ máme 
\[
\varphi(p^k) = p^k- p^{k-1} = (p-1)p^{k-1}.
\] 

Dále položme $n_i=p_i^{r_i}$ a $n=\prod_{i=1}^k n_i$ 
a uvažujme zobrazení $H:\Z_n\to\prod_{i=1}^k\Z_{n_i}$ z Věty \ref{CRT}. 
Všimněme si, že $\prod_{i=1}^k\Z_{n_i}(\cdot)$ s operací z Příkladu~\ref{0.4} tvoří monoid s neutrálním prvkem $H(1)=(1,\dots,1)$, 
a proto platí ekvivalence
\[
(a_1,\dots,a_k)\in(\prod_{i=1}^k\Z_{n_i})^* \Leftrightarrow \forall i=1,\dots,n \exists b_i: a_i\cdot b_i=1 \Leftrightarrow 
(a_1,\dots,a_k)\in\prod_{i=1}^k\Z_{n_i}^*.
\]
Protože jsou $n_1,\dots,n_k$ nesoudělné,
je $H$ podle \ref{CRT} bijekce, a proto platí
\[
a\in\Z_n^* \Leftrightarrow \exists b\in \Z_n: a\cdot b=1 \Leftrightarrow \exists c\in\prod_{i=1}^k\Z_{n_i}: H(a)\cdot c=H(1) \Leftrightarrow 
H(a)\in(\prod_{i=1}^k\Z_{n_i})^*.
\]
Spojíme-li obě pozorování dostáváme rovnost $H(\Z_n^*)=\prod_{i=1}^k\Z_{n_i}^*$. Odtud a z výše dokázaného faktu $\varphi(n_i)=(p_i-1)\cdot p_i^{k-1}$ plyne
dokazovaná rovnost

$
\varphi(n)=|\Z_n^*|=|H(\Z_n^*)|=|\prod_{i=1}^k\Z_{n_i}^*|=\prod_{i=1}^k\varphi(n_i)=\prod_{i=1}^k(p_i-1)\cdot p_i^{k-1}
$
\end{proof}

%\begin{prikl}\label{2.5a} \rm Uvažujme podgrupu $\langle30\rangle$ grupy $\Z_{72}(+)$, pak podle \ref{2.8} všimněme si, že hledáme-li generátor grupy $\langle30\rangle=\langle\NSD(30,72)\rangle=\langle6\rangle$. Grupa $\Z_{72}(+)$ přitom podle \ref{phi} obsahuje právě $\varphi(72)=\varphi(2^3\cdot 3^2)=(2-1)2^2\cdot (3-1)3^1=24$ generátorů a podgrupa $\langle6\rangle\cong \Z_{12}$ má právě $\varphi(24)=\varphi(2^3\cdot 3)=8$ generátorů.
%\end{prikl}
%Nyní zobecníme úvahu příkladu \ref{2.5a}.



\begin{prikl}\label{cykl} \rm (1) Uvažujme cyklickou grupu $G(\cdot)$ řádu $n:=|G|$.
Potom $G(\cdot)$ obsahuje právě $\varphi(n)$
generátorů. Protože díky Lagrangeově větě řád podgrupy vždy dělí řád grupy,
podle \ref{2.8} $G(\cdot)$ pro každý dělitel řádu cyklické grupy existuje
právě jedna podgrupa daného řádu, obsahuje $G(\cdot)$ právě tolik podgrup,
kolik existuje dělitelů jejího řádu. Máme-li $n=\prod_{i=1}^kp_i^{r_i}$, kde
$p_1<p_2<\dots<p_k$ jsou prvočísla a $r_i\in \N$, pak děliteli $n$
jsou právě čísla $\prod_{i=1}^kp_i^{s_i}$, kde $0\le s_i\le r_i$, tedy
$G(\cdot)$ obsahuje právě $\prod_{i=1}^k(r_i+1)$ podgrup a podle 
\ref{phi} právě $\prod_{i=1}^k (p_i-1)p_i^{r_i-1}$ generátorů.

Konečně si všimněme, že pro $k$, které nedělí $n$ nemáme žádný prvek $G$ řádu $k$, zatímco pro $k/n$ existuje právě $\varphi(k)$ generátorů jediné cyklické podgrupy řádu $k$, tedy
právě $\varphi(k)$ prvků $G$ řádu $k$.
Toto pozorování můžeme shrnout do vzorce uvažujícího všech $n$ prvků grupy $G(\cdot)$, z nichž každý má určitý řád dělící $n$:
\[
n=\sum_{k/n}\varphi(k).
\]

(2) Konkrétně, vezmeme cyklickou grupu $\Z_{50}(+)$.
Protože $50=2\cdot 5^2$, dostáváme z bodu (1), že $\Z_{50}(+)$ obsahuje $\varphi(50)=20$
generátorů a právě $6=2\cdot 3$ podgrup. Vezmeme-li například podgrupu
$\langle 42 \rangle$ grupy $\Z_{50}(+)$ (a jiné než cyklické
podgrupy tato grupa podle \ref{2.5} neobsahuje), pak díky \ref{2.8}
víme, že $\langle 42 \rangle=\langle \NSD(42,50) \rangle=\langle 2 \rangle=2\Z_{50}$,
a jedná se tedy o podgrupu řádu $25=\frac{50}{2}$ a tudíž je
prvek $42$ řádu $25$ a naopak prvků řádu $25$ najdeme v $\Z_{50}(+)$ právě $\varphi(25)=20$.
\end{prikl}




\begin{pozn}\label{2.6} Buď $G(\cdot)$ konečná grupa.
Potom $g^{|G|}=e$ pro každý prvek $g\in G$.
\end{pozn}
\begin{proof} Z Poznámky~\ref{ord} plyne, že $g^n = e$ a podle Věty~\ref{Lagrange} 
$n/|G|$, proto 
\[
g^{|G|}= (g^{n})^{\frac{|G|}{n}} = e^{\frac{|G|}{n}} = e,
\]
kde první rovnost plyne z \ref{2.2}.
\end{proof}

Předchozí poznámka tedy říká, že řád konečné grupy je exponentem každého jejího prvku.
Toto pozorování využije následující důsledek, který je pro prvočíselné $n$ znám také jako Malá Fermatova věta:

\begin{theorem}[Eulerova věta]\label{MFT} Pro nesoudělná kladná celá čísla 
$a,n>1$ je
\[a^{\varphi(n)}\equiv 1 \ (\md n).\]
\end{theorem}
\begin{proof} Díky Poznámce~\ref{kong-Z} tvrzení stačí dokázat pro hodnoty $a\in\Z_n$.
Použijeme k tomu Poznámku~\ref{2.6}, kde jako grupu $G$ můžeme díky \ref{1.6} vzít grupu invertibilních prvků 
$\Z_n^*(\cdot)$ monoidu $\Z_n(\cdot)$ tj. prvků nesoudělných s $n$, která má podle definice Eulerovy funkce právě $\varphi(n)$ prvků.
Protože $a\in\Z_n^*$,  dostáváme pomocí \ref{2.6}
\[
(a^{\varphi(n)})\md n=(a^{|\Z_n^*|})\md n=1.
\]
\end{proof}


Než obrátíme pozornost k aplikacím předchozích pozorování, vyslovme
pozorování, které slouží jako technický nástroj níže popsaného protokolu RSA.

\begin{pozn}\label{2.12} Buď $p$ a $q$ dvě různá lichá prvočísla
a $m=\nsn(p-1,q-1)$. Potom pro každé $a\in \Z_{pq}$ a $u\in\N$ platí, že
$(a^{mu+1})\rm{\md pq}=a$.
\end{pozn}
\begin{proof} Nejprve ukážeme, že $(a^{m+1})\rm{\md pq}=a$.

Podle Věty \ref{MFT} $(x^m)\rm{\md p}=1$ a $(y^m)\rm{\md q}=1$
pro ta $x$, která nejsou násobkem $p$ a ta $y$, která nejsou násobkem $q$.
Dále zřejmě platí $((up)^{m+1})\md p=0 $,
 a proto i 
$(x^{m+1})\md p=(x)\md p$ a $(y^{m+1})\md q=(y)\md q$
pro každé nezáporné celé $x$ a $y$. Vezměme nyní $a\in \Z_{pq}$.
Z předchozího pozorování plyne, že  
\[
((a)\md p,(a)\md q)=((a^{m+1})\md p, (a^{m+1})\md q),
\]
a díky Větě \ref{CRT} použité pro bijekci $\Z_{pq}\to\Z_p\times\Z_q$
dostáváme, že shodné jsou i vzory prvků $((a)\md p,(a)\md q)$ a 
$((a^{m+1})\md p, (a^{m+1})\md q)$, proto 
\[
(a^{m+1})\rm{mod\ pq}=a.
\]

Nyní indukcí díky \ref{2.2} dostáváme, že 
$a^{um+1}=a^{(u-1)m}\cdot a^{m+1} = a^{(u-1)m+1}=a$ pro každé $u\in \N$ a
$a\in \Z_{pq}$.
\end{proof}

\begin{prikl}[Rivest, Shamir, Adleman]\label{RSA} \rm
Nejprve zvolíme $p$ a $q$ dvě různá lichá prvočísla a položme $m=\nsn(p-1,q-1)$.

Vezměme $e<m$ nesoudělné s $m$ a pak (například pomocí Eukleidova algoritmu)
najdeme takové $d<m$, že $(ed)\md m = 1$.
Nyní podle \ref{2.12} pro každé $a\in \Z_{pq}$ platí, že $(a^e)^d=a^{ed}=a^{um+1}=a$ (počítáno v
$\Z_{pq}$, tedy modulo $pq$).

Pomocí vlastnosti čísel $p$, $q$, $m$, $d$, $e$ můžeme nyní popsat
protokol asymetrického šifrování známý pod zkratkou RSA.
Položíme-li $n=p\cdot q$, je
veřejným klíčem dvojice čísel $(n, e)$ a soukromý klíč tvoří {\it tajný exponent}
$d$. Chceme-li zprávu $a\in \Z_{n}$ adresovat majiteli soukromého klíče,
stačí ji zašifrovat pomocí mocnění veřejně známou hodnotou $e$ v 
monoidu $\Z_{n}(\cdot)$ a odeslat hodnotu $x=(a^e)\md pq$. K jejímu rozluštění
stačí umocnit v $\Z_{n}(\cdot)$ pomocí tajného exponentu, protože
$x^d=(a_i^e)^d=a_i^{ed}=a_i$.

Naopak, zveřejnění-li majitel soukromého klíče zašifrovanou 
zprávu 
\[(a_1^d)\md\ n,\dots,(a_k^d)\md\ n,
\]
 mohou si
příjemci zprávy stejným způsobem (tj. umocněním na veřejně známý exponent $e$:
$((a_1^d)^e)mod\ n,\dots,((a_k^d)^e )mod\ n = (a_1,\dots,a_k)$) ověřit, že
odesilatel zprávy opravdu zná tajný exponent (vlastnictví soukromého klíče tedy garantuje
pravost elektronického podpisu).

Poznamenejme, že je  ze znalosti $n=pq$ a $e$ obtížné najít $d$ (odpovídá to nalezení
prvočíselného rozkladu čísla n, což je úloha, pro níž není znám algoritmus polynomiální časové složitosti vzhledem k bitové délce), zatímco mocnění čísel v $\Z_{pq}$ je (i pro velké exponenty a velké $pq$)
velmi snadné a rychlé.
\end{prikl}


Důkaz následujícího tvrzení o cyklických grupách je elegantnější,
využijeme-li jistých znalostí z teorie polynomů nad obecným tělesem, 
proto ho provedeme později:

\begin{theorem}\label{T^*} Nechť $T$ je komutativní těleso s operacemi $+$ a $\cdot$ a nechť $G$ je konečná podgrupa
multiplikativní grupy $T\setminus\{0\}(\cdot)$. Potom $G$ je cyklická grupa.
\end{theorem}


Zatímco je protokol RSA založen na diskrétním odmocňování, následující dvě aplikace využívají tak zvaný
problém {\it diskrétního logaritmu}, tedy obtížnost nalezení přirozeného $n$ pro známé prvky $g,h$ vhodné grupy pro něž $h=g^n$.

\begin{prikl}[Diffieho–Hellmanův protokol výměny klíčů]\label{dl} \rm  Otázku domluvy tajného klíče veřejným kanálem
lze s použitím cyklické grupy, například multiplikativní grupy $\Z_{p}^{*}(\cdot)$ pro $p$ (dostatečně velké) prvočíslo
následovně: Veřejným klíčem bude kromě prvočísla $p$ ještě generátor $g$ grupy  $\Z_{p}^{*}(\cdot)$, tedy prvek splňující
podmínku $\langle g\rangle=\Z_{p}^{*}$, který existuje díky Větě~\ref{T^*}. Každá strana komunikace zvolí svou tajnou hodnotu čísla 
$m$ a $n$ ze $\Z_{p}^{*}$ a
vzájemně si pošlou hodnotu $x=g^m$ a $y=g^n$. Poté co obě strany umocní přijatou hodnotu na svůj tajný exponent, získají
obě společný tajný klíč
\[
s= x^n= g^{mn}=y^m.
\]
Bez rychlého výpočtu diskrétního logaritmu (který v grupě $\Z_{p}^{*}(\cdot)$ není k dispozici) nelze ze znalosti hodnot
$x$ a $y$ zjistit hodnotu $s$.
\end{prikl}


\begin{prikl}[ElGamal] \rm Tentokrát využijeme problém diskrétního logaritmu pro stejnou úlohu, kterou řeší \ref{RSA}.
Opět zvolíme cyklickou grupu  $\mathcal G=G(\cdot)$, její generátor $a$ a náhodné číslo $k\in \Z_{|G|}$ a spočítáme
$b=a^k$ (bohužel nemůžeme už vzít například grupu $\Z_{p}^{*}(\cdot)$ pro $p$ prvočíslo, protože je pro ni je znám 
útok, který popisovaný protokol prolomí, místo toho se obvykle volí grupa definovaná pomocí eliptických křivek).
Veřejný klíč je potom trojice $\mathcal G, a, b$ a tajným klíčem hodnota $k$. Chceme-li zašifrovat zprávu $w\in G$,
náhodně zvolíme $r\in \Z_{|G|}$ a spočítáme $x=a^r$ a $y=w\cdot b^r$. Posílanou zprávou je dvojice $(x,y)$,
kterou příjemce znalý tajného klíče snadno rozšifruje výpočtem
\[
y\cdot x^{-k}=w\cdot b^r\cdot (a^{r})^{-k}=w\cdot a^{kr}\cdot a^{-kr}=w.
\]
I tentokrát bez schopnosti rychlého výpočtu diskrétního logaritmu nelze ze znalosti veřejného klíče a hodnot dvojice $(x,y)$
zprávu $w$ rozšifrovat.
\end{prikl}



%\begin{prikl} \rm (1) Je-li  $p$ prvočíslo, pak $\Z_{p}$ je se sčítáním a násobením modulo $p$ těleso, proto je podle předchozí věty $\Z_{p}^{*}(\cdot)$ cyklická grupa řádu $p-1$. Je-li $p-1=\prod_{i=1}^kp_i^{s_i}$ prvočíselný rozklad, kde $p_1<p_2<\dots<p_k$ a $r_i>0$, pak můžeme generátory a podgrupy grupy $\Z_{p}^{*}(\cdot)$ počítat postupem Příkladu \ref{cykl}. Tedy $\Z_{p}^{*}(\cdot)$ obsahuje právě $\prod_{i=1}^k (p_i-1)p_i^{r_i-1}$ generátorů a $\prod_{i=1}^k(r_i+1)$ podgrup.

%(2) Z předchozí úvahy plyne, že $\Z_{53}^{*}(\cdot)$ je cyklická grupa řádu $52=2^2\cdot 13$, proto $\Z_{53}^{*}(\cdot)$ obsahuje právě $2\cdot 12=24$ generátorů a $3\cdot 2=6$ podgrup. \end{prikl}





\vskip 1cm

\section{Základy univerzální algebry}

Smyslem této kapitoly je nahlédnout, že některé výsledky, které jsme formulovali pro grupy, lze v téměř nezměněné podobě formulovat
i v mnohem obecnějším kontextu a lze jich tak využít i pro další algebraické objekty. Ačkoli tvrzení, která (znovu) dokážeme v obecné situaci, platí i pro algebraické objekty, již s grupami mají jen málo společného, my jich využijeme především při práci s pojmem okruhu, kde strukturu Abelovy grupy zatížíme dalšími podmínkami.

Konkrétně si na příkladech všimneme pojmů algebra, podalgebra, homomorfismus a kongruence,
které zobecňují pojmy grupa, podgrupa, grupový homomorfismus a ekvivalence slučitelná s operací
zkoumané v předchozích kapitolách. Koncepty, které lze zcela přímočaře přeložit do obecného kontextu
shrnují Poznámka~\ref{3.4} a \ref{US}.


Připomeňme, že každé zobrazení $A^n\to A$ pro celé $n\ge 0$ se nazývá {\it $n$-ární operací na množině} $A$,
kde $n$ budeme nazývat {\it arita} neboli {\it četnost} operace.
Zaveďme nyní pojmy obecné algebry a podalgebry:

\begin{definice} Je-li $I$ množina, budeme říkat zobrazení $\Omega:I\to \N_{0}=\N\cup\{0\}$
{\it typ}. Řekneme, že $A(\alpha_i|\ i\in I)$ je {\it algebra typu $\Omega$}, je-li $A$ neprázdná a
pro každé $i\in I$ je $\alpha_i$ právě $\Omega(i)$-ární operací na $A$.

Buď $\alpha$ $n$-ární operace na $A$. Řekneme, že podmnožina
$B\subseteq A$ je {\it uzavřená na operaci $\alpha$}, jestliže 
$\alpha(a_1,\ldots,a_n)\in B$
pro všechna $a_1,\ldots,a_n\in B$. Řekneme, že $B\subseteq A$ je {\it podalgebra}
algebry $A(\alpha_i|\ i\in I)$, je-li $B$ uzavřená na všechny operace $\alpha_i$, $i\in I$.
\end{definice}

Je-li indexová množina $I$ konečná, můžeme předpokládat, že je dobře uspořádaná $I=\{i_1,\dots,i_k\}$, a tedy typ lze
chápat jako konečnou posloupnost arit jednotlivých operací, místo $A(\alpha_i|\ i\in I)$
budeme psát $A(\alpha_{i_1},\dots, \alpha_{i_k})$
a typ $\Omega$ budeme zapisovat jako vektor
$(\Omega(i_1),\dots. \Omega(i_k))$.

\begin{prikl}\rm 
(1) Uvážíme grupu $G(\cdot)$ s unární operací inverzního prvku
$^{-1}$ a nulární operací $1$. Pak $G(\cdot)$, $G(\cdot, ^{-1})$ a $G(\cdot, ^{-1},1)$ představují různé algebry.
\begin{enumerate}
\item[(a)] Podalgebry algebry $G(\cdot, ^{-1},1)$ typu $(2,1,0)$ jsou právě podmnožiny $G$ uzavřené na $1$ (tj. obsahující prvek $1$),
na inverzy a součiny, což jsou podle definice právě podgrupy grupy $G(\cdot)$.
\item[(b)] Je-li $H$ neprázdná podalgebra algebry $G(\cdot, ^{-1})$ typu $(2,1)$, pak existuje $h\in H$, a proto $1=h\cdot h^{-1}\in H$.
Tedy neprázdné podalgebry $G(\cdot, ^{-1})$ jsou právě podgrupy $G(\cdot)$, navíc prázdná množina je v souladu
s definicí také podalgebra.
\item[(c)] Podalgeber algebry $G(\cdot)$ typu $(2)$ je obecně mnohem víc než podgrup grupy $G(\cdot)$.
Například pro každé $g\in G$ a $n\in\N$ tvoří množina $\{g^k|\ k\ge n\}$ podalgebru $G(\cdot)$.
V případě $G(\cdot)=\Z(+)$ to znamená, že množiny $\{ak|\ k\ge n\}$ jsou podalgebry, speciálně množina všech přirozených čísel,
která podgrupou $\Z(+)$ určitě není.
\end{enumerate}


(2) Je-li $\mathbf T$ těleso, pak je algebrou $\mathbf T(+,\cdot)$ či $\mathbf T(+,-,\cdot,0,1)$, pro vektorový prostor $V$
nad $\mathbf T$, je algebrou $V(+,\cdot t|t\in\mathbf T)$ nebo $V(+,0,\cdot t|t\in\mathbf T)$. Všimněme si, že pro nekonečné těleso
potřebujeme uvažovat nekonečně mnoho unárních operací.
Podalgebrou algebry $V(+,0,\cdot t|t\in\mathbf T)$ jsou právě podprostory tohoto vektorového prostoru a 
podalgebry algebry $V(+,\cdot t|t\in\mathbf T)$ jsou právě podprostory a prázdná množina.

(3)  Je-li $\mathcal A=A(\alpha_i|\ i\in I)$ obecná {\it algebra typu $\Omega$},
je $A$ jistě její triviální podalgebrou. Pokud $\mathcal A$ neobsahuje žádné nulární operace, je prázdná množina triviální podalgebrou.

(4) Každá podalgebra algebry $\mathbb Z(+,-,0,1)$ typu $(2,1,0,0)$ je
podalgebrou algebry  $\mathbb Z(+,-,0)$, tedy podgrupou a nutně obsahuje prvek $1$, proto $\mathbb Z(+,-,0,1)$ obsahuje jedinou podalgebru 
$\mathbb Z$.
\end{prikl}


Označíme-li $\beta_i=\alpha_i|_{B^n}$ omezení $n$-ární operace $\alpha_i$ na 
$B^n$, potom pro podalgebru $B$ leží všechny hodnoty zobrazení 
$\beta_i$ opět v $B$. Zobrazení  $\beta_i$ tedy můžeme chápat jako operace
na množině $B$ a tak dostáváme strukturu algebry $B(\beta_i|\ i\in I)$ na každé podalgebře
$B$.

\begin{definice} Nechť  symbol $\alpha$ označuje $n$-ární operaci na množině $A$ a $\beta$ je
$n$-ární operace na množině $B$.
Řekneme, že zobrazení $f:A\to B$ je {\it slučitelné s operacemi $\alpha$ a $\beta$}, jestliže 
$f(\alpha(a_1,\ldots,a_n))=\beta(f(a_1),\ldots,f(a_n))$. 
Zobrazení $f:A\to B$ mezi dvěma algebrami $\A=A(\alpha_i|\ i\in I)$ a $\B=B(\beta_i|\ i\in I)$
stejného typu $\Omega$ budeme říkat {\it homomorfismus}, je-li slučitelné s operacemi $\alpha_i$ a $\beta_i$, 
pro všechna $i\in I$.
Bijektivní homomorfismus budeme nazývat {\it izomorfismus}.
Jestliže mezi dvěma algebrami $\A$ a $\B$ existuje izomorfismus, říkáme, že $\A$ a $\B$ jsou {\it izomorfní} a píšeme $\A\cong \B$
nebo zkráceně $A\cong B$.
\end{definice}

Poznamenejme, že budeme obvykle odpovídající operace dvou algeber stejného typu
označovat stejně, tedy $A(\alpha_i|\ i\in I)$ a $B(\alpha_i|\ i\in I)$. V takovém případě 
slučitelnosti s operací $\alpha_i$ pro nějaké (nebo všechna) $i\in I$.

\begin{prikl}\rm (1) 
Buď $G_i(\cdot)$ pro $i=1,2$ grupy s unární operací inverzního prvku
$^{-1}$ a nulární operací $1$. pak každý homomorfismus grup
$G_1(\cdot)$ a $G_2(\cdot)$ je podle \ref{1.17}(1) homomorfismem 
algeber $G_1(\cdot)$ a $G_2(\cdot)$, $G_1(\cdot,^{-1})$ a $G_2(\cdot^{-1})$
i $G_1(\cdot,^{-1},1)$ a $G_2(\cdot,^{-1},1)$

(2) Nechť $U$ a $V$ jsou dva vektorové prostory nad tělesem $T$. Potom každé lineární
zobrazení (homomorfismus)
vektorových prostorů je homomorfismem algeber $U(+,\cdot t|t\in T)$ a
$V(+,\cdot t|t\in T)$.

(3) Označme $M_n(T)$ množinu všech čtvercových matic nad tělesem $T$ a $\cdot$ budiž symbolem násobení matic. Potom zobrazení, které každé matici přiřadí její determinant, je homomorfismem algebry $M_n(T)(\cdot)$ do $T(\cdot)$ (poznamenejme, že se jedná právě o monoidy).
\end{prikl}



\begin{definice} Nechť $\rho$ je ekvivalence a $\alpha$ je $n$-ární operace na množině $A$. 
Řekneme, že $\rho$ je {\it slučitelná s $\alpha$}, jestliže pro každý systém prvků
$a_1,\dots,a_n, b_1\dots, b_n\in A$, pro které $(a_i, b_i)\in \rho$, $i=1,\dots,n$,
platí, že $(\alpha(a_1,\dots,a_n), \alpha(b_1,\dots,b_n))\in \rho$.
Je-li $A(\alpha_i|\ i\in I)$ algebra a $\rho$ ekvivalence na množině $A$,
pak $\rho$ nazveme {\it kongruencí}, je-li $\rho$ slučitelná se všemi
operacemi $\alpha_i$, $i\in I$. 
\end{definice}


\begin{prikl}\label{3.3}\rm
(1) Ekvivalence $\equiv  \ (\md n)$ tvoří podle Poznámky~\ref{kong-Z} kongruenci na algebře $\Z(+,-,0,\cdot)$.

(2) $\id$ a $A\times A$ jsou kongruence na libovolné algebře $A(\alpha_i|\ i\in I)$.

(3) Každá ekvivalence je slučitelná s libovolnou nulární operací, protože dvojice
$(\alpha,\alpha)$ je ekvivalentní díky reflexivitě ekvivalence pro každou
nulární operaci $\alpha$
\end{prikl}


Připomeňme, že je-li $f:A\to B$ zobrazení, rozumíme jeho {\it jádrem} $\ker f$ relaci
danou předpisem: $(a,b)\in ker\ f \Leftrightarrow f(a)=f(b)$.
Nyní jsme připraveni vyslovit obdobu Poznámky \ref{1.17} pro obecné algebry:

\begin{pozn}\label{3.4} Nechť $A_1(\alpha_i|\ i\in I)$,  
$A_2(\alpha_i|\ i\in I)$ a $A_3(\alpha_i|\ i\in I)$ jsou algebry stejného typu,
$f:A_1\to A_2$ a $g:A_2\to A_3$ jsou homomorfismy a $B$ je podalgebra algebry $A_2(\cdot)$. 
\begin{enumerate}
\item[(1)] $gf$ je také homomorfismus,
\item[(2)] je-li $f$ izomorfismus, pak $f^{-1}$ je izomorfismus,
\item[(3)] obraz $g(B)$ je podalgebra algebry $A_3(\alpha_i|\ i\in I)$ a 
úplný vzor $f^{-1}(B)$ je podalgebra algebry $A_1(\alpha_i|\ i\in I)$,
\item[(4)] $\ker f$ je kongruence na algebře $A_1(\alpha_i|\ i\in I)$.
\end{enumerate}
\end{pozn}
\begin{proof} Důkaz je snadným zobecněním důkazu příslušných bodů \ref{1.17}.

(1) Je-li $\alpha_i$ $n$-ární operace na $A_1$, $A_2$ a $A_3$ a vezmeme-li 
$a_1,\dots a_n \in A_1$, pak 
$gf(\alpha_i(a_1,\dots a_n))= g(\alpha_i(f(a_1),\dots f(a_n)))= 
\alpha_i(gf(a_1),\dots gf(a_n))$.

(2) Stačí opět ověřit, že $f^{-1}$ je homomorfismus. Zvolíme-li 
libovolně $n$-ární operaci $\alpha_i$ a prvky $a_1,\dots a_n \in A_2$,
potom $f(\alpha_i(f^{-1}(a_1),\dots, f^{-1}(a_n))) = \alpha_i(a_1,\dots a_n)$, proto
$\alpha_i(f^{-1}(a_1),\dots, f^{-1}(a_n)) = f^{-1}(\alpha_i(a_1,\dots a_n))$.

(3) Nechť je opět $\alpha_i$ libovolná $n$-ární operace na $A_2$ i $A_3$.
Vezměme nejprve  $c_1,\dots c_n \in g(B)$, tj. existují
$b_1,\dots b_n \in B$, pro která $g(b_j)=c_j$, $j=1,\dots,n$. 
Protože $\alpha_i(b_1,\dots b_n) \in B$,
dostáváme bezprostředně z definice, že
$\alpha_i(c_1,\dots c_n)=\alpha_i(g(b_1),\dots g(b_n))=g(\alpha_i(b_1,\dots b_n))\in g(B)$.

Nyní zvolme 
$a_1,\dots a_n\in f^{-1}(B)$, tj. $f(a_j)\in B$. Potom 
$f(\alpha_i(a_1,\dots a_n))= \alpha_i(f(a_1),\dots f(a_n)) \in B$.

(4) Vezměme $n$-ární operaci $\alpha_i$ na $A_1$ a $A_2$ a prvky $a_1,\dots a_n, b_1,\dots b_n \in A_1$,
o nichž víme, že $(a_j,b_j)\in\ker f$, tedy $f(a_j)=f(b_j)$, pro každé $j=1\dots n$.
Potom z definice homomorfismu dostaneme rovnost
\[
f(\alpha_i(a_1,\dots a_n))= \alpha_i(f(a_1),\dots f(a_n))=\alpha_i(f(b_1),\dots f(b_n))=
f(\alpha_i(b_1,\dots b_n)),\]
čímž jsme ověřili, že 
$(\alpha_i(a_1,\dots a_n),\alpha_i(b_1,\dots b_n))\in \ker f$. Že se jedná o ekvivalenci
je snadné cvičení.
\end{proof}

\begin{pozn}\label{US} Nechť $\A=A(\alpha_i|\ i\in I)$ je algebra a $A_j$ jsou podalgebry $\A$
a $\rho_j$ kongruence na $\A$ pro každé $j\in J$.  
\begin{enumerate}
\item[(1)] $\bigcap_{j\in J}A_j$ je podalgebra $\A$,
\item[(2)] $\bigcap_{j\in J}\rho_j$ je kongruence na $\A$.
\end{enumerate}
\end{pozn}
\begin{proof} (1) Obdoba Poznámky~\ref{1.9}(2). Nechť $\alpha_i$ je libovolná $n$-ární 
operace na $A$ a $a_1,\dots a_n \in \bigcap_{j\in J}A_j$. 
Protože $\bigcap_{j\in J}A_j\subseteq A_k$ pro každé $k\in J$ a $A_k$ je podalgebra
$A(\alpha_i|\ i\in I)$ máme $\alpha_i(a_1,\dots a_n) \in A_k$, tedy
$\alpha_i(a_1,\dots a_n) \in \bigcap_{j\in J}A_j$.

(2) Protože $\id\subseteq \rho_j$ pro všechna $j\in J$, máme $\id\subseteq \bigcap_{j\in J}\rho_j$, tedy relace $\bigcap_{j\in J}\rho_j$ je reflexivní. Je-li $(a,b)\in \bigcap_{j\in J}\rho_j$, máme $(a,b)\in \rho_j$, ze symetrie potom $\rho_j$ i $(b,a)\in \rho_j$ pro všechna $j\in J$, tudíž $(b,a)\in \bigcap_{j\in J}\rho_j$. Konečně platí-li, že $(a,b), (b,c)\in \bigcap_{j\in J}\rho_j$, pak tranzitivita jednotlivých relací $\rho_j$, které všechny obsahují průnik $\bigcap_{j\in J}\rho_j$ implikuje, že $(a,c)\in \rho_j$, a proto $(a,c)\in \bigcap_{j\in J}\rho_j$. 

Mějme $\alpha_i$ nějakou $n$-ární operaci na $A$ a vezměme 
prvky $a_1,\dots a_n, b_1,\dots b_n \in A$, pro něž platí, že
$(a_k,b_k)\in \bigcap_{j\in J}\rho_j$ ($\subseteq \rho_j$ pro všechna $j\in J$).
Potom pro všechna $j\in J$ máme
$(\alpha_i(a_1,\dots a_n),\alpha_i(b_1,\dots b_n))\in \rho_j$ , tedy $(\alpha_i(a_1,\dots a_n),\alpha_i(b_1,\dots b_n))\in \bigcap_{j\in J}\rho_j$.
\end{proof}




\vskip 1cm

\section{Homomorfismy, izomorfismy a rozklad algeber}


V návaznosti na předchozí kapitolu nahlédneme, že na faktorizaci nosné množiny algebry, která umožňuje opětovné zavedení struktury algebry stejného typu, lze přirozeně nahlížet prostřednictvím homomorfismů.
Ve speciálním případě grup zjistíme, že kongruence jsou právě ekvivalence $\rmod\ H$ pro normální podgrupy $H$. Hlavním výsledkem kapitoly budou dvě věty o izomorfismu, které nabízejí technicky velmi příjemné uchopení faktorizace.


%a pozorněji než v grupovém případě prozkoumáme otázku, proč dvě izomorfní algebry chápeme jako stejné.
%Zatímco je zavedení faktorové algebry zcela přímočarým zobecněním definice faktorové grupy, vyslovení Druhé věty o izomorfismu vyžaduje nový pojem faktorové ekvivalence.


Připomeňme, že pro ekvivalenci $\rho$ na množině $G$ rozumíme {\it přirozenou projekci} na faktorovou množinu $G/\rho$ 
zobrazení $\pi_\rho: G\to G/\rho$ dané podmínkou $\pi_\rho(g)= [g]_\rho$, kde $g\in G$.
Všimněme si, že $\ker\pi_\rho=\rho$.

Je-li $\rho$ ekvivalence na množině $A$, připomeňme, že {\it faktorem množiny} 
(často se také mluví o {\it kvocientu})
$A$ podle ekvivalence $\rho$ jako množinu $A/\rho=\{[a]_\rho|\ a\in A\}$, kde 
$[a]_\rho=\{b\in A|\ (a,b)\in \rho\}$ jsou rozkladové třídy (kosety), tedy
$A/\rho$ tvoří rozklad množiny $A$. 
Naopak máme-li $\{B_i|\ i\in I\}$ rozklad množiny $A$, pak relace $\rho$
určená podmínkou: $(a,b)\in\rho \Leftrightarrow \exists i\in I: a,b\in B_i$
je ekvivalencí a $A/\rho = \{B_i|\ i\in I\}$.
Zobrazení $\pi_\rho: A\to A/\rho$ dané podmínkou $\pi_\rho(a)= [a]_\rho$, kde $a\in A$ se nazývá  {\it přirozená projekce} .



%V případě, že nemůže dojít k omylu nebo jednotlivé operace na algebře nepotřebujeme explicitně uvažovat, budeme označovat algebru jen její nosnou množinou.


\begin{definice} Nechť $\rho$ je ekvivalence a $\alpha$ je $n$-ární operace na množině $A$. 
Je-li $\rho$ slučitelná s $\alpha$, definujeme operaci $\alpha$ na
faktoru $A/\rho$ předpisem
$\alpha([a_1]_\rho,\dots,[a_n]_\rho) = [\alpha(a_1,\dots,a_n)]_\rho$.
Je-li $\rho$ kongruence na algebře $A(\alpha_i|\ i\in I)$, pak tímto způsobem definujeme
na $A/\rho$ strukturu algebry stejného typu.
\end{definice}


\begin{pozn}\label{3.9} Je-li $\rho$ kongruence na algebře $\A=A(\alpha_i|\ i\in I)$, pak je 
definice algebry $A/\rho$ korektní, jde o algebru stejného
typu jako $\A$ a přirozená projekce $\pi_\rho: A\to A/\rho$ je homomorfismus.
\end{pozn}
\begin{proof} Označme $\Omega:I\to \N_{0}=\N\cup\{0\}$ typ algebry $\A$ a zvolme libovolné $i\in I$.
Jestliže $[a_j]_\rho =[b_j]_\rho\in A/\rho$, kde $j=1,\dots \Omega(i)$,
potom $(a_j, b_j)\in\rho$ pro všechna $j=1,\dots \Omega(i)$, proto
$[\alpha_i(a_1, \dots, a_{\Omega(i)})]_\rho=[\alpha_i(b_1, \dots, b_{\Omega(i)})]_\rho$, tedy
definice operací na $A/\rho$ je korektní. 

Podobně pro $a_{1},\dots, a_{\Omega(i)}\in A$ platí, že
$\alpha_i(\pi(a_1), \dots, \pi(a_{\Omega(i)}))=$
\[
= \alpha_i([a_1]_\rho, \dots, [a_{\Omega(i)}]_\rho)=
[\alpha_i(a_1, \dots, a_{\Omega(i)})]_\rho=
\pi(\alpha_i(a_1, \dots, a_{\Omega(i)})),
\]
což znamená, že je $\pi$ opravdu homomorfismus.
\end{proof}

Algebru $A/\rho(\alpha_i|\ i\in I)$ z předchozí poznámky budeme nazývat {\it faktorovou algebrou} algebry $\A$ a budeme ji 
značit $\A/\rho$.

Nyní si uvědomíme, že kongruence na grupě jsou právě ekvivalence $\rmod\ H=\lmod\ H$ pro normální podgrupy $H$.

\begin{theorem}\label{kongruence1} Pro grupu $G(\cdot)$ a relaci $\rho$ jsou následující podmínky ekvivalentní:
\begin{enumerate}
\item[(1)] $\rho$ je kongruence na algebře $G(\cdot)$,
\item[(2)] $\rho$ je kongruence na algebře $G(\cdot, ^{-1},1)$,
\item[(3)] $H=[e]_\rho$ je normální podgrupa $G(\cdot)$ a $\rho=\rmod\ H$ ($=\lmod\ H$).
\end{enumerate}
\end{theorem} 
\begin{proof} (1)$\Rightarrow$(2) V Příkladu \ref{3.3}(3) jsme si uvědomili, že je každá ekvivalence slučitelná s nulární operací $1$.
Nechť dále $(a,b)\in \rho$ a dokážeme, že rovněž $(a^{-1},b^{-1})\in \rho$. Z~reflexivity $\rho$ plyne, že $(a^{-1},a^{-1}), (b^{-1},b^{-1})\in \rho$ a díky symetrii $\rho$ platí, že $(b,a)\in \rho$. Využijeme-li dvakrát slučitelnosti $\rho$ s operací $\cdot$ dostáváme, že 
\[
(a^{-1}\cdot b,1)=(a^{-1}\cdot b,a^{-1}\cdot a)\in \rho\,
\] a tudíž $(a^{-1},b^{-1})= (a^{-1}\cdot b\cdot b^{-1},1\cdot b^{-1})\in \rho$.

(2)$\Rightarrow$(3)
Protože je $\rho$ ekvivalence, tedy reflexivní relace, leží $1$ v třídě $[1]_\rho$.
Zvolme $a,b\in [1]_\rho$ a $g\in G$. 
Potom $(1,a), (1,b)\in \rho$ a využijeme-li
slučitelnosti $\rho$ s operacemi $\cdot$ a $^{-1}$, dostáváme, že $(1,a\cdot b)=(1\cdot 1,a\cdot b)\in \rho$, že
$(1,a^{-1})=(1^{-1},a^{-1})\in \rho$ a že $(1,g\cdot a\cdot g^{-1})(g\cdot 1\cdot g^{-1},g\cdot a\cdot g^{-1})\in \rho$. 
Proto $a\cdot b, a^{-1}, g\cdot a\cdot g^{-1}\in [1]_\rho$, čímž jsme ověřili, že je $[1]_\rho$ normální podgrupa $G(\cdot)$.

Zbývá dokázat, že
$(a,b)\in\rho$, právě když $(a,b)\in\lmod\ [1]_\rho$. Jestliže nejprve $(a,b)\in\rho$,
potom $(1,a^{-1}\cdot b) =(a^{-1}\cdot a,a^{-1}\cdot b)\in\rho$, protože je $\rho$
ekvivalence slučitelná s $\cdot$, tedy $(a,b)\in\lmod\ [1]_\rho$. Naopak,
zvolíme-li $(a,b)\in\lmod\ [1]_\rho$, pak $(a,b)=(a\cdot 1,a\cdot a^{-1}\cdot b) \in\rho$.
Konečně podle \ref{1.12}(4) platí, že $\rmod\ [1]_\rho=\lmod\ [1]_\rho$.

(3)$\Rightarrow$(1) Předpokládejme, že je $H$ normální podgrupa $G(\cdot)$
a definujme relaci $\rho$ jako $\rmod\ H$ (tj. $(a,b)\in \rho$ $\leftrightarrow$ $a\cdot b^{-1}\in H$). Podle \ref{1.9}(5) a (7) je $\rho$ 
ekvivalence slučitelná s s operací $\cdot$  a přímým výpočtem zjistíme,
že $[1]_\rho=H$. 
\end{proof}


Věta \ref{kongruence1}, která říká, že kongruenci $\rho$ na grupě jednoznačně odpovídá normální podgrupa $H=[e]_\rho$,
nám umožňuje faktorovou množinu zapisovat ve tvaru $G/H:=G/\rho=G/\rmod H$.
Obvyklý zápis faktorové grupy 
$G/\rho(\odot)$ tedy bude tvaru $G/H(\cdot)$, kde 
$H=[e]_\rho$ s prvky 
$
[a]_H=[a]_\rho=aH=Ha
$
z nichž $[e]_\rho=H$ je neutrální a operacemi
\[
[a]_H\cdot [b]_H =aH \cdot bH = [a\cdot b]_H =(a\cdot b)H,\ \ \ \ 
[a]_H^{-1}= [a^{-1}]_H = a^{-1}H
\] 
Podobně budeme přirozenou projekci
$G$ na $G/H$ označovat symbolem $\pi_H$, tedy $\pi_H(a)=[a]_H=aH$.


\begin{definice} Nechť $\rho\subseteq\sigma$ jsou dvě ekvivalence na $A$.
Definujme relaci $\sigma/\rho$ na $A/\rho$ následovně: 
$([a]_\rho,[b]_\rho)\in\sigma/\rho \Leftrightarrow (a,b)\in\sigma$.
\end{definice}

\begin{pozn}\label{3.10} Buď $\rho$ kongruence na algebře $\A=A(\alpha_i|\ i\in I)$.

{\rm (1)} Je-li $\sigma$ kongruence na $\A$ obsahující $\rho$, 
je $\sigma/\rho$ dobře definovaná kongruence na algebře $\A/\rho$.

{\rm (2)} Je-li 
$\eta$ kongruence na algebře $\A/\rho$, potom existuje právě jedna kongruence $\sigma$
na algebře $\A$ obsahující $\rho$, pro níž $\eta=\sigma/\rho$. 
\end{pozn}

\begin{proof} (1) Stačí ověřit, že je definice $\sigma/\rho$ korektní. Zbytek plyne bezprostředně z definic relace $\sigma/\rho$ a operace na faktorové algebře
$A/\rho$. Mějme $[a_1]_\rho=[a_2]_\rho$ $[b_1]_\rho=[b_2]_\rho$.
Potom $(a_1,a_2), (b_1,b_2)\in \rho\subseteq \sigma$, tedy díky tranzitivitě  
a symetrii $\sigma$ platí, že $(a_1,b_1)\in\sigma$ $\Leftrightarrow$ $(a_2,b_2)\in\sigma$.

(2) Jediný možný způsob, jak definovat $\sigma$ nám dává předpis
$(a,b)\in\sigma \Leftrightarrow ([a]_\rho,[b]_\rho)\in\eta$.
Nyní stačí přímočaře nahlédnout, že jsme takto zavedli kongruenci na $A$.
\end{proof}




\begin{theorem}\label{ob.o homomorfismu} Nechť $f:A\to B$ je homomorfismus dvou algeber
$\A=A(\alpha_i|\ i\in I)$ a $\B=B(\alpha_i|\ i\in I)$ stejného typu.

{\rm (1) (Věta o homomorfismu)}
Je-li $\rho$ kongruence na algebře $\A$, pak existuje homomorfismus
$g:A/\rho\to B$ splňující podmínku $g\pi_\rho=f$ právě tehdy, když
$\rho\subseteq \ker f$. Navíc, pokud $g$ existuje, je $g$ izomorfismus,
právě když $f$ je na a $\ker f=\rho$.

{\rm (2) (1. věta o izomorfismu)}  $f(A)$ je podalgebra $\B$ (tedy algebra stejného typu) a
$A/ker\ f$ je izomorfní $f(A)$.
\end{theorem}
\begin{proof} Tvrzení dokážeme stejným postupem jako Větu o homomorfismu a 1. věta o izomorfismu pro grupy 
(\ref{o homomorfismu}).

(1)
Nejprve  předpokládejme, že existuje homomorfismus 
$g:A/\rho\to B$ splňující podmínku $g\pi_\rho=f$, tedy $g([a]_\rho)=f(a)$ a
vezměme $(a_1,a_2)\in\rho$. Pak $[a_1]_\rho=[a_2]_\rho$,
a proto $f(a_1)=g([a_1]_\rho)=g([a_2]_\rho)=f(a_2)$. 
Tedy $(a_1,a_2)\in\ker f$.

Je-li naopak $\rho\subseteq \ker f$, ověřujeme, že definice
$g$ daná předpisem $g([a]_\rho)=f(a)$ je korektní.
Vezmeme-li $[a_1]_\rho=[a_2]_\rho$, pak 
$g([a_1]_\rho)=f(a_1)=f(a_2)=g([a_2]_\rho)$.
Že je $g$ homomorfismus je zjevné z jeho definice.

Konečně dokažme závěrečnou ekvivalenci. Protože 
$g(A/\rho)=f(A)$, vidíme, že $g$ je na, právě když je $f$ na.
Je-li $g$ navíc prosté a zvolíme-li $(a_1,a_2)\in\ker f$, pak
$g([a_1]_\rho)=f(a_1)=f(a_2)=g([a_2]_\rho)$, a proto $(a_1,a_2)\in\rho$.
Ověřili jsme, že $\ker f\subseteq \rho$, a protože už víme, že
$\rho\subseteq \ker f$, máme rovnost $\rho=\ker f$.
Konečně předpokládejme, že $g([a_1]_\rho)=g([a_2]_\rho)$.
Potom $f(a_1)=f(a_2)$, a proto $(a_1,a_2)\in\rho$ a $[a_1]_\rho=[a_2]_\rho$,
čímž jsme ověřili, že je $g$ prosté.

(2) Rozmyslíme si, že podle \ref{3.4}(3) je $f(A)$ podalgebra algebry $\B$, 
omezíme-li tedy obor hodnot zobrazení $f$, můžeme ho chápat jako homomorfismus $f:A\to f(A)$. Nyní aplikujeme (1) pro $\rho=\ker\ f$
a dostaneme přímo požadovaný izomorfismus $\psi:A/\ker\ f\to f(A)$.
\end{proof}

\begin{theorem}[2. věta o izomorfismu]\label{ob.2. o homomorfismu}
Nechť $\rho\subseteq \sigma$ jsou dvě kongruence na algebře $\A$.
Pak je algebra $\A/\sigma$ izomorfní algebře $(\A/\rho)/(\sigma/\rho)$.
\end{theorem}
\begin{proof} 
Nejprve použijeme \ref{ob.o homomorfismu}(1) pro
homomorfismy $\pi_\sigma:A\to A/\sigma$ a  
$\pi_\rho:A\to A/\rho$, která nám dává 
homomorfismus $g:A/\rho\to A/\sigma$ splňující vztah $g([a]_\rho)=[a]_\sigma$.
Nyní přímočaře spočítáme 
$\ker g=\{([a]_\rho,[b]_\rho)|\ (a,b)\in \sigma\}=\sigma/\rho$ a použijeme Větu~\ref{ob.o homomorfismu}(2), která nám dá 
izomorfimus $\A/\sigma \cong (\A/\rho)/\ker g=(\A/\rho)/(\sigma/\rho)$.
\end{proof}

\begin{prikl} \rm
Máme-li homomorfismus 
$F_n:\Z\to \Z_n$ grupy $\Z(+)$
do grupy $\Z_n(+)$ s počítáním modulo $n$ daný
předpisem $F_n(k) = (k)mod\ n$, potom \ref{o homomorfismu}(2) zajišťuje
izomorfismus $\Z/\Ker\ F_n(+)\cong \Z_n(+)$. Navíc je zjevně
$(a,b)\in ker\ F_n$, právě když $n/(a-b)$, tedy $\ker\ F_n=(\equiv  \ (\md n)$ a $\Ker\ F_n=n\Z$.

Všimněme si, že na faktorové množině $\Z/n\Z =\Z/(\equiv  \ (\md n))$ máme
dobře zavedenu strukturu grupy $\Z/n\Z(+)$ předpisem
\[
[a]_{\equiv(\md n)}+[b]_{\equiv(\md n)}=[a+b]_{\equiv(\md n)}
\]
\end{prikl}

Nakonec s využitím Věty \ref{kongruence1} přeformulujeme obecné věty o homomorfismu a izomorfismu pro grupy:

\begin{dusl}\label{o homomorfismu} Nechť $\varphi:G_1\to G_2$ je homomorfismus grup $G_1(\cdot)$ a $G_2(\cdot)$.

{\rm (1)(Věta o homomorfismu) }
Je-li $H$ normální podgrupa $G_1(\cdot)$, pak existuje homomorfismus
$\psi:G_1/H\to G_2$ splňující podmínku $\psi\pi_H=\varphi$ právě tehdy, když
$H\subseteq \Ker \varphi$ (tj. $\rmod H\subseteq \rmod\ \Ker \varphi$). Navíc, 
jestliže $\psi$ existuje, je $\psi$ izomorfismus,
právě když $\varphi$ je na a $\Ker \varphi=H$.

{\rm (2)(1. věta o izomorfismu) }
$\varphi(G_1)$ je podgrupa $G_2$ (tedy opět grupa) a 
$G_1/\Ker \varphi(\cdot)$ je izomorfní $\varphi(G_1)(\cdot)$.
\end{dusl}

%\begin{proof} (1) Nejprve  předpokládejme, že existuje homomorfismus $\psi:G_1/H\to G_2$ splňující $\psi\pi_H=\varphi$, tedy $\psi([a]_H)=\varphi(a)$. Zvolme $a\in H$. Pak $[a]_H=H=[e]_H$ je neutrální prvek grupy $G_1/H(\cdot)$, a proto $\varphi(a)=\psi([a]_H)=e$ podle \ref{1.17}(1). Tedy $a\in \Ker \varphi$, čímž jsme ověřili, že $H\subseteq \Ker \varphi$.

%Naopak, nechť $H\subseteq \Ker \varphi$. Musíme ověřit, že jediná možná definice $\psi$ daná předpisem $\psi([a]_H)=\varphi(a)$ je korektní. Vezměme proto $[a]_H=[b]_H$. Potom $a\cdot b^{-1}\in H\subseteq \Ker \varphi$, tedy $e=\varphi(a\cdot b^{-1})=\varphi(a)\cdot \varphi(b)^{-1}$ podle \ref{1.17}(1), a proto $\varphi(a)=\varphi(b)$. Konečně
%\[ \psi([a]_H\cdot [b]_H) = \psi([a\cdot b]_H) = \varphi(a\cdot b) = \varphi(a)\cdot \varphi(b) = \psi([a]_H)\cdot \psi([b]_H), \] tedy $\psi$ je homomorfismus.

%Zbývá ověřit závěrečnou ekvivalenci. Předně si uvědomme, že  $\psi(G_1/H)=\varphi(G_1)$, tedy $\psi$ je na, právě když je $\varphi$ na. Nechť je $\psi$ navíc prosté a zvolme $a\in\Ker \varphi$. Pak $\psi([a]_H)=\varphi(a)=e$. Protože $\psi([e]_H)=\psi(H)=e$, plyne z prostoty $\psi$, že $[a]_H=H$, tedy $a\in H$. Ověřili jsme, že $\Ker \varphi\subseteq H$, a protože už víme, že $H\subseteq \Ker \varphi$, máme rovnost $H=\Ker \varphi$. Konečně předpokládejme, že $\psi([a]_H)=\psi([b]_H)$. Potom $\varphi(a)=\varphi(b)$ a $a\cdot b^{-1}\in \Ker \varphi = H$. Tudíž $(a,b)\in\rmod H$ a $[a]_H=[b]_H$,čímž jsme ověřili, že je $\psi$ prosté.

%(2) Z \ref{1.17}(5) dostáváme, že $\varphi(G_1)$ je podgrupa $G_2$. Omezíme-li obor hodnot zobrazení $\varphi$, můžeme ho chápat jako homomorfismus $\varphi:G_1\to \varphi(G_1)$. Nyní aplikujeme (1) pro $H=\Ker \varphi$ a dostaneme přímo požadovaný izomorfismus $\psi:G_1/\Ker \varphi\to \varphi(G_1)$. \end{proof}


\begin{dusl}[2. věta o izomorfismu]\label{2. o izomorfismu}
Nechť $G(\cdot)$ je grupa a $H$, $K$ její normální podgrupy.
Jestliže  $H\subseteq K$ ,
pak $K/H$ je normální podgrupa grupy $G/H(\cdot)$ a faktorová grupa $G/K(\cdot)$
je izomorfní grupě $(G/H)/(K/H)(\cdot)$.
\end{dusl}
%\begin{proof} Nejprve použijeme \ref{o homomorfismu}(1) pro homomorfismy $\pi_K:G\to G/K$ (jako $\varphi$ z \ref{o homomorfismu}(1)) a  $\pi_H:G\to G/H$ (jako $\pi_H$ z \ref{o homomorfismu}(1)). Protože podle předpokladu $H\subseteq K=\Ker\pi_K$, dává nám \ref{o homomorfismu}(1) homomorfismus $\psi:G/H\to G/K$ splňující vztah $\psi([a]_H)=[a]_K$. Všimněme si, že je $\psi$ zjevně na. Nyní přímočaře spočítáme $\Ker \psi=\{[a]_H\in G/H|\ \psi([a]_H)=[a]_K=[e]_K\}=K/H$. Poznamenejme, že je $\Ker \psi=K/H$ normální podgrupa $G/H(\cdot)$ podle \ref{1.17}(5). Nyní pro homomorfismus $\psi$ využijeme \ref{o homomorfismu}(2), abychom dostali $G/K=\psi(G/H)\cong (G/H)/\Ker \psi  = (G/H)/(K/H)$. \end{proof}





\begin{comment}

2018/19 nebude

Na závěr zobecníme princip dobře známý z lineární algebry, který říká, že je homomorfismus určen hodnotami na množině generátorů.
Nejprve ovšem vysvětlíme, co pojem množina generátorů v obecném případě znamená. 

\begin{definice} Buď $\A=A(\alpha_i|\ i\in I)$algebra a $X\subseteq A$. Potom podalgebru $\langle X\rangle$
algebry $\A$, kterou dostaneme jako průnik všech podalgeber $\A$ obsahujících množinu
$X$, což je podle \ref{US} podalgebra, nazveme pod\-algebrou {\it generovanou} $X$ (nebo budeme říkat, že $X$ 
{\it generuje} podalgebru $\langle X\rangle$). Řekneme, že $X$ {\it generuje} $\A$, jestliže $\langle X\rangle=A$.
\end{definice}


\begin{pozn}\label{gen} Buď $f, g: A\to B$ dva homomorfismy algeber stejného typu
a nechť $X\subseteq A$ generuje algebru $\A$. Jestliže $f(x)=g(x)$ pro všechna
$x\in X$, potom $f=g$. 
\end{pozn}
\begin{proof} Nejprve ukážeme, že je množina $C=\{a\in A|\ f(a)=g(a)\}$ podalgebrou
algebry $A$. Vezměme $n$-ární operaci $\alpha$ algebry $A$ a 
nechť $a_1,\dots, a_n\in C$. Pak 
$f(\alpha(a_1,\dots, a_n))=\alpha(f(a_1),\dots, f(a_n))=\alpha(g(a_1),\dots, g(a_n))
=g (\alpha(a_1,\dots, a_n))$, proto $\alpha(a_1,\dots, a_n)\in C$.
Všimneme-li si, že $X\subseteq C$, dostaneme $A=\langle X\rangle\subseteq C$,
čímž jsme dokončili důkaz.
\end{proof}


\begin{prikl} \rm (1) Uvažujme algebru celých čísel $\Z(+)$ a nějaký grupoid $G(+)$, tedy algebru s jednou binární operací $+$. Pak sice $\langle \{1\}\rangle= \mathbf{N}$, ale 
nejmenší podalgebra $\Z(+)$ obsahující množinu $\{-1,1\}$ je už rovna celému $\Z$
tj. $\langle \{-1,1\}\rangle= \Z$.

Nechť $f, g:\Z\to G$ je homomorfismus. Uvědomme si, že nejmenší podalgebra $\Z(+)$ obsahující množinu $\{-1,1\}$ je už rovna celému $\Z$ tj. $\langle \{-1,1\}\rangle= \Z$. Podle předchozí poznámky jsou tedy $f$ a $g$ shodné, jestliže $f(1)=g(1)$ a $f(-1)=g(-1)$.

(2) Uvažujme-li nyní dva homomorfismy $f, g:\Z\to G$ na algebře celých čísel $\Z(+,-)$ a obecné algebře $G(+,-)$  s jednou binární operací $+$ a jednou unární operací $-$. Nechť $f, g:\Z\to G$ je homomorfismus. Potom $\langle 1\rangle= \Z$, a podle \ref{gen} jsou $f$ a $g$ shodné, jestliže $f(1)=g(1)$. 

(3)  Algebru $\Z(+,-,1)$ dokonce generuje prázdná množina, tedy $\langle \emptyset\rangle= \Z$ a tudíž existuje nejvýše jeden homomorfismus
algebry $\Z(+,-,1)$ do obecné algebry $G(+,-,1)$ .
\end{prikl}







Velmi důležitým a užitečným faktem obecné algebry, který jsme už bez velkých komentářů několikrát použili,
je pozorování, že dvě izomorfní algebry jsou z hlediska algebry nerozlišitelné, mají všechny vlastnosti stejné
a platí o nich tudíž stejná tvrzení. Důvod platnosti takového pozorování je v podstatě velmi elementární:
u vlastností izomorfních algeber nezáleží na tom jak konkrétně vypadají jejich prvky (a ,,překlad"  zajišťuje bijekce určená izomorfismem),
podstatné je, že operace jsou na odpovídajících prvcích stejné, což právě zajišťuje slučitelnost operace s izomorfismem.
Samotná přesná formalizace uvedené myšlenky, která je tvrzením o metajazyku algebry, vyžaduje pečlivou práci s formální logikou a my ji zde pouze pro informaci
alespoň naznačíme.

\vskip 5mm 

Připomeňme, že  term je jakákoli proměnná a jsou-li $t_1,\dots, t_n$ termy a $\alpha$ funkční symboly (operace) četnosti $n$, pak
i $\alpha(t_1,\dots, t_n)$, je term, dále je-li $P$ predikát četnosti $n$ a $t_1,\dots, t_n$ jsou termy, pak je výraz
$P(t_1,\dots, t_n)$ atomickou formulí a a jsou-li $\varphi$ a $\psi$ dvě formule, pak výrazy $(\varphi\to\psi)$,
$(\varphi\land\psi)$,  $(\varphi\lor\psi)$,  $\neg\varphi$, $\forall\varphi$ a $\exists\varphi$ jsou rovněž formule.
Jazykem predikátové logiky (prvního řádu) potom rozumíme všechny formule, které vyniknou z daného systémem funkčních a predikátových symbolů.

Dále připomeňme, že formule $\varphi$ platí ve struktuře $A$,
značíme $\A\models\varphi$, právě když je $\varphi$ splněna každým ohodnocením proměnných nosné množiny 
$A$ struktury $\A$.
Uzavřenou formulí rozumíme formuli, která neobsahuje žádnou volnou proměnnou.

V našich úvahách se pro jednoduchost omezíme na jazyk s jediným predikátovým symbolem $=$, proměnnými jako prvky algebry
a funkčními symboly reprezentující operace daných algeber.

\begin{theorem} Nechť $A(\alpha_i|\ i\in I)$ a $B(\alpha_i|\ i\in I)$ jsou dvě izomorfní algebry stejného typu.
Potom uzavřená formule $\varphi$ jazyka algeber platí v algebře $A(\alpha_i|\ i\in I)$, právě když platí v algebře
$B(\alpha_i|\ i\in I)$.
\end{theorem}
\begin{proof} 
Nechť $f: A\to B$ je nějaký izomorfismus algeber $\A=A(\alpha_i|\ i\in I)$ a $\B=B(\alpha_i|\ i\in I)$, $\varphi$ formule. 
Vezmeme-li nějaké ohodnocení $e$ formule $\varphi$ v $A$, označíme $fe$ zobrazení, které
hodnotě $e(x)$ nějaké proměnné v $A$ přiřadí hodnotu $fe(x)$ téže proměnné v $B$. 
Je-li $E$ množina všech ohodnocení formule $\varphi$ v $A$, vidíme, že množina $\{fe|\ e\in E\}$ tvoří právě množinu všech
ohodnocení formule $\varphi$ v $B$, neboť $f$ je bijekce.
Dále snadno nahlédneme, že pro každou uzavřenou formuli $\varphi$ platí, že buď  $\A\models\varphi$ nebo
$\A\models\neg\varphi$,
a protože $f$ je izomorfismus algeber $\A$ a $\B$, stačí 
indukcí podle počtu kroků, jimiž je $\varphi$ odvozena z atomický formulí a jimiž jsou v nich vytvořeny zúčastněné termy, dokázat
$\A\models\varphi$ implikuje $\B\models\varphi$.


Nejprve uvážíme jedinou atomickou formuli $t=s$, kde 
$t=t(x_1,\dots,x_n)$ a $s=s(x_1,\dots,x_n)$ jsou termy v proměnných $x_1,\dots,x_n$.
Mějme realizaci nějaké funkčního symbolu na obou algebrách, tedy právě $n$-ární operaci $\alpha_i$
pro nějaké $i\in I$ a předpokládáme například, že $t=\alpha_i(t_1,\dots,t_n)$, kde $t_1,\dots,t_n$ jsou termy a nechť $e$ je nějaké ohodnocení formule $t=s$.
Protože $e(\alpha_i(t_1,\dots,t_n)=\alpha_i(e(t_1),\dots,e(t_n))$ a z indukčního předpokladu užitého pro termy $t_1,\dots,t_n$ víme,
že $f(e(t_i))=fe(t_i)$ (t.j. obraz izomorfismem $f$ termu $t_i$ ohodnoceného v algebře $A$ pomocí $e$ je týž jako ohodnocení termu $t_i$ ohodnocený v algebře $B$
ohodnocením $fe$). Protože je $f$ homomorfismus, vidíme, že
\[
f(e(\alpha_i(t_1,\dots,t_n)))=f(\alpha_i(e(t_1),\dots,e(t_n))) =\]
\[=\alpha_i(fe(t_1),\dots,fe(t_n))=fe(\alpha_i(t_1,\dots,t_n)).\]
Tím jsme ověřili, že platnost $e(t)=e(s)$ implikuje platnost $fe(t)=fe(s)$.

Zbytek důkazu už je jen přímočaré indukční ověření platnosti formule na $\B$ vzniklé použitím pravidel $(\varphi\to\psi)$,
$(\varphi\land\psi)$,  $(\varphi\lor\psi)$,  $\neg\varphi$, $(\forall x)\varphi$ a $(\exists x)\varphi$
z kratších for\-mulí $\varphi$ a $\psi$ za předpokladu, že daná dlouhá formule platí na $\A$.
\end{proof}

Závěrem poznamenejme, že ve skutečnosti na izomorfních algebrách ekvivalence platí i pro výroky vyřčené v mnohem bohatším jazyce (například tvrzení, které se vyslovuje o struktuře
podalgeber nějaké algebry).


\end{comment}



\vskip 1cm

\section{Okruhy a ideály}

Nyní obrátíme svou pozornost k další důležité třídě algebraických objektů, jimiž jsou okruhy, tedy komutativní aditivní grupa disponující navíc asociatívním násobením,
které je pomocí distributivity svázáno se sčítáním. Jedná se o společné uchopení známých struktur těles a celých čísel s opreacemi sčítání a násobení.

Protože je naším hlavním cílem konstrukce a algoritmické uchopení (především konečných) těles,
zaměříme se na obecný popis těles (Věta~\ref{5.5}) a charakterizaci těch faktorů komutativních okruhů, které
tvoří těleso (Věta~\ref{teleso}).

\begin{definice} {\it Okruhem} budeme nazývat každou takovou algebru
$R(+,\cdot,-,0,1)$, že $R(+)$ je komutativní grupa s neutrálním prvkem $0$ a operací opačného
prvku $-$, $R(\cdot)$ je monoid s neutrálním prvkem 1 a pro každé $a,b,c\in R$ platí, 
že $a\cdot(b+c)=a\cdot b + a\cdot c$
a $(a+b)\cdot c = a\cdot c + b\cdot c$. 
Prvek okruhu $R(+,\cdot,-,0,1)$ se nazývá {\it invertibilní}, 
jedná-li se o invertibilní prvek monoidu $R(\cdot)$. 

Řekneme, že je okruh 

- {\it komutativní}, je-li operace $\cdot$ komutativní,

- {\it obor}, jestliže pro každé $a,b\in R$ platí implikace $a\cdot b=0\Rightarrow a=0$ nebo $b=0$,

- {\it těleso}, jsou-li všechny prvky množiny $R\setminus\{0\}$ invertibilní a $0\neq 1$ a

- {\it komutativní těleso}, je-li to komutativní okruh a zároveň těleso. 
\end{definice}




\begin{prikl}\rm  (1) Je-li $T$ těleso ve smyslu definice z lineární algebry, pak je algebra $T(+,\cdot,-,0,1)$
komutativním tělesem.

(2) Je-li $T$ těleso a $M_n(T)$ značí množinu všech čtvercových matic nad $T$ stupně
$n$, pak $M_n(T)(+,\cdot,-,\mathbf 0_n,\mathbf I_n)$ je okruh.

(3) $\Z(+,\cdot,-,0,1)$ je obor  a  $\Z_n(+,\cdot,-,0,1)$ jsou pro každé přirozené $n>1$
jsou komutativní okruhy. Z lineární algebry víme, že je $\Z_n(+,\cdot,-,0,1)$ komutativní těleso, právě když je $n$ prvočíslo.
%(4) Nechť $V$ je vektorový prostor. Označme $End(V)$ množinu všech homomorfismů prostoru $V$ do sebe (tzv. endomorfismů). Na této množině můžeme definovat sčítání a opačný prvek předpisem $[f+g](\mathbf v)=f(\mathbf v)+g(\mathbf v)$ a $[-f](\mathbf v)=-f(\mathbf v)$ pro každé $\mathbf v\in V$. Označíme-li nulový homomorfismus symbolem $0_V$ a $\circ$ označuje skládání, pak $End(V)(+,\circ,-,0_V,Id)$ je okruh. 
\end{prikl}


\begin{pozn}\label{5.2} Nechť $R(+,\cdot,-,0,1)$ je okruh. Pak pro každé $a,b\in R$ platí:
\begin{enumerate}
\item[(1)] $0\cdot a=a\cdot 0=0$,
\item[(2)] $(-a)\cdot b= a\cdot (-b)=-(a\cdot b)$, $(-1)\cdot a = a\cdot (-1) =-a$,
%\item[(4)] $(-a)\cdot (-b) =a\cdot b$,
\item[(3)] $1$ je různé od $0$, právě když $|R|>1$ (tj. R je netriviální okruh).
\end{enumerate}
\end{pozn}
\begin{proof} U bodů (1) a (2) dokážeme jen jednu rovnost, důkaz druhé je symetrický.

(1) Využijeme-li definitorickou vlastnost prvku $0$ a distributivitu,
dostaneme $a\cdot 0 = a\cdot (0+0)= a\cdot 0+a\cdot 0$. Přičteme-li k levé a pravé straně
rovnosti $a\cdot 0 = a\cdot 0+a\cdot 0$ prvek $-(0\cdot a)$, vidíme, že $a\cdot 0=0$.

(2) Opět díky distributivitě máme $(-a)\cdot b + a\cdot b = (-a+a)\cdot b=0\cdot b=0$,
kde poslední rovnost plyne z (1).

Poslední rovnost dostáváme přímo z (2) pro $b=1$.

%(4) Stačí dvakrát aplikovat (2): $(-a)\cdot (-b) =-(a\cdot (-b)= -(-a\cdot b)=a\cdot b$.

(3) Přímá implikace je triviální, předpokládejme tedy, že $1= 0$ a vezměme libovolné
$a\in R$. Potom $a=a\cdot 1=a\cdot 0=0$ podle definice a (1).
\end{proof}

\begin{definice} Nechť $R(+,\cdot,-,0,1)$ je okruh. 
Řekneme, že množina $I\subseteq R$ je {\it pravý} (resp. {\it levý}) {\it ideál}
okruhu $R$, jestliže je $I$ podgrupa grupy $R(+)$ a 
pro každé $i\in I$ a $r\in R$ platí, že $i\cdot r\in I$ (resp. $r\cdot i\in I$).
Množinu $I$ nazveme {\it ideálem}, je-li pravým a zároveň levým ideálem.
\end{definice}


\begin{prikl}\label{hlid}\rm  (1) $\{0\}$ a $R$ jsou  ideály každého
okruhu $R$.

(2) Podle \ref{2.5} jsou ideály okruhu celých čísel $\Z(+,\cdot,-,0,1)$ právě tvaru
$k\Z$ a ideály okruhu $\Z_n(+,\cdot,-,0,1)$ tvaru
$k\Z_n$, kde $k<n$ je $0$ nebo dělitel čísla $n$.

(3) Množiny $aR=\{a\cdot r|\ r\in R\}$ (resp. $Ra=\{r\cdot a|\ r\in R\}$) jsou
(tzv. {\it hlavní}) pravé (resp. levé) ideály okruhu $R$ pro každé $a\in R$. 
Ověříme to například pro $aR$. Je-li $ar, as\in aR$, pak díky distributivitě
$ar+as=a(r+s)\in aR$ a $-ar=a(-r)\in aR$ podle \ref{5.2}(2). Dále
$0=a0\in aR$ díky \ref{5.2}(1) a $(ar)x=a(rx)\in aR$ díky asociativitě
pro libovolné $x\in R$.
\end{prikl}

Nechť $R(+,\cdot,-,0,1)$ je okruh.
Poznamenejme, že se ideálům $\{0\}$ a $R$ říká {\it triviální} ideály a
(levý, pravý) netriviální ideál $I$ okruhu $R(+,\cdot,-,0,1)$ (tj. platí-li, že $\{0\}\ne I\ne R$) se nazývá
{\it vlastní}. Pravé (levé) ideály tvaru $aR$ ($Ra$) popsané v Příkladu \ref{hlid}(3) jsou 
takzvané {\it hlavní} pravé (levé) ideály.   
Konečně alespoň dvouprvkovému  okruhu se říká {\it netriviální okruh}.

Nyní dokážeme elementární poznámku, která nám umožní charakterizovat tělesa pomocí pojmu pravý (levý ideál).

\begin{pozn}\label{5.4} Je-li $R(+,\cdot,-,0,1)$ okruh a $I$ jeho pravý nebo levý ideál,
pak $I= R$, právě když $1\in I$.
\end{pozn} 
\begin{proof} Protože $1\in R$, je přímá implikace triviální.
Jestliže $I$ pravý (levý) ideál, který obsahuje prvek $1$ a vezmeme libovolné $r\in R$, potom $r=1\cdot r = (r \cdot 1)\in I$,
tedy $I=R$.
\end{proof}

\begin{theorem}\label{5.5} V netriviálním okruhu $R(+,\cdot,-,0,1)$ je ekvivalentní:
\begin{enumerate}
\item[(1)] $R$ je těleso, 
\item[(2)] $R$ neobsahuje žádné vlastní pravé ideály,
\item[(3)] $R$ neobsahuje žádné vlastní levé ideály.
\end{enumerate}
\end{theorem}
\begin{proof} Stačí dokázat ekvivalenci (1) a (2).

Předpokládejme, že je $R$ těleso a mějme nějaký nenulový pravý ideál $I$.
Pak existuje $0\ne i\in I$ a k němu inverzní prvek $i^{-1}\in R$,
tedy $1=i\cdot i^{-1} \in I$ a proto $I=R$ podle \ref{5.4}.

Předpokládejme, že $R$ neobsahuje žádné vlastní pravé ideály a vezměme libovolně
nenulový prvek $a\in R$. Potom $0\ne a=a\cdot 1\in aR$, tedy podle předpokladu $aR=R$.
Proto existuje $b\in R$, pro nějž $a\cdot b=1$. Poznamenejme, že díky \ref{5.2}(1) a (4)
opět $b\ne 0$, a tudíž můžeme stejným argumentem najít $c\in R$, pro které $b\cdot c=1$.
Nyní $a=c$  podle \ref{1.4} a $b$ je tedy inverzní k $a$.
\end{proof}


Poznamenejme, že existují okruhy (říká se jim \emph{jednoduché}), které neobsahují žádné vlastní (oboustranné) ideály,
a zároveň se nejedná o tělesa. Typickým příkla\-dem jsou maticové okruhy $M_n(T)$, kde $n>1$ a $T$ je komutativní těleso.


%\begin{definice} Je-li $R(+,\cdot,-,0,1)$ okruh a $\rho$ ekvivalence na $R$, řekneme, že $\rho$ je \emph{okruhová kongruence}, pokud je $\rho$ slučitelná jak s operací $+$, tak s operací $\cdot$. V případě, že je to zřejmé z kontextu, přívlastek \uv{okruhová} se vynechává. \end{definice}

Připomeňme, že {\it Homomorfismus} ({\it izomorfismus})  okruhů bude homomorfismus (izomorfismus) příslušných algeber.
Uvážíme-li ideál $I$ okruhu $R(+,\cdot,-,0,1)$, pak je  $I$ podgrupa grupy $R(+)$, tedy můžeme pracovat s ekvivalencí $\rmod\ I$
danou podmínkou $(a,b)\in\rmod\ I\Leftrightarrow a-b=a+(-b)\in I$.
{\it Podokruhem} okruhu $R(+,\cdot,-,0,1)$ budeme rozumět každou podalgebru algebry $R(+,\cdot,-,0,1)$.

%Nyní budeme aplikovat Větu~\ref{kongruence1} na aditivní grupu okruhu:

%\begin{theorem} Je-li $R(+,\cdot,-,0,1)$ okruh, pak zobrazení $I\mapsto \rmod\ I$ a $\rho\mapsto [0]_\rho$ jsou vzájemně inverzní zobrazení 
%mezi množinou všech ideálů grupy $R(+,-,0)$ a množinou všech kongruencí okruhu.
%\end{theorem}
%\begin{proof}
%Podle  Větu~\ref{kongruence1} jsou $H\mapsto \rmod\ H$ a $\rho\mapsto [0]_\rho$ vzájemně inverzní zobrazení mezi množinou všech podgrup grupy $R(+,-,0)$ a množinou všech jejích grupových kongruencí. Ukážeme, že jde (po zúžení) o vzájemně inverzní zobrazení mezi množinou všech ideálů okruhu $\mathcal R$ a množinou všech okruhových kongruencí tohoto okruhu.

%Ať je nejprve $H$ ideál okruhu $\mathcal R$. Předpokládejme, že $(a,b), (c,d)\in\rmod\ H$, čili $a-b,c-d\in H$. Potom ovšem i $(a-b)c+b(c-d)=ac-bd\in H$, tj. $(ac,bd)\in\rmod H$ a $\rmod\ H$ je tedy okruhová kongruence.

%Opačně mějme dánu okruhovou kongruenci $\rho$ a $r\in R$ buď libovolný prvek. Triviálně máme $(r,r)\in\rho$. Je-li dále $(a,0)\in\rho$, potom $(ra,r0)=(ra,0)\in\rho$ a také $(ar,0r)=(ar,0)\in\rho$. Jinými slovy: $a\in [0]_\rho$ implikuje jak $ra\in [0]_\rho$, tak $ar\in [0]_\rho$, a tedy $[0]_\rho$ je ideál okruhu $\mathcal R$.
%\end{proof}

%Můžeme analogicky modifikovat pro okruhy i Poznámky~\ref{faktor} a \ref{1.17}. Je-li $I$ ideál (resp. $\rho$ jemu odpovídající kongruence), potom lze na množině $R/I = R/\rmod\ I$ definovat obvyklým způsobem definovat kromě operace $+$ (tj. aplikace Poznámky~\ref{faktor} na grupu $R(+,-,0)$) i operaci $\cdot$ vztahem $(a+I)\cdot (b+I) = ab+I$ (resp. $[a]_\rho\cdot[b]_\rho = [ab]_\rho$). 

\begin{pozn}\label{okr-kongr} Nechť $\mathcal R=R(+,\cdot,-,0,1)$ a $\mathcal S=S(+,\cdot,-,0,1)$ jsou okruhy, $I$ ideál okruhu $\mathcal R$ a 
$\varphi:R\to S$ okruhový homomorfismus.
\begin{enumerate}
\item[(1)] $\rmod\ I$ je kongruence okruhu $\mathcal R$. Označíme-li $R/I:=R/\rmod\ I$, pak je faktorová algebra $R/I(+,\cdot,-,[0]_I,[1]_I)$ rovněž okruh
a přirozená projekce $\pi_I:R\to R/I$ okruhový homomorfismus.
\item[(2)] $\Ker\varphi$ je ideál okruhu $\mathcal R$.
\end{enumerate}
\end{pozn}
\begin{proof} (1) Podle \ref{3.3}(1),(3) je $\rmod\ I$ ekvivalence slučitelná s operacemi $+$, $-$, $0$ a $1$. Zbývá ukázat slučitelnost s násobením.
Zvolme $(a,b), (c,d)\in\rmod\ I$.
Pak $a-b, c-d, (a-b)c, b(c-d)\in I$, a tudíž $ac-bd = (a-b)c + b(c-d)\in I$. Proto
i $(a\cdot c,b\cdot d)\in\rho$, čímž jsme ověřili, že je $\rmod\ I$ kongruence na
$R(+,\cdot,-,0,1)$.

To, že je $R/I(+,\cdot,-,I,1+I)$ okruh se snadno přímočaře ověří z definice a fakt, že je $\pi_I$ homomorfismus plyne okamžitě z \ref{3.9}.

(2) $\Ker\varphi$ je jistě normální podgrupa a zbývá nahlédnout, že pro každé $r\in R$ a $k\in \Ker\varphi$
je 
\[
\varphi(r\cdot k)=\varphi(r)\cdot \varphi(k)= \varphi(r)\cdot0=0=0\cdot\varphi(r)=\varphi(k)\cdot\varphi(r)=\varphi(k\cdot r),
\]
tedy $r\cdot k,k\cdot r\in \Ker\varphi$.
\end{proof}

Právě zavedenému  okruhu říkáme \emph{faktorový okruh} (nebo krátce \emph{faktorokruh}) okruhu $R$ podle ideálu~$I$ . 

\begin{definice} Řekneme, že ideál $I$ komutativního okruhu $\mathcal R=R(+,\cdot,-,0,1)$ je \emph{maximální}, pokud $I\neq R$ a 
pro každý ideál $J$, že $I\subseteq J$, platí buď $J=I$ nebo $J= R$. 
\end{definice}

Všimněme si, že v tělese je maximálním ideálem právě nulový ideál.

Nyní zformulujeme tvrzení, které charakterizuje, kdy je faktor komutativního okruhu těleso.
Toto tvrzení bude hrát zásadní roli v konstrukci konečných těles, jíž se budeme zabývat v následující kapitole.

\begin{theorem}\label{teleso} Nechť $R(+,\cdot,-,0,1)$ je komutativní okruh a $I$ jeho ideál. Potom je $R/I(+,\cdot,-,[0]_I,[1]_I)$ komutativní těleso právě tehdy, když $I$ je maximální ideál.
\end{theorem}
\begin{proof} Označme $\mathcal I_{I}^{R}$ množinu všech ideálů 
okruhu $\mathcal R$ obsahujících ideál $I$ a $\mathcal I_{0}^{R/I}$ množinu všech ideálů okruhu $R/I(+,\cdot,-,[0]_I,[1]_I)$. Nejprve dokážeme obecnější pozorování, v němž si uvědomíme vztah množiny ideálů faktorového a původního okruhu.

\begin{lemma} Je-li $\pi_I:R\to R/I$ přirozená projekce, 
pak jsou zobrazení 
\[J\to \pi(J)\ \ \ \text{ a }\ \ \ \widetilde{J}\to \pi^{-1}(\widetilde{J})
\]
vzájemně inverzní bijekce mezi množinami $\mathcal I_{I}^{R}$ a $\mathcal I_{[0]}^{R/I}$.
\end{lemma}

Protože je $\pi$ grupový homomorfismus, jsou pro ideál $J$ okruhu $\mathcal R$ a ideál $\widetilde{J}$ okruhu $\mathcal R/I$
obraz $\pi(J)$ i úplný vzor $\pi^{-1}(\widetilde{J})$ podgrupy, navíc platí, že $I\subseteq \pi^{-1}(\widetilde{J})$. Dále potřebujeme nahlédnout, že se jedná opravdu o ideály.
Zvolíme-li $r\in R$ a $j\in J$, pak 
\[
\pi_I(r)\cdot \pi_I(j)=\pi_I(rj) \in \pi_I(J),\ \ 
\pi_I(j)\cdot \pi_I(r)=\pi_I(jr) \in \pi_I(J)
\]
a podobně pro pro $r\in R$ a $j\in \pi^{-1}(\widetilde{J})$
\[
\pi_I(rj)=\pi_I(r)\cdot \pi_I(j) \in \widetilde{J},\ \ 
\pi_I(jr)=\pi_I(j)\cdot \pi_I(r) \in \widetilde{J},
\]
tedy obě uvažovaná zobrazení jsou dobře definovaná zobrazení mezi množinami $\mathcal I_{I}^{R}$ a $\mathcal I_{[0]}^{R/I}$.
Protože $\pi\pi^{-1}(\widetilde{J})=\widetilde{J}$ a $\pi^{-1}\pi(J)=J$, jedná se vzájemně inverzní bijekce, čímž máme Lemma dokázáno.

Nyní si stačí všimnout, že je $R/I(+,\cdot,-,[0]_I,[1]_I)$ podle Věty~\ref{5.5} komutativní těleso právě tehdy, když $\mathcal I_{0}^{R/I}$ obsahuje pouze triviální ideály, což je díky
Lemmatu ekvivalentní podmínce, že $\mathcal I_{I}^{R}$ obsahuje právě dva ideály, tedy právě když je $I$ je maximální ideál.
\end{proof}


%Ať $R/I$ je těleso a buď $J\supsetneq I$ ideál v $R$. Potom je $\pi_I(J)$ ideál v $R/I$, přičemž $\pi_I(J)\neq\{I\}$, tj. nejde o triviální (nulový) ideál. Podle Věty~\ref{5.5} musí být již $\pi_I(J)=R/I$. Musí tedy existovat $r\in J$ tak, že $r+I=1+I$, tj. $1-r\in I$, z čehož ihned plyne $1=r+(1-r)\in J$, a proto $J = R$. Dokázali jsme, že $I$ je maximální ideál.

%Je-li naopak $I$ maximální ideál a $a\in R\setminus I$ (tj. $a+I\neq I$ v okruhu $R/I$), pak snadno ověříme, že je množina $aR+I=\{ar+i|\ r\in R, i\in I\}$ ideál obsahující jako vlastní podmnožinu $I$. Proto z maximality $I$ plyne, že $aR+I=R$, odkud  dostáváme existenci takového $r\in R$ a $i\in I$, že $ar+i = 1$ a tedy $1-ar\in I$. Jinak řečeno $(a+I)(r+I)=ar+I=1+I$ v okruhu $R/I$, což znamená, že $r+I$ je inverz v okruhu $R/I$ k nenulovému prvku $a+I$. Ověřili jsme, že $R/I$ je těleso.



%Následující příklady analogií z kapitoly o grupách ponecháváme čtenáři k rozmyšlení.

%\begin{prikl}\label{analogie} \rm (1) Analogie Poznámky~\ref{1.17} pro okruhy. Jsou-li $R,S$ okruhy a $\psi:R\to S$ okruhový homomorfismus, potom je $\Ker(\psi)$ ideál okruhu $R$, Im$(\psi)$ je podokruh okruhu $S$ a platí: je-li $I$ ideál v $R$, pak $\psi(I)$ je ideál v Im$(\psi)$; je-li $J$ ideál v $S$, pak $\psi^{-1}(J)$ je ideál v $R$.

%(2) Analogie věty o homomorfismu a vět o izomorfismu (\ref{o homomorfismu}(1), \ref{o homomorfismu}(2), \ref{2. o izomorfismu}) pro okruhy. Stačí nahradit pojmy grupa, podgrupa, normální podgrupa, grupový homomorfismus za pojmy okruh, podokruh, ideál, okruhový homomorfismus. Důkazy stačí jen nepatrně rozšířit o ověřování, že vše sedí nejen pro grupovou operaci $+$, ale i pro okruhové násobení $\cdot$.\end{prikl}


\vskip 1cm

\section{Okruhy polynomů a konstrukce těles}

V následující kapitole ukážeme dvě cesty, jak najít další přirozené (a občas i užitečné)
příklady těles.
Zatímco druhá z nich zobecňuje známou konstrukci zlomků, která z celých čísel vytváří těleso racionálních čísel (Věta~\ref{fractions}),
v první konstrukci využijeme faktorizace okruhů polynomů nad tělesy $\mathbb Z_p$, kde $p$ je prvočíslo, abychom
dostali libovolné konečné těleso (Věta~\ref{finfields}). Nejprve ovšem zavedeme polynomy nad obecnými okruhy a uvědomíme si, že známý školský algoritmus dělení se zbytkem funguje
v mnohem obecnější situaci než jsme zvyklí.

\subsection{Konečná tělesa}

\begin{definice} Buď  okruh. 
Položme $R[x]=\{p:\mathbf N_0\to R \mid \{n\mid p(n)\ne 0\}\text{ je konečné}\}$.
Prvek $p\in R[x]$ budeme zapisovat také ve tvaru $p=\sum_{n\in \mathbf N_0}p_nx^n$,
kde $p_n=p(n)$, tedy $R[x]$ obsahuje právě všechny formální nekonečné sumy
s konečným nosičem.
Na $R[x]$ definujme binární operace $+$ a $\cdot$, unární operaci $-$
a nulární operace $\mathbf 0$ a $\mathbf 1$ pro 
$p=\sum_{n\in \mathbf N_0}p_nx^n$ a $q=\sum_{n\in \mathbf N_0}q_nx^n$: 
\[
p+q = \sum_{n\in \mathbf N_0}(p_n+q_n)x^n,\ \ \ \ \ \ 
p\cdot q = \sum_{n\in \mathbf N_0} (\sum_{i=0}^n p_i\cdot q_{n-i})x^n,
\]
\[
-p=\sum_{n\in \mathbf N_0}-p_nx^n,\ \ 
\mathbf 0=\sum_{n\in \mathbf N_0}0x^n,\ \ 
\mathbf 1 = 1x^0 + \sum_{n>0}0x^n.
\]
Je-li $p\ne \mathbf 0$,
budeme největší takové $n\in \mathbf N_0$, že $p_n\ne 0$, nazývat stupněm
polynomu $p$. Stupeň polynomu $\mathbf 0$ položíme roven $-1$.
Stupeň polynomu $p$ budeme označovat $\st p$.
\end{definice}


\begin{pozn}\label{polynomy} Nechť $R(+,\cdot,-,0,1)$ je okruh a $p,\ q\in R[x]$.
\begin{enumerate}
\item[(1)] $R[x](+,\cdot,-,\mathbf 0,\mathbf 1)$ je okruh a
 množina $\{sx^0 \mid s\in R\}$ jeho podokruh izomorfní okruhu $R(+,\cdot,-,0,1)$,
\item[(2)] $\st (p+q)\le \max(\st p,\ \st q)$, je-li $p,q\ne\mathbf 0$, pak $\st p\cdot q\le \st p+ \st q$ a
je-li navíc $R$ oborem integrity, potom $\st p\cdot q= \st p+ \st q$,
\item[(3)] $R[x]$ je obor integrity právě tehdy, když je $R$ obor integrity.
\end{enumerate}
\end{pozn}
\begin{proof} Mějme
$p=\sum_{n\in \mathbf N_0}p_nx^n$, $q=\sum_{n\in \mathbf N_0}q_nx^n$, 
$r=\sum_{n\in \mathbf N_0}r_nx^n\in R[x]$.

(1) Nejprve poznamenejme, že jsou všechny operace dobře definované
a přímočaře ověřme komutativitu a asociativitu operace $+$:
\[
p+q = \sum_{n\in \mathbf N_0}(p_n+q_n)x^n =
\sum_{n\in \mathbf N_0}(q_n+p_n)x^n = q+p,
\]
\[
(p+q)+r = 
\sum_{n\in \mathbf N_0}((p_n+q_n)+r_n)x^n = 
\sum_{n\in \mathbf N_0}(p_n+(q_n+r_n))x^n =
p+(q+r). 
\]
Protože $\mathbf 0$ je zjevně neutrální prvek operace $+$ a vidíme, že
$p+(-p)=\mathbf 0$, je $R(+,-,0)$ komutativní grupa.
Podobně 
\[
r\cdot(p+q) = 
r\cdot \sum_{n\in \mathbf N_0}(p_n+q_n)x^n=
\sum_{n\in \mathbf N_0} (\sum_{i=0}^n r_i\cdot (p_{n-i}+q_{n-i}))x^n
=
\]
\[
= \sum_{n\in \mathbf N_0} (\sum_{i=0}^n r_i\cdot p_{n-i} )x^n +
\sum_{n\in \mathbf N_0} (\sum_{i=0}^n r_i\cdot q_{n-i})x^n
= p\cdot r+q\cdot r,
\]
důkaz druhé distributivity je symetrický.
Konečně zbývá ověřit, že je $R(\cdot,1)$ monoid:
\[
(p\cdot q)\cdot r = 
\sum_{n\in \mathbf N_0} (\sum_{i+j=n}p_i\cdot q_j)x^n \cdot r
= 
\sum_{n\in \mathbf N_0} (\sum_{i+j+k=n}p_i\cdot q_j\cdot r_k)x^n
= p\cdot (q\cdot r),
\]
\[
p\cdot\mathbf 1 = 
\sum_{n\in \mathbf N_0} (\sum_{i=0}^n p_i\cdot \mathbf 1_{n-i})x^n
\sum_{n\in \mathbf N_0} (p_n\cdot 1)x^n
= p = \mathbf 1\cdot p,
\]
kde $\mathbf 1 =\sum_{n}\mathbf 1_{n}x^n$, tedy $\mathbf 1_0=1$
a $\mathbf 1_n=0$ pro všechna $n>0$.
Bezprostředně z konstrukce okruhu $R[x]$ vidíme, že zobrazení $\nu:R\to R[x]$
dané vztahem $\nu(r)=rx^0$ je prostý okruhový homomorfismus, proto díky
\ref{ob.o homomorfismu}(2) dostáváme izomorfismus
okruhu $R(+,\cdot,-,0,1)$ s podokruhem $\nu(R)=\{sx^0|\ s\in R\}$.

(2) Nerovnost $\st p+q\le \max(\st p,\ \st q)$ plyne z inkluze 
\[
\{n\mid p_n+q_n\ne0\} \subseteq \{n\mid p_n\ne0\}\cup \{n\mid q_n\ne0\}.
\]

Označme $\nu=\st p$ a $\mu=\st q$ a uvědomme si pro každé 
$n>\nu+ \mu$, že koeficient u $x^n$
v polynomu $p\cdot q$ je 
$\sum_{k=0}^n(p_k\cdot q_{n-k})= \sum_{k=0}^{n-\mu}(p_k\cdot 0)
+\sum_{k=n-\mu+1}^n(0\cdot q_{n-k})=0$, proto $\st p\cdot q\le \nu+ \mu$.

Je-li $R$ obor integrity, máme koeficient polynomu $p\cdot q$ u $x^{\nu+\mu}$:
\[
\sum_{k=0}^{\nu+\mu}(p_k\cdot q_{n-k})= 
\sum_{k=0}^{n-\mu-1}(p_k\cdot 0) + p_\nu\cdot q_\mu
+\sum_{k=n-\mu+1}^n(0\cdot q_{n-k})= p_\nu\cdot q_\mu\ne 0,
\]
neboť $p_\nu\ne 0$ a $q_\mu\ne 0$.

(3) Je-li $R[x]$ obor integrity, je každý jeho podokruh oborem integrity,
tedy i okruh $R$ podle (1).
Je-li $R$ obor integrity, pak snadno nahlédneme, že je násobení polynomů komutativní a  pro každé $p,q\ne\mathbf 0$, máme podle (3) $\st p\cdot q=\st p+\st q\ge 0$,
proto $p\cdot q\ne 0$. Navíc 44
\end{proof}

Okruhu $R[x](+,\cdot,-,\mathbf 0,\mathbf 1)$  budeme říkat
{\it okruhem polynomů} jedné neurčité a jeho prvkům {\it polynomy}.





\begin{theorem}[O dělení se zbytkem]\label{dsz} Nechť $R(+,\cdot,-,0,1)$ je obor,
$a,\ b\in R[x]$, kde $b=\sum b_nx^n$. Předpokládejme, že $m=\st b\ge 0$ a $b_m$
je invertibilní v $R$. Pak existují takové jednoznačně určené polynomy
$q,\ r\in R[x]$, že $a=b\cdot q + r$ a $\st r< \st b$.
\end{theorem}
\begin{proof} Existenční část tvrzení dokážeme pomocí algoritmu:

{\tt
VSTUP: $a,\ b\in R[x]$, kde $b_{\st b}$ invertibilní

VÝSTUP: $q,\ r\in R[x]$, pro které $a=q\cdot b + r$, $\st r<\st b$
\begin{enumerate}
\item[0.] $m:=\st b$; $n:=\st a-m$;
\item[1.] if $n<0$ then return $0, a$ else $r:=a$;
\item[2.] for $i:=n$ downto $0$ do $\{ q_i:=r_{i+m}b_m^{-1}; r:= r-q_ix^{i}b;\}$
\item[3.] return $\sum_iq_ix^i, \ r$.
\end{enumerate}
}

Indukcí podle $i$ ve for-cyklu snadno nahlédneme, že algoritmus pracuje správně.

Zbývá ukázat jednoznačnost. Předpokládejme, že $a=b\cdot q' + r'$ a $\st r'< \st b$.
Potom $b\cdot(q-q')=r'-r$ a podle \ref{polynomy}(3) a protože $\st(r'-r)< \st b$,
dostáváme $r'-r=0$, a proto $q-q'=0$ 
\end{proof}


\begin{dusl}\label{T[x]}
Nechť $T(+,\cdot,-,0,1)$ je komutativní těleso. Pak je každý 
ideál okruhu $T[x](+,\cdot,-,\mathbf 0,\mathbf 1)$
hlavní.
\end{dusl}
\begin{proof}  
Vezměme libovolný nenulový ideál $I$ a v ideálu $I$ zvolme nenulový polynom 
$p$ nejmenšího možného stupně. Zřejmě $pT[x]\subseteq I$. Nechť
$i\in I$. Pak podle \ref{dsz} existují takové polynomy $q,r\in T[x]$, že 
$i=p\cdot q +r$ a $\st(r)<\st(p)$. Protože $r=i-p\cdot q \in I$
a $\st(p)$ byl minimální, je nutně $r=0$ a $pT[x]=I$.
\end{proof}

\begin{definice} Nechť $\mathcal R=R(+,\cdot,-,0,1)$ je komutativní okruh a $a,b\in R$. Řekneme, že $a$ \emph{dělí} $b$,
$a|b$, existuje-li  $c\in R$, pro které $a\cdot c=b$. O neinvertibilním nenulovém prvku $p\in R$ řekneme, že je \emph{ireducibilní}, pokud pro každý rozklad 
$p=a\cdot b$ platí že je $a$ nebo $b$ invertibilní.
\end{definice}

\begin{prikl}\rm  (1)  Prvočísla jsou právě ireducibilní prvky oboru celých čísel. Navíc je-li $p$ prvo\-číslo a $n\mathbb Z$ ideál okruhu celých čísel, pro který 
$p\mathbb Z\subseteq n\mathbb Z$, pak $n|p$, tedy buď $n\mathbb Z=p\mathbb Z$ nebo $n\mathbb Z=\mathbb Z$, což znamená, že $p\mathbb Z$ je maximální ideál.

(2) Ireducibilní prvky v okruhu polynomů nad tělesem jsou právě ireducibilní polynomy.
\end{prikl}

Všimněme si, že přímo z definice dostáváme charakterizaci relace dělitelnosti pomocí inkluze hlavních ideálů:

\begin{pozn}\label{HI} Nechť $R(+,\cdot,-,0,1)$ komutativní okruh a $a,b\in R$. Pak
\[
a/b \Leftrightarrow b\in aR \Leftrightarrow bR\subseteq aR.
\]
\end{pozn}


Smyslem následujícího tvrzení je pozorování, že nám faktorizace okruhu polynomů nad tělesem podle ideálu generovaného
ireducibilním polynomem dá těleso.


\begin{pozn} \label{OIHI} Je-li $T(+,\cdot,-,0,1)$ komutativní těleso a $I$ ideál okruhu polynomů $T[x](+,\cdot,-,0,1)$, pak
je  $I$ maximální právě tehdy, když existuje ireducibilní polynom $f\in T[x]$ takový, že $I=fT[x]$
\end{pozn}

\begin{proof} 
Z \ref{T[x]} víme, že existuje $f\in T[x]$ takový, že $I = fT[x]$. Dále si stačí všimnout, že pro ideál $gT[x]$ máme $fT[x]\subsetneq gT[x]\subsetneq T[x]\Leftrightarrow g|f$ a současně $g\!\not|\, 1$ a $f\!\not|\, g$; pravá strana ekvivalence neříká nic jiného, než $g|f$ a $0<$ def $g<$ deg $f$, tj. $f$ není ireducibilní.
\end{proof}


Nyní zkonstruujeme konečná (komutativní) tělesa, přičemž budeme následující výsledek brát jako fakt, který dokážeme až příští semestr.

\begin{fakt}\label{11.6} Pro každé prvočíslo $p$ a $n\in \N$ existuje ireducibilní polynom $f\in\Z_p[x]$ stupně $n$. Navíc v $\Z_p[x]$ platí $f|(x^{p^n}-x)$.
\end{fakt}

Větu o konečných tělesech zformulujeme v klasickém znění. Důkaz bodu (2) a (3) ovšem uvádíme jen informativně.

\begin{theorem}\label{finfields}
{\rm (1)} Je-li $p$ prvočíslo a $n\in\N$, existuje komutativní těleso o $p^n$ prvcích.

{\rm (2)} Je-li $\mathbb F$ konečné těleso, pak $|\mathbb F|=p^n$ pro $p$ prvočíslo a $n\in \N$.

{\rm (3)} Libovolná dvě konečná komutativní tělesa o témže počtu prvků jsou izomorfní.
\end{theorem}

\begin{proof} (1) Díky \ref{11.6} existuje ireducibilní polynom $u\in\Z_p[x]$ stupně $n$. 
Definujme $\mathbb F_{p^n} = \Z_p[x]/u\Z_p[x]$. Potom z Poznámky~\ref{OIHI} a Faktu~\ref{teleso} plyne, že $\mathbb F_{p^n}$ je komutativní těleso.
Označíme-li $I = u\Z_p[x]$, v tomto tělese (pro $g,h\in\Z_p[x]$) platí $g+I = h+I$ právě tehdy, když $u$ dělí $g-h$; mj. tedy $g+I = (g\;\md u)+ I$. 
Jako zbytky po dělení $u$ figurují právě všechny polynomy nad $\Z_p$ stupně menšího než $n$, těch je $p^n$, což je následně i počet prvků $\mathbb F_{p^n}$.

(2) Mějme konečné těleso $\mathbb F$. Uvažujme cyklickou podgrupu $\langle 1\rangle$ grupy $\mathbb F(+,-,0)$. Ta musí být konečná, a tedy $\Z_p(+)\cong \langle 1\rangle(+)$ 
pro nějaké $p\in \N$. Uvažujme dále izomorfismus, který posílá prvek $k\in\Z_p$ na prvek $\underbrace{1+1+\dotsc +1}_{k\times}$ tělesa $\mathbb F$, a 
jak je v podobných případech zvykem, pro další úvahy ztotožníme prvky tělesa $\mathbb F$ tvaru $\underbrace{1+1+\dotsc +1}_{k\times}$, kde $0\leq k<p$, a prvky množiny $\Z_p$. Z grupy $\Z_p$ tímto ztotožněním uděláme podgrupu grupy $\mathbb F(+,-,0)$.
Jelikož z distributivity máme 
\[(\underbrace{1+1+\dotsc +1}_{k\times})(\underbrace{1+1+\dotsc +1}_{m\times})=\underbrace{1+1+\dotsc +1}_{km\times}=\underbrace{1+1+\dotsc +1}_{(km\;\md p)\times},
\]
tvoří $\Z_p$ dokonce podokruh tělesa $\mathbb F$.
Dále $p$ musí být prvočíslo, jinak by existovaly $0\neq k,m\in\Z_p$ tak, že $km=0$, což v žádném tělese (tedy ani v $\mathbb F$) není možné.

Nyní je již snadné si uvědomit, že $\mathbb F$ tvoří vektorový prostor nad svým podtělesem $\Z_p$, a položíme-li  $n:=\dim_{\Z_p}\mathbb F$, pak $|\mathbb F| = p^n$.

$(3)$ Ukážeme, že je-li $\mathbb F$ konečné komutativní těleso o $p^n$ prvcích, potom $\mathbb F\cong \mathbb F_{p^n}$ pro těleso $\mathbb F_{p^n}$ z části (1).
Tak jako v bodu (2) budeme předpokládat, že $\Z_p$ je přímo podtělesem tělesa $\mathbb F$ (nikoliv pouze izomorfní podtělesu generovanému prvkem 1).

Nejprve nahlédneme, že každý prvek tělesa $\mathbb F$ je kořenem polynomu $x^{p^n}-x\in\Z_p[x]$. To pro $0$ zřejmě platí a pro nenulové prvky to plyne aplikací Poznámky~\ref{2.6} na grupu $\mathbb F^*(.)$, která má $p^n-1$ prvků.
Z  \ref{11.6} navíc plyne, že ireducibilní polynom $u\in\Z_p[x]$ použitý ke konstrukci tělesa $\mathbb F_{p^n}$, dělí v $\Z_p[x]$ polynom $x^{p^n}-x$.
To ovšem znamená, že ho dělí i v jeho nadokruhu $\mathbb F[x]$. Máme tedy nějaký polynom $g$ takový, že $ug = x^{p^n}-x$. Dosadíme-li nyní libovolný prvek $a\in\mathbb F$, máme $u(a)g(a)= 0$, což znamená, že $a$ je kořen jednoho ze dvou těchto polynomů. Jelikož polynom $g$ má menší stupeň než $p^n$ (a tedy méně než $p^n$ kořenů), musí existovat nějaké $a\in \mathbb F$,
které je kořenem polynomu $u$.

Pro toto $a$ uvažujme dosazovací zobrazení $\Omega_a:\Z_p[x]\to\mathbb F$ definované vztahem $\Omega_a(h) = h(a)$. Snadno nahlédneme, že
$\Omega_a(h+k)=\Omega_a(h)+\Omega_a(k)$, $\Omega_a(h\cdot k)=\Omega_a(h)\cdot\Omega_a(k)$ a $\Omega_a(1)=\Omega_a(1)$, což znamená, že
jde o (takzvaný dosazovací) homomorfismus. Výše jsme dokázali, že $u\Z_p[x]\subseteq\Ker(\Omega_a)$, můžeme proto užít \ref{ob.o homomorfismu}, která nám dá (jediný) okruhový homomorfismus $\psi:\Z_p[x]/u\Z_p[x]\to\mathbb F$, pro nějž $\Omega_a = \psi\pi_{u\Z_p[x]}$. Jelikož $\Omega_a(1)=1\neq 0$, je $\psi$ nenulový homomorfismus. 
Víme, že $\Ker(\psi)$ musí být ideál tělesa $\mathbb F_{p^n}$, a tedy nutně $\Ker(\psi)$ je triviální (jednoprvkový) ideál 
(užíváme Větu~\ref{5.5}). To ovšem znamená, že $\psi$ je prosté, a tedy musí být i na, jelikož jde o zobrazení mezi dvěma stejně velkými konečnými množinami.
Tudíž $\psi$ je hledaný izomorfismus těles $\mathbb F_{p^n}$ a $\mathbb F$.
\end{proof}

\begin{prikl}\rm (1) Postupem důkazu bodu (1) Věty \ref{finfields} zkonstruujeme konečné těleso o $8=2^3$ prvcích.
Zvolme ireducibilní polynom $f=x^3+x+1$ (rozložitelnost polynomu stupně 3 implikuje, že má kořen, což zde neplatí) a dostaneme těleso $\mathbb F_{8} =\{a+bx+cx^2+f\Z_2[x]\mid a,b,c\in \Z_2\}=\{a+b\alpha+c\alpha^2|\ a,b,c\in \Z_2\}$, kde
$\alpha:= x+f\Z_2[x]$.

(2) Pokud bychom chtěli zkonstruovat těleso, které má právě $2^{13}$ prvků, potřebovali bychom najít nad tělesem $\Z_2$
ireducibilní polynom stupně $13$. Poznámka \ref{11.6} nám říká, že ho lze najít mezi děliteli polynomu $x^{2^{13}}-x$,
navíc poznamenejme, že není příliš těžké ověřit silnější tvrzení, že ireducibilní polynom $g\in\Z_p[x]$ stupně $k$ dělí 
polynom $x^{p^n}-x$, právě když $k/n$. Protože je $13$ prvočíslo, obsahuje ireducibilní rozklad polynomu $x^{2^{13}}-x$
právě všechny ireducibilní polynomy stupně $13$ a $1$. Zřejmě  právě
polynomy $x$ a $x+1$ jsou jediné dva ireducibilní polynomy stupně $1$ nad $\Z_2$, proto
snadnou úvahou o stupních zjistíme, že se polynom 
$\frac{x^{2^{13}}-x}{x(x+1)}=\sum_{i=0}^{2^{13}-2}x^i$ rozkládá právě na $\frac{2^{13}-2}{13}=630$ ireducibilních polynomů
stupně $13$. Ireducibilní polynom stupně stupně $13$ je tvaru $\sum_{i=0}^{13}a_ix^i$, kde $a_{13}=1$ 
a dále $a_0=1$, neboť $0$ není kořenem a $\sum_{i=0}^{13}a_i=1$, neboť ani $1$ není kořenem. To znamená, že při náhodné
volbě máme $630$ příznivých možností ze $2^{11}$, tedy více než třicetiprocentní pravděpodobnost úspěchu.
To, zda je náhodný polynom dělitel polynomu $x^{2^{13}}-x$ přitom můžeme otestovat (v tomto případě ještě)
rychlým algoritmem dělení se zbytkem.
\end{prikl}

 Wedderburnova věta říká, že všechna konečná tělesa jsou komutativní. Důkaz ale není nikterak triviální. V důkazu části (3) jsme využili komutativitu tělesa $\mathbb F$, abychom mohli argumentovat, že polynom $g$ nemá v $\mathbb F$ více kořenů, než je jeho stupeň; to ovšem nad nekomutativními tělesy neplatí! Stačí uvážit polynom $x^2+1$ nad tělesem kvaternionů. Ten má za kořeny $i,j,k,-i,-j,-k$.

\subsection{Podílová tělesa}

Následující tvrzení zobecňuje dobře známou konstrukci zlomků pro všechny obo\-ry integrity.
Jejím důsledkem je fakt, že každý obor integrity lze chápat jako podokruh nějakého tělesa
(konkrétně svého podílového tělesa).

Uvažujme obor $R(+,\cdot,-,0,1)$, a definujme algebru
$F(+,\cdot,-,\mathbf 0,\mathbf 1)$, kde $F= R \times (R\setminus\{0\})$ s operacemi:
\[
(a,b)\cdot (c,d)=(a\cdot c, b\cdot d),\ \  
(a,b)+ (c,d)=(a\cdot d + b\cdot c, b\cdot d),\ \  -(a,b)=(-a,b),\]
$\mathbf 0=(0,1)$ a $\mathbf 1=(1,1)$.
Na množině $F$ konečně definujme relaci $\sim$
předpisem $(a,b)\sim (c,d)\Leftrightarrow a\cdot d = b\cdot c$.


\begin{theorem}\label{fractions} Pro algebru  $F(+,\cdot,-,\mathbf 0,\mathbf 1)$ platí: 
\begin{enumerate}
\item[(1)] $F(+)$ a $F(\cdot)$ jsou komutativní monoidy,
\item[(2)] $\sim$ je kongruence na $F(+,\cdot,-,\mathbf 0,\mathbf 1)$ a
$(0,a)\sim \mathbf 0$ a $(a,a)\sim \mathbf 1$ pro každé 
$a \in R\setminus\{0\}$,
\item[(3)] $F/\sim(+,\cdot,-,[\mathbf 0],[\mathbf 1])$ je komutativní těleso,
\item[(4)] zobrazení $\sigma: R\to F/\sim$
dané předpisem $\sigma(r)= [(r,1)]_\sim$ je prostý okruhový homomorfismus.
\end{enumerate}
\end{theorem}
\begin{proof} Vezměme $(a,b),(c,d), (e,f)\in F$.

(1) Postupujeme zcela přímočaře podle definice. 
\[
(a,b)+((c,d)+(e,f))= (a,b)+((cf+de,df))= ((adf+b(cf+de),bdf)) = 
\]
\[
=((adf+bcf+bde,bdf)) = (((ad+bc)f+bde,bdf)) = ((a,b)+(c,d))+(e,f),
\]
\[
(a,b)+(c,d) = (ad+bc,bd) = (cb+ad,bd) = (c,d) + (a,b).
\]
Ověřili jsme, že je operace $+$ asociativní a komutativní. Uvážíme-li, že $(a,b)+(0,1)=(a,b)$, máme dokázáno,
že $F(+)$ je komutativní monoid. Totéž provedeme pro násobení:
\[
(a,b)\cdot((c,d)\cdot(e,f))= (a,b)\cdot((ce,df))= (ace,bdf)) = ((a,b)\cdot(c,d))\cdot(e,f),
\]
dále $(a,b)\cdot(c,d) =  (c,d) \cdot (a,b)$ a $(a,b)\cdot(1,1)=(a,b)$, proto i $F(\cdot)$
je komutativní monoid.

(2) Předně uvažme, že je relace $\sim$ reflexivní a symetrická a předpokládejme, že
$(a,b)\sim(c,d)$ a $(c,d)\sim(e,f)$, tedy $ad=bc$ a $cf=de$. Potom $adf=bcf=bde$, a proto
$(af-be)d=0$. Jelikož $d\ne 0$, dostáváme z definice oboru integrity, že $af-be=0$, a tudíž
$(a,b)\sim(e,f)$. Díky pozorování Příkladu 3.3 z minulého semestru 
zbývá ověřit slučitelnost $\sim$ s operacemi $+$, $\cdot$ a $-$.
Předpokládejme, že $(a_i,b_i)\sim(c_i,d_i)$  tedy $a_id_i=c_ib_i$ pro $i=1,2$.
Proto $ (a_1b_2 + b_1a_2)d_1d_2 = a_1d_1\cdot b_2d_2 + a_2d_2\cdot b_1d_1
= c_1b_1\cdot b_2d_2 + c_2b_2\cdot b_1d_1 = (c_1d_2 + d_1c_2)b_1b_2$, tedy 
$(a_1,b_1)+(a_2,b_2)\sim(c_1,d_1)+(c_2,d_2)$. Dále $a_1a_2d_1d_2=c_1c_2b_1b_2$, tudíž 
$(a_1,b_1)\cdot(a_2,b_2)\sim(c_1,d_1)\cdot(c_2,d_2)$ a konečně $(-a_1,b_1)\sim(-c_1,d_1)$ podle 
5.2(2). Vztahy $(0,a)\sim \mathbf 0$ a $(a,a)\sim \mathbf 1$ plynou okamžitě z definice $\sim$.

(3) Díky (1), (2) a 3.10 už víme, že $F/\sim(+)$ a $F/\sim(\cdot)$
jsou komutativní monoidy. Zbývá tedy dokázat existenci opačných prvků monoidu $F/\sim(+)$
a distributivitu. Označme $\frac{a}{b}$ rozkladové třídy $[(a,b)]_\sim$. Všimněme si,
že $\frac{ad}{bd}=\frac{ac}{bc}$ pro každé nenulové $b,d\in R$, protože $(ad,bd)\sim(ac,bc)$.
Nyní snadno spočítáme, že 
\[
\frac{a}{b}+\frac{-a}{b}=\frac{a+(-a)}{bb}=\frac{0}{bb}=\mathbf 0,
\]
\[
\frac{a}{b}\cdot\frac{c}{d}+\frac{a}{b}\cdot\frac{e}{f} = 
\frac{acbf+bdae}{bdbf} = \frac{acf+ade}{bdf} = \frac{a}{b}\cdot \frac{cf+de}{df} =
\frac{a}{b}\cdot(\frac{c}{d}+\frac{e}{f}).
\]
Konečně, zvolíme-li $\frac{a}{b}\ne \mathbf 0$, pak $(a,b)\not\sim(0,1)$, tedy $a\ne 0$,
a proto $\frac{b}{a}\in F$ a $\frac{a}{b}\cdot \frac{b}{a}=\mathbf 1$. Tím jsme
dokázali, že každý nenulový prvek $F$ je invertibilní, a proto je 
$F/\sim$ komutativní těleso.

(4) Okamžitě vidíme, že je $\frac{a}{1}\cdot\frac{b}{1}=\frac{a\cdot b}{1}$, 
$\frac{a}{1}+\frac{b}{1}=\frac{a+b}{1}$ a $\sigma(1)=\mathbf 1$, proto je
$\sigma$ homomorfismus. Konečně, je-li $\sigma(a)=\sigma(b)$, pak $a=b$, tedy jde o
prostý homomorfismus.
\end{proof}

\begin{definice} Komutativní těleso  $F/\sim$ budeme nazývat {\it podílovým tělesem} 
oboru $R$ a jeho prvky budeme značit $\frac{a}{b}=[(a,b)]_\sim$.
\end{definice}

\begin{prikl}\rm (1) Těleso racionálních čísel $\Q(+,\cdot,-,0,1)$
je podílovým tělesem oboru celých čísel $\Z(+,\cdot,-,0,1)$.

(2) Těleso racionálních lomených funkcí je podílovým tělesem oboru reálných polynomů $\mathbb R[x](+,\cdot,-,0,1)$.
%(3) Podílové těleso oboru polynomů $\Z_2[x](+,\cdot,-,0,1)$ je příkladem nekonečného tělesa charakteristiky 2.
\end{prikl}





\vskip 1cm

\section{Svazy a Booleovy algebry}

Závěrečnou kapitoly kurzu věnujeme algebraickému popisu uspořádaných mno\-žin.
Nejprve si rozmyslíme, že jistou třídu uspořádaných množin lze 
nahlížet jako algebry s dvojicí binárních operací.
Algebraický pohled nám umožní pracovat se všemi standardními univerzálně algebraickými pojmy. 
Na závěr se budeme zabývat pojmem obecné Booleovy algebry jako distributivního svazu s komplementy a ukaážeme, že 
konečné Booleovy algebry nejsou (až na izomorfismus) ničím jiným než systémy všech podmnožin nějaké množiny.


Připomeňme, že relaci $\le$ na množině $M$ se říká {\it uspořádání}, 
je-li reflexivní a tranzitivní a splňuje-li podmínku $a\le b,
\ b\le a \Rightarrow a = b$ pro každé $a,b\in M$ (tj. jde o slabě antisymetrickou relaci).
Dvojice $(M,\le)$ se obvykle nazývá uspořádaná množina.

\begin{definice} Nechť $\le$ je uspořádání na množině $M$ a $A\subseteq M$.
Řekneme, že $m\in A$ je {\it nejmenší} (resp. {\it největší}) prvek množiny
$A$, jestliže $m\le a$ (resp. $a\le m$) pro všechna $a\in A$.
{\it Supremem} (resp. {\it infimem}) množiny $A$ budeme rozumět nejmenší prvek
množiny $\{n\in M|\ \forall a\in A:\ a\le n  \}$ (resp. největší prvek
množiny $\{n\in M|\ \forall a\in A:\ n\le a  \}$), supremum značíme $\sup_\le$
a infimum $\inf_\le$. Dvojici $(M,\le)$  budeme říkat {\it svaz}, pokud pro každé dva prvky 
$a, b\in A$ existuje supremum a infimum množiny $\{a, b\}$. Svaz $(M,\le)$ je úplným svazem,
existuje-li supremum a infimum každé podmnožiny množiny $M$.
\end{definice}



\begin{prikl}\label{4.1}\rm Připomeňme známé příklady uspořádání a svazů:
\begin{enumerate}
\item[(1)] Relace $/$ dělitelnosti  na množině všech přirozených čísel $\mathbb{N}$ (tj. daná podmínkou $a/b \equiv \exists c: b=a\cdot c$) je uspořádání na $\mathbb{N}$, navíc $\sup_/(n,m) = \nsn(n,m)$ a 
$\inf_/(a,b) = \NSD(n,m)$, proto je $(\mathbb{N}, /)$ svaz.
\item[(2)] Přirozené uspořádání $\le$ indukuje na množině všech celých (reálných, racionálních) čísel $\mathbb{Z}$ 
($\mathbb{R}$, $\mathbb{Q}$) strukturu (dokonce lineárně uspořádaného) svazu, kde $\sup_\le (a,b) = \max(a,b)$ a 
$\inf_\le (a,b) = \min(a,b)$.
\item[(3)] Inkluze tvoří na množině všech podmnožin $\mathcal{P}(X)$ množiny $X$ uspořádání a $(\mathcal{P}(X), \subseteq)$ úplný svaz
kde $sup_\subseteq(\mathcal B) = \bigcup \mathcal B$ a 
$inf_\subseteq(\mathcal B) = \bigcap \mathcal B$ pro každou podmnožinu
$\mathcal B\subseteq\mathcal{P}(X)$.
\item[(4)] Je-li $\mathcal{C}$ množina všech podalgeber nebo všech
kongruencí na nějaké algebře, ukážeme, že $(\mathcal{C},\subset)$ tvoří úplný svaz, kde
$\sup_\subseteq(\mathcal{B}) = \bigcap\{C\in\mathcal{C}|\bigcup \mathcal{B}\subseteq C\}$ 
a $\inf_\subseteq(\mathcal{B}) = \bigcap \mathcal{B}$ pro každé $\mathcal{B}\subseteq\mathcal{C}$ .

$\subseteq$ je uspořádání a 
$\bigcap \mathcal{B}$ je zjevně infimem.
Protože je množina $\mathcal{C}$ dle \ref{US} uzavřená na průniky, vidíme, že 
$\bigcap\{X\in\mathcal{C}|\bigcup \mathcal{B}\subseteq X\}$ tvoří nejmenší prvek 
$\mathcal{C}$ obsahujícím všechna $B\in \mathcal{B}$, což je podle definice
právě supremum vzhledem k inkluzi.
\item[(5)] $\id$ je na libovolné neprázdné množině $M$ uspořádání, ovšem pro $|M|>1$ se jistě nejedná o svaz.
\end{enumerate}
\end{prikl}

Je-li $(M,\le)$ svaz, budeme pro každé dva prvky
$m,n\in M$ značit $m\lor n = \sup_\le(m,n)$ a 
$m\land n = \inf_\le(m,n)$. Zavedené binární  operace $\lor$ a $\land$ nazveme
{\it spojení} a {\it průsek}.


Konečné uspořádané množiny je často výhodné znázornit Hasseovým diagramem,
připomeňme jeho definici:

Je-li $(M,\le)$ je uspořádaná množina a $a,b,c \in M$, řekneme, že prvek $b$
{\it pokrývá} prvek $a$ (píšeme $a <\cdot\ b$), jestliže  $a\le b$, $a$ není $b$ a 
$a\le c\le b \Rightarrow c=a$ nebo $c=b$.
 
{\it Hasseovým diagramem} uspořádané množiny $(M,\le)$ rozumíme orientovaný graf, jehož vrcholy tvoří
prvky množiny M a $a$ je s $b$ spojen takovou hranou, že $b$ se nachází výše než
$a$, právě když  $b$ pokrývá $a$.

\begin{prikl}\label{HD}\rm Uveďme uspořádané množiny popsané Hasseovými diagramy:
\begin{enumerate}
\item[(1)] Uvažujme svazy $(S_1,\le)$ a $(S_2,\le)$, kde $S_1=\{0,1,a,b\}$ je dán  relacemi:$0<\cdot\ a <\cdot\ 1$ a $S_2=\{\mathbf 0,\mathbf 1,\mathbf A,\mathbf B\}$ popisuje $0<\cdot\ b <\cdot\ 1$ a $\mathbf 0<\cdot\ \mathbf A<\cdot\ \mathbf B <\cdot\ \mathbf1$. Pak je jsou jejich 
Hasseovy diagramy následující:

\tikz {
\node (0) at (1,5)  {$S_1:$};
\node (1) at (3,2)  {$0$};
\node (2) at (2,3.5)  {$a$};
\node (3) at (4,3.5) {$b$};
\node (4) at (3,5)  {$1$};
\node (s) at (6,5)  {$S_2:$};
\node (a) at (7,2)  {$\mathbf 0$};
\node (b) at (7,3)  {$\mathbf A$};
\node (c) at (7,4) {$\mathbf B$};
\node (d) at (7,5)  {$\mathbf 1$};
\node (e) at (0,5)  {};
\draw (a) edge[-] (b) (b) edge[-] (c) (c) edge[-] (d)
(1) edge[-] (2) edge[-] (3) (2) edge[-] (4) (3) edge[-]  (4);
}
     
\item[(2)] Žádný z následujících Hasseových diagramů uspořádaných množin neurčuje svaz, protože pro prvky $x$ a $y$ neexistuje infimum:

\tikz {
\node (2) at (2,3)  {$x$};
\node (3) at (4,3) {$y$};
\node (4) at (3,4.5)  {$\bullet$};
\node (a) at (7,2)  {$\bullet$};
\node (b1) at (6,3)  {$\bullet$};
\node (b2) at (8,3)  {$\bullet$};
\node (c1) at (6,4)  {$x$};
\node (c2) at (8,4)  {$y$};
\node (d) at (7,5)  {$\bullet$};
\node (e) at (0,5)  {};
\draw (a) edge[-] (b1) edge[-] (b2) (b1) edge[-] (c1) edge[-] (c2) 
(b2) edge[-] (c1) edge[-] (c2) (c1) edge[-] (d) (c2) edge[-] (d)
(2) edge[-] (4) (3) edge[-]  (4);
}
\end{enumerate}
\end{prikl}


\begin{theorem}\label{4.3} 
{\rm (1)}  Je-li $(M,\le)$ svaz, pak pro všechna $a,b,c\in M$ platí:
\begin{enumerate}
\item[(S1)] $a\lor b = b\lor a$, $a\land b = b\land a$,
\item[(S2)] $a\lor a = a = a\land a$,
\item[(S3)] $a\lor (b\lor c) = (a\lor b)\lor c$, $a\land (b\land c) = (a\land b)\land c$,
\item[(S4)] $a\lor (b\land a) = a = a\land (b\lor a)$.
\end{enumerate}

{\rm (2)} Nechť $M(\land, \lor)$ je algebra s dvěma binárními operacemi, které splňují
podmín\-ky {\rm (S1) -- (S4)} a definujme na $M$ relaci $\le$ předpisem: 
$a\le b \Leftrightarrow b = a\lor b$.
Pak platí $a\le b \Leftrightarrow a = a\land b$, dále $(M,\le)$ je svaz a
$\sup_\le(a,b) = a\lor b$ a $\inf_\le(a,b) = a\land b$.
\end{theorem}
\begin{proof}
(1)  Vlastnosti (S1) a (S2) jsou okamžitým důsledkem definice $\land$ a $\lor$.

(S3) Položme $d=a\lor (b\lor c)$. Dokážeme, že je $d$ supremem množiny $\{a,b,c\}$.
Podle definice $\lor$ je $a\le d$ a $b,c\le b\lor c\le d$, tedy $d$ je horní odhad
množiny $\{a,b,c\}$. Zvolme nějaké $e$, pro něž $a,b,c\le e$. Pak
$(b\lor c)\le e$, protože je $e$ horní odhad množiny $\{b,c\}$ a $(b\lor c)$ je supremem
této množiny. Stejným argumentem dostaneme $a\lor(b\lor c)\le e$, tedy 
$a\lor(b\lor c)=\sup_\le(\{a,b,c\})=c\lor(a\lor b)=(a\lor b)\lor c$ díky (S1).
Důkaz druhé podmínky je symetrický.

(S4) Protože $b\land a\le a$ a $a\le a$, máme $a\lor(b\land a)\le a$. Naopak
$a\le a\lor(b\land a)$, tedy ze slabé antisymetrie plyne, že $a= a\lor(b\land a)$.
I tentokrát pro ověření druhé podmínky stačí zaměnit spojení průsekem a relaci $\le$ relací $\ge$.

(2) Nejprve ukážeme, že je $\le$ uspořádání. Protože $a=a\lor a$ díky (S2),
máme podle definice $a\le a$. Vezmeme-li $a\le b$ a $b\le c$, tj.
$b=a\lor b$, $c=b\lor c$, pak $c=(a\lor b)\lor c=a\lor (b\lor c)=a\lor c$
díky (S3), tedy $a\le c$. Konečně platí-li, že $a\le b$ a $b\le a$, dostáváme
z (S1), že $b=a\lor b=b\lor a=a$.

Nyní ověříme, že $b = a\lor b \Leftrightarrow a = a\land b$.
Za symetrie podmínek pro $\land$ a $\lor$ plyne, že stačí abychom ověřili
jen jednu implikaci. Nechť například $b = a\lor b$. Potom 
$a\land b = a\land (a\lor b) =a\land (b\lor a)=a$ podle (S1) a (S4).
Vidíme, že je definice $\le$ symetricky formulovatelná pomocí podmínky
$a\le b \Leftrightarrow a = a\land b$.

Zbývá dokázat, že $\sup_\le(a,b) = a\lor b$ (tvrzení pro $\land$ se dokáže
symetricky). Předně $a\lor(a\lor b)=(a\lor a)\lor b=a\lor b$ díky (S3) a (S2)
a $b\lor(a\lor b)=(a\lor b)\lor b = a\lor (b\lor b)=a\lor b$ díky (S1), (S3) a (S2),
tudíž $a,b\le(a\lor b)$. Vezmeme-li prvek $c$, pro který $a,b\le c$, pak
$c=a\lor c$ a $c=b\lor c$, proto $c=a\lor (b\lor c)=(a\lor b)\lor c$ podle (S3).
Tím jsme ověřili, že $(a\lor b)\le c$, což znamená, že $\sup_\le(a,b) = a\lor b$.
\end{proof}

Dokázané tvrzení poskytuje dva ekvivalentní pohledy na svaz: buď jako na uspořádanou množinu $(M,\le)$
se supremy a infimy nebo algebru $M(\land, \lor)$ splňující čtveřici axiomů (S1)--(S4). V následujícím textu budeme v závislosti na kontextu pracovat s oběma pohledy na svaz.

\begin{prikl}\label{4.5} \rm U příkladů svazů uvedených v \ref{4.1} 
máme tedy dva způsoby jak na svaz
nahlížet:
\begin{enumerate}
\item[(1)] $(\mathbf{N}, /)$ odpovídá algebře $\mathbf{N}(\NSD, \nsn)$,
\item[(2)] $(\Z,\le)$ (respektive $(\mathbf{R},\le)$, $(\mathbf{Q},\le)$)
odpovídá algebře $\Z(\min, \max)$ (respektive $\mathbf{R}(\min, \max)$, $\mathbf{Q}(\min, \max)$),
\item[(3)] $(\mathcal{P}(X), \subseteq)$ odpovídá algebře $\mathcal{P}(X)(\cap, \cup)$.
\end{enumerate}
\end{prikl}






%\begin{theorem}\label{4.6} Je-li $\mathcal{C}$ množina všech podalgeber nebo všech kongruencí na nějaké algebře, pak $(\mathcal{C},\subset)$ tvoří úplný svaz, kde $\sup_\subseteq(\mathcal{B}) = \bigcap\{C\in\mathcal{C}|\bigcup \mathcal{B}\subseteq C\}$  a $\inf_\subseteq(\mathcal{B}) = \bigcap \mathcal{B}$ pro každé $\mathcal{B}\subseteq\mathcal{C}$ . \end{theorem}
%\begin{proof} $\subseteq$ je uspořádání a $\bigcap \mathcal{B}$ je zjevně infimem. Protože je množina $\mathcal{C}$ dle \ref{US} uzavřená na průniky, vidíme, že $\bigcap\{X\in\mathcal{C}|\bigcup \mathcal{B}\subseteq X\}$ tvoří nejmenší prvkem $\mathcal{C}$ obsahujícím všechna $B\in \mathcal{B}$, což je podle definice právě supremum vzhledem k inkluzi. \end{proof}

%\begin{pozn} Nechť $M(\land, \lor)$ je svaz, $a,b,c\in M$ a $a\le c$. Potom $a\lor(b\land c)\le (a\lor b)\land c$. \end{pozn} 
%\begin{proof} Protože $a\le a\lor b$ a $b\land c\le b\le a\lor b$, máme z definice suprema $a\lor(b\land c)\le a\lor b$. Podobně $a\le a\lor c$ a $b\land c\le c$, proto $a\lor(b\land c)\le c$. Využijeme-li nyní definici infima množiny $\{a\lor b, c\}$, pak dostaneme $a\lor(b\land c)\le (a\lor b)\land c$. \end{proof}






%\vskip 1cm

%\section{Svazy podmnožin a kongruencí}


%V závěrečné kapitole  se budeme věnovat izomorfnímu popisu dvou zajímavých tříd svazů: konečným Booleovým algebrám a svazu kongruencí grupy a okruhu. K tomu účelu zavedeme pojmy  obecné Booleovy algebry jako distributivního svazu s komplementy a uzávěrového systému. Izomorfismu svazů tak využijeme pro důkaz tvrzení, že konečné Booleovy algebry nejsou (až na izomorfismus) ničím jiným než systémy všech podmnožin nějaké množiny, a pro lepší porozumění vztahu kongruencí a normálních podgrup pro grupy a vztahu kongruencí a ideálů pro okruhy.

Nyní popíšeme izomorfismy svazů chápaných jako algebry pomocí poj\-mu monotónní zobrazení.

\begin{definice} Nechť $f: A\to B$ je zobrazení a $(A,\le)$ a $(B,\le)$ 
jsou svazy. Řekneme, že je $f$ {\it homomorfismus} ({\it izomorfismus})
jde-li o homomorfismus (izomorfismus) algeber $A(\land, \lor)$ a $B(\land, \lor)$ a
$f$ nazveme {\it monotónním} zobrazením, platí-li implikace
$a_1\le a_2 \Rightarrow f(a_1)\le f(a_2)$.
{\it Podsvazem} svazu $A(\land, \lor)$ budeme rozumět podalgebru algebry $A(\land, \lor)$.
\end{definice}


\begin{pozn}\label{4.12} Homomorfismus svazů je monotónní zobrazení.
\end{pozn} 
\begin{proof} Je-li $f: A\to B$ homomorfismus svazů a $a_1\le a_2\in A$,
pak $a_2=a_1\lor a_2$. Proto $f(a_2)=f(a_1\lor a_2)=f(a_1)\lor f(a_2)$
a tedy $f(a_1)\le f(a_2)$.
\end{proof}


\begin{theorem}\label{4.14} Bijekce svazů $f$ je izomorfismus, právě když jsou $f$ i $f^{-1}$ 
monotónní zobrazení.
\end{theorem} 
\begin{proof} Díky \ref{4.12} stačí dokázat zpětnou implikaci.
Ověříme slučitelnost $f$ například s $\lor$. Mějme $f: A\to B$ takovou bijekci
svazů, že $f$ i $f^{-1}$ jsou monotónní, a zvolme $a,b\in A$. Protože
$a,b\le a\lor b$, je $f(a),f(b)\le f(a\lor b)$, tudíž $f(a)\lor f(b)\le f(a\lor b)$.
Podobně $f(a),f(b)\le f(a)\lor f(b)$, proto $a,b\le f^{-1}(f(a)\lor f(b))$ a
$a\lor b\le f^{-1}(f(a)\lor f(b))$. Použijeme-li na poslední vztah znovu monotonii
$f$, dostaneme $f(a\lor b)\le f(a)\lor f(b)$. Ze slabé antisymetrie $\le$, potom
plyne, že $f(a\lor b)= f(a)\lor f(b)$.
\end{proof}




\begin{prikl}\rm Pro svazy z Příkladu \ref{HD}(1)
uvažujme zobrazení $f(0)= \mathbf 0$, $f(1)= \mathbf 1$, $f(a)= \mathbf A$, $f(b)= \mathbf B$:

\tikz {
\node (1) at (4,2)  {$0$};
\node (2) at (3,3)  {$a$};
\node (3) at (5,4) {$b$};
\node (4) at (4,5)  {$1$};
\node (a) at (7,2)  {$\mathbf 0$};
\node (b) at (7,3)  {$\mathbf A$};
\node (c) at (7,4) {$\mathbf B$};
\node (d) at (7,5)  {$\mathbf 1$};
\node (e) at (0,5)  {};
\draw (a) edge[-] (b) (b) edge[-] (c) (c) edge[-] (d)
(1) edge[-] (2) edge[-] (3) (2) edge[-] (4) (3) edge[-]  (4)
(2) edge[->]  (b) (3) edge[->]  (c) (1) edge[->]  (a) (4) edge[->]  (d) ;
}

Zřejmě jde o monotónní zobrazení, ale nejedná se o homomorfismus svazů, protože $f(a\land b)=f(0) = \mathbf 0\ne \mathbf A = f(a)\land f(b)$.
\end{prikl}







%\subsection{Booleovy algebry}

Nyní budeme zkoumat svazy splňující některé další přirozené identity.

\begin{definice} Uvažujme svaz $S(\land, \lor)$ (chápaný jako algebra).

Řekneme, že je $S(\land, \lor)$
%{\it modulární}, jestliže pro každá taková $a,b,c \in S$, že $a\le c$, platí rovnost $a\lor(b\land c) = (a\lor b)\land c$ a svaz je 
{\it distributivní} svaz,
platí-li pro každé $a, b, c\in S$ rovnost $a\lor(b\land c)= (a\lor b)\land (a\lor c)$.

Nechť svaz $S(\land, \lor)$ obsahuje nejmenší prvek $\mathbf 0$ a největší prvek $\mathbf 1$
(vzhledem k uspořádání $\le$ danému podmínkou $a\le b \Leftrightarrow b = a\lor b$).
Prvek $a\in S$ nazveme {\it atomem} (resp. 
{\it koatomem}), jestliže $a$ pokrývá $\mathbf 0$ (resp. $\mathbf 1$ pokrývá $a$).
{\it Komplementem} prvku $a\in S$ nazveme takový prvek $a'\in S$, že $a\lor a' = \mathbf 1$
a $a\land a' = \mathbf 0$.
\end{definice}

%\begin{pozn} Každý distributivní svaz je modulární. \end{pozn}
%\begin{proof} Předpokládejme, že $a\le c$, tj. $(a\lor c)=c$. Potom nám distributivita dává rovnost $a\lor(b\land c)= (a\lor b)\land(a\lor c)=(a\lor b)\land c$. \end{proof}



\begin{pozn}\label{4.15} {\rm (1)} Svaz $S(\land, \lor)$ je distributivní, právě když
pro každé $a, b, c\in S$ platí, že $a\land(b\lor c)= (a\land b)\lor (a\land c)$,
tedy svaz $S(\land, \lor)$ je distributivní, právě když
je opačný svaz $S(\lor, \land)$ distributivní.

{\rm (2)} Každý prvek distributivního svazu má nejvýše jeden komplement.
\end{pozn}

\begin{proof} (1) Ze symetrie vlastností operací plyne, že stačí dokázat pouze jednu
implikaci. Nechť je svaz distributivní. Budeme s využitím definice
distributivity a \ref{4.3} upravovat:
$(a\land b)\lor (a\land c) = ((a\land b)\lor a)\land ((a\land b)\lor c)
= a\land (a\lor c)\land (b\lor c)
=a\land (b\lor c)$, kde druhá  rovnost plyne z (S4) a třetí rovnost plyne z (S1) a (S4).

(2) Nechť $a\lor b_i = \mathbf 1$ a $a\land b_i = \mathbf 0$
pro $i=1,2$. Pak $b_i=b_i\land1=b_i\land(a\lor b_j)=(b_i\land a)\lor (b_i\land b_j) =
\mathbf 0\lor (b_i\land b_j)=b_i\land b_j$, tedy $b_i\le b_j$ pro všechna
$i,j\in\{1,2\}$, což znamená, že $b_1= b_2$. 
\end{proof}



%\begin{theorem} Svaz je modulární právě tehdy, když neobsahuje podsvaz izomorfní svazu $\mathcal N_5$. \end{theorem}

%Obdobné tvrzení lze (obdobnými prostředky) dokázat i pro distributivní svazy: svaz je distributivní, právě když neobsahuje ani podsvaz izomorfní svazu $\mathcal N_5$ , ani podsvaz izomorfní svazu $\mathcal M_5$.

%Příští semestr dokážeme, že je svaz modulární, právě když neobsahuje podsvaz izomorfní svazu $\mathcal N_5$, a že je distributivní, právě když neobsahuje ani podsvaz izomorfní $\mathcal N_5$, ani podsvaz izomorfní $\mathcal M_5$.






\begin{definice} {\it Booleovou algebrou} nazveme takovou algebru 
$S(\lor, \land, \mathbf 0, \mathbf 1,\ ')$, že $S(\land, \lor)$ je distributivní
svaz s největším prvkem $\mathbf 1$ a nejmenším prvkem $\mathbf 0$
a unární operace~$'$ přiřadí každému prvku jeho komplement.
{\it Homomorfismem} ({\it izomorfismem}) Booleových algeber rozumíme homomorfismus (izomorfismus)
algeber v obvyklém smyslu.
\end{definice}

\begin{prikl}\rm 
Nechť $\mathcal{P}(X)$ je množina všech podmnožin množiny $X$
a pro každou podmnožinu $Y\subseteq X$ definujme $Y'=X\setminus Y$.
Pak je svaz $\mathcal{P}(X)(\cap, \cup)$ distributivní a $\mathcal{P}(X)(\cup, \cap, \emptyset, X,\ ')$ je Booleova algebra.
\begin{comment}

(2) Svazy $\mathcal M_5=\{0,1,u,v,w\}$ (říká se mu obvykle {\it diamant}) a $\mathcal N_5=\{0,1,a,b,c\}$ (tzv. {\it pentagon})
dané Hasseovými diagramy

\tikz {
\node (0) at (1,5)  {$\mathcal M_5:$};
\node (1) at (3,2)  {$0$};
\node (2) at (1.5,3.5)  {$u$};
\node (3) at (3,3.5) {$v$};
\node (5) at (4.5,3.5) {$w$};
\node (4) at (3,5)  {$1$};
\node (s) at (6,5)  {$\mathcal N_5:$};
\node (a) at (8,2)  {$0$};
\node (b) at (9.5,3)  {$b$};
\node (c) at (9.5,4) {$c$};
\node (d) at (8,5)  {$1$};
\node (f) at (6.5,3.5)  {$a$};
\node (e) at (0,5)  {};
\draw (a) edge[-] (b) (b) edge[-] (c) (c) edge[-] (d) (a) edge[-] (f) (f) edge[-] (d)
(1) edge[-] (2) edge[-] (3) (1) edge[-] (5) (5) edge[-] (4) (2) edge[-] (4) (3) edge[-]  (4);
}

nejsou distributivní, protože 
\[
u\land (v\lor w)=u\land 1 = u \ne 0 =0\land 0 =  (u\land v)\lor (u\lor w),\]
\[
a\land (b\lor c)=a\land 1 = c \ne 0 =0\land 0 =  (a\land b)\lor (a\lor c).\]

Navíc si všimněme, že prvek $u$ ve svazu $\mathcal M_5$ a prvek 
$a$ ve svazu $\mathcal M_5$ nají dva různé komplementy.

%(3) Svaz $(N_5,\le)$, kde $N_5=\{0,1,a,b,c\}$, daný relacemi: $0<\cdot\ a <\cdot\ c <\cdot\ 1$, $0<\cdot\ b <\cdot\ 1$ (tzv. pentagon, $\mathcal N_5$) není modulární, protože $a\le c$ a $a\lor(b\land c)= a \ne c =(a\lor b)\land c$.
%(4) Množina všech podprostorů vektorového prostoru  tvoří spolu s inkluzí modulární svaz.
\end{comment}
\end{prikl}


\begin{pozn} Nechť $S(\lor, \land, \mathbf 0, \mathbf 1,\ ')$ je Booleova algebra.
Pak pro každé $a, b \in S$ platí:
\begin{enumerate}
\item[(1)] $(a')'=a$, 
\item[(2)] $(\mathbf 1)'= \mathbf 0$ a $(\mathbf 0)'= \mathbf 1$,
\item[(3)] $(a\lor b)' = a'\land b'$, $(a\land b)' = a'\lor b'$.
\end{enumerate}
\end{pozn}
\begin{proof} (1) a (2) plyne přímo z definice a \ref{4.15}(2).

(3) $(a\lor b) \land (a'\land b') = (a \land a'\land b') \lor  (b\land a'\land b') =
\mathbf 0\lor \mathbf 0 = \mathbf 0$ a podobně
$(a\lor b) \lor (a'\land b') = (a\lor b\lor a') \land  (a\lor b\lor b') = \mathbf 1\lor \mathbf 1 = \mathbf 1$.

Důkaz druhé rovnosti je symetrický.
\end{proof}

\begin{theorem}\label{BA} Buď $S(\lor, \land, \mathbf 0, \mathbf 1,\ ')$ konečná Booleova algebra
a $A$ buď množina všech atomů svazu $S$. Potom zobrazení
$\phi: \mathcal P(A)\to S$ dané předpisem  $\phi(B)=\sup B$
je izomorfismus Booleových algeber $S(\lor, \land, \mathbf 0, \mathbf 1,\ ')$
a $P(A)(\cup, \cap, \emptyset, A,\ ')$.
\end{theorem}
\begin{proof} Pro každé $M=\{m_1,\dots, m_n\}\subseteq S$ značme $\bigwedge M=m_1\land m_2\land\dots\land m_n$ a $\bigvee M=m_1\lor m_2\lor\dots\lor m_n$,
dále $\bigwedge \emptyset=\mathbf 1$ a $\bigvee \emptyset=\mathbf 0$

Definujme nejprve zobrazení $\psi: S\to \mathcal P(A)$ předpisem
$\psi(s)=\{a\in A|\ a\le s\}$. Okamžitě vidíme, že zobrazení $\phi$ i $\psi$ jsou monotónní
vzhledem k inkluzi a $\phi(\emptyset)=\mathbf 0$. Ukážeme-li navíc, že je $\phi$ bijekce slučitelná
s průsekem a spojením, pak nutně $\phi(A)=\mathbf 1$ a $\phi(B')=\phi(B)'$ pro každé
$B\in\mathcal P(A)$. Podle \ref{4.14} tedy zbývá ověřit, že $\phi\circ\psi=\Id_{S}$ i 
$\psi\circ\phi=\Id_{\mathcal P(A)}$,
tedy že $\phi$ je bijekce a $\phi^{-1}=\psi$.

Položme $t=\phi\psi(s)=\bigvee\{a\in A|\ a\le s\}$. Potom $t=\bigvee\{a\in A|\ a\le s\}\le s$.
Všimněme si, že díky distributivitě $s=s\land\mathbf 1=s\land(t\lor t')=(s\land t)\lor(s\land t')=t\lor(s\land t')$.
Předpokládáme-li, že $t\ne s$, pak z předchozího vidíme, že $(s\land t')\ne\mathbf 0$, a díky konečnosti
$S$ najdeme nějaký atom $a_0$, který leží pod prvkem $s\land t'$, tedy $a\le t'$ a $a\in\psi(s)$, a proto 
$a\le t$. Zjistili jsme, že $a\le t\land t' = \mathbf 0$, což je spor, tudíž $s=t$.

Nyní položme $C=\psi\phi(B)=\{a\in A|\ a\le \bigvee B\}$. Vezmeme-li $b\in B$, pak $b\le\bigvee B$, a proto
$b\in C$, čímž jsme ověřili inkluzi $B\subseteq C$. Zvolme tedy $c\in C$ a uvažme,
že $\mathbf 0\ne c = c\land \bigvee B = \bigvee\{c\land b|\ b\in B\}$ díky distributivitě a konečnosti $B$.
To ovšem znamená, že existuje $b\in B$, pro něž $c\land b\ne\mathbf 0$. Protože jsou oba prvky $b$ a $c$
atomy, máme $b=c$, čímž jsme dokázali, že $B= C$.
\end{proof}


Nyní je snadné uvědomit si, že je-li $S(\lor, \land, \mathbf 0, \mathbf 1,\ ')$ Booleova algebra o $64=2^6$ prvcích,
pak je podle předchozí věty izomorfní Booleově algebře $P(X)(\cup, \cap, \emptyset, ,\ ')$ pro $X=\{1,2,3,4,5,6\}$.

Z téhož důvodu neexistuje žádná patnáctiprvková Booleova algebra, protože podle Věty~\ref{BA} musí být každá Booleova algebra
izomorfní potenční Booleově algebře, tedy musí mít $2^n$ prvků, kde $n$ je počet atomů.

\begin{comment}

% 2018/19 NEBUDE

\subsection{Svazy kongruencí}

\begin{definice} Nechť je $A$ množina a $\mathcal{C}\subseteq\mathcal P(A)$ je nějaký systém podmnožin množiny A. Řekneme, že $\mathcal{C}$ je   {\it uzávěrovým systémem nad $A$}, pokud
\begin{enumerate} \item[(1)] $A\in\mathcal{C}$, \item[(2)] pro každý podsystém $\{B_i|\ i\in I\}\subseteq \mathcal{C}$, je $\bigcap\{B_i|\ i\in I\}\in \mathcal{C}$.
\end{enumerate}\end{definice}

Všimněme si, že každý uzávěrový systém tvoří úplný svaz:

\begin{pozn}\label{4.6} {\rm (1)} Je-li $\mathcal{C}$ uzávěrový systém, 
pak $(\mathcal{C}, \subseteq)$ tvoří úplný svaz, kde
$\sup_\subseteq(\mathcal{B}) = \bigcap\{C\in\mathcal{C}|\bigcup \mathcal{B}\subseteq C\}$ 
a $\inf_\subseteq(\mathcal{B}) = \bigcap \mathcal{B}$ pro každé $\mathcal{B}\subseteq\mathcal{C}$ .

{\rm (2)} Systém všech podalgeber i systém všech
kongruencí na algebře spolu s inkluzí je uzávěrový systém a tedy úplný svaz.
\end{pozn}
\begin{proof} (1) $\subseteq$ je uspořádání a 
$\bigcap \mathcal{B}$ je zjevně infimem.
Protože je $\mathcal{C}$ uzavřené na průniky, je 
$\bigcap\{X\in\mathcal{C}|\bigcup \mathcal{B}\subseteq X\}$ nejmenším prvkem 
$\mathcal{C}$ obsahujícím všechna $B\in \mathcal{B}$, což je podle definice
právě supremum vzhledem k inkluzi.

(2) Stejná úvaha jako v \ref{4.1}(4).
\end{proof}


\begin{theorem}\label{kongruence2} {\rm (1)} Všechny normální podgrupy libovolné grupy $G(\cdot)$ tvoří spolu s inkluzí svaz
a zobrazení $\rho\to [1]_\rho$ je izomorfismus svazu všech kongruencí na grupě $G(\cdot)$
svazu všech normálních podgrup.

{\rm (2)} Všechny kongruence a všechny ideály okruhu 
$R(+,\cdot,-,0,1)$ tvoří spolu s inkluzí svazy a zobrazení $\rho\to [0]_\rho$ je izomorfismus svazu všech kongruencí
na svazu všech ideálů okruhu $R$.
\end{theorem}
\begin{proof}
Nejprve dokážeme technické lemma:
\begin{lemma} Buď $\mathcal C$ uzávěrový systém obsažený v systému všech ekvivalencí
na množi\-ně $A$. Nechť pro $\mathcal N\subseteq \mathcal P(A)$ a $e\in A$ platí:
\begin{enumerate}
\item[(a)] $[e]_\rho\in \mathcal N$ pro každé $\rho\in \mathcal C$,
\item[(b)] pro každé $N\in \mathcal N$ existuje takové $\rho\in \mathcal C$,
že $N=[e]_\rho$,
\item[(c)] pro každé $\rho, \eta\in \mathcal C$ platí, že 
$[e]_\rho\subseteq [e]_\eta\Rightarrow \rho\subseteq \eta$.
\end{enumerate}
Pak $\mathcal N$ je uzávěrový systém na $A$ a tedy podle \ref{4.6} svaz a zobrazení
$\varphi: \mathcal C\to\mathcal N$ dané předpisem $\varphi(\rho)=[e]_\rho$
je izomorfismus svazů.
\end{lemma}
{\it Důkaz lemmatu.} Nejprve ukážeme, že je $\mathcal N$ uzávěrový systém.
Protože $A\times A\in\mathcal C$, máme $A=[e]_{A\times A}\in \mathcal N$ díky (a).
Vezmeme-li $N_i\in \mathcal N$, $i\in I$, pak podle (b) existuje pro každé $i\in I$
taková ekvivalence $\rho_i\in\mathcal C$, že $N_i=[e]_{\rho_i}$.
Protože je $\mathcal C$ uzávěrový systém, tedy $\bigcap_{i\in I}\rho_i\in\mathcal C$,
dostáváme $\bigcap_{i\in I}N_i = \bigcap_{i\in I}[e]_{\rho_i}
=[e]_{\bigcap_{i\in I}\rho_i} \in \mathcal N$ opět díky (a).

Nyní stačí podle \ref{4.14} ověřit, že je $\varphi$ dobře definovaná bijekce
a že $\varphi$ i $\varphi^{-1}$ jsou monotónní vzhledem k inkluzi.
Korektnost definice přitom zaručuje podmínka (a), podmínka (b) říká, že
je $\varphi$ na $\mathcal N$, a z podmínky (c) plyne, že jde o prosté zobrazení.
Konečně, je-li $\rho\subseteq \eta$, pak $[e]_\rho\subseteq [e]_\eta$ pro každou 
dvojici ekvivalencí $\rho$ a $\eta$, což zaručuje monotónii $\varphi$,
a monotónie $\varphi^{-1}$ je přímo obsahem podmínky (c).
\qed

(1) Označme symbolem $\mathcal C$ množinu všech kongruencí na 
$G(\cdot)$, tj. ekvivalencí slučitelných s operací $\cdot$ (viz \ref{3.3}(3)),
symbolem $\mathcal N$ množinu všech normálních podgrup $G(\cdot)$ a symbolem $e$ neutrální prvek 
$G(\cdot)$. Z \ref{4.6} plyne, že je $\mathcal C$ uzávěrový
systém a \ref{kongruence1} zaručuje, že jsou splněny předpoklady (a), (b), (c)
Lemmatu, odkud plyne závěr.

(2) Nejprve dokážeme, že ekvivalence $\rho$ je kongruence
na $R(+,\cdot,-,0,1)$, právě když $[0]_\rho$ je ideál a 
$\rho=\Ker[0]_\rho$. V \ref{okr-kongr}(1) jsme dokázali zpětnou implikaci.
Je-li naopak $\rho$ je kongruence na okruhu $R$, pak jde také o kongruenci grupy $R(+)$, proto je $[0]_\rho$
podle \ref{kongruence1} podgrupou $R(+)$ a $(a,b)\in \rho \Leftrightarrow a-b\in [0]_\rho$.
Zbývá ověřit, že jde o ideál. Zvolme $i\in [0]_\rho$ a $r\in R$, tedy $(i,0)\in\rho$
a $(r,r)\in\rho$, proto $(ir,0)=(ir,0r)\in\rho$ a $(ri,0)=(ri,r0)\in\rho$, tedy
$ir,ri\in I$.

Nyní stejným způsobem jako v důkazu (1)
nahlédneme že jsou pro $e=0$, $\mathcal C$ množinu všech kongruencí a $\mathcal N$ množinu všech
ideálů okruhu $R(+,\cdot,-,0,1)$ splněny předpoklady Lemmatu, odkud dostáváme závěr.
\end{proof}


\begin{prikl}\rm Podle předchozí věty a \ref{2.8} tvoří svaz všech kongruencí na dvanácti\-prvkové cyklické grupě právě 
šestiprvková množina kongruencí $\rmod \langle i\rangle$ pro $i\in \{0,1,2,3,4,6,\}$ s inkluzí a tento svaz je stejný jako svaz kongruencí
na okruhu $\mathbb Z_{12}(+,\cdot,-,0,1)$.
\end{prikl}

\end{comment}

\vskip 1cm

\section{Shrnutí}

Na závěr kurzu si uvědomme jakými algebraickými prostředky disponujeme, jaké je jejich místo v kontextu matematiky
a k jakým účelům se dají využít.

\subsection{Teorie čísel a okruhy} Otázky teorie čísel lze formulovat právě jazykem teorie okruhů,
tedy jazykem pracujícím se dvěma distributivitou svázanými asociativními binárními operacemi. Samotná teorie čísel fakticky
pracuje s konkrétním okruhem celých čísel, ovšem mnohá její tvrzení lze vyslovit a dokázat v obecnějším kontextu 
teorie okruhů a naopak mnohé poznatky a postupy teorie okruhů poskytují
užitečný aparát v teorii čísel. Klíčem k pochopení tohoto vztahu je vyjádření dělitelnosti (tedy základnímu výrazovému
prostředku teorie čísel) pomocí inkluze ideálů, jež je formulováno ($a/b \Leftrightarrow bR\subseteq aR$) 
v elementárním pozorování \ref{HI}.

Co důležitého se nám podařilo nahlédnout:
\begin{enumerate} 
\item[\ref{zva}] Základní věta aritmetiky. Obdobu tohoto tvrzení lze dokázat i pro další třídy okruhů (například pro okruhy
jednoho či více proměnných nad tělesem). 
\item[\ref{CRT}] Čínská věta o zbytcích pro celá čísla. I toto tvrzení lze  zobecnit a využít například 
pro rychlé násobení polynomů.
\item[\ref{teleso}] Tvrzení, že tělesem jsou právě faktory komutativního okruhu podle maximálního ideálu, spolu
\item[\ref{dsz}] s algoritmickou větou o dělení se zbytkem, nám umožňuje
\item[\ref{finfields}] konstruovat konečná tělesa (ta jsou posléze základním stavebním kamenem algebraické
teorie kódů).
\end{enumerate}

\subsection{Grupy} Základnějším, ačkoli možná méně přirozeným objektem našeho zkoumání byly jednotlivé
binární operace. Omezíme-li se na množiny s jedinou asociativní binární operací, pak neutrální prvek
ani invertibilní prvky obecně nemusí být k dispozici, ovšem existují-li, jsou určeny jednoznačně.
Navíc v každém monoidu, jak množinu s asociativní binární operací a neutrálním prvkem nazýváme, vždy najdeme
kanonickou grupu invertibilních prvků (\ref{1.6}).

Co důležitého se nám podařilo nahlédnout:
\begin{enumerate} 
\item[\ref{phi}] Vzorec pro výpočet Eulerovy funkce, tedy počtu invertibilních prvků monoidu 
$\Z_n(\cdot)$ získaný pomocí Čínské věty o zbytcích je užitečný v kontextu teorie čísel. 
\item[\ref{Lagrange}] Lagrangeova věta popisující vztah počtu prvků grupy a její podgrupy je důsledek zkoumání vlastností kongruencí $\rmod$ a $\lmod$, jejichž dalšími dů\-sledky jsou 
\item[\ref{kongruence1}] popis kongruencí grupy pomocí pojmu normální podgrupa. %a posléze
%\item[\ref{kongruence2}] jednoznačná korespondence svazů normálních podgrup (resp. ideálů) a kongruencí grup (resp. okruhů).
\item[\ref{2.4}] Snadný popis struktury cyklických grup umožňuje
\item[\ref{2.8}] zesílit tvrzení Lagrangeovy věty pro cyklické grupy a formulovat
\item[\ref{MFT}] Eulerovu větu, která je základním nástrojem několika kryptografických aplikací
(protokoly RSA, Diffie–Hellman, ElGamal).
\end{enumerate}

\subsection{Univerzální algebra}
Mnoho základních úvah o konkrétních algebraických objektech, jaké tvoří například grupy nebo okruhu,
má stejnou podstatu, a proto je možné učinit je velmi obecně pro abstraktní algebry opatřené systémem
blíže nespecifikovaných operací. Velmi užitečný prostředek, jak porozumět inkluzí uspořádaným systémům podalgeber a kongruencí algeber, což jsou základní nástroje zkoumání obecných algeber, je pojem svazu,
který představuje algebraicky uchopené uspořádané množiny.



Co důležitého se nám podařilo nahlédnout:
\begin{enumerate} 
\item[\ref{3.9}] Uvědomili jsme si, že faktorizovat algebry lze právě podle kongruencí a že přirozená projekce na faktorovou algebru je právě homomorfismus.
\item[\ref{ob.o homomorfismu}] 1.věta o izomorfismu jako důsledek Věty o homomorfismu %, kterou jsme nejprve dokázali v jednodušším případě grup \ref{o homomorfismu}, 
umožňuje překládat problémy týkající se faktorových algeber do
podalgeber známých algeber,
\item[\ref{ob.2. o homomorfismu}] zatímco 2.věta o izomorfismu ukazuje, že faktor faktorové algebry lze vždy izomorfně přeložit
na faktor původní algebry.
\item[\ref{4.14}] Tvrzení, že izomorfismy svazů lze popsat jazykem monotónie, využívá důkaz
\item[\ref{BA}] izomorfního popisu konečných Booleových algeber jako potenční Booleovy algebry.
\end{enumerate}



\end{document}



\begin{pozn}\label{faktor} Nechť $G(\cdot)$ je grupa a $\rho$ ekvivalence na
$G$ slučitelná s $\cdot$. Na faktorové množině $G/\rho$ definujeme operaci
$\odot$ předpisem $[a]_\rho\odot [b]_\rho = [a\cdot b]_\rho$.
Tato definice je korektní, $G/\rho(\odot)$ je opět grupa a přirozená projekce
$\pi_\rho$ je homomorfismus.
\end{pozn} 
\begin{proof} Abychom ověřili korektnost definice, musíme ukázat, že definice nezávisí
na volbě zástupce ekvivalenčních tříd. Mějme tedy $[a]_\rho=[c]_\rho$
a $[b]_\rho=[d]_\rho$, tj. $(a,c),$ $(b,d)\in\rho$. 
Potom díky slučitelnosti $\rho$ s operací máme $(a\cdot b,c\cdot d)\in\rho$, proto
$[a\cdot b]_\rho = [c\cdot d]_\rho$.

Vezmeme-li $[a]_\rho, [b]_\rho, [c]_\rho\in\rho$, pak přímo z definice vidíme, že 
\[
[a]_\rho\odot ([b]_\rho\odot [c]_\rho]) = [a\cdot(b\cdot c)]_\rho
= [(a\cdot b)\cdot c]_\rho = ([a]_\rho\odot [b]_\rho)\odot [c]_\rho,
\]
tedy operace $\odot$ je asociativní. To, že je neutrálním prvkem právě
$[e]_\rho$ a inverzním prvkem k prvku $[a]_\rho$ právě prvek $[a^{-1}]_\rho$,
dostaneme přímým výpočtem. Konečně 
$\pi_\rho(a\cdot b)=[a\cdot b]_\rho =[a]_\rho\odot [b]_\rho=\pi_\rho(a)\odot\pi_\rho(b)$
z definice.
\end{proof}




