MAI062 wiki-skripta

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) \, $
2. $ T \, $ je těleso s operacemi $ + \, $, $ \cdot \, $ ($ -,0,1 \, $), potom $ T(+,\cdot) \, $ a $ T(+,\cdot,-,0,1) \, $ jsou algebry
3. $ 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) \, $.
2. $ \mathbb{Z} \, $ je podalgebrou tělesa $ \mathbb{Q}(+,\cdot) \, $, $ \mathbb{Q}(+,\cdot,-,0,1) \, $
3. $ A=\{1\} \, $ je podalgebrou $ \mathbb{Z}(\cdot) \, $, není podalgebrou $ \mathbb{Z}(+) \, $
4. 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)
2. 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 \, $)
   2. $ det \, $ je homomorfismus algeber $ [M_n(T)](\cdot, I_n, 0_n) \, $ a $ T(\cdot, 1, 0) \, $
3. $ \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 \, $.
2. 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} \, $.
2. 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
2. $ f \, $ je prosté právě tehdy, když $ \ker{f}=id \, $
3. $ \ker{\pi_\varrho}=\varrho \, $
4. 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)

2. $ 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 \, $
3. $ \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 \, $

4. "$ \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

Tato část je neúplná a potřebuje rozšířit. 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
2. $ 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.

Tato část je neúplná a potřebuje rozšířit. 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
2. $ M_n(T)(\cdot,I_n) \, $ je monoid
3. $ 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\} \, $
2. $ (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\}) \, $)

3. $ (M_n(T))^*=GL_n(T) \, $-invertibilní (regulární) matice, $ GL_n(T)(\cdot, ^{-1},I_n) \, $--grupa
4. $ {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

• 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 \, $

• 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é

• 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 \, $