Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 %&latex \documentclass[a4paper]{article} \frenchspacing \usepackage[cp1250]{inputenc} \usepackage{czech} \usepackage{a4wide} \usepackage{amsmath, amsthm, amssymb, amsfonts} \usepackage[mathcal]{eucal} \font\bigrm = csr10 scaled \magstep 2 \font\bigbf = csb10 scaled \magstep 4 \def\main#1{ \medskip \centerline{ \bigbf #1 } \medskip } \def\chap#1{ \medskip \centerline{ \bigrm #1 } \medskip } \def\dfn#1{ \noindent \bf Def.: \it#1 \newline } \def\dfnname#1{{\bf#1}} \def\veta#1#2#3{ \newline \noindent \bf Věta #1: #2 \it Důkaz: #3 \newline} \def\pozn#1#2#3{ \newline \noindent \bf Poznámka #1: #2 \it Důkaz: #3 \newline} \def\impl{\Rightarrow} \def\to{\rightarrow} \def\biject{\leftrightarrow} \def\exist{\exists} \def\foreach{\forall} \def\onlyif{\Leftrightarrow} \def\implr{\Leftarrow} \def\c#1{{\cal #1}} \def\mcal#1{{\bf #1}} \def\mod{{\rm mod\ }} \def\ker{{\rm ker\ }} \def\rmod{{\rm rmod}} \def\lmod{{\rm lmod}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage[normalem]{ulem} \begin{document} \section{Algebry, homomorfismy, kongruence} \dfn{ $ A $ množina, zobrazení $ \alpha : A^n \to A $, kde $ n \in \{0,1, ...\}$ je \dfnname{n-ární operace} ($n$ je \dfnname{arita}). } \dfn{ $\alpha_i, i \in I $ operace na $A$, pak $A(\alpha_i|i\in I )$ je \dfnname{algebra}.} \dfn{ mn. $B$ je \dfnname{uzavřená} na operaci $\alpha$, když $\foreach b_1, ... b_n \in B$ platí $\alpha(b_1, ... b_n) \in B$. } \dfn{ $A(\alpha_i|i\in I)$ algebra, $B\subseteq A$. $B$ je \dfnname{podalgebra} $A$, je-li uzavřená na $\alpha_i \foreach i\in I$. } \pozn{ 1.1 }{ Průnik podalgeber je podalgebra. } { Vezmu $b_1, ... b_n \in \cap_{j\in J}A_j$. Vím že $\alpha(b_1, ..b_n)\in A_j\ \foreach j\in J$. } \dfn{ Zobr. $f: A\to B$ je \dfnname{slučitelné} s operací $\alpha$, pokud $a_1, .. a_n\in A$ $\impl$ $f(\alpha_{(A)}(a_1, ... a_n )) = \alpha_{(B)}( f(a_1), ... f(a_n) )$. } \dfn{ Algebry $A$ a $B$, které mají stejný počet operací stejné arity, jsou \dfnname{algebry stejného typu}. } \dfn{ Pro algebry \uline{stejného typu} je $f:A\to B$ \dfnname{homomorfismus}, pokud je slučitelné se všemi jejich operacemi. (\forall\alpha,a_1, .. a_n\in A:\ $f(\alpha_A(a_1, ..a_n))=\alpha_B(f(a_1), ..f(a_n))$) } \pozn{$\bigstar$ 1.2 }{ Složení homomorfismů je homomorfismus. Je-li $f$ bijekce a homomorfismus, je $f^{-1}$ taky homomorfismus. } { pro 1 lib.operaci, ze slučitelnosti, z def. bijekce. } \pozn{$\bigstar$ 1.3 }{ Nechť $f:A\to B$ je homomorfismus, nechť $C$ je podalgebra $A$, $D$ podalgebra $B$. Pak $f(C)$ je podalgebra $B$ a $f^{-1}(D) = \{a\in A|f(A)\in D\}$ je podalgebra $A$. } { pro 1 lib.operaci ověřit uzavřenost, z def. homomorfismu, def. podalgebry. } \dfn{ Bijektivní homomorfismus je \dfnname{izomorfismus}(mezi množinami můžeme bez ztráty jakékoliv informace přecházet), algebry stejného typu jsou \dfnname{izomorfní}, $\exists$-li mezi nimi aspoň 1 izomorfismus. }\dfn{\dfnname{Relace} na množině $A$ je lib. podmnožina $\rho\subseteq A\times A$. $(a,b)\in\rho\stackrel{\mathrm{def}}\equiv a\rho b$, \\ $\rho^{-1} = \{(a,b)|(b,a)\in\rho\}$ - \dfnname{opačná relace}, $\rho^{+} = \{(a,c)|\exists a= b_0,..b_n =c\in A; (b_i,b_{i+1})\in\rho\}$ - \dfnname{tranzitivní obal}, $id = \{(a,a)| a\in A \}$ - \dfnname{identita}, $\rho^{-1}\subseteq\rho$ - \dfnname{symetrická}, $id\subseteq\rho$ - \dfnname{reflexivní}, $\rho^{+}\subseteq\rho$ - \dfnname{tranzitivní}. Reflexivní, symetrická a tranzitivní relace je \dfnname{ekvivalence}. }\dfn{ $A/\rho = \{ [a]_{\rho} | a \in A \}$ je \dfnname{faktorová množina}, kde $[a]_{\rho} = \{b\in A | (a,b)\in\rho\}$ jsou \dfnname{třídy ekvivalence}. }\dfn{$f:A\to B$, $\ker f: (a_1,a_2)\in \ker f \stackrel{\mathrm{def}}\equiv f(a_1) = f(a_2)$ je \dfnname{jádro} zobr. $f$.} \dfn{ \dfnname{přirozená projekce} mn. $A$ podle $\rho$ je $\pi_{\rho}: A\rightarrow A/\rho$, t.ž. $\pi_{\rho}(a) = [a]_{\rho}$. } \pozn{$\bigstar$ 1.4 }{ $f:A\to B$ zobr., $\rho$ ekviv. na $A$. (1) $\ker f$ je ekvivalence na $A$. (2) $f$ je prosté $\onlyif\ \ker f = id$. (3) $\ker \pi_{\rho} = \rho$. (4) zobr. $g:A/\rho\to B$, splňující podmínku $g\circ\pi_{\rho} = f$ existuje $\onlyif \rho\subseteq\ \ker f$ } {(1) z def. $\ker f$ se dostane z ekvivalence $"="$, (2),(3) z def., (4) $(\impl)$ vezmu $(a_1,a_2)\in\rho$, potom $f(a_1)=f(a_2)$, tedy $(a_1,a_2)\in\ \ker f$. $(\implr)$ $a_1\rho a_2 \stackrel{\rho\subseteq\ \ker f}\impl f(a_1) = f(a_2) \impl g([a_1]_{\rho}) = g([a_2]_{\rho})$, tedy g je korektně definované. } \dfn{ $\rho\subseteq\sigma$ 2 ekvivalence na $A$. Pak \dfnname{$\sigma$/$\rho$ - faktor-ekvivalence} je relace definovaná: $([a]_{\rho},[b]_{\rho})\in\sigma/\rho\ \stackrel{\mathrm{def}}\equiv (a,b)\in\sigma$. } \pozn{$\bigstar$ 1.5 }{ (1) Nechť $\rho\subseteq\sigma$ jsou ekvivalence na $A$. Pak $\sigma/\rho$ je ekvivalence na $A$. (2) Nechť $\eta$ je ekvivalence na $A/\rho$, pak ex. právě 1 ekvivalence $\sigma$ na $A$, t.ž. $\rho\subseteq\sigma$ a $\sigma/\rho = \eta$. } { (1) dokázat korektnost definice $\sigma/\rho$ - $([a_1]_{\rho} = [a_2]_{\rho}, [b_1]_{\rho} = [b_2]_{\rho}$, $(a_1,b_1)\in\sigma)$ $\impl$ (z tranzitivity $\sigma$) $(a_2,b_2)\in\sigma$. důkaz ekvivalence - přímo. (2) $\sigma$ najdu podle předpisu $([a]_{\rho},[b]_{\rho})\in\eta\onlyif(a,b)\in\sigma$, $\sigma\subset\rho$, $\sigma$ je ekvivalence (z ekvivalence $\eta$) $\impl$ ex. faktor-ekvivalence. }\dfn{\dfnname{$\mathbf{\rho}$ slučitelná s $\mathbf{\alpha$}, pokud $a_1, ... a_n, b_1, ... b_n : (a_i,b_i)\in\rho\ \foreach i \impl \alpha(a_1,...a_n) \rho\ \alpha(b_1,...b_n)$. } \dfn{\dfnname{kongruence} je každá ekvivalence slučitelná se všemi operacemi algebry.} \pozn{$\bigstar$ 1.6 }{ $f:A\to B$ je homomorfismus algeber stejného typu $\impl \ker f$ je kongruence na $A$. } { $\ker f$ je ekvivalence z 1.4(1), slučitelnost přímo z homomorfismu f } \dfn{ Relace \dfnname{$\rho$ slučitelná s $\alpha$}, pak $\alpha$ na A/$\rho$ def.: $\alpha([a_1]_{\rho},... [a_n]_{\rho}) = [ \alpha(a_1, ... a_n) ]_{\rho}$. Kongruence $\rho$ na A, pak stejným způsobem def. na A/$\rho$ strukturu algebry.} \veta{$\bigstar$ 1.7 }{ $\rho$ kongruence na $A \impl$ přirozená projekce $\pi_{\rho}:A\to A/\rho$ je homomorfismus.} { $\foreach$ operaci $\alpha$ na $A$ def. $\alpha$ na $A/\rho$ - faktor operaci, sluč. s $\pi_{\rho}$. } \pozn{$\bigstar$ 1.8 }{ Nechť $\rho$ je kongruence na $A$ a $\sigma$ ekvivalence na $A$, $\rho\subseteq\sigma$. Pak $\sigma$ je kongruence na $A$ $\onlyif$ $\sigma/\rho$ je kongruence na $A/\rho$. } { $(\impl)$ - z 1.5 plyne ekvivalence $\sigma/\rho$, dokázat slučitelnost s lib. operací $\alpha([a_1]_{\rho}, ... [a_n]_{\rho}) = [ \alpha(a_1, ... a_n) ]_{\rho}$ - ze sluč. $\sigma$. $(\implr)$ dokázat slučitelnost - to samé naopak. } \pozn{$\bigstar$ 1.9 (Věta o homomorfismu) }{ Nechť $f:A\to B$ je homomorfismus algeber stejného typu a $\rho$ kongruence na $A$. Pak (1) ex. homomorfismus $g:A/\rho\to B$, t.ž. $f=g\pi_{\rho}$, právě když $\rho\subseteq \ker f$. (2) $g$ je navíc izomorfismus, právě když $f$ je na a $\rho = \ker f$. } { (1) $(\impl)$ přímý důsledek 1.4(4), $(\implr)$ zobr. $g:g([a_i]_{\rho})=f(a_i)$ je dobře definované podle 1.4(4), slučitelnost přímo z předpokladů. (2) $(\impl)$ $(a_1,a_2)\in\rho\impl g([a_1])=f(a_1)= f(a_2)=g([a_2])$ ($g$ prosté) $\impl[a_1]=[a_2]$. $(\implr)$ dokázat prostost $g$: $f(a_1)=g([a_1])=g([a_2])= f(a_2)\ \impl\ (a_1,a_2)\in \ker f = \rho\ \impl [a_1]_{\rho} = [a_2]_{\rho}$. } \veta{$\bigstar$ 1.10 (1. věta o izomorfismu) }{ Nechť $f:A\to B$ je homomorfismus algeber stejného typu, pak $f(A)$ je algebra stejného typu a $^{A}/_{\ker f}$ je izomorfní algebře $f(A)$. } { definuji $\rho = \ker f$, z pozn. 1.9 ex. homomorfismus $g:\ ^A/_{\ker f}\to f(A)$, $g$ je na $f(A)$, protože $f$ je na $f(A)$, $\rho = \ker f$ $\impl$ $g$ je izomorfismus. } \veta{$\bigstar$ 1.11 (2. věta o izomorfismu) }{ Nechť $\rho\subseteq\eta$ jsou kongruence na algebře $A$. Pak $^{(A/\rho)}/_{(\eta/\rho)}$ je izomorfní $^A/_{\eta}$. } { z 1.9 (pro $f=\pi_{\eta}$) $\exists$ homomorfismus $g: A/\rho\to A/\eta: g([a]_{\rho})=[a]_{\eta}$. $g$ je (z def.) na, z 1.10 (pro $g$): $A/\eta\ \simeq\ ^{(A/\rho)}/_{\ker g}$. z def. $g$ $\ker g = \eta/\rho$. } \section{ Algebry s jednou binární operací } \dfn{ Algebra $G(.)$ s 1 binární operací je \dfnname{grupoid}. \\\dfnname{Neutrální prvek} je $e\in G: e. g = g. e = g\ \foreach g\in G$. Algebra $G(.,e)$ s $\cdot$ asociativní je \dfnname{monoid}. } \pozn{$\bigstar$ 2.1 }{ Každý grupoid odsahuje nevýš 1 neutrální prvek. }{ mějme $e,f$ dva neutr.prvky pak: $e=e. f=f$} \pozn{ 2.2 }{ $M(.,e)$ monoid, $a,b,c \in M$. Pokud $(a. b = e)\ \&\ (b. c = e)$, pak $a = c$ } { $a = ae = a(bc) = (ab)c = ec = c$. } \dfn{ $M(.,e)$ monoid, $m\in M$, Pak $m^{-1}\in M$ je \dfnname{inverzní prvek}, pokud $m. m^{-1} = m^{-1}. m = e$. Prvek je \dfnname{invertibilní}, pokud má nějaký inverzní prvek.} \pozn{$\bigstar$ 2.3 }{ Buď $M(.,e)$ monoid, pak $M^{*}=\{m\in M | \exists m^{-1} \}$ je jeho podmonoid. Každý inverzní prvek je invertibilní. }{ uzavřenost na $e\in M^{*}$ ; $\cdot$ pro součin 2 prvků z $M^{*}$ ex. inv. prvek; inverz k inverzu je pův. prvek z def. } \dfn{ Algebra $G(\cdot,^{-1},e)$ je \dfnname{grupa}, pokud je $G(\cdot,e)$ monoid a $^{-1}$ je operace inv. prvku. } \dfn{ \dfnname{Normální podgrupa} je každá podgrupa $H$ grupy $G$ kde $\foreach g\in G\ \foreach h\in H:g.h.g^{-1} \in H$. \\$G$ je \dfnname{komutativní (abelovská)}, pokud je $\cdot$ komutativní. } \pozn{$\bigstar$ 2.4 }{ $M(\cdot,e)$ monoid, $M^{*}$ množ. všech jeho invertibilních prvků. Omezíme-li operaci $\cdot$ na $\cdot_{M^{*}}$ na prvky z $M^{*}$ a jako $^{-1}$ vezmeme operaci inv. prvku na $M^{*}$, pak $M^{*}(\cdot_{M^{*}},^{-1},e)$ je grupa. }{ Z 2.3 je možné $\cdot$ omezit na $M^{*}$, $M^{*}$ je podmonoid $M(\cdot,e)$ z def. je grupa. } \pozn{ 2.5 }{ Každá podgrupa komutativní grupy je normální. }{$H$ podgrupa $G$ komutativní, $g\in G\ h\in H:g.h.g^{-1}=g.g^{-1}.h=1.h=h\in H$.} \veta{ 2.6 }{ Nechť $G(\cdot,^{-1},e)$ je grupa a $\rho$ relace na $G$. Pak $\rho$ je kongruence $\onlyif [e]_{\rho}$ je normální podgrupa $G$ a $(g,h)\in\rho$ právě když $g^{-1}.h\in[e]_{\rho}$. } { $"\impl":$ $\rho$ kongruence - ověřit uz. na $e$ (z refl.), uz. na $^{-1}$: $(e,h)\in\rho\impl (e^{-1}(=e),h^{-1})\in\rho$; uz. na $\cdot$: $(e,g),(e,h)\in\rho\impl(e.e,g.h)\in\rho$; z toho $[e_{\rho}]$ je podgrupa. $(e,h)\in\rho$, $g\in G$ $\impl (g^{-1}(hg),g^{-1}(eg)) = (g^{-1}gh,e)\in\rho$ (refl., sluč.)- normální podgrupa. Ověření $(g,h)\in\rho \onlyif g^{-1}h\in[e]_{\rho}$: $(\impl)$ ze sluč., vynásobit zleva $g^{-1}$, $(\implr)$ vynásobit zleva $g$. $"\implr":$ def. $\rho:(g,h)\in\rho \stackrel{\mathrm{def}}\equiv g^{-1}.h \in H$, dokázat že $\rho$ je ekvivalence (přímo), $[e]_{\rho} = H$ (přímo), slučitelnost s operacemi - $e$ platí $\foreach$ refl. relaci, $^{-1}: g^{-1}h\in H \impl h^{-1}g \in H\impl h(h^{-1}g)h \in H$, $\cdot: \bar h\bar g^{-1}\in H(=\bar g(\bar g^{-1}\bar h)\bar g^{-1})$; $\bar g^{-1}\cdot(g^{-1}\cdot h.\bar h.\bar g^{-1}).\bar g = (g\bar g)^{-1}(h\bar h)\in H$. } \dfn { \dfnname{ G/H } $= G/\rho_{h}$, kde $\rho_h$ je kongruence odp. dle 2.6 normální podgrupě $H$. } \section{ Uzávěrové systémy na algebře } \dfn{ $A$ množina, $\c{C} \subseteq\cal{P}(A)$. $\c{C}$ je \dfnname{uzávěrový systém}, pokud \bf{(1)} $A \in\c{C}$ \bf{(2)} $\{B_i|i\in I\}\subseteq \c{C}\impl\cap_{i\in I} B_i\in\c{C}$. } \dfn{ \dfnname{Uzávěr} je zobrazení $cl_{\c{C}}:\c{P}(A)\to \c{C}$ definované $cl_{\c{C}}(B) = \cap_{C\in\c{C},B\subseteq C}C$ } \dfn{ Zobrazení $\alpha:\c{P}(A)\to\c{P}(A)$ je \dfnname{uzávěrový operátor}, pokud \bf{(1)} $B\subseteq\alpha(B)\ \foreach B\in\c{P}(A)$ \bf{(2)} $\alpha(\alpha(B)) = \alpha(B)\ \foreach B\in\c{P}(A)$ \bf{(3)} $ \alpha(B)\subseteq\alpha(C)\ \foreach B\subseteq C\subseteq A$. } \pozn{ 3.1 }{ Systém všech podalgeber algebry A tvoří uzávěrový systém. }{ z 1.1 - průnik podalgeber je podalgebra - vyhovuje } \veta{$\bigstar$ 3.2 }{ (1) Je-li $\c{C}$ uzávěrový systém, pak $cl_{\c{C}}$ je uzávěrový operátor. (2) Je-li $\alpha:\c{P}(A)\to\c{P}(A)$ uzávěrový operátor, pak množina $\c{C} = \{ C\in\c{P}(A), \alpha(C)=C \}$ tvoří uzávěrový systém a $\alpha = cl_{\c{C}}$. } {(1) dokázat axiomy uz. operátoru pro $cl_{\c{C}}$ - 1. plyne z vl. $cl_{\c{C}}$, 2. obě inkluze ($\subseteq$ z 1., $\supseteq$ z 2. ax. uz. systému), 3. z teorie množin. (2) dokázat axiomy $\c{C}$ - 1. $A$ a je pevný bod $\alpha$, 2. $\alpha(\cap_{i\in I}B_i) = \cap_{i\in I}B_i$ - $\supseteq$ z 1.ax.uz.op, $\subseteq$ z 3.ax.uz.op., dokázat že $\alpha(B)= \cap_{C\in\c{C},B\subseteq C}C\ \foreach B$ - $\alpha(B)\in\c{C}$ podle 2.ax.uz.op., $B\subseteq\alpha(B)$ z 1.ax. $\impl\alpha(B)\supseteq cl(B)$. $\alpha(B)\subseteq\cap\{C\in\c{C},B\subseteq C\}, \alpha(B)\subseteq\alpha(C) = C$ - z 3.ax. } \pozn{$\bigstar$ 3.3 }{ Množina všech uzávěrových systémů na množině $A$ tvoří uzávěrový systém na $\c{P}(A)$. } {1.ax.: $A\subseteq\c{P}(A), \cap_{B_i\in\c{P}(A)}B_i\in\c{P}(A)$, 2.ax.: $\cap_{i\in I}\c{C}_i$ uz. systém?: 1.ax.: $\c{P}(A)$ je uz. systém; $A\in\cap_{i\in I}\c{C}_i$, 2.: $B_j\in\cap_{i\in I}\c{C}_i\ j\in J\impl\ \cap_{j\in J}B_i\in\cap_{i\in I}\c{C}_i$. } \pozn{ 3.4 }{ Nechť $\c{A}$ a $\c{B}$ jsou 2 uz. systémy na $A$; $C,D\subseteq A$, t.ž. $\c{A}\subseteq\c{B}$ a $C\subseteq D$, potom $cl_{\c{B}}(C)\subseteq cl_{\c{A}}(D)$. } {$cl_{\c{B}}(C)\subseteq cl_{\c{B}}(D)$ platí dle 3.2(1), $cl_{\c{B}}(D)\subseteq cl_{\c{A}}(D)$ rozepsat jako průniky množin, z teorie množin jako 3.2(1)-3. } \pozn{ 3.5 }{ Množina věch reflexivních(symetrických, tranzitivních) relací a množina všech ekvivalencí na množině $A$ tvoří uzávěrový systém na $A\times A$. } { pro reflexivní $id\subset A\times A$, $id\subset\cap_{i}\rho_i$, kde $\rho_i$ je refl. - OK, symetrická a tranzitivní podobně, ekvivalence z 3.3 a průniku předch. } \pozn{ 3.5 }{ Všechny kongruence na algebře tvoří uzávěrový systém na $A\times A$. }{ pro každou operaci zvl. množina sluč. relací $\c{R}_i$ je uz. systém, kongruence z průniku (je průnik uz. systém?). 1.ax $A\times A$ je sluč. s čímkoliv, 2.ax přímo } \pozn{ }{ Nechť $\rho$ je relace na $A$ Je-li reflexivní(symetrická), pak $\rho^{+}$ a $\rho\cup\rho^{-1}$ je taky reflexivní(symetrická).}{ přímo. } \pozn{ 3.6 }{ Nechť $\rho$ je relace, pak $((\rho\cup id)\cup(\rho\cup id)^{-1})^{+} = (\rho\cup\rho^{-1}\cup id)^{+}$ je nejmenší ekvivalence obs. $\rho$ (uzávěr $\rho$ v uz. systému ekvivalencí). }{ ekvivalence z předchozí pozn., minimalita zřejmá (musím mít zaručenu refl., sym. i trans.) } \dfn{ Nechť $A$ je algebra, $X\subseteq A$, $\c{A}$ je uz. systém všech podalgeber. Pak $cl_{\c{A}}(X)$ je \dfnname{ podalgebra generovaná množinou } $X$. } \pozn{ 3.7 }{ Nechť $f, g: A\to B$ jsou 2 homomorfismy algeber stejného typu a $cl_{\c{A}}(X) = A$. Pokud $f(x)=g(x)\ \foreach x\in X$ (mn. generátorů), pak $f = g$. } { Vezmu $Y = \{a\in A | f(a) = g(a)\}$, $Y\supseteq X$, dokážu sluč. s lib. operací $\impl Y$ je podalgebra, $cl_{\c{A}}(Y)\supseteq cl_{\c{A}}(X)$. } \section{ Svazy } \dfn{ Relace $\leq$ na mn. $A$ je (částečné) \dfnname{uspořádání}, pokud je reflexivní, tranzitivní a slabě antisymetrická (tj. $a\leq b, b\leq a\impl a=b$). } \dfn{ Pro usp. $\leq$ na $A$, $B\subseteq A$ je $a\in B$ \dfnname{nejmenší(největší) prvek}, jestliže $\foreach b \in B\ a\leq b (\foreach b\in B\ b\leq a)$. $m\in A$ je \dfnname{infimum(supremum)} množiny $B$, jde li o největší prvek množiny $\{a\in A| a\leq b\ \foreach b\in B\}$ (nejmenší prvek množiny $\{a\in A|b\leq a\ \foreach b\in B\}$). Značení: $\inf_{\leq} B\ (\sup_{\leq} B)$. } \dfn{ Dvojici $(A,\leq)$ nazvu \dfnname{svazem}, je-li $\leq$ uspořádání a $\foreach$ dvojici $\{a,b\}\subseteq A$ ex. $\sup_{\leq}(\{a,b\})$ a $\inf_{\leq}(\{a,b\})$. } \dfn{ O svazu $(A, \leq)$ řekneme, že je \dfnname{úplný}, jestliže ex. $\inf_{\leq}(B)$, resp. $\sup_{\leq}(B)$ pro $\foreach B\subseteq A$ (implikuje existenci nejv. a nejm. prvku) } \dfn{ $\forall a,b\in A$ označme bin.operace \dfnname{spojení} $m\vee n=\sup_{\leq}(\{m,n\})$ a \dfnname{průsek} $m\wedge n=\inf_{\leq}(\{m,n\})$} \pozn{$\bigstar$ 4.1 }{ Buď $A(\wedge,\vee)$ svaz pak platí: (1) $a\wedge b = b\wedge a$, $a\vee b = b\vee a$, (2) $a\vee a = a = a\wedge a$, (3) $a\wedge(b\wedge c) = (a\wedge b)\wedge c$ (pro $\vee$ stejně), (4) $a\wedge(b\vee a) = a = a\vee(b\wedge a )$. (pro $a,b$ lib. z $A$). } { (1),(2) \textbraceleft a,b\textbraceright=\textbraceleft b,a\textbraceright, (3) z def. suprema a tranzitivity $a\leq(a\vee b)\vee c$, stejně pro b,c; proto pro nejmenší horní odhad $\{b,c\}$, tj. $b\vee c$ platí taky; dále nejm. odhad $\{a,(b\vee c)\}$ $\impl$ $a\vee(b\vee c)\leq(a\vee b)\vee c$, zpět symetricky. (4) $a\leq a\vee(b\wedge a)$ z def. suprema, opačně platí - horní odhady $(b\wedge a)\leq a$. } \pozn{$\bigstar$ 4.2 }{ Buď $S(\wedge,\vee)$ algebra s 2 bin. operacemi pro něž platí 4.1. Definujme relaci $\leq$ na $S$: $a\leq b \stackrel{\mathrm{def}}\equiv (a\vee b = b)$. Potom $(S,\leq)$ tvoří svaz, kde $\sup_{\leq}(\{a,b\}) = a\vee b$, $\inf_{\leq}(\{a,b\}) = a\wedge b$. Tj. můžeme "svaz" říkat algebře $S(\wedge,\vee)$. } { a): ověřit že $\leq$ je uspořádání (přímo), pak $a\leq b \equiv a = a\wedge b$ (z def., 4.1(1)), potom $\inf_{\leq}\{a,b\} = a\wedge b$: $a\wedge b\leq a, a\wedge b\leq b$ (z 4.1) $\impl a\wedge b\leq \inf\{a,b\}$, pak $c\leq a, b \impl c\leq(a\wedge b)$. (pro $\sup$ symetricky). } \veta{$\bigstar$ 4.3 }{ Každý uzávěrový systém $\c{C}$ je úplným svazem $(\c{C},\subseteq)$, kde $\sup_{\subseteq}(\c{B}) = cl_{\c{C}}(\cup\c{B})$ a $\inf_{\subseteq}(\c{B}) = cl_{\c{C}}(\cap\c{B})$. } {$\subseteq$ je zjevně uspořádání. $\bigcap\mathcal{B}\in\mathcal{C}$, $\bigcap\mathcal{B}\subseteq B\ \forall B\in\mathcal{B}$, $X\subseteq B\ \forall B\in\mathcal{B}\Rightarrow X\subseteq\bigcap\mathcal{B}$. $\forall B\in\mathcal{B}\quad B\subseteq\bigcup\mathcal{B}\subseteq \cl_\mathcal{C}(\bigcup\mathcal{B})\in\mathcal{C}$. } \pozn{$\bigstar$ 4.4 }{ Je-li $S(\wedge,\vee)$ svaz, potom je $S(\vee,\wedge)$ taky svaz (opačný svaz) }{ plyne z (4.1), (4.2) - opačný svaz s opačným uspořádáním } \dfn{ Nechť $S(\wedge,\vee)$ je svaz, potom $a$ \dfnname{pokrývá} b ($b<\cdot a$), pokud $a,b,c\in S:\ b\leq a,\ b\neq a,\\ b\leq c\leq a\impl b = c$ nebo $a = c$. }\dfn{ \dfnname{Hasseův diagram} svazu je graf s vrcholy z $S$, mezi $a,b$ bude hrana že $a$ bude \dfnname{pod} $b$, pokud $a<\cdot b$. } \pozn{$\bigstar$ 4.5 (slabá modularita) }{ Nechť $S(\wedge,\vee)$ je svaz, $a,b,c\in S$. Pokud $a\leq c$, potom $a\vee(b\wedge c)\leq (a\vee b)\wedge c)$ } { z dolních odhadů : $a\leq((a\vee b)\wedge c)$, $b\wedge c\leq((a\vee b)\wedge c)$ } \dfn{ $S(\wedge,\vee)$ je \dfnname{modulární}, pokud $\foreach a,b,c\in S:a\leq c\impl\ a\vee(b\wedge c) = (a\vee b)\wedge c$. } \dfn{ $S(\wedge,\vee)$ je \dfnname{distributivní}, pokud $\foreach a,b,c\in S: a\vee(b\wedge c) = (a\vee b)\wedge (a\vee c)$. } \pozn{$\bigstar$ 4.6 }{ $S(\wedge,\vee)$ distributivní $\Leftrightarrow$ pokud je opačný $S(\vee,\wedge)$ distributivní }{ $(\Rightarrow)$ $(a\wedge b)\vee (a\wedge c) = ((a\wedge b)\veea)\wedge ((a\wedge b)\veec) = a\wedge ((a\wedge b)\veec) = a \wedge ((a \vee c) \wedge (b \vee c)) = (a \wedge (a \vee c)) \wedge (b \vee c) = a \wedge (b \vee c)$. $(\Leftarrow)$ to samé opačně} \pozn{$\bigstar$ 4.7 }{ Každý distributivní svaz je modulární }{$a\vee(b\wedge c) = (a\vee b)\wedge (a\vee c)\stackrel{a\leq c}=(a\vee b)\wedge c$ } \veta{ 4.8 }{ $S(\wedge,\vee)$ modulární $\Leftrightarrow$ obsahuje podsvaz pentagon }{ dokážeme že pentagon není modulární, S pokud je modulární nemůže obsahovat podsvaz izomorfní s pentagonem, pokud S není modulární... } \dfn{ Nechť $0\in S\ (1\in S)$ je nejmenší(největší) prvek $S$, potom $a$ nazveme \dfnname{atom(koatom)} svazu $S$, jestliže $0<\cdot a$ $(a<\cdot 1)$. \dfnname{Komplement $a'\in S$} k $a\in S$ je def. $a\vee a'=1$ a $a\wedge a'=0$} \pozn{ 4.9 }{ Každý prvek distr. svazu má nejvýše 1 komplement }{ b,c komplementy a. Pak $b = b \wedge 1 = b\wedge(a\vee b\wedge a)\vee(b\wedge c) = b\wedge c$. Tudíž $b \geq c$. Obdobně dostaneme $b \leq c$, a tedy $b = c$. } \dfn{\dfnname{Booleovou algebrou} nazveme $S(\vee,\wedge,0,1,')$, že $S(\wedge,\vee)$ je distributivní svaz s nejv. prvkem $1$ a nejm. $0$ a unární operace $'$ která přiřadí každému prvku komplement} \pozn{ 4.10 }{ $S(\vee,\wedge,0,1,')$ je Booleova algebra, $\forall a,b\in S$ platí: (1) $(a')'=a$, (2) $(a\vee b)'=a'\wedge b'$, (3) $(a\wedge b)'=a' \vee b'$, (4) $(1)'=0$ $(0)'=1$}{ (1) podle 4.9 (2)(3) $(a \wedge b) \vee (a' \vee b' ) = (a \vee a' \vee b' ) \wedge (b \vee a' \vee b' ) = 1 \wedge 1 = 1. (a \wedge b) \wedge (a' \vee b' ) = (a \wedge b \wedge a' ) \vee (a \wedge b \wedge b' ) =0 \vee 0=0$ } \dfn{ $f:A\to B$, kde $(A,\leq),(B,\leq)$ jsou svazy. Pak $f$ je \dfnname{monotónní}, pokud $\foreach a_1,a_2 \in A: a_1\leq a_2\impl f(a_1)\leq f(a_2)$ (opačné se nepoužívá). } \veta{$\bigstar$ 4.11 }{ $S(\vee,\wedge,0,1,')$ je konečná Booleova algebra a A je množina všech atomů svazu S. Potom $\varphi: P(A)\to S$ dané $\varphi(A)=\vee_B$ je izomorfismus bool. algeber $S(\vee,\wedge,0,1,')$ a $P(A)(\cup,\cap,\emptyset,X,')$}{ TODO (15.2) } \pozn{$\bigstar$ 4.12 }{ Homomorfismus svazů je monotónní. }{ $a\leq b \impl$(4.2) $b = a\vee b\impl f(b) = f(a\vee b) = f(a)\vee f(b)\ \impl\ f(a)\leq f(b)$. } \veta{$\bigstar$ 4.13 }{ Bijekce svazů $f$ je izomorfismus $\onlyif$ $f$ i $f^{-1}$ jsou monotónní. } { $(\impl)$ zřejmé (4.12); $(\implr)$ sluč. s $\vee$ (podle (4.4) platí i pro $\wedge$). Z monotonie a odhadů $f(a)\vee f(b)\leq f(a\vee b)$, z monotonie $f^{-1}$ $a\vee b\leq f^{-1}(f(a)\vee f(b))$, aplikovat $f$, vyjde op. nerovnost. $f$ je bijekce, proto i $f^{-1}$ je homomorfismus. } \pozn{$\bigstar$ 4.14 }{ Nechť $A$ je množina, $e\in A$, $\c{C}$ je uz. systém na $A\times A$, obsažený v množině všech ekvivalencí (tj. podmnožina množiny ekvivalencí), systém podmnožin $\c{N} \subseteq \c{P}(A)$. Nechť platí: (1) $[e]_{\rho}\in\c{N}\ \foreach\rho\in\c{C}$, (2) $\foreach N\in\c{N}\ \exists\rho\in\c{C} :\ N = [e]_{\rho}$, (3) $\foreach \rho,\eta\in \c{C}: [e]_{\rho}\subseteq [e]_{\eta}\ \impl\ \rho\subseteq\eta$. Pak $\c{N}$ tvoří uzávěrový systém, zobrazení $\varphi:\c{C}\to\c{N}: \varphi(\rho) = [e]_{\rho}$ je svazový izomorfismus. } { $\c{N}$ je usp. množina; $\varphi$ je dobře definované, na z (1),(2); z (3) je prosté - $\varphi(\rho) = \varphi(\eta) \impl \rho=\eta$ $\impl$ je bijekce, $\varphi^{-1}([e]_{\rho}) = \rho$. Z (3) je $\varphi^{-1}$ monotónní, $\rho\subseteq\eta: \varphi(\rho) = [e]_{\rho}\subseteq[e]_{\eta} = \varphi(\eta)$ - $\varphi$ je monotónní. Mám bijekci oběma směry mezi svazem a usp. množinou $\impl$ mám na $\c{N}$ i $\c{C}$ stejnou strukturu vzhledem k $\subseteq$. Proto $\c{N}$ je uz. systém, zbytek z (4.13). } \veta{$\bigstar$ 4.15 }{ Množina všech normálních podgrup grupy tvoří svaz, izomorfní svazu všech kongruencí. }{ podle (4.14) - z (2.6) $[e]_{\rho}, \rho\in\c{C}$ je norm. podgrupa $\impl$ (4.14(1)) OK, $\foreach N\in\c{N}: \rho_N:(a,b)\in\rho_N\stackrel{\mathrm{def}}\equiv a^{-1}b\in N$ je z (2.6) kongruence a $N=[e]_{\rho_N}$ $\impl$ (4.14(2)) OK, $[e]_{\rho}\subseteq[e]_{\eta}$ z (2.6) $\impl \rho\subseteq\eta$ $\impl$ (4.14(3)) OK. $\varphi(\rho) = [e]_{\rho}$ je izomorfismus. } \dfn{Nechť A a B jsou množiny. Dvojici zobrazeni $\alpha: \mathcal{P}(A)\to\mathcal{P}(B)$ a $\beta : \mathcal{P}(B)\to\mathcal{P}(A)$ se říka \dfnname{Galoisova korespondence}, jsou-li $\forall A_1,A_2 \in \mathcal{P}(A)$ a $\forall B_1,B_2 \in\mathcal{P}(B)$ splněny následující podmínky: \textbf{(1)} $A_1\subseteq A_2 \impl \alpha(A_2) \subseteq \alpha(A_1)$ a $B_1 \subseteq B_2 \impl \beta(B2)\subseteq \beta(B1)$, \textbf{(2)} $A_1 \subseteq \beta\alpha(A_1)$ a $B_1 \subseteq \alpha\beta(B1)$.} \veta{$\bigstar$ 4.16 }{ Buď $\alpha : \mathcal{P}(A) \to \mathcal{P}(B)$ a $\beta : \mathcal{P}(B) \to \mathcal{P}(A)$ Galoisova korespondence. Potom jsou zobrazení $\beta\alpha$ a $\alpha\beta$ uzávěrové operátory. Označme A a B uzávěrové systémy příslušné uzávěrovým operátorům $\beta\alpha$ a $\alpha\beta$. Pak $\alpha(A) \subseteq B$ a $\beta(B) \subseteq A$. Označíme-li $\alpha' : A \to B$ a $\beta' : B \to A$ příslušné restrikce zobrazení $\alpha$ a $\beta$, pak $\alpha'$ a $\beta'$ jsou bijekce a $\alpha' = (\beta')^{-1}$. Navíc $\forall A_1,A_2 \in A$ a $\forall B_1,B_2 \in B$ platí, že $A_1 \subseteq A_2 \onlyif \alpha(A_2) \subseteq \alpha(A_1)$ a $B_1 \subseteq B_2 \onlyif \beta(B_2) \subseteq \beta(B_1)$. }{ Z $A_1 \subseteq A_2 \subseteq A$ podle \textbf{(1)} dostáváme $\alpha(A_1 ) \supseteq \alpha(A_2 )$, a opět podle \textbf{(1)} $\beta\alpha(A_1 ) \subseteq \beta\alpha(A_2 )$. Podle 4.14 je $\beta\alpha\beta\alpha(A_1 ) = \beta\alpha(A_1 )$. Dokázali jsme, že $\beta\alpha$ je uzávěrový operátor. Podobně je i $\alpha\beta$ uzávěrový operátor. Je-li $A_1 \subseteq A$, je $\alpha\beta\alpha(A_1 ) = \alpha(A_1 )$, a tudíž $\alpha(A_1 ) \in \mathcal{B}$. Podobně $\beta(B_1 ) \in \mathcal{A}$ pro $B_1 \subseteq B$. Pro $A_1 \in \mathcal{A}$ je $\beta\alpha(A_1 ) = A_1$ a pro $B_1 \in \mathcal{B}$ je $\alpha\beta(B_1 ) = B_1$ , takže $\alpha'$ a $\beta'$ jsou vzájemně inverzní. Jsou-li $A_1, A_2 \in \mathcal{A}$, tak z $A_1 \subseteq A_2$ plyne $\alpha(A_1 ) \supseteq \alpha(A_2 )$ podle \textbf{(1)}. Platí-li $\alpha(A_1 ) \supseteq \alpha(A_2 )$, tak $A_1 = \beta\alpha(A_1 ) \subseteq \beta\alpha(A_2 ) = A_2$ . } \section{ Grupy } \pozn{ 5.1 }{ Je-li zobr. $f:G\to H$, kde $G,H$ jsou grupy, slučitelné s bin. operací $\cdot$ , pak je homomorfismus. } { pro $e$: $f(e) = f(e.e) = f(e).f(e)$. $f(e)^{-1}$ ex. (z def. grupy), zleva jím vynásobit. pro $^{-1}$: $e = f(e) = f(g.g^{-1}) = f(g).f(g^{-1})$, opačné symetricky, chová se jako inverz k $f(g)$. } \dfn{ $H,K\subseteq G(\cdot,^{-1},1),\ g\in G:\ \dfnname{HK}$= \{$h.k |\ h\in H\,k\in K\}, \ \dfnname{gH}= \{g\}H,\ \dfnname{Hg}= H\{g\}$ \\$H$ podgrupa $G$, pak def. relace: $(a,b)\in \dfnname{rmod_H$} \stackrel{\mathrm{def}}\equiv ab^{-1}\in H$, $(a,b)\in \dfnname{lmod_H$} \stackrel{\mathrm{def}}\equiv a^{-1}b\in H$. } \pozn{$\bigstar$ 5.2 }{ Pro $G(\cdot,^{-1},1)$, $H$ podgrupa $G$ a $a,b\in G$ platí: (1) $\rmod_H$ i $\lmod_H$ jsou ekvivalence. (2) $(a,b)\in \rmod_H \onlyif (a^{-1},b^{-1})\in \lmod_H$ (pro norm. podgrupy $\lmod$ a $\rmod$ splývají a jsou navíc kongruence). (3) $|G/\rmod_H| = |G/\lmod_H|$, (4) $[a]_{\rmod_H} = Ha$, $[a]_{\lmod_H} = aH$, (5) $|[a]_{\rmod_H}| = |[a]_{\lmod_H}| = |H|$. } { (1) reflexivní z uzavřenosti $H$ na $e$, symetrické z uz. $H$ na $^{-1}$, tranzitivní z uz. $H$ na $\cdot$, detail viz (2.6) pro norm. podgrupy. (2) přímo z def., symetrie $\lmod$. (3) ex. bijekce z $\lmod_H$ do $\rmod_H$: $f:G\to G: f(g) = f(g^{-1})$ (involuce), proto mám bijekci $g: G/\rmod_H\to G/\lmod_H: g( [a]_{\rmod_H} ) = [a^{-1}]_{\lmod_H}$. (4) $[a_{\rmod_H}] = \{ x\in G|\exists h\in H: h^{-1}a = x \} = Ha$, $\lmod_H$ symetricky. (5) def. zobr. $b: H\to Ha: b(h) = ha$. zjevně na, prosté: $h_1 a = b(h_1) = b(h_2) = h_2 a$, vynásobit $a^{-1}$ zprava. } \dfn{ $H$ podgrupa $G(\cdot,^{-1},1)$. \dfnname{Index} podgrupy $H$ v $G$ je číslo $[G:H] = |G/\rmod_H| = |G/\lmod_H|$. \dfnname{Řád} $G$ je $|G|$. } \veta{$\bigstar$ 5.3 (Lagrange) }{ Je-li $H\leq G(\cdot,^{-1},1)$, pak $|G| = [G:H]\cdot|H|$. } { $|G| = |\dot\cup \{A\ |\ A\in G/\rmod_H\}| = \sum_{A\in G/\rmod_H}|A| $(5.2(5))$= \sum_{A\in G/\rmod_H}|H|$ $= |H|\cdot[G:H]$. } \pozn{$\bigstar$ 5.4 (důsledek) }{ Velikost podgrupy dělí velikost konečné grupy - \textbar H\textbar/\textbar G\textbar. }{ plyne z (5.3) } \dfn{ Grupa $G(\cdot,^{-1},1)$ a $a\in G$. Definujme \dfnname{indukci}: $a^0=1$, $a^n=a^{n-1}.a$ $\forall n>0$, $a^n=(a^{-1})^{-n}.a$ $\forall n<0$, } \pozn{ 5.5 }{ Je-li $\varphi:\mcal{Z}\to G:\varphi_g (n) = g^{n}$, kde $g\in G(\cdot,^{-1},1)$, pak $\varphi$ je grupový homomorfismus $\mcal{Z}(+,-,0)$ do $G(\cdot,^{-1},1)$ a $\varphi(\mathbb{Z})=\{g^z|z\in\mathbb{Z}\}=\langle g\rangle$. } { Podle (5.1) slučitelnost s $\cdot$ stačí. Přímo, zvl. případy pro $\varphi(m+n)$, kde $m,n \geq,< 0$. Podle 1.3 $\varphi(\mathbb{Z})$ je podgrupa $G$, $g=g^{-1}$, $\forall$ podgrupa s $g$ obsahuje $g\cdot.. g$ a $g^{-1}\cdot.. g^{-1}$ (obojí k-krát) $\forall k\in\mathbb{N}$, tedy $\varphi(\mathbb{Z})=\langle g\rangle$.} \dfn{ Pro $G(\cdot,^{-1},1), g\in G$ je $\langle g\rangle = \langle\{g\}\rangle$ nejmenší podgrupa obs. prvek $g$.\\ $G$ je \dfnname{cyklická}, pokud $\exist g\in G:\ \langle g\rangle = G$. \dfnname{Řád prvku} cyklické grupy je nejmenší mocnina daného prvku, že výsledkem je neutrální prvek.} \pozn{ 5.6 }{ (1) $\forall H$ podrupa $\mcal{Z}(+,-,0)$ $\exists k\geq0,k\in\mcal{Z}$ t.ž. $k\mcal{Z} =\langle k\rangle = H$ ($\foreach$ podgrupa je cyklická). (2) $\foreach H$ podrupa $ \mcal{Z_n}(+,-,0) (n\in \mcal{N})\ \exist k:\ k=0$ nebo $k|n$, t.ž. $k\mcal{Z_n}=\langle k\rangle=H$. } { $H=\{0\}$ triv. příp., vezmu $H\ne \{0\}$. $\exist k\in H, k>0$, vezmu nejmenší takové. $\langle k\rangle\subseteq H$, $a\in H$ lib., vydělím $a\div k$ se zbytkem $y = a + k\cdot(.-x)$. $a\in H, k(-x)\in H \impl y\in H$, $y 0:$ z (5.5) dostanu izomorfismus $\psi: \mcal{Z}\to \mcal{Z}_n$, z (3.4) $\mcal{Z}_n \simeq \mcal{Z}/n\mcal{Z}\ \simeq\ \mcal{Z}/\ker \varphi\ \simeq\ G$ - dostanu (2). } \pozn{$\bigstar$ 5.8 (důsledek)}{ Každá (1) podgrupa a (2) faktorová grupa cyklické grupy je cyklická. } { (1) $G$ z (5.7) a (5.6); (2) pro $g, \langle g\rangle=G$: $\langle [g]_{\rho}\rangle = G/\rho$. } \pozn{$\bigstar$ 5.9 }{ Nechť $G(\cdot,^{-1},1)$ je konečná grupa, Pak $\foreach g\in G: g^{|G|} = 1$. } { $g^k = 1$, kde $k=|\langle g\rangle|$ (z izomorf. s $\mcal{Z}_k$), podle (5.4) $k\ |\ |G|$, $g^{|G|} =$(důsledek 5.5),(5.4) $(g^{k})^{{|G|\over k}} = 1^{{|G|\over k}} = 1$. } \veta{$\bigstar$ 5.10 }{ Nechť $G(\cdot,^{-1},1)$ je konečná cyklická grupa a $k | |G|$, pak $\exists! H\leq G$, t.ž. $|H| = k$. } { $k=1\impl H = \{0\}$, $k>1: H=\langle {n \over k}\rangle=\{0,{n\over k},{2n\over k},...{(k-1)n\over k}\}$. Jednoznačnost: $|K|=k, \exist a: K=\langle a\rangle$ $K\simeq\mcal{Z}_k (1\biject a,x\biject(ax)\mod n)$. $\exist b\in Z: ka=bn$, $a=b({n\over k})\ \impl\ a$ leží v $\langle k\rangle$. $K$ a $\langle k\rangle$ jsou 2 stejně velké konečné mn. - ex. izomorfismus. } \pozn{ 5.11 }{ (1) Nechť $n\in\mcal{N}, a\in\mcal{Z}_n$, $k=NSD(a,n)$, Pak $a\mcal{Z}_n=k\mcal{Z}_n$. (2) $a\mcal{Z}_n = \mcal{Z}_n\ \onlyif\ NSD(a,n)=1$. } { (1) $k=(ax)+ny = (ax) \mod n$, $k|a$ $\impl$ $\exists\mu:(k\mu)\mod n=a$ $\impl$ $a\in\langle k\rangle$. (2) $(\implr)$ plyne z (1) pro $k=1$. $(\impl)$: $\exists x,y: ax+ny = 1$, $c|a,c|n\impl c|1$, tj. $NSD(a,n)=1$. } \dfn{ Zobrazení $\varphi:\mcal{N}\to\mcal{N}$: $\varphi(n)=|\{k|01 \}|$. (2) na $\mcal{Z}_n\times\mcal{Z}_m$ definovat násobení, dostanu "součinový" monoid. $f:\mcal{Z}_{mn}\to \mcal{Z}_n\times\mcal{Z}_m: f(k) = (k \mod n, k \mod m)$ je homomorfismus (přímo ověřit slučitelnost s $"\cdot", 1$), je prosté ($f(k)=f(l), k\leq l$ - $k\ \mod n = l\ \mod n, k\ \mod m = l\ \mod m$, z nesoudělnosti $n,m$ $l=k$). je i na (2 stejně velké konečné mn.) $\impl$ je izomorfismus. $(a,b)\in \mcal{Z}_n\times\mcal{Z}_m$ je invertibilní $\onlyif a,b$ jsou invertibilní v $\mcal{Z}_{nm}$. $\varphi(nm)=$(z 5.12)$|\mcal{Z}^{*}_{nm}| = |(\mcal{Z}_n\times\mcal{Z}_m)^{*}|=|\mcal{Z}_n^{*}\times\mcal{Z}_m^{*}|=|\mcal{Z}_n^{*}|\cdot|\mcal{Z}_m^{*}| =$(5.12)$\varphi(n).\varphi(m)$. } \veta{$\bigstar$ 5.17 }{ Je-li $n=p_1^{k_1}.p_2^{k_2}\cdot....p_l^{k_l}$ prvočíselný rozklad čísla $n$, t.j $p_i$ jsou prvočísla, $p_i\not =p_j\ i\not =j, k_i\geq1$, pak $\varphi(n)=\Pi_{i=1}^{l}(p_i - 1)p_i^{k_i - 1}$. } { indukcí z (5.16(2)), úprava výrazu podle (5.16(1)) } \veta{ 5.18 }{ Nechť $T$ je těleso s operacemi $+,\cdot$. $(T-\{0\})(\cdot,^{-1},1)$ je komutativní grupa (z lin. algebry). Nechť $G$ je konečná podgrupa $(T-\{0\})(\cdot,^{-1},1)$. Pak je $G$ cyklická. } { bez důkazu. } \section{ Okruhy a ideály } \dfn{ Nechť $R(+,\cdot,-,0,1)$ je algebra, t.ž. $R(+,-,0)$ tvoří komutativní grupu, $R(\cdot,1)$ je monoid a platí $a(b+c)=ab+ac$ a $(a+b)c=ac+bc\ \foreach a,b\in R$ (distributivita). Pak je $R$ \dfnname{okruh}. Pokud je $\cdot$ komutativní pak R je \dfnname{komutativní okruh}} \pozn{ 6.1 }{ Pro každé 2 prvky $a,b\in R(+,\cdot,-,0,1)$ platí: (1) $0a = a0 = 0$, (2) $(-a)b=a(-b)=-(ab)$, (3) $(-1).b=b.(-1)=-b$, (4) $(-a)(-b)=ab$, (5) $|R|>1 \onlyif 0 \not =1$ }{ (1)$\ 0.a=(0+0).a=0.a+0. a\Rightarrow 0=0.a$; (2)$\ 0=0.b=(a+(-a)).b=a.b+(-a).b\Rightarrow -(a.b)=(-a).b$; (3)$\ 0=0.b=(1+(-1)).b=1.b+(-1).b\Rightarrow (-1).b=-b$; (4)$(-a).(-b)=-(a.(-b))=-(-(a.b))=a.b$; (5) předp. že $0=1$, $\forall r\in R$, $r=1.r=0.r=0$, tedy $R=\{0\}$. } \dfn{ Nechť $R(+,\cdot,-,0,1)$ je okruh a $I\subseteq R$. Pak $I$ je \dfnname{pravý(levý) ideál}, pokud $I$ podgrupa $R(+,-,0)$ (je i normální, protože $R$ je komutativní) a $\foreach i\in I, r\in R: i.r\in I$ (levý $r.i\in I$) (důsledek: uzavřenost $I$ na násobení). $I$ je \dfnname{ideál}, pokud je pravý a zároveň levý ideál. } \dfn{ Ideál je \dfnname{netriviální} nebo \dfnname{vlastní}, pokud $I\not =\{0\}$ a $I\not = R$ . $a\in R\quad aR=\{a.r|r\in R\}$ je \dfnname{hlavní pravý ideál}, $Ra=\{r.a|r\in R\}$ je \dfnname{hlavní levý ideál}.} \veta{$\bigstar$ 6.2 }{ Buď $R(+,\cdot,-,0,1)$ okruh. Pak zobrazení, které kongruenci $\rho$ na okruhu $R$ přiřadí $[0]_{\rho}$ je izomorfismus svazu všech kongruencí a svazu všech ideálů (tj. $[0]_{\rho}$ je ideál). Navíc $(a,b)\in\rho \onlyif a+(-b)\in[0]_{\rho}$. } { z (4.14), předp. (4.14(1)) - $\rho$ je kongruence i na $R(+,-,0)$, $[0]_{\rho}$ je norm. podgrupa (z (2.6),(4.15)), ověřit $\foreach i\in[0]_{\rho},\ \foreach r\in R: ir\in[0]_{\rho}, ri\in[0]_{\rho}$ - z $(i,0)\in\rho, (r,r)\in\rho$, $\rho$ sluč. s $"\cdot"$. (4.14(2)) z 2.6 $\rho$ kongruence na $R(+,-,0)$, dokázat slučitelnost s $"\cdot", 1$ - $"1"$ z reflexivity; $"\cdot":$ $(a_1,a_2)\in\rho$, $(b_1,b_2)\in\rho$, $(a_1-a_2)b_1 \in I$, $a_2(b_1-b_2)\in I$ $\impl$ $(a_1 b_1)-(a_2 b_2)=(a_1 -a_2)b_1+a_2(b_1 -b_2)\in I$. (4.14(3)) $\rho,\eta:[0]_{\rho}\subseteq[0]_{\eta} \impl \rho\subseteq\eta$ - platí i pro systém kongruencí na $R(+,-,0)$ z (4.15), ten je větší $\impl$ platí. } \dfn{\dfnname{Invertibilním prvkem} okruhu $R(+,\cdot,-,0,1)$ rozumíme invertibilní prvek monoidu $R(\cdot, 1)$. Okruh nazvu \dfnname{tělesem}, je-li každý jeho nenulový prvek invertibilní ($R^*=R\smallsetminus\{0\}$). Ideál $I$ je \dfnname{maximální}, jestliže $I$ je koatom ve svazu všech ideálů. } \pozn{6.3}{$R(+,\cdot,-,0,1)$ je okruh a $a\in R$, $a$ je invertibilní $\onlyif$ $aR=Ra=R$}{ Je-li $Ra = R$, $\exists c \in R$, že $ca = 1$. Je-li $c$ inverzní prvek $a$, je $r = rca \in Ra$ $\forall r \in R$ } \veta{$\bigstar$ 6.4}{V netriviálním $R(+,\cdot,-,0,1)$ je ekvivalentní: (1) $R(+,\cdot,-,0,1)$ je těleso, (2) $\{0\}, R$ jsou jediné pravé ideály okruhu, (3) $\{0\}, R$ jsou jediné levé ideály okruhu \end{enumerate} }{$(\Rightarrow)$ Buď $I$ pravý ideál $\neq \{0\}$, tj. $\exists i\in I\quad i\neq 0$. $R$ je těleso, tedy ke každému prvku existuje inverzní prvek, $1=i.i^{-1}\in I$. Tedy $\forall r\in R\quad r=1.r\in I$ a proto $I=R$. \\ ($\Leftarrow$) Oveříme existenci inverzního prvku pro $a\in R\smallsetminus\{0\}$. Vezměme pravý ideál $aR$ a pro ten platí $0\neq a=a.1\in aR\neq\{0\}$. $aR=R$ tj. $\exists b\quad a.b=1$ (mohu předpokládat že $0\neq 1$), $b\neq 0$ dle 6.1 Stejný argument značí, že $bR=R$ tj. $\exists c\quad b.c=1$. Tedy $a=c$, tj. $b=a^{-1}$. } \veta{$\bigstar$ 6.5}{Je-li $R(+,\cdot,-,0,1)$ komutativní okruh, $I$ je ideál, pak $R/I(+,\cdot,-,0,1)$ je těleso právě tehdy když $I$ je maximální. }{ Je-li $J$ ideál, pak dle věty 6.2 je $\varrho_J$ kongruence odpovídající $J$. $J$ je koatom právě tehdy když $\varrho_J$ je koatom. Dle věty 6.2 stačí dokázat, že $R/I$ je tělesem právě tehdy když $\varrho_I$ je koatom ve svazu kongruencí na $R(+,\cdot,-,0,1)$ (dle tvrzení 1.8, je-li $\eta$ ekvivalence na $R/\varrho_I$, potom $\exists\sigma\supseteq\varrho_I\quad \eta=\sigma/\varrho_I$). Tedy $\id$ a $R/I\times R/I$ jsou jediné kongruence na $R/I(+,\cdot,-,0,1)$. Dle věty 6.4 je $R/I(+,\cdot,-,0,1)$ těleso právě tehdy když obsahuje právě $\{[0]_{\varrho_I}\},R/I$, což jsou jediné ideály, a tedy dle věty 6.2 za $R/I$ máme právě kongruence $\underbrace{\varrho_{\{[0]\}_{\varrho_I}} }_{id}$ a $\underbrace{\varrho_{R/I}=R/I\times R/I}_{R/I\times R/I}$. } \dfn{$a\in R, n\in\mathbb{Z}$ \bf(1) $0\times a & = & 0\in R$, (2) $n\times a & = & ((n-1)\times a)+a\quad\forall n>0$, (3) $n\times a & = & |n|\times(-a)\quad\forall n<0$ } \pozn{6.6}{ Definujme zobrazení $\varphi:\mathbb{Z}\to R$ předpisem $\varphi(n)=n\times 1$. Pak $\varphi$ je okruhový homomorfismus ($\mathbb{Z}(+,\cdot,-,0,1)$ a $R(+,\cdot,-,0,1)$), $\varphi(\mathbb{Z})$ je nejmenší podobraz $R$ obsahující $1$ a existuje jednoznačně určené $p\in\mathbb{N}_0$ takové, že $ \{n\in\mathbb{Z}|\varphi(n)=0\}=p\mathbb{Z}. $ }{ Podle 5.5 je $\varphi$ homomorfismus grupy $\mathbb{Z}(+,-,0)$, $R(+,-,0)$, navíc $\varphi(\mathbb{Z})=\gen{1}$. $\varphi(1)=1\times 1=1$, $\varphi(a).\varphi(b)=(a\times 1).(b\times 1)=a\times(b\times 1)\stackrel{\mathrm{\ref{imp:5_6}}}{=}(a\times b)\times 1=\varphi(a.b)$. $\varphi(\mathbb{Z})$ je podokruh dle 1.1, tedy $\varphi(\mathbb{Z})$ je nejmenší podokruh. Buď $I=\{n|\varphi(n)=0\}$, platí $n\in I\quad \varphi(-n)=-\varphi(n)=-0=0$, $n+m\in I\quad \varphi(n+m)=\varphi(n)+\varphi(m)=0+0=0$, tedy $I$ je podgrupa $\mathbb{Z}(+,-,0)$. Dle tvrzení 5.6 $\exists p\ge 0\quad p\mathbb{Z}=I$. } \dfn{ \dfnname{Charakteristikou okruhu} $R(+,\cdot,-,0,1)$ rozumíme $p$ z poznámky 6.6. } \pozn{6.7}{ Buď $R(+,\cdot,-,0,1)$ komutativní okruh, $a,b\in R$ $n\in\mathbb{N}$ $(a+b)^n=(\underbrace{(a+b).\dots\cdot(a+b)}_{n})=\sum_{k=0}^{n}{{n \choose k}\times a^k.b^{n-k}} $ }{ Stejně jako v $\mathbb{R}$. } \pozn{ 6.8 (důsledek) }{ Buď $R(+,\cdot,-,0,1)$ komutativní okruh prvočíselné charakteristiky $p$. Pak zobrazení $R\to R:a\to a^p$ je okruhový homomorfismus (Frobeniův). }{ Platí $(a+b)^p=a^p+\underbrace{\left(\sum_{k=1}^{p-1}{{p\choose k}\times a^k.b^{p-k}}\right)}_{p\textrm{ dělí tento člen}}+b^p=a^p+b^p$. Dle 5.1 je $a\to a^p$ homomorfismus na $R(+,-,0)$ a $R(+,-,0)$, $1^p=1$ a $(a.b)^p=a^p.b^p$. } \dfn{Komutativní okruh $R(+,\cdot,-,0,1)$ je \dfnname{obor integrity} pokud $\forall a,b\in R$ platí $ a.b=0\Rightarrow$ $a=0$ nebo $b=0$ $ ($a\neq 0, b\neq 0\Rightarrow a.b\neq 0$). } \pozn{$\bigstar$ 6.9}{Pro algebru $F(+,\cdot,-,0,1)$ (1) $F(+,0)$, $F(\cdot,1)$ jsou komutativní monoidy, (2) $\sim$ je kongruence na algebře $F(+,\cdot,-,0,1)$, (3) $(0,1)\sim(0,a)$ a $(1,1)\sim (a,a)$ $\forall a\in R\smallsetminus\{0\}$, (4) $F/\sim(+,\cdot,-,[0]_\sim,[1]_\sim)$ je komutativní těleso, (5) $R\to F/\sim:r\to[(r,1)]_\sim$ je prostý okruhový homomorfismus. \end{enumerate} } {} \dfn{Komutativní těleso $F/\sim(+,\cdot,-,[0]_\sim,[1]_\sim)$ nazýváme \dfnname{podílovým tělesem}, píšeme $\frac{a}{b}$=$[(a,b)]_\sim$} \end{document}