## toto je pracovní verze vzniklá převodem z texu, ještě potřebuje vyčistit ## # Algebry, homomorfismy, kongruence # ### Definice ### Buď $A \,$ množina a $n\in\mathbb{N}_0 \,$. *Operací* (arity $n \,$ nebo $n \,$-ární) rozumíme zobrazení $\alpha:A^n\to A \,$. ### Označení ### $n=0,A^0\to A, \alpha_0()=a_0 \,$, běžně píšeme $\alpha_0 \,$ namísto $a_0 \,$. ### Definice ### Buď $\alpha_i \,$, $i\in I \,$, operace na množině A. Pak *algebrou* nazvu každou takovou uspořádanou dvojici $A(\alpha_i|i\in I) \,$. ### Příklad ### 1. $\mathbb{Z}(+) \,$, $\mathbb{Z}(+,-,0) \,$, $\mathbb{Z}(+,\cdot,-,0,1) \,$ 1. $T \,$ je těleso s operacemi $+ \,$, $\cdot \,$ ($-,0,1 \,$), potom $T(+,\cdot) \,$ a $T(+,\cdot,-,0,1) \,$ jsou algebry 1. $T \,$ je těleso s operacemi $+ \,$, $\cdot \,$, buď $V \,$ vektorový prostor s operacemi $+ \,$ a $\cdot t|t \in T \,$, potom $V(+,\cdot t) \,$ je algebra ### Definice ### Buď $A \,$ množina, $B\subseteq A \,$. Je-li $\alpha \,$ $n \,$-ární operace, $n\in\mathbb{N}_0 \,$, na $A \,$, řekneme, že $B \,$ je *uzavřená* na $\alpha \,$, pokud $\forall b_1,\ldots,b_n\in B \,$ $\alpha(b_1,\ldots,b_n)\in B \,$. Je-li $A(\alpha_i|i\in I) \,$ algebra, potom $B\subseteq A \,$ nazveme *podalgebrou* (algebry $A(\alpha_i|i\in I) \,$), pokud $B \,$ je uzavřená na operace $\alpha_i \,$ $\forall i\in I \,$. ### Příklad ### 1. $k\in\mathbb{Z}\quad k\mathbb{Z}=\{kz|z\in\mathbb{Z}\} \,$, podalgebry $\mathbb{Z}(+) \,$ a $\mathbb{Z}(+,-,0) \,$. 1. $\mathbb{Z} \,$ je podalgebrou tělesa $\mathbb{Q}(+,\cdot) \,$, $\mathbb{Q}(+,\cdot,-,0,1) \,$ 1. $A=\{1\} \,$ je podalgebrou $\mathbb{Z}(\cdot) \,$, není podalgebrou $\mathbb{Z}(+) \,$ 1. podprostor je podalgebrou vektorového prostoru $V(+,\cdot t) \,$, $\emptyset \,$ je také podalgebrou ### Poznámka ### Buď $A(\alpha_i|i\in I) \,$ algebra a $B \,$ její podalgebra. $\beta_i:B^{n_i}\to B \,$, je-li $\alpha_i \,$ $n_i \,$-ární operace $\beta_i(b_1,\ldots,b_n)=\alpha_i(b_1,\ldots,b_n)\in B\ \forall i\in I\ \forall b_1,\ldots,b_n\in B \,$, potom $B(\beta_i|i\in I) \,$ je algebra. ### Poznámka 1.1 ### Buď $A(\alpha_i|i\in I) \,$ algebra a $B_j,j\in J \,$ nechť jsou její podalgebry. Pak $\bigcap_{j\in J}B_j \,$ je opět podalgebra algebry $A(\alpha_i|i\in I) \,$. #### Důkaz #### $\alpha_i \,$ operace na $A \,$, $b_1,\ldots,b_{n_i}\in\bigcap_{j\in J}B_j\subseteq B_j\ \forall j \,$ ($n_i \,$ arita operace $\alpha \,$). $\alpha_i(b_1,\ldots,b_{n_i})\in B_j\forall j \,$, protože $B_j \,$ je podalgebra, tedy $\alpha_i(b_1,\ldots,b_{n_i})\in\bigcap_{j\in J}B_j \,$. ### Definice ### Buď $\alpha \,$ operace arity $n \,$ na množinách $A \,$ a $B \,$ a $f:A\to B \,$ zobrazení. Řekněme, že *$f \,$ je slučitelné s (operací) $\alpha \,$* , jestliže $\forall a_1,\ldots,a_n\in A \,$ platí
$ f(\alpha(a_1,\ldots,a_n))=\alpha(f(a_1),\ldots,f(a_n)). \,$
### Definice ### Nechť $A(\alpha_i|i\in I) \,$, $B(\alpha_i|i\in I) \,$ jsou algebry. Řekneme, že jsou *stejného typu* , pokud $\alpha_i \,$ je $n_i \,$-ární operací na $A \,$ i na $B \,$. ### Definice ### O zobrazení $f:A\to B \,$ řekneme, že je *homomorfismus* (algeber $A(\alpha_i|i\in I) \,$, $B(\alpha_i|i\in I) \,$), je-li $f \,$ *slučitelné* , s $\alpha_i\forall i\in I \,$. ### Příklad ### 1. $V_1(+,\cdot t) \,$, $V_2(+,\cdot t) \,$ dva vektorové prostory nad tělesem $T \,$, pak homomorfismy algeber $V_1(+,\cdot t) \,$ a $V_2(+,\cdot t) \,$ jsou právě lineární zobrazení (tj. homomorfismy v lineárně algebraickém smyslu) 1. 1. $det \,$ je homomorfismus algeber $\[M_n(T)](\cdot) \,$ a $T(\cdot) \,$ ($M_n(T) \,$ jsou čtvercové matice $n\times n \,$ nad tělesem $T \,$) 1. $det \,$ je homomorfismus algeber $\[M_n(T)](\cdot, I_n, 0_n) \,$ a $T(\cdot, 1, 0) \,$ 1. $\pi_n:\mathbb{Z}\to\mathbb{Z}_n \,$ $\pi_n(z)=(z)\mod{n} \,$, $\pi_n \,$ je homomorfismus $\mathbb{Z}(+,-,\cdot,0,1) \,$ a $\mathbb{Z}_n(+,-,\cdot,0,1) \,$ ### Poznámka 1.2. ### Nechť $A(\alpha_i|i\in I) \,$, $B(\alpha_i|i\in I) \,$, $C(\alpha_i|i\in I) \,$ jsou algebry stejného typu a $f:A\to B \,$ a $g:B\to C \,$ jsou homomorfismy, pak $gf:A\to C \,$ je také homomorfismus. Navíc, je-li $f \,$ bijekce, pak i $f^{-1} \,$ je homomorfismus. #### Důkaz #### Nechť $\alpha_i \,$ je libovolná operace arity $n \,$, $a_1,\ldots,a_n\in A \,$, potom
$\begin{matrix} gf(\alpha_i(a_1,\ldots,a_n)) & = & g(f(\alpha_i(a_1,\ldots,a_n)))\\ & = & g(\alpha_i(f(a_1),\ldots,f(a_n)))\\ & = & \alpha_i(g(f(a_1)),\ldots,g(f(a_n))). \end{matrix} \,$
Nechť $f \,$ je bijekce, $f^{-1}:B\to A \,$, $b_1,\ldots,b_n\in B \,$, $\exists a_1,\ldots,a_n\in A \,$ že $f(a_i)=b_i \,$ a $f^{-1}(b_i)=a_i \,$, potom
$\begin{matrix} f^{-1}(\alpha_i(b_1,\ldots,b_n)) & = & f^{-1}(\alpha_i(f(a_1),\ldots,f(a_n)))\\ & = & f^{-1}f(\alpha_i(a_1,\ldots,a_n))\\ & = & \alpha_i(f^{-1}(b_1),\ldots,f^{-1}(b_n)). \end{matrix} \,$
### Poznámka 1.3. ### Buď $A(\alpha_i|i\in I) \,$ a $B(\alpha_i|i\in I) \,$ algebry stejného typu, $f:A\to B \,$ homomorfismus a $C \,$ buď podalgebra $A(\alpha_i|i\in I) \,$ a $D \,$ podalgebra $B(\alpha_i|i\in I) \,$. Pak $f(C) \,$ je podalgebra $B(\alpha_i|i\in I) \,$ a $f^{-1}(D)=\{a\in A|f(a)\in D\} \,$ je podalgebra $A(\alpha_i|i\in I) \,$. #### Důkaz #### Nechť $\alpha_i \,$ je libovolná operace arity $n \,$, $b_1,\ldots,b_n\in f(C) \,$ tj. $\exists c_1,\ldots,c_n\in C \,$ že $f(c_i)=b_i \,$, potom
$ \alpha_i(b_1,\ldots,b_n)=f(\alpha_i(c_1,\ldots,c_n))\in f(C). \,$
Nechť $a_1,\ldots,a_n\in f^{-1}(D) \,$, $f(a_i)\in D \,$, potom
$ f(\alpha_i(a_1,\ldots,a_n))=\alpha_i(f(a_1),\ldots,f(a_n))\in D, \,$
tj. $\alpha_i(a_1,\ldots,a_n)\in f^{-1}(D) \,$. ### Poznámka ### Je-li jasná struktura algebry $A(\alpha_i|i\in I) \,$, budeme často říkat *algebra $A \,$* (namísto algebra $A(\alpha_i|i\in I) \,$). \paragraph{Připomínka a označení.}(8) $\varrho\subseteq A\times A \,$ nazveme *relací na $A \,$* , $(a,b)\in\varrho \,$ (ekvivalentně $a\varrho b \,$). Je-li $\varrho \,$ relace na $A \,$, potom
$\begin{matrix} \varrho^{-1} & = & \{(a,b)\in A\times A|(b,a)\in\varrho\}\\ \varrho^+ & = & \{(a,b)\in A\times A|\exists a_0,\ldots,a_n;a_0=a,a_n=b,(a_i,a_{i+1})\in\varrho\}\\ id & = & \{(a,a)\in A\times A|a\in A\}. \end{matrix} \,$
Řekneme že relace $\varrho \,$ je symetrická, reflexivní, tranzitivní, jestliže $\varrho^{-1}\subseteq\varrho \,$, $id\subseteq\varrho \,$, $\varrho^+\subseteq\varrho \,$. Ekvivalence je reflexivní, symetrická a tranzitivní relace. ### Definice ### Buď $\varrho \,$ ekvivalence na množině $A \,$. Pak faktorem $A \,$ podle $\varrho \,$ rozumíme $A/\varrho=\{\[a]_{\varrho}|a\in A\} \,$, kde $\[a]_{\varrho}=\{b\in A|(a,b)\in\varrho\} \,$. ### Poznámka ### 1. Nechť $\varrho \,$ je ekvivalence na množině $A \,$. Pak $A/\varrho \,$ tvoří rozklad $A \,$. 1. Je-li $\{B_i|i\in I\} \,$ rozklad množiny $A \,$, pak relace $\eta \,$ daná vztahem $(a,b)\in\eta\Leftrightarrow\exists i\in I\ a,b\in B_i \,$ je ekvivalence ($A=\bigcup B_i \,$ a $B_i\cap B_j=\emptyset\ \forall i\neq j \,$). #### Důkaz #### 1. $A=\bigcup_{a\in A}\[a]_{\varrho} \,$,
$\begin{matrix} \emptyset\neq\[a]_{\varrho}\cap\[b]_{\varrho} & \Rightarrow & (a,c)\in\varrho,(b,c)\in\varrho\\ & \Rightarrow & (a,c)\in\varrho,(c,b)\in\varrho \\ & \Rightarrow & (a,b)\in\varrho \end{matrix} \,$
$\forall d\in\[b]_{\varrho} \,$ platí $d\in\[a]_{\varrho} \,$, tj. $\[b]_{\varrho}\subseteq \[a]_{\varrho} \,$ a symetricky $\[b]_{\varrho}\supseteq \[a]_{\varrho} \,$, tedy $\[b]_{\varrho}=\[a]_{\varrho} \,$. 1. zřejmé ### Definice ### Buď $f:A\to B \,$ zobrazení a $\varrho \,$ ekvivalence,
$ \ker{f} = \{(a,b)\in A\times A|f(a)=f(b)\} \,$
je *jádro* zobrazení $f \,$, $\pi_{\varrho}:A\to A/\varrho \,$ budiž *přirozená projekce* , tj. zobrazení $\pi_{\varrho}(a)=\[a]_\varrho \,$. ### Poznámka 1.4. ### Nechť $f:A\to B \,$ je zobrazení a $\varrho \,$ ekvivalence na $A \,$. Potom platí: 1. $\ker{f} \,$ je ekvivalence 1. $f \,$ je prosté právě tehdy, když $\ker{f}=id \,$ 1. $\ker{\pi_\varrho}=\varrho \,$ 1. zobrazení $g:A/\varrho\to B \,$ takové, že $g \pi_\varrho=f \,$ existuje právě tehdy, když $\varrho\subseteq\ker{f} \,$ #### Důkaz #### 1. $f(a)=f(a)\ \forall a\in A \,$, tedy $(a,a)\in\ker{f} \,$ (reflexivita) #:$f(a)=f(b) \,$ (tj. $(a,b)\in\ker{f} \,$), tedy $f(b)=f(a) \,$ tj. $(b,a)\in\ker{f} \,$ (symetrie) #:$f(a)=f(b)=f(c) \,$, tedy $f(a)=f(c) \,$ tj. $(a,c)\in\ker{f} \,$ (tranzitivita) 1. $f \,$ je prosté $a,b\in A \,$ $f(a)=f(b)\Rightarrow a=b \Leftrightarrow (a,b)\in\ker{f}\Rightarrow a=b\Leftrightarrow\ker{f}=id \,$ 1. $\ker{\pi_\varrho}=\{(a,b)\in A\times A|\[a]_\varrho=\pi_\varrho(a)=\pi_\varrho(b)=\[b]_\varrho\}=\{(a,b)\in A\times A|(a,b)\in\varrho\}=\varrho \,$ # "$\Rightarrow \,$" :: mějme $g:A/\varrho\to B \,$, $g(\[a]_\varrho)=g(\pi_\varrho(a))=f(a)\ \forall a\in A \,$; $(a,b)\in\varrho \,$ tj. $\[a]_\varrho=\[b]_\varrho \,$, $g(\[a]_\varrho)=f(a) \land g(\[b]_\varrho)=f(b) \Rightarrow (a,b)\in\ker{f} \,$ "$\Leftarrow \,$" :: $\varrho\subseteq\ker{f} \,$ je-li $g\pi_\varrho=f \,$ je $g \,$ korektně definována, tedy $g(\[a]_\varrho)=f(a) \,$, $\[a]_\varrho=\[b]_\varrho \,$ tj. $(a,b)\in\varrho\Rightarrow (a,b)\in\ker{f} \,$ tj. $f(a)=f(b)\Rightarrow g(\[a]_\varrho)=g(\[b]_\varrho) \,$ ### Definice ### {{TODO|doplnit-uplne nove}} Nechť � ⊆ � jsou dvě ekvivalence na A. Definujme relaci �/� na A/� následovně: (\[a]�, \[b]�) ∈ �/� ⇔ (a, b) ∈ �. ### Poznámka 1.5. ### (1) Nechť � ⊆ � jsou dvě ekvivalence na A. Pak �/� je dobře definovaná ekvivalence na A/�. (2) Nechť � je ekvivalence na množině A a � je ekvivalence na A/�. Potom existuje právě jedna ekvivalence � na A, pro níž � = �/�. #### Důkaz #### (1) viz \[D, 1.8] a (2) viz \[D, 1.9]. � ### Definice ### Buď $\varrho \,$ ekvivalence na $A \,$, $\alpha \,$ je $n \,$-ární operace na $A \,$. Řekneme, že $\varrho \,$ je *slučitelná s $\alpha \,$* , platí-li $a_1,\ldots,a_n,b_1,\ldots,b_n\in A \,$, kde $n \,$ je arita operace $\alpha \,$, jestliže $(a_i,b_i)\in\varrho\ \forall i=1,\ldots,n \,$ potom $(\alpha(a_1,\ldots,a_n),\alpha(b_1,\ldots,b_n))\in\varrho \,$. Řekneme, že ekvivalence $\varrho \,$ na algebře $A(\alpha_i|i\in I) \,$ je *kongruence* , jesliže je $\varrho \,$ slučitelná s $\alpha_i\forall i\in I \,$. ### Poznámka 1.6. ### Buď $f:A\to B \,$ homomorfismus dvou algeber stejného typu. Pak $ker f \,$ je kongruence (na $A \,$). #### Důkaz #### $\ker{f} \,$ je ekvivalence dle 10. Nechť $\alpha_i \,$ je operace na $A \,$ (i na $B \,$), $a_1,\ldots,a_n,b_1,\ldots,b_n\in A \,$ $(a_j,b_j)\in \ker{f} \,$ tj. $f(a_j)=f(b_j)\ \forall j=1,\ldots,n \,$, $f(\alpha_i(a_1,\ldots,a_n))=\alpha_i(f(a_1),\ldots,f(a_n))=\alpha_i(f(b_1),\ldots,f(b_n))=f(\alpha_i(b_1,\ldots,b_n)) \,$ tj. $(\alpha_i(a_1,\ldots,a_n),\alpha_i(b_1,\ldots,b_n))\in \ker{f} \,$ ### Definice ### Nechť $A(\alpha_i|i\in I) \,$ je algebra a $\varrho \,$ budiž kongruence na $A \,$. Pak na $A/\varrho \,$ definujeme strukturu algebry
$ \forall i\in I\ \alpha_i(\[a_1]_\varrho,\ldots,\[a_{n_i}]_\varrho)=\[\alpha_i(a_1,\ldots,a_{n_i})]_\varrho \,$
kde $n_i \,$ je arita operace $\alpha_i \,$. ### Věta 1.7. ### Definice struktury algebry na $A/\varrho \,$ je korektní, algebra $A/\varrho(\alpha_i|i\in I) \,$ je stejného typu jako $A(\alpha_i|i\in I) \,$ a $\pi_\varrho \,$ je homomorfismus. #### Důkaz #### $\[a_j]_\varrho=\[b_j]_\varrho\ j=1,\ldots,n_i \,$ tj. $(a_j,b_j)\in\varrho\Rightarrow (\alpha_i(a_1,\ldots,a_n),\alpha_i(b_1,\ldots,b_n))\in\varrho \,$, $\alpha_i(\[a_1]_\varrho,\ldots,\[a_{n_i}]_\varrho){=}^{\mathrm{def}}\[\alpha_i(a_1,\ldots,a_{n_i})]_\varrho \,$, $\alpha_i(\[b_1]_\varrho,\ldots,\[b_{n_i}]_\varrho){=}^{\mathrm{def}}\[\alpha_i(b_1,\ldots,b_{n_i})]_\varrho \,$. Dokážeme že $\pi_\varrho \,$ je homomorfismus, $\pi_\varrho(\alpha_i(a_1,\ldots,a_n))=\[\alpha_i(a_1,\ldots,a_{n_i})]{=}^{\mathrm{def}}\alpha_i(\[a_1]_\varrho,\ldots,\[a_{n_i}]_\varrho])=\alpha_i(\pi_\varrho(a_1),\ldots,\pi_\varrho(a_{n_i})) \,$. ### Příklad ### 1. $\mathbb{Z}(+,-,\cdot) \,$ $a,b\in\mathbb{Z} \,$ $n\in\mathbb{N} \,$, $a\sim_n b \,$ jesliže $n|a-b \,$ ($\Leftrightarrow a\mod{n}=b\mod{n} \,$) $\[a\equiv b\mod{n}] \,$. $\sim_n \,$ je zjevně ekvivalence, $\sim_n \,$ je slučitelná s $+ \,$, $a_1\sim_n b_1 \,$ tedy $n|a_1-b_1 \,$, $a_2\sim b_2 \,$ tedy $n|a_2-b_2 \,$, tedy $n|(a_1-b_1)+(a_2-b_2)=(a_1+a_2)-(b_1+b_2) \,$, podobně pro $-,\cdot \,$. $\mathbb{Z}/\sim_n(+,-,\cdot) \,$ $\mathbb{Z}/\sim_n=\{\[0]_{\sim_n},\[1]_{\sim_n},\ldots,\[n-1]_{\sim_n}\}=\{\[a]_{\sim_n}|a\in\mathbb{Z}_n\} \,$. $\[a]_{\sim_n}+\[b]_{\sim_n}=\[a+b]_{\sim_n}=\[(a+b)\mod{n}] \,$ 1. $A(\alpha_i|i\in I) \,$ algebra, $id,A\times A \,$ jsou kongruentní operace v této algebře 1. $A \,$ buď množina, $e \,$ je nulární operace, $\varrho \,$ ekvivalence je slučitelná s $e \,$, tedy $(e,e)\in\varrho \,$ ### Poznámka 1.8. ### {{TODO|doplnit z izomorfismů}} Buď � kongruence na algebře A a � ekvivalence na A obsahující �. Pak je � kongruence na algebře A právě tehdy, když je �/� kongruence na algebře A/�. ====Důkaz.==== Viz \[D, 3.4]. � ### Poznámka 1.9. (Věta o homomorfismu) ### Buď f : A → B homomorfismus dvou algeber stejného typu a nechť � je kongruence na algebře A. Pak existuje homo- morfismus g : A/� → B splňující podmínku g�� = f právě tehdy, když � ⊆ ker f. Navíc, pokud g existuje, je g izomorfismus, právě když f je na a ker f = �. ====Důkaz.==== Viz \[D, 3.7]. � ### Věta 1.10 (1. věta o izomorfismu). ### Nechť f : A → B je homomorfismus dvou algeber stejného typu. Pak f(A) je podalgebra B (tedy algebra stejného typu) a A/ker f je izomorfní f(A). Důkaz. Viz \[D, 3.9]. � 4 ### Příklad. ### Mějme homomorfismus fn : Z → Zn algebry Z(+, ·,−, 0) do algebry Zn(+, ·,−, 0) s počítáním modulo n daný předpisem fn(k) = (k)mod n. Pak podle 1. věty o izomorfismu je Z/ker fn ∼= Zn, navíc je zjevně (a − b) ∈ ker fn, právě když n/(a − b). ### Věta 1.11 (2. věta o izomorfismu). ### Nechť � ⊆ � jsou dvě kongruence na algebře A. Pak algebra A/� je izomorfní algebře (A/�)/(�/�). ====Důkaz.==== Viz \[D, 3.10]. # Algebry s jednou binární operací # ### Definice ### Algebru $G(\cdot) \,$ nazveme *grupoidem* je-li $\cdot \,$ binární operace. Prvek $e\in G \,$ nazveme neutrálním prvkem operace $\cdot \,$, platí-li $\forall g\in G\ g\cdot e=e\cdot g=g \,$. Řekneme, že algebra $G(\cdot, e) \,$ je *monoid* , je-li $\cdot \,$ asociativní operace ($\forall a,b,c\in G\ a\cdot(b\cdot c)=(a\cdot b)\cdot c \,$) a $e \,$ je neutrální prvek. *Podgrupoid* (*podmonoid* ) bude podalgebrou grupoidu (monoidu). ### Poznámka ### Buď $G(\cdot) \,$ grupoid a $e,f \,$ jeho dva neutrální prvky. Pak platí $e=f \,$. #### Důkaz #### $e=e\cdot f=f \,$ ### Příklad ### $G \,$ je lib. množina pro kterou platí $|G|>1 \,$, $a*b=a\ \forall a,b\in G \,$. Potom $G(*) \,$ neobsahuje žádný neutrální prvek. ### Příklad ### 1. $X \,$ je množina písmen, $M(X) \,$ množina slov, tj. konečné posloupnosti prvků z $X \,$, $x_1,x_2,\ldots,x_k\in X \,$; místo $(x_1,x_2,\ldots,x_k) \,$ píšeme $x_1x_2\ldots x_k \,$, definujeme operaci $\cdot \,$ jako $x_1\ldots x_k\cdot y_1\ldots y_l=x_1\ldots x_ky_1\ldots y_l \,$, $\lambda \,$-prázdná posloupnost; potom $M(X)(\cdot,\lambda) \,$ je monoid 1. $X \,$ je množina $T(X)=\{f:X\to X\} \,$, $\circ \,$ skládání zobrazení, potom $T(X)(\circ,id) \,$ je tzv. transformační monoid 1. $M_n(T)(\cdot,I_n) \,$ je monoid 1. $A \,$ buď algebra (nebo např. graf, topologický prostor, "geometrický útvar"), $End(A)=\{f:A\to A|f \,$je homomorfismus$\}\ (\subseteq T(A)) \,$, potom $End(A)(\circ,id) \,$ je monoid, např. $A \,$ je vektorový prostor dimenze $n \,$ (v lineární algebře $M_n(T)(\cdot, I_n) \,$ a $End(A)(\circ, id) \,$) ### Poznámka ### Je-li $S(\cdot, 1) \,$ monoid a platí, že $a\cdot b=1=c\cdot a \,$ pro nějaké $a,b,c\in S \,$, pak $b=c \,$. #### Důkaz #### $c=c\cdot 1=c\cdot(a\cdot b)=(c\cdot a)\cdot b=1\cdot b=b \,$ ### Příklad ### $T(\mathbb{N})(\circ, 1) \,$, $\alpha(k)=2k \,$, $\beta(k)=\[\frac{k}{2}] \,$, potom $\beta\alpha=id \,$ ale $\alpha\beta\neq id \,$, obecně $\forall\gamma:\mathbb{N}\to\mathbb{N} \,$ platí že $\alpha\gamma \,$ není zobrazení na, tedy $\alpha\gamma\neq id \,$. ### Definice ### Je-li $S(\cdot, 1) \,$ monoid, potom prvek $a^{-1}\in S \,$ pro nějaké $a\in S \,$ nazveme inverzním, jestliže $a^{-1}\cdot a=1=a\cdot a^{-1} \,$. Prvek, pro nějž existuje inverzní prvek nazveme *invertibilním* prvkem (monoidu). ### Poznámka ### Nechť $S(\cdot, 1) \,$ je monoid a označme $S^* \,$ množinu všech invertibilních prvků tohoto monoidu. Pak $S^* \,$ je podmonoid monoidu $S(\cdot, 1) \,$. Navíc každý inverzní prvek je invertibilní. #### Důkaz #### $a\cdot a^{-1}=1=a^{-1}\cdot a\stackrel{\mathrm{def}}{\Rightarrow}(a^{-1})^{-1}=a \,$, tedy každý inverzní prvek je invertibilní. $1\cdot 1=1\Rightarrow 1\in S^* \,$ a pro $a,b\in S^* \,$ platí $(b^{-1}\cdot a^{-1})\cdot(a\cdot b)\stackrel{\mathrm{asoc.}}{=}b^{-1}\cdot(a^{-1}\cdot a)\cdot b=b^{-1}\cdot b=1 \,$ a $(a\cdot b)\cdot(b^{-1}\cdot a^{-1})\stackrel{\mathrm{asoc.}}{=}a\cdot(b^{-1}\cdot b)\cdot a^{-1}=a\cdot a^{-1}=1 \,$, tedy $(a\cdot b)^{-1}=b^{-1}\cdot a^{-1}\Rightarrow a\cdot b\in S^* \,$. ### Definice ### Algebru $G(\cdot, ^{-1},1) \,$ nazveme *grupou* , je-li $G(\cdot, 1) \,$ monoid a ${}^{-1} \,$ je unární operace, která každému prvku přiřadí inverzní prvek monoidu $G(\cdot, 1) \,$. *Komutativní (Abelovou) grupou* nazveme grupu s komutativní operací $\cdot \,$ ($\forall a,b\in G\ a\cdot b=b\cdot a \,$). *Podgrupou* rozumíme podalgebru grupy. Normální podgrupou $H \,$ grupy $G(\cdot, ^{-1},1) \,$ budeme rozumět podgrupu splňující $\forall g\in G\forall h\in H\quad g\cdot h\cdot g^{-1}\in H \,$. ### Poznámka ### Nechť $S(\cdot, 1) \,$ je monoid a $S^* \,$ množina všech invertibilních prvků. Nechť ⊙ je restrikce $\cdot \,$ na $S^* \,$ (⊙$:S^*\times S^*\to S^* \,$, a a ⊙ b$=a\cdot b\ \forall a,b\in S^* $) a ${}^{-1} \,$ budiž operace inverzního prvku. Pak $S^*( \,$⊙$, ^{-1},1) \,$ je grupa. #### Důkaz #### Dle 15 jsou ⊙$, {}^{-1}, 1 \,$ korektně definované operace na $S^* \,$ a $S^*( \,$⊙$,1) \,$ je monoid dle stejného tvrzení. ${}^{-1} \,$ je operace inverzního prvku dle definice. ### Příklad ### 1. $(M(X))^*=\{\lambda\} \,$ 1. $(T(X))^*=S(X)=\{f:X\to X|f\textrm{-bijekce}\} \,$, $S(X)(\circ, ^{-1},id) \,$-grupa ("symetrická" grupa) #:($S_n=S(\{1,2,\ldots,n\}) \,$) 1. $(M_n(T))^*=GL_n(T) \,$-invertibilní (regulární) matice, $GL_n(T)(\cdot, ^{-1},I_n) \,$--grupa 1. ${End(A)}^*=Aut(A)=\{f:A\to A| \,$-bijektivni homomorfismus$\} \,$, $Aut(A)(\,$⊙$, ^{-1},id) \,$-grupa, $Aut(\mathbb{Z}_n)=\{f:\mathbb{Z}_n\to\mathbb{Z}_n|f\,$-homomorfismus, f bijekce$=\{x\to(x\cdot k)\mod{n}|k\in\mathbb{Z}_n,\gcd{(k,n)}=1\} \,$. ### Poznámka ### Každá podgrupa komutativní grupy je normální. #### Důkaz #### $H \,$ buď podgrupa, $G(\cdot, ^{-1},1) \,$ komutativní grupa, $g\in G\ h\in H:g\cdot h\cdot g^{-1}=g\cdot g^{-1}\cdot h=1\cdot h=h\in H \,$. ### Věta ### Nechť $G(\cdot, ^{-1}, 1) \,$ je grupa a $\varrho \,$ je relace na $G \,$. Pak $\varrho \,$ je kongruence na $G(\cdot, ^{-1}, 1) \,$ právě tehdy, když $\[1]_\varrho \,$ je normální podgrupou grupy $G \,$ a $(g,h)\in\varrho\Leftrightarrow g^{-1}\cdot h\in \[1]_\varrho \,$. #### Důkaz #### "$\Rightarrow \,$" :: $\varrho \,$ buď kongruence 1. *dokážeme že $\[1]_\varrho \,$ je podgrupa $G \,$ $(1,1)\in\varrho\Rightarrow 1\in\[1]_\varrho \,$\\ $a\in\[1]_\varrho\stackrel{\mathrm{def}}{\Rightarrow}(1,a)\in\varrho\Rightarrow(1^{-1},a^{-1})=(1,a^{-1})\in\varrho\Rightarrow a^{-1}\in\[1]_\varrho \,$\\ $a,b\in\[1]_\varrho\stackrel{\mathrm{def}}{\Rightarrow}(1,a),(1,b)\in\varrho\Rightarrow(1\cdot 1,a\cdot b)=(1,a\cdot b)\in\varrho\Rightarrow a\cdot b\in \[1]_\varrho \,$ 1. *dokážeme normalitu $\[1]_\varrho \,$\\ $g\in G \,$ $h\in\[1]_\varrho \,$ a $(g,g)\in\varrho \,$, $(1,h)\in\varrho \,$ vyplývá $(g\cdot 1,g\cdot h)\in\varrho \,$, dále z $(g^{-1},g^{-1})\in\varrho \,$ výplývá $(g\cdot 1\cdot g^{-1},g\cdot h\cdot g^{-1})\in\varrho\Rightarrow(1,g\cdot h\cdot g^{-1})\in\varrho\Rightarrow g\cdot h\cdot g^{-1}\in\[1]_\varrho \,$ # *$(g^{-1}\cdot h)\in\[1]_\varrho\Rightarrow\underbrace{(1,g^{-1}\cdot h)=(g^{-1}\cdot g,g^{-1}\cdot h)\in\varrho}_{(g^{-1}\cdot h)\in\[1]_\varrho}\Rightarrow(g\cdot 1,g\cdot g^{-1}\cdot h)\in\varrho\Rightarrow(g,h)\in\varrho \,$ "$\Leftarrow \,$" :: $H \,$ buď normální podgrupa, definujme relaci $\varrho \,$ jako $(a,b)\in\varrho\stackrel{\mathrm{def}}{\equiv} a^{-1}\cdot b\in H \,$ # *dokážeme že $\varrho \,$ je ekvivalence $\forall g\in G \,$\\ $g^{-1}\cdot g=1\in H\Rightarrow (g,g)\in\varrho \,$ (reflexivita)\\ $(g,h)\in\varrho \,$ $g^{-1}\cdot h\in H\Rightarrow h^{-1}\cdot (g^{-1})^{-1}=h^{-1}\cdot g\in H \,$ tj. $(h,g)\in\varrho \,$ (symetrie)\\ $(g,h)\in\varrho \,$ $(h,r)\in\varrho\Rightarrow g^{-1}\cdot h,h^{-1}\cdot r\in H\Rightarrow g^{-1}\cdot r=g^{-1}\cdot h\cdot h^{-1}\cdot r\in H \,$ tj. $(g,r)\in\varrho \,$ (tranzitivita) # *$\[1]_\varrho=H \,$ je zřejmé 1. *dokážeme že $\varrho \,$ je slučitelné s operacemi\\ $(1,1)\in\varrho\Rightarrow \varrho \,$ slučitelné s 1\\ $(g,h)\in\varrho\Rightarrow g^{-1}\cdot h\in H\Rightarrow g\cdot(g^{-1})\cdot h)\cdot g^{-1}\in H\Rightarrow (h^{-1},g^{-1})\in\varrho\Rightarrow (g^{-1},h^{-1})\in\varrho \,$\\ $(g_1,h_1)\in\varrho\Rightarrow g^{-1}_1\cdot h_1\in H \,$\\ $(g_2,h_2)\in\varrho\Rightarrow g^{-1}_2h_2\in H\Rightarrow g_2\cdot(g^{-1}_2\cdot h_2)\cdot g^{-1}_2\in H\Rightarrow g^{-1}_1\cdot h_1\cdot h_2\cdot g^{-1}_2\in H \Rightarrow g^{-1}_2\cdot (g^{-1}_1\cdot h_1\cdot h_2\cdot g^{-1}_2)\cdot g_2\in H=(g_1\cdot g_2)^{-1}\cdot(h_1\cdot h_2)\in H\Rightarrow (g_1\cdot g_2,h_1\cdot h_2)\in\varrho \,$ __NOTOC__