ALGEBRA I PRO INFORMATIKY

JAN ŽEMLIČKA

Úvod

Velmi zhruba řečeno je centrálním objektem zájmu algebry množina opatřená jistým systémem operací. Přitom nás mohou zajímat nejen strukturní vlastnosti takové množiny popsané podmínkami vyjádřené právě pomocí operací, nýbrž i vztahy různých množin s podobnými systémy operací či vlastnosti tříd takových množin.

Dříve než se začneme systematicky zabývat abstraktními úvahami o takových algebraických objektech (které se budou zpravidla opírat o nějaký systém axiomatických požadavků na operace), uveďme 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.

Příklad 0.1. Uvažme množinu celých čísel Z a na ní obvyklé operace sčítání + a násobení ·. Pro libovolné přirozené číslo n položme nZ = {n · z| z ∈ Z}. Nyní si můžeme všimnout, že je množina nZ ţuzavřená” na obě uvažované operace, tj. pro každou dvojici a, b ∈ nZ platí, že a + b, a · b ∈ nZ, tedy operace + a · můžeme uvažovat také omezeně na množině nZ. Ačkoli pro žádné n > 1 množiny nZ 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 → nZ 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 · e = a”, pak je tato podmínka na množině Z splněna pro e = 1, zatímco na množině nZ zjevně neplatí.

Příklad 0.2. V souladu se značením zavedeným na kurzu lineární algebry položme Z_{n} = {0, 1, …, n − 1} pro nějaké celé číslo n > 1. Zaveďme na Z_{n} operace + a · předpisem a + b = (a + b)mod n a a · b = (a · b)mod n, kde mod 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 → Z_{n} předpisem F_{n}(k) = (k)mod n. Všimněme si, že tentokrát zobrazení F sice není bijekce, ale obě operace sčítání a násobenní ţpřevádí” na nově zavedené + a ·, tedy F_{n}(a+b) = F_{n}(a)+F_{n}(b) i F_{n}(a · b) = F_{n}(a) · F_{n}(b).

Definice. Binární operací na množině A budeme rozumět libovolné zobrazení A × A → A (obvykle ji budeme zapisovat centrálně). Máme-li binární operaci ∗ na množině A, nějakou podmnožinu U množiny A a binární operaci ∘ na množině B. Řekneme, že U je uzavřená na operaci ∗, jestliže pro všechna x, y ∈ U platí, že x ∗ y ∈ U, a zobrazení f : A → B nazveme slučitelné s operacemi ∗ a ∘ je-li pro všechna x, y ∈ A splněna rovnost f(x ∗ y) = f(x) ∘ f(y).

Date: 19.1.2010.

Všimněme si, že zobrazení f_{n} z 0.1 je slučitelné s operacemi + a není slučitelné s operacemi ·, zatímco zobrazení F_{n} z 0.2 je slučitelné s oběma páry operací + i ·.

Příklad 0.3. Vezměme přirozené číslo n ≥ 2 a označme ∼_{n} relaci na množině celých čísel Z danou předpisem: a ∼_{n} b ↔ n/(a − b). Není těžké si uvědomit, že se jedná o ekvivalenci (obvykle se jí říká kongruence na Z), která splňuje pro všechna taková celá a_{1}, a_{2}, b_{1}, b_{2}, že a_{1} ∼_{n} b_{1} a a_{2} ∼_{n} b_{2} podmínky (a_{1} + a_{2}) ∼_{n} (b_{1} + b_{2}) a (a_{1} · a_{2}) ∼_{n} (b_{1} · b_{2}). Navíc si můžeme všimnout jejího těsného vztahu k zobrazení F_{n} z 0.2, neboť platí, že a ∼_{n} b, právě když F_{n}(a) = F_{n}(b).

Připomeňme, že relací na množině A rozumíme libovolnou podmnožinu A × A.

Definice. Uvažujme na množině A binární operaci ∗ a relaci ∼. Řekneme, že ∼ je slučitelná s operací ∗, jestliže pro všechny takové prvky a_{1}, a_{2}, b_{1}, b_{2} ∈ A, pro něž a_{1} ∼ b_{1} a a_{2} ∼ b_{2} platí, že (a_{1} ∗ a_{2}) ∼ (b_{1} ∗ b_{2}).

V Příkladu 0.3 jsme tedy zjistili, že je ţkongruence” ∼_{n} slučitelná s oběma operacemi + i ·.

Příklad 0.4. Mějme kladná celá čísla n_{1}, …, n_{k} a položme n = n_{1} · n_{2} · · · · · n_{k}. Zaveďme nyní na kartézském součinu ∏_{i=1}^{k} Z_{n_{i}} po složkách operace + a ·: (a_{1}, a_{2}, …, a_{k}) + (b_{1}, b_{2}, …, b_{k}) = (a_{1} + b_{1}, a_{2} + b_{2}, …, a_{k} + b_{k}) a (a_{1}, a_{2}, …, a_{k}) · (b_{1}, b_{2}, …, b_{k}) = (a_{1} · b_{1}, a_{2} · b_{2}, …, a_{k} · b_{k}) a definujme zobrazení G : Z → ∏_{i=1}^{k} Z_{n_{i}} předpisem G(a) = ((a)mod n_{1}, …, (a)mod n_{k}) a stejným předpisem zavedeme i zobrazení H : Z_{n} → ∏_{i=1}^{k} Z_{n_{i}}. Obě zobrazení jsou opět slučitelná s + a ·.

Tvrzení této a následující kapitoly budou bez důkazu využívat základních poznatků teorie čísel, především jednoznačnost (až na pořadí) ireducibilního rozkladu a Euklidova algoritmu na nalezení největšího společného dělitele.

V následující poznámce budeme uvažovat operace na kartézských součinech zavedené v Příkladu 0.4.

Poznámka 0.5 (Čínská věta o zbytcích). Nechť n_{1}, n_{2}, …, n_{k} jsou po dvou nesoudělná kladná celá čísla a n = n_{1} · n_{2} · · · · · n_{k}, potom zobrazení f : Z_{n} → ∏_{i=1}^{k} Z_{n_{i}} dané předpisem f(x) = (x mod n_{1}, x mod n_{2}, …, x mod n_{k}) je bijekce slučitelná s operací + a s operací ·.

Důkaz. Přímo z definice snadno vidíme, že je f zobrazení slučitelné s oběma operacemi. Zbývá nahlédnout, že jde o bijekci. Protože jsou Z_{n} a ∏_{i=1}^{k} Z_{n_{i}} stejně velké konečné množiny, stačí ověřit, že je f prosté. Nechť pro a ≤ b ∈ Z_{n} platí, že f(a) = f(b). Potom f(b − a) = 0, tedy n_{i}/b − a pro všechna i = 1, …, k. Protože jsou n_{i} po dvou nesoudělná a 0 ≤ b − a ≤ n − 1, máme i n/b − a, tudíž b = a. □

Čínská věta o zbytcích nám umožňuje ţalgebraicky” přesně reprezentovat větší množinu Z_{n} pomocí počítání v menších množinách Z_{n_{i}}, což je postup, který se při potřebě exaktního počítání s velkými čísly (například při práci s velkými prvočísly) často používá.

Definice. Zobrazení φ : N → N dané předpisem φ(n) = |{0 < k < n| NSD(k, n) = 1}| nazveme Eulerovou funkcí.

Poznámka 0.6. Je-li p prvočíslo a k kladné celé číslo, pak φ(p^{k}) = (p − 1) · p^{k−1}.

Důkaz. Číslo menší než p^{k} je soudělné s p^{k}, právě když je násobkem čísla p. Kladných násobků čísla p menších než p^{k} je zřejmě právě p^{k−1} − 1. To znamená, že naopak kladných čísel nesoudělných s p^{k} máme φ(p^{k}) = (p^{k} − 1) − (p^{k−1} − 1) = p^{k} − p^{k−1} = (p − 1)p^{k−1}. □

Věta 0.7. Buď p_{1} < p_{2} < ⋯ < p_{k} prvočísla a r_{1}, r_{2}, …, r_{k} kladná celá čísla. Potom φ(∏_{i=1}^{k} p_{i}^{r_{i}}) = ∏_{i=1}^{k} φ(p_{i}^{r_{i}}) = ∏_{i=1}^{k} (p_{i} − 1)p_{i}^{r_{i}−1}.

Důkaz. Zvolme libovolné a ∈ Z_{n}. Položme n = ∏_{i=1}^{k} p_{i}^{r_{i}} a (a_{1}, …, a_{k}) = f(a). Podle 0.5 je zobrazení f : Z_{n} → ∏_{i=1}^{k} Z_{p_{i}^{r_{i}}} bijekce. Abychom ověřili rovnost

φ(∏_{i=1}^{k} p_{i}^{r_{i}}) = ∏_{i=1}^{k} φ(p_{i}^{r_{i}}), stačí nám nahlédnout, že NSD(a, n) = 1 právě tehdy, když NSD(a_{i}, n_{i}) = 1 pro všechna i = 1, …, k, protože ∏_{i=1}^{k} φ(n_{i}) = | ∏_{i=1}^{k} {a ∈ Z_{n_{i}} \ {0}| NSD(a, n_{i}) = 1}|.

Jestliže NSD(a, n) ≠ 1, existuje prvočíslo p, které dělí n, a díky jednoznačnosti prvočíselného rozkladu tudíž existuje i, pro něž p dělí n_{i}. Tedy buď a_{i} = 0 nebo p dělí a_{i}, proto NSD(a_{i}, n_{i}) ≠ 1. Naopak, jesliže NSD(a_{i}, n_{i}) ≠ 1, pak existuje dělitel c > 1 čísel a_{i} i n_{i}, proto c dělí i a = a_{i} + xn_{i} i n = n_{1} … n_{i} … n_{k}.

Konečně rovnost ∏_{i=1}^{k} φ(p_{i}^{r_{i}}) = ∏_{i=1}^{k} (p_{i} − 1)p_{i}^{r_{i}−1} plyne okamžitě z 0.6 □

Příklad 0.8. Nechť X je neprázdná množina písmen a M(X) je množina všech slov, tj. všech konečných posloupností písmen. Zaveďme na této množině binární operaci skládání ·: x_{1} … x_{n} · y_{1} … y_{m} = x_{1} … x_{n}y_{1} … y_{m} a dále označme λ prázdné slovo. Snadno nahlédneme, že je operace · asociativní (je-li X aspoň dvouprvková množina, pak operace není komutativní) a platí, že λ · s = s · λ = s pro každé s ∈ M(X).

Mějme dvě slova a, b ∈ M(X). Obsahuje-li slovo s_{a} podposloupnost a, slovo s_{b} vznikne ze slova s_{a} tak, že podposloupnost a v s_{a} nahradíme podposloupností b. Ztotožníme-li všechny takové dvojice slov, t.j. zavedeme-li podmínkou s_{a} ∼ s_{b} a s_{b} ∼ s_{c} relaci ∼ na M(X), pak ∼ bude ekvivalence slučitelná s operací ·.

1. Množiny s asociativní binární operací

Připomeňme, že binární operace ∗ na A je asociativní (resp. komutativní), platí-li pro všechna x, y, z ∈ A rovnost x ∗ (y ∗ z) = (x ∗ y) ∗ z (resp. x ∗ y = y ∗ x).

Definice. Uvažujme binární operací ∗ na množině A. Neutrálním prvkem operace ∗ rozumíme takový prvek e ∈ A, že g ∗ e = e ∗ g = g pro všechna g ∈ A.

Poznámka 1.1. Každá binární operace má nejvýše jeden neutrální prvek.

Důkaz. Jsou-li e, f dva neutrální prvky, pak e = e ∗ f = f. □

Příklad 1.2. Je-li X aspoň dvouprvková množina a definujeme-li na X binární operaci ∗ předpisem x ∗ y = x, je operace ∗ asociativní, ale X neobsahuje žádný neutrální prvek. Přitom dokonce každý prvek X splňuje první z rovností, kterou je neutrální prvek definován.

Definice. Nechť · je binární operace na množině S a 1 její neutrální prvek. Řekneme, že prvek s ∈ S je invertibilní, existuje-li takový prvek s^{−1} ∈ S, že s^{−1} · s = s · s^{−1} = 1. Prvek s^{−1} nazveme inverzním prvkem k prvku s.

Definice. Množině G s binární operací · budeme říkat grupoid (a budeme psát G(·)). O grupoidu G(·) řekneme, že je:

- pologrupa, je-li operace · asociativní,

- monoid, je-li operace · asociativní a v G leží její neutrální prvek,

- grupa, je-li G(·) monoid, jehož každý prvek je invertibilní,

- komutativní grupa (nebo abelovská grupa), je-li G(·) grupa a · je komutativní.

V Příkladech 0.1 a 0.3 jsme připomněli asociativní a komutativní operace + a · na množině celých čísel (a v Příkladech 0.2 a 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í.

Příklad 1.3. (1) Množina M(X) z Příkladu 0.8 tvoří s operací skládání (tzv. slovní) monoid.

(2) Buď X nějaká neprázdná množina a označme T (X) množinu všech zobrazení množiny X do sebe. Potom T (X)(∘) tvoří (s operací skládání ∘) (tzv. transformační) monoid.

(3) Čtvercové matice M_{n}(T) nad tělesem T stupně n spolu s násobením tvoří monoid M_{n}(T)(·) (neutrálním prvkem je zde jednotková matice).

Nestanovíme-li jinak, bude v následujícím 1 označovat neutrální prvek operace · (a 0 pro operaci +) a s^{−1} bude inverzní prvek k s vzhledm k operaci · (a −s bude inverz vzhledem k operaci +).

Poznámka 1.4. Buď S(·) monoid a a, b, c ∈ S. Platí-li, že a · b = c · a = 1, potom b = c je jednoznačně určený inverzní prvek k prvku a.

Důkaz. Stačí ověřit, že b = c. S využitím asociativity počítejme: c = c·1 = c·(a·b) = (c · a) · b = 1 · b = b. □

Příklad 1.5. Uvažujme transformační monoid T (N) na množině všech přirozených čísel a nechť α(k) = 2k a β(k) = [\frac{k}{2}]. Pak βα = Id a αβ ≠ Id. Prvky α a β monoidu T (N) splňují právě jednu z definitorických rovností invertibilního prvku, invertibilní tedy nejsou (a podle 1.4 být nemohou).

Poznámka 1.6. Množina všech invertibilních prvků monidu S(·) je uzavřená na operaci ·. Je-li navíc s invertibilní prvek, pak i s^{−1} je invertibilní a (s^{−1})^{−1} = s.

Důkaz. Označme S^{∗} množinu invertibilních prvků monidu S(·) Vezmeme-li prvky g_{1} a g_{2} z S^{∗}, platí, že existují prvky h_{1}, h_{2} ∈ S, pro něž g_{i} · h_{i} = h_{i} · g_{i} = 1, kde i = 1, 2. Tedy (g_{1} · g_{2}) · (h_{2} · h_{1}) = g_{1} · (g_{2} · h_{2}) · h_{1} = g_{1} · 1 · h_{1} = g_{1} · h_{1} = 1 a symetricky (h_{2} · h_{1}) · (g_{1} · g_{2}) = 1.

Druhá vlastnost plyne okamžitě z definitorické podmínky s · s^{−1} = s^{−1} · s = 1 a z 1.4. □

Poznámka 1.7. Nechť S(·) je monoid a S^{∗} množina všech jeho invertibilních prvků. Označíme-li ·_{S^{∗}} restrikci ·|_{S^{∗}×S^{∗}} operace · na množinu S^{∗} × S^{∗}, pak S^{∗}(·_{S^{∗}}) je grupa.

Důkaz. Podle 1.6 je množina S^{∗} uzavřená na operaci ·, proto je ·|_{S^{∗}×S^{∗}} dobře definovaná asociativní binární operace na S^{∗}. Protože 1 · 1 = 1, leží neutrální prvek 1 v množině S^{∗}. Konečně, S^{∗} obsahuje inverzní prvky opět díky 1.6. □

Příklad 1.8. (1) Grupa invertibilních prvků slovního monoidu M(X)(·) obsahuje pouze neutrální prvek e.

(2) Grupu invertibilních prvků transformačního monoidu T (X)(∘) tvoří právě všechny bijekce S(X) na množině X (mluvíme o symetrické grupě nebo grupě permutací).

(3) Grupu invertibilních prvků monoidu čtvercových matic M_{n}(T)(·) stupně n tvoří právě všechny regulární matice stupně n.

Definice. Podgrupou grupy G(·) budeme rozumět každou neprázdnou podmnožinu H množiny G, která je uzavřená na · a pro jejíž každý prvek h ∈ H platí, že h^{−1} ∈ H. Normální podgrupa je podgrupa H grupy G splňující navíc podmínku g · h · g^{−1} ∈ H pro každé g ∈ G a h ∈ H.

Poznámka 1.9. Nechť G(·) je grupa, H a H_{i}, i ∈ I její podgrupy.

(1) 1 ∈ H,

(2) H(·) tvoří s operací omezenou na množinu H opět grupu,

(3) ⋂_{i∈I} H_{i} je podgrupa grupy G(·),

(4) jsou-li všechny podgrupy H_{i} normální, pak je i podgrupa ⋂_{i∈I} H_{i} normální,

(5) je-li G(·) komutativní grupa, pak je podgrupa H vždy normální.

Důkaz. (1) Protože je H neprázdná, obsahuje nějaké h ∈ H. Tedy h^{−1} ∈ H a 1 = h · h^{−1} ∈ H.

(2) Díky (1) obsahuje H neutrální prvek vzhledem k ·, zbytek plyne okamžitě z definice podgrupy a vlastností operace · na G (srovnej s 1.6).

(3) 1 ∈ H_{i} pro všechna i ∈ I podle (1), tedy ⋂_{i∈I} H_{i} je neprázdná. Zvolme libovolně a, b ∈ ⋂_{i∈I} H_{i}. Potom a · b ∈ H_{i} pro každé i ∈ I díky uzavřenosti H_{i} na operaci ·, tedy a · b ∈ ⋂_{i∈I} H_{i}. Podobně podle definice a^{−1} ∈ H_{i} pro každé i ∈ I, proto a^{−1} ∈ ⋂_{i∈I} H_{i}.

(4) Zvolme h ∈ ⋂_{i∈I} H_{i} a g ∈ G. Pak g · h · g^{−1} ∈ H_{i} pro všechna i ∈ I, a tudíž g · h · g^{−1} ∈ ⋂_{i∈I} H_{i}.

(5) Díky komutativitě binární operace platí pro každé g ∈ G a h ∈ H, že g · h · g^{−1} = g · g^{−1} · h = h ∈ H. □

Příklad 1.10. (1) Všimněme si, že v každé grupě G(·) tvoří množiny {1} a G (tzv. 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 nZ = {n · z| z ∈ Z} jsou pro každé nezáporné celé n podgrupou grupy Z(+) (viz 0.1). Napak, uvažujme libovolnou nenulovou podgrupu P grupy Z(+). Protože P obsahuje nějaký nenulový prvek a s každým a ∈ P je i −a ∈ 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 = nZ. Indukcí díky uzavřenosti P na sčítání nahlédneme, že 2n = n + n ∈ P, 3n ∈ P, …, kn ∈ P, …, pro každé přirozené k. Protože −n ∈ P, dostanem stejným argumentem, že nZ ⊆ P. Nyní zvolme libovolně a ∈ 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 ∈ P plyne, že z = a + (−qn) ∈ P, a z minimality volby n dostáváme, že z = 0, tedy nZ = P.

(3) Uvažujme grupu permutací na množině {1, …, n}, obvykle se značí S_{n}(∘) (viz také 1.8(2)). Snadno nahlédneme, že množina všech sudých permutací A_{n} je normální podgrupou S_{n}(∘). Navíc lze (elemntárními prostředky) dokázat, že grupa S_{n}(∘) neobsahuje pro n ≠ 4 jiné normální podgrupy než {Id}, S_{n} a A_{n} (v případě S_{4} se vyskytuje ještě jedna další výjimečná normální podgrupa). Uveďmě alespoň příklad zjevné podgrupy T = {Id, (12)} grupy S_{3}, která není normální, protože například (13) ∘ (12) ∘ (13)^{−1} = (23) ∉ T.

Definice. Nechť H a K jsou dvě podmnožiny grupy G(·) a g ∈ G. Definujme množiny HK = {h·k| h ∈ H, k ∈ K}, gH = {g}H a Hg = H{g}. Je-li H podgrupa G, definujme na G relaci rmod H (resp. lmod H) podmínkou: (a, b) ∈ rmod H (resp. (a, b) ∈ lmod H) ⇔ a · b^{−1} ∈ H (resp. ·a^{−1}b ∈ H).

Příklad 1.11. Mějme dvě normální podgrupy H a K grupy G(·). Pak pro každé h_{0} ∈ H a k ∈ K existuje h_{1} ∈ H, pro které k · h_{0} · k^{−1} = h_{1}, tedy k · h_{0} = h_{1} · k a KH ⊆ HK. Symetrický argument dokazuje i obrácenou inkluzi, proto KH = HK. Nyní snadno nahlédneme, že je součin HK rovněž podgrupou G(·): zřejmě je HK neprázdné a zvolíme-li h_{0}, h_{1} ∈ H a k_{0}, k_{1} ∈ K, potom (h_{0} · k_{0})^{−1} = k_{0}^{−1} · h_{0}^{−1} ∈ KH = HK a dále existuje takové h_{2} ∈ H, že k_{0} · h_{1} = h_{2} · k_{0}, proto h_{0} · k_{0} · h_{1} · k_{1} = h_{0} · h_{2} · k_{0} · k_{1} ∈ HK. Konečně vezmeme-li libovolné prvky g ∈ G, h ∈ H a k ∈ K, pak platí g · h · k · g^{−1} = (g · h · g^{−1}) · (g · k · g^{−1}) ∈ 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}).

Relací na množině A budeme rozumět každou podmnožinu A × A Nechť ρ je relace na A, označme:

- ρ^{−1} = {(b, a)| (a, b) ∈ ρ} (opačná relace),

- ρ^{+} = {(a, b)| ∃a = a_{0}, a_{1}, …, a_{n−1}, a_{n} = b ∈ A; (a_{i}, a_{i+1} ) ∈ ρ} (tranzitivní obal),

- id = {(a, a)| a ∈ A} (identita). Řekneme, že relace ρ je symetrická, jestliže ρ^{−1} ⊆ ρ, tranzitívní, pokud ρ^{+} ⊆ ρ,

a reflexivní, v případě, že id ⊆ ρ. Ekvivalencí budeme nazývat každou symetrickou, tranzitívní a reflexivní relaci.

Definice. Nechť ρ je ekvivalence na množině A. Definujme faktor množiny (často se říká také kvocient) A podle ekvivalence ρ jako množinu A/ρ = {[a]_{ρ}| a ∈ A}, kde [a]_{ρ} = {b ∈ A| (a, b) ∈ ρ}, a přirozenou projekci zobrazení π_{ρ} : A → A/ρ dané podmínkou π_{ρ}(a) = [a]_{ρ}.

Všimněme si, že je-li ρ ekvivalence na A, pak A/ρ = {[a]_{ρ}| a ∈ A} tvoří rozklad množiny A. Naopak máme-li {B_{i}| i ∈ I} rozklad množiny A, pak relace ρ určená podmínkou: (a, b) ∈ ρ ⇔ ∃i ∈ I : a, b ∈ B_{i} je ekvivalencí a A/ρ = {B_{i}| i ∈ I}.

Poznámka 1.12. Nechť G(·) je grupa a H její podgrupa. Potom platí:

(1) rmod H i lmod H jsou ekvivalence na G,

(2) (a, b) ∈ rmod H ⇔ (a^{−1}, b^{−1}) ∈ lmod H pro každé a, b ∈ G,

(3) |G/rmod H)| = |G/lmod H|,

(4) rmod H = lmod H, právě když je H normální podgrupa G(·),

(5) [a]_{rmod H} = Ha a [a]_{lmod H} = aH pro každé a ∈ G,
(6) |[a]_{rmod H}| = |[a]_{lmod H}| = |H| pro každé a ∈ G.

Důkaz. (1) Tvrzení dokážeme jen o rmod H, pro lmod H bude důkaz symetrický. Podle 1.9(1) podgrupa H obsahuje neutrální prvek 1, proto pro každé a ∈ G máme a · a^{−1} = 1 ∈ H, tedy (a, a) ∈ rmod H. Předpokládáme-li, že (a, b) ∈ rmod H, pak a · b^{−1} ∈ H, proto i b · a^{−1} = (a · b^{−1})^{−1} ∈ H (podle 1.4 a 1.6), tudíž (b, a) ∈ rmod H. Nyní předpokládejme, že (a, b), (b, c) ∈ rmod H, což podle definice naší relace znamená, že a · b^{−1}, b · c^{−1} ∈ H. Z uzavřenosti H na binární operaci plyne, že (a · b^{−1}) · (b · c^{−1}) ∈ H, tedy a · c^{−1} = a · b^{−1} · b · c^{−1} ∈ H a (a, c) ∈ rmod H. Tím jsme ověřili, že je relace rmod H reflexivním, symetrická a tranzitivní.

(2) Díky 1.6 máme rovnost a · b^{−1} = (a^{−1})^{−1} · b^{−1}, proto a · b^{−1} ∈ H ⇔ (a^{−1})^{−1} · b^{−1} ∈ H, čímž jsme dokončili důkaz.

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

(4) Předpokládejme, že rmod H = lmod H a zvolme h ∈ H a g ∈ G. Potom (g ·h)^{−1} ·g = h^{−1} ·g^{−1} ·g = h^{−1} ∈ H, tedy (g ·h, g) ∈ lmod H = rmod H. Z definice rmod H dostaneme g · h · g^{−1} ∈ H.

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

(5) Opět se budeme věnovat jen ekvivalenci rmod H. Použijeme definici rozkladové třídy:

[a]_{rmod H} = {b ∈ A| (a, b) ∈ rmod H} = {b ∈ A| ∃h ∈ H : a · b^{−1} = h} =

= {b ∈ A| ∃h ∈ H : b = h^{−1} · a} = {b ∈ A| ∃h′ ∈ H : b = h′ · a} = Ha.

(6) Definujme zobrazení b : H → Ha (resp. H → aH) předpisem b(h) = h · a (resp. b(h) = a · 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} · a = h_{1} · a. Tuto rovnost zprava (resp. zleva) přenásobíme hodnotou a^{−1}, abychom dostali h_{0} = h_{0} · a · a^{−1} = h_{1} · a · 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 (5). □

Definice. Buď H podgrupa grupy G(·). Potom číslu [G : H] = |G/rmod H| (= |G/lmod H| podle 1.12) budeme říkat index podgrupy H v grupě G a velikosti |G| množiny G budeme říkat řád grupy G.

Věta 1.13 (Lagrange). Je-li H podgrupa grupy G(·), pak |G| = [G : H] · |H|.

Důkaz. Podle 1.12(1) je rmod H ekvivalence, proto G = ˙⋃_{A∈G/rmod H}A, kde sjednocujeme disjunktní množiny. Využijeme-li dále poznatek 1.12(6), který říká, že všechny ekvivalenční třídy mají počet prvků stejný jako množina H, pak dostáváme

|G| = |⋃^{∘}_{A∈G/rmod H}A| = ∑_{A∈G/rmod H} |A| = ∑_{A∈G/rmod H} |H| = [G : H] · |H|.
□

Důsledek 1.14. Je-li G konečná grupa, potom řád každé její podgrupy dělí řád grupy G.

Všimněme si, že grupa prvočíselného řádu obsahuje jen triviální podgrupy.

Věta 1.15. Nechť G(·) je grupa a ρ relace na G. Pak ρ je ekvivalence slučitelná s operací · právě tehdy, když H = [1]_{ρ} je normální podgrupa G(·) a ρ = rmod H.

Důkaz. (⇒) Nejprve předpokládejme, že je ρ je ekvivalence slučitelná s operací ·. Protože je ρ reflexivní relace, leží 1 v třídě [1]_{ρ} a ta je tudíž neprázdná. Zvolme a, b ∈ [1]_{ρ} a g ∈ G. Vidíme, že (1, a), (1, b) ∈ ρ, navíc, z reflexivity ρ plyne, že (a^{−1}, a^{−1}), (g^{−1}, g^{−1}), (g, g) ∈ ρ. Nyní využijeme slučitelnosti ρ s ·, abychom dostali, že (1·1, a·b) ∈ ρ, dále že (1·a^{−1}, a·a^{−1}) ∈ ρ a (g ·1·g^{−1}, g ·a·g^{−1}) ∈ ρ. Využijeme-li vlastností neutrálního prvku a symetrie ρ, vidíme, že (1, a·b), (1, a^{−1}), (1, g·a·g^{−1}) ∈ ρ, tedy a·b, a^{−1}, g ·a·g^{−1} ∈ [1]_{ρ}, čímž máme ověřeno, že je [1]_{ρ} normální podgrupa G(·). Připomeňme, že podle 1.12(4) rmod [1]_{ρ} = lmod [1]_{ρ}.

Nyní bychom měli dokázat, že (a, b) ∈ ρ, právě když (a, b) ∈ lmod [1]_{ρ}. Jestliže nejprve (a, b) ∈ ρ, potom (1, a^{−1} · b) = (a^{−1} · a, a^{−1} · b) ∈ ρ, protože je ρ ekvivalnce slučitelná s ·, tedy (a, b) ∈ lmod [1]_{ρ}. Naopak, zvolíme-li (a, b) ∈ lmod [1]_{ρ}, pak (a, b) = (a · 1, a · a^{−1} · b) ∈ ρ.

(⇐) Předpokládejme, že je H normální podgrupa G(·) a definujme relaci ρ jako rmod H (tj. (a, b) ∈ ρ ↔ a · b^{−1} ∈ H). Podle 1.12(1) je ρ ekvivalence a přímým výpočtem zjistíme, že [1]_{ρ} = H. Zvolme nyní (a_{0}, b_{0}), (a_{1}, b_{1}) ∈ ρ, tj. a_{0} · b_{0}^{−1} i a_{1} · b_{1}^{−1} jsou prvky H. Nyní použijeme normalitu H, abychom dostali, že b_{0}^{−1} · a_{0} = b_{0}^{−1} ·(a_{0} ·b_{0}^{−1})·b_{0} ∈ H. Uzavřenost H na · zaručuje, že b_{0}^{−1} ·a_{0} ·a_{1} ·b_{1}^{−1} ∈ H a dalším využitím normality získáme a_{0} · a_{1} · (b_{0} · b_{1})^{−1} = b_{0} · (b_{0}^{−1} · a_{0} · a_{1} · b_{1}^{−1}) · b_{0}^{−1} ∈ H, tedy (a_{0} · a_{1}, b_{0} · b_{1}) ∈ ρ, čímž jsme ověřili slučitelnost ρ s s operací ·. □

Poznámka 1.16. Nechť G(·) a H(·) jsou grupy a f : G → H je zobrazení slučitelné s operací ·. Pak je f(1) = 1 a f(g^{−1}) = (f(g))^{−1} pro každé g ∈ G.

Důkaz. Protože f(1) = f(1 · 1) = f(1) · f(1), stačí rovnost f(1) = f(1) · f(1) přenásobit prvkem f(1)^{−1}, abychom dostali 1 = f(1)·f(1)^{−1} = f(1)·f(1)·f(1)^{−1} = f(1). Dále 1 = f(1) = f(g^{−1} · g) = f(g^{−1}) · f(g) a podobně 1 = f(g) · f(g^{−1}), proto f(g^{−1}) = (f(g))^{−1}. □

Definice. Zobrazení f : G → H grup G(·) a H(·) slučitelné s jejich binárními operacemi se nazývá (grupový) homomorfismus. Bijektivní homomorfismus budeme nazývat izomorfismus. Podmnožině Kerf = {g ∈ G| f(g) = 1} i relaci kerf = {(g_{1}, g_{2}) ∈ G × G| f(g_{1}) = f(g_{2})} budeme říkat 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 izomorfní a píšeme G_{1} ≅ G_{2}.

Poznámka 1.17. Nechť G_{1}(·), G_{2}(·) a G_{3}(·) jsou grupy, f : G_{1} → G_{2} a g : G_{2} → G_{3} jsou homomorfismy a H podgrupa grupy G_{2}(·).

(1) gf je také homomorfismus,

(2) je-li f bijekce, pak f^{−1} je izomorfismus,

(3) obraz g(H) je podgrupa G_{3}(·) a úplný vzor f^{−1}(H) je podgrupa G_{1}(·),

(4) Kerf je normální podgrupa G_{1}(·) a kerf = rmod Kerf,

(5) kerf je ekvivalence slučitelná s operací · na G_{1},

Důkaz. (1) Je-li a, b ∈ G_{1}, pak gf(a · b) = g(f(a) · f(b)) = g(f(a)) · g(f(b)).

(2) Stačí ověřit, že f^{−1} je homomorfismus. Zvolíme-li c, d ∈ G_{2}, potom f(f^{−1}(c)· f^{−1}(d)) = c · d, proto f^{−1}(c) · f^{−1}(d) = f^{−1}(c · d).

(3) Nejprve ukážeme, že je g(H) podgrupa G_{3}(·). g(H) je zjevně neprázdná množina. Vezměme u, v ∈ g(H), tj. existují c, d ∈ H, pro která g(c) = u a g(d) = v. Protože c · d, c^{−1} ∈ H, dostáváme přímo z definice, že u · v = g(c) · g(d) = g(c · d) ∈ g(H), a u^{−1} = g(c)^{−1} = g(c^{−1}) ∈ g(H) podle 1.16.

Poznamenejme, že 1 ∈ f^{−1}(H), tedy jde o neprázdnou množinu a zvolme a, b ∈ f^{−1}(H), tj. f(a), f(b) ∈ H. Potom opět f(a) · f(b) = f(a · b) ∈ H, a f(a^{−1}) = f(a)^{−1} ∈ H, tedy a · b, a^{−1} ∈ f^{−1}(H), tedy f^{−1}(H) je podgrupa.

(4) Protože {1} je podgrupa G_{2}(·) a Kerf = f^{−1}({1}), je Kerf podgrupa podle (3). Vezmeme-li libovolné g ∈ G_{1} a h ∈ Kerf, potom f(g · h · g^{−1}) = f(g) · f(h) · f(g^{−1}) = f(g) · 1 · f(g)^{−1} = 1, tedy g · h · g^{−1} ∈ Kerf. Zbývá si uvědomit, že f(a) = f(b) ⇔ f(a) · f(b)^{−1} = 1 ⇔ f(a · b^{−1}) = 1 ⇔ a · b^{−1} ∈ Kerf.

(5) Plyne okamžitě z (4) a 1.15. □

Věta 1.18. Nechť G(·) je grupa a ρ ekvivalence na G slučitelná s ·. Na faktorové množině G/ρ definujeme operaci ⊙ předpisem [a]_{ρ} ⊙ [b]_{ρ} = [a · b]_{ρ}. Tato definice je korektní, G/ρ(⊙) je opět grupa a přirozená projekce π_{ρ} je homomorfismus.

Důkaz. Abychom ověřili korektnost definice, musí ukázat, že definice nezávisí na volbě zástupce ekvivalenčních tříd. Mějme tedy [a]_{ρ} = [c]_{ρ} a [b]_{ρ} = [d]_{ρ}, tj. (a, c), (b, d) ∈ ρ. Potom díky slučitelnosti ρ s operací máme (a · b, c · d) ∈ ρ, proto [a · b]_{ρ} = [c · d]_{ρ}.

Vezmeme-li [a]_{ρ}, [b]_{ρ}, [c]_{ρ} ∈ ρ, pak přímo z definice vidíme, že

[a]_{ρ} ⊙ ([b]_{ρ} ⊙ [c]_{ρ}]) = [a · (b · c)]_{ρ} = [(a · b) · c]_{ρ} = ([a]_{ρ} ⊙ [b]_{ρ}) ⊙ [c]_{ρ},

tedy operace ⊙ je asociativní. To, že je neutrálním prvkem právě [1]_{ρ} a inverzním prvkem k prvku [a]_{ρ} právě prvek [a^{−1}]_{ρ}, dostaneme přímým výpočtem. Konečně π_{ρ}(a · b) = [a · b]_{ρ} = [a]_{ρ} ⊙ [b]_{ρ} = π_{ρ}(a) ⊙ π_{ρ}(b) z definice. □

Grupu zavedenou na faktorové množině budeme nazývat faktorovou grupou. Věta 1.15, která říká, že každé ekvivalenci ρ slučitelné s binární operací na grupě jednoznačně odpovídá normální podgrupa H, nám umožňuje faktorovou množinu zapisovat ve tvaru G/H, navíc je běžné, že se operace na faktorové grupě označuje stejně jako operace na původní grupě. Obvyklý zápis faktorové grupy G/ρ(⊙) bude tedy G/H(·), kde H = [1]_{ρ} a [a]_{ρ} · [b]_{ρ} = [a · b]_{ρ}. Podobně budeme přirozenou projekci G na G/H označovat symbolem π_{H} a místo [a]_{ρ} budeme psát [a]_{H}.

Příklad 1.19. Uvážíme-li na grupě Z(+) ekvivalenci ∼_{n} zavedenou v Příkladu 0.3, jedná se o ekvivalenci slučitelnou s operací + a [0]_{∼_{n}} = nZ, proto ∼_{n}= rmod nZ a na faktorové množině Z/nZ = Z/ ∼_{n} máme dobře zavedenu strukturu grupy Z/nZ(+) předpisem [a]_{∼_{n}} + [b]_{∼_{n}} = [a + b]_{∼_{n}}.

Poznámka 1.20 (Věta o homomorfismu). Buď f : G_{1} → G_{2} homomorfismus grup G_{1}(·) a G_{2}(·) a nechť H je normální podgrupa G_{1}(·). Pak existuje homomorfismus g : G_{1}/H → G_{2} splňující podmínku gπ_{H} = f právě tehdy, když H ⊆ Kerf (tj. rmodH ⊆ rmod Kerf). Navíc, jestliže g existuje, je g izomorfismus, právě když f je na a Kerf = H.

Důkaz. Nejprve předpokládejme, že existuje homomorfismus g : G_{1}/H → G_{2} splňující gπ_{H} = f, tedy g([a]_{H}) = f(a). Zvolme a ∈ H. Pak [a]_{H} = H = [1]_{H} je neutrální prvek grupy G_{1}/H(·), a proto f(a) = g([a]_{H}) = 1 podle 1.16. Tedy a ∈ Kerf, čímž jsme ověřili, že H ⊆ Kerf.

Naopak, nechť H ⊆ Kerf. Musíme ověřit, že jediná možná definice g daná předpisem g([a]_{H}) = f(a) je korektní. Vezměme proto [a]_{H} = [b]_{H}. Potom a·b^{−1} ∈ H ⊆ Kerf, tedy 1 = f(a · b^{−1}) = f(a) · f(b)^{−1} podle 1.16, a proto f(a) = f(b). Konečně

g([a]_{H} · [b]_{H}) = g([a · b]_{H}) = f(a · b) = f(a) · f(b) = g([a]_{H}) · g([b]_{H}),

tedy g je homomorfismus.

Zbývá ověřit závěrečnou ekvivalenci. Předně si uvědomme, že g(G_{1}/H) = f(G_{1}), tedy g je na, právě když je f na. Nechť je g navíc prosté a zvolme a ∈ Kerf. Pak g([a]_{H}) = f(a) = 1. Protože g([1]_{H}) = g(H) = 1, plyne z prostoty g, že [a]_{H} = H, tedy a ∈ H. Ověřili jsme, že Kerf ⊆ H, a protože už víme, že H ⊆ Kerf, máme rovnost H = Kerf. Konečně předpokládejme, že g([a]_{H}) = g([b]_{H}). Potom f(a) = f(b) a a · b^{−1} ∈ Kerf = H. Tudíž (a, b) ∈ rmodH a [a]_{H} = [b]_{H}, čímž jsme ověřili, že je g prosté. □

Věta 1.21 (1. věta o izomorfismu). Nechť f : G_{1} → G_{2} homomorfismus grup G_{1}(·) a G_{2}(·). Pak f(G_{1}) je podgrupa G_{2} (tedy opět grupa) a G_{1}/Kerf(·) je izomorfní f(G_{1})(·).

Důkaz. Z 1.17(3) dostáváme, že f(G_{1}) je podgrupa G_{2}. Omezíme-li obor hodnot zobrazení f, můžeme ho chápat jako homomorfismus f : G_{1} → f(G_{1}). Nyní aplikujeme 1.20 pro H = Kerf a dostaneme přímo požadovaný izomorfismus g : G_{1}/Kerf → f(G_{1}). □

Příklad 1.22. Mějme homomorfismus f_{n} : Z → Z_{n} grupy Z(+) do grupy Z_{n}(+) s počítáním modulo n daný předpisem f_{n}(k) = (k)mod n. Pak máme podle 1.21 izomorfismus Z/Ker f_{n}(+) ≅ Z_{n}(+), navíc je zjevně (a, b) ∈ ker f_{n}, právě když n/(a − b), a Ker f_{n} = nZ.

Věta 1.23 (2. věta o izomorfismu). Nechť G(·) je grupa a H, K její normální podgrupy. Jestliže H ⊆ K , pak K/H je normální podgrupa grupy G/H(·) a faktorová grupa G/K(·) je izomorfní grupě (G/H)/(K/H)(·).

Důkaz. Opět nejprve použijeme 1.20 pro homomorfismy π_{K} : G → G/K (jako f z 1.20) a π_{H} : G → G/H (jako π_{H} z 1.20). Protože podle předpokladu H ⊆ K = Kerπ_{K}, dává nám 1.20 homomorfismus g : G/H → G/K splňující vztah g([a]_{H}) = [a]_{K}. Všimněme si, že je g zjevně na. Nyní přímočaře spočítáme Kerg = {[a]_{H} ∈ G/H| g([a]_{H}) = [a]_{K} = [1]_{K}} = K/H. Poznamenejme, že je Kerg = K/H normální podgrupa G/H(·) podle 1.17(3). Nyní pro homomorfismus g využijeme 1.21, abychom dostali G/K = g(G/H) ≅ (G/H)/Kerg = (G/H)/(K/H). □

2. Cyklické grupy

Připomeňme, že podle 1.9(3) je průnik libovolného systému podgrup zase podgrupou. Uvážíme-li grupu G(·) a podmnožinu X ⊆ G, pak průnik všech podgrup G(·) obsahujících X je rovněž podgrupou obsahující X, označme ho ⟨X⟩, zjevně se jedná o nejmenší takovou podgrupu vzhledem k inkluzi. Speciálně budeme psát ⟨g⟩ místo ⟨{g}⟩, je-li g ∈ G.

Definice. Buď G(·) grupa a X ⊆ G. Podgrupu ⟨X⟩ nazveme podgrupu G(·) generovanou množinou X. Řekneme, že G(·) je cyklická grupa, existuje-li takový prvek g ∈ G, že ⟨g⟩ = G.

Nechť G(·) je grupa a ∈ G. Definujme indukcí:

a^{0} = 1,

a^{n} = a^{n−1} · a pro každé n > 0,
a^{n} = (a^{−1})^{−n} pro každé n < 0.

Poznámka 2.1. Nechť G(·) je grupa a a ∈ G. Zobrazení ϕ : Z → G dané předpisem ϕ(n) = a^{n} je homomorfismus grupy Z(+) do grupy G(·) a ϕ(Z) = ⟨a⟩ = {a^{n}| n ∈ Z}.

Důkaz. Potřebujeme pro každou dvojici m, n ∈ Z ověřit, že ϕ(n + m) = a^{n+m} = a^{n} · a^{m} = ϕ(n) · ϕ(m). Přitom a^{n+m} = a^{n} · 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}·a^{m} = (a^{−1})^{−n}·a^{m} = a^{n+m} . Podobně pro n záporné, m kladné a m + n záporné máme a^{n} · a^{m} = (a^{−1})^{−n} · a^{m} = (a^{−1})^{−n−m} = a^{n+m} .

Závěrem poznamenejme, že ϕ(Z) je právě tvaru ϕ(Z) = {a^{n}| n ∈ Z}, a proto se jedná o nejmenší podgrupu G(·) obsahující a. □

Důsledek 2.2. Nechť G(·) je grupa a ∈ G. Potom pro každé n, m ∈ Z platí, že a^{−n} = (a^{n})^{−1} a (a^{n})^{m} = a^{nm}.

Příklad 2.3. (1) Z(+) je cyklická grupa, kde Z = ⟨1⟩ = ⟨−1⟩.

(2) Z_{n}(+) je pro každé přirozené n cyklická grupa s operacemi definovanými modulo n, kde Z_{n} = ⟨a⟩, právě když NSD(a, n) = 1.

Věta 2.4. Buď G(·) cyklická grupa.

(1) Je-li G nekonečná, pak G(·) ≅ Z(+).

(2) Je-li n = |G| konečné, pak G(·) ≅ Z_{n}(+).

Důkaz. Vezměme nějaký generátor g cyklické grupy G(·), tedy ⟨g⟩ = G a definujme zobrazení ϕ : Z → G dané předpisem ϕ(n) = g^{n}. Podle 2.1 jde o homomorfismus a ϕ(Z) = ⟨g⟩ = G, tedy ϕ je zobrazení na. Nyní podle 1.21 je Z/Kerϕ(+) ≅ G(·). Zbývá si rozmyslet, jak vypadá Z/Kerϕ. Z 1.10(2) víme, že Kerϕ = nZ pro vhodné nezáporné celé n. V připadě, že n = 0, pak Z/Kerϕ = Z/{0} ≅ Z, a v případě kladného n je Z/Kerϕ = Z/nZ ≅ Z_{n} podle 1.22. □

Poznámka 2.5. Každá faktorová grupa i podgrupa cyklické grupy je opět cyklická.

Důkaz. Snadno nahlédneme, že je-li g generátor cyklické grupy G(·), pak [g]_{H} je generátor její faktorové grupy G/H(·).

Díky 2.4 stačí tvrzení o podgrupách dokázat pro grupy Z(+) a Z_{n}(+). Nejprve ho dokažme pro grupu Z(+). V 1.10(2) jsme ověřili, že Z(+) jiné podgrupy než podgrupy tvaru nZ neobsahuje. Přitom ⟨n⟩ = nZ je cyklická grupa, čímž je tvrzení ověřeno.

Nyní využijeme homomorfismu f_{n} : Z → Z_{n} z 1.22. Zvolíme-li podgrupu H grupy Z_{n}(+), pak f_{n}^{−1}(H) je podle předchozí úvahy a 1.17(3) cyklická podgrupa Z, tedy H = f_{n}(f_{n}^{−1}(H)) je cyklická podgrupa Z_{n}(+). □

Poznámka 2.6. Buď G(·) konečná grupa. Potom g^{|G|} = 1 pro každý prvek g ∈ G.

Důkaz. ⟨g⟩ je cyklická grupa řádu n, tedy je podle 2.4 izomorfní Z_{n}(+), proto g^{n} = 1. Podle 1.13 n/|G|, tedy g^{|G|} = (g^{n})^{\frac{|G|}{n}} = 1^{\frac{|G|}{n}} = 1, kde 1. rovnost plyne z 2.2. □

Věta 2.7. Nechť G(·) je konečná cyklická grupa. Pak pro každé přirozené k, které dělí řád grupy G, existuje právě jedna podgrupa grupy G řádu k.

Důkaz. K důkazu využijeme charakterizace cyklických grup 2.4, díky němuž stačí tvrzení dokázat pro (izomorfní) grupu Z_{n}(+). Jestliže k = 1, je tvrzení triviální, předpokládejme tedy, že k > 1. Potom snadno nahlédneme, že množina ⟨\frac{n}{k}⟩ = \{0, \frac{n}{k}, 2\frac{n}{k}, …, (k − 1)\frac{n}{k}\} je podgrupa a |⟨\frac{n}{k}⟩| = k. Mějme nyní nějakou podgrupu H grupy Z_{n}(+) řádu k. Podle 2.6 (k · h)mod n = 0, proto k · h = c · n pro vhodné celé číslo c. Tedy h = c · \frac{n}{k}. Tím jsme ověřili, že H je částí podgrupy ⟨\frac{n}{k}⟩. Protože se jedná o dvě konečné stejně velké množiny, dostáváme, že H = ⟨\frac{n}{k}⟩, čímž jsme ověřili jednoznačnost volby. □

Pro každé přirozené k (resp. k ∈ Z_{n}) označujme kZ = ⟨k⟩ = {kz| z ∈ Z} (resp. kZ_{n} = ⟨k⟩ = {k · z| z ∈ Z_{n}}).

Poznámka 2.8. Nechť n ∈ N, a ∈ Z_{n} \ {0} a k/n. Pak aZ_{n} = kZ_{n}, právě když NSD(a, n) = k. Speciálně platí, že aZ_{n} = Z_{n} (tj. a generuje grupu Z_{n}(+)), právě když NSD(a, n) = 1.

Důkaz. Nejprve předpokládejme, že aZ_{n} = kZ_{n}. Potom k ∈ aZ_{n}, tedy existuje celé x, pro které (a · x)mod n = k. Proto také existuje takové celé y, že a · x + n · y = k. Odtud plyne, že NSD(a, n)/k. Podobně, protože a ∈ kZ_{n} existují celá u a v, pro něž k · u + n · v = a, a protože k/n, nutně musí k/a. Vidíme, že k/NSD(a, n), tudíž NSD(a, n) = k.

Nyní předpokládejme, že NSD(a, n) = k. Potom díky Euklidovu algoritmu existují x ∈ Z_{n} a celé y, pro něž a · x + n · y = k. Proto (a · x)mod n = k, tudíž k ∈ aZ_{n} a kZ_{n} ⊆ aZ_{n}. Konečně, protože k/a, vidíme, že a ∈ kZ_{n}, a proto aZ_{n} ⊆ kZ_{n}, což znamená, že kZ_{n} = aZ_{n}. □

Důsledek 2.9. Je-li n ∈ N, pak číslo φ(n) udává počet prvků, které generují grupu Z_{n}(+) a počet invertibilních prvků monoidu Z_{n}(·).

Příklad 2.10. (1) Uvažujme konečnou cyklickou grupu G(·). Potom nám 2.9 říká, že G(·) obsahuje právě φ(|G|) generátorů, a podle 2.7 G(·) obsahuje právě tolik podgrup, kolik je dělitelů jejího řádu.

(2) Vezměme cyklickou grupu Z_{50}(+). V bodu (1) jsme nahlédli, že Z_{50}(+) obsahuje φ(50) = 20 generátorů a právě 6 podgrup. Vezmeme-li například podgrupu ⟨42⟩ grupy Z_{50}(+) (a jiné než cyklické podgrupy tato grupa podle 2.5 neobsahuje), pak díky 2.8 víme, že ⟨42⟩ = ⟨NSD(42, 50)⟩ = ⟨2⟩ = 2Z_{50}, a jedná se tedy o podgrupu řádu 25 = \frac{50}{2} .

Věta 2.11 (Malá Fermatova věta). Pro nesoudělná kladná celá čísla a, n > 1 je (a^{φ(n)})mod n = 1.

Důkaz. Nejprve uvážíme, že (a^{φ(n)})mod n = ((a)mod n^{φ(n)})mod n, což znamená, že tvrzení stačí dokázat pro a < n. Nyní vezmem jako grupu G z 2.6 grupu invertibillních prvků Z_{n}^{∗}(·) monoidu Z_{n}(·) tj. prvků nesoudělných s n podle 2.9. Protože a ∈ Z_{n}^{∗}, je (a^{φ(n)})mod n = (a^{|Z_{n}^{∗}|})mod n = 1 díky 2.6 a 2.9. □

Poznámka 2.12. Buď p a q dvě různá lichá prvočísla a m = nsn(p − 1, q − 1). Potom pro každé a ∈ Z_{pq} platí, že (a^{m+1} )mod pq = a.

Důkaz. Podle 2.11 (x^{m})mod p = 1 a (y^{m})mod q = 1 pro x, která nejsou násobkem p a y, která nejsou násobkem q. Dále zřejmě platí ((up)^{m+1} )modp = 0 a proto i (x^{m+1} )mod p = (x)mod p a (y^{m+1} )mod q = (y)mod q pro každé nezáporné celé x a y. Vezměme nyni a ∈ Z_{pq}. Z předchozího pozorování plyne, že ((a)mod p, (a)mod q) = ((a^{m+1} )mod p, (a^{m+1} )mod q), a díky Větě 0.5 použité pro bijekci Z_{pq} → Z_{p}×Z_{q} dostáváme, že shodné jsou i vzory prvků ((a)mod p, (a)mod q) a ((a^{m+1} )mod p, (a^{m+1} )mod q), tedy, že (a^{m+1} )mod pq = a. □

Příklad 2.13 (Rivest, Shamir, Adleman). Opět zvolme p a q dvě různá lichá prvočísla a položme m = nsn(p − 1, q − 1). Indukcí díky 2.12 a 2.2 dostaneme, že a^{um+1} = a^{(u−1)m} · a^{m+1} = a^{(u−1)m+1} = a pro každé u ∈ N a a ∈ Z_{pq}.

Vezměme e < m nesoudělné s m a pak (například pomocí Euklidova algoritmu) najdeme takové d < m, že (ed)mod m = 1. Nyní pro každé a ∈ 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 · q, je veřejným klíčem je dvojice čísel (pq, e) a soukromý klíč tvoří tajný exponent d. Chceme-li informaci vyjádřenou posloupností hodnot a_{1}, …, a_{k} ∈ Z_{pq} adresovat majiteli soukromého klíče, stačí ji zašifrovat pomocí mocnění veřejně známou hodnotou e v monoidu Z_{pq}(·, 1), tj. odeslat zprávu (a_{1}^{e})mod pq, …, (a_{k}^{e})mod pq. K jejímu rozluštění stačí umocnit v Z_{pq}(·, 1) pomocí tajného exponentu, protože (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})mod pq, …, (a_{k}^{d})mod pq, 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 pq, …, ((a_{k}^{d})^{e})mod pq = a_{1}, …, a_{k}) ověřit, že odesilatel zprávy opravdu zná tajný exponent.

Poznamenejme, že je ze znalosti n 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í složitosti), zatímco mocnění čísel v Z_{pq} je (i pro velké exponenty a velké pq) velmi snadné a rychlé.

Důkaz následujícího tvrzení o cyklických grupách, který vyžaduje znalosti z teorie polynomů nad obecným tělesem, provedeme až v příštím semestru:

Věta 2.14. Nechť T (+, ·) je komutativní těleso a nechť G je konečná podgrupa multiplikativní grupy T \ {0}(·,^{−1} , 1). Potom G je cyklická grupa.

3. Univerzální pohled: pojem algebry

Definice. Pro každé celé n ≥ 0 nazveme n-ární operací na množině A každé zobrazení A^{n} → A (číslo n budeme nazývat aritou nebo četností operace). Nechť (α_{i}| i ∈ I) je systém operací na množině A. Pak dvojici A(α_{i}| i ∈ I) nazveme algebrou.

1-ární operace se obvykle nazývají unárními operacemi, 2-árním operacím se říká binární operace a 3-ární se nazývají ternárními operacemi. Uvědomme si, že nulární operace vyznačuje v algebře jeden její prvek, proto ji můžeme se tímto vyznačeným prvkem ztotožnit.

Příklad 3.1. (1) Uvážíme-li grupu G(·) s unární operací inverzního prvku ^{−1} a nulární operací 1, pak G(·), G(·,^{−1} ), G(·,^{−1} , 1) tvoří (formálně různé) příklady algeber.

(2) Je-li T těleso, pak je algebrou T(+, ·) či T(+, −, ·, 0, 1), pro vektorový prostor V nad T, je algebrou V (+, ·t|t ∈ T).

Definice. Buď α n-ární operace na A. Řekneme, že podmnožina B ⊆ A je uzavřená na operaci α, jestliže α(a_{1}, …, a_{n}) ∈ B pro všechna a_{1}, …, a_{n} ∈ B. Řekneme, že B ⊆ A je podalgebra algebry A(α_{i}| i ∈ I), je-li B uzavřená na všechny operace α_{i}, i ∈ I.

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

Definice. Nechť symbol α označuje n-ární operaci na množině A i B. Řekneme, že zobrazení f : A → B je slučitelné s operací α, jestliže f(α(a_{1}, …, a_{n})) = α(f(a_{1}), …, f(a_{n})). Řekneme, že algebry A(α_{i}| i ∈ I) a B(α_{i}| i ∈ I) jsou stejného typu, pokud α_{i} označuje na množině A i na množině B dvě operace stejné arity. Zobrazení f : A → B mezi dvěma algebrami stejného typu budeme říkat homomorfismus, je-li slučitelné se všemi operacemi α_{i}, i ∈ I. Bijektivní homomorfismus budeme nazývat izomorfismus. Jestliže mezi dvěma algebrami A a B existuje izomorfismus, říkáme, že A a B jsou izomorfní a píšeme A ≅ B.

Příklad 3.2. (1) Buď G_{i}(·) pro i = 1, 2 grupy s unární operací inverzního prvku −1 a nulární operací 1. pak každý homomorfimus grup G_{1}(·) a G_{2}(·) je podle 1.16 homomorfismem algeber G_{1}(·) a G_{2}(·), G_{1}(·,^{−1} ) a G_{2}(·^{−1}) i G_{1}(·,^{−1} , 1) a G_{2}(·^{−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(+, ·t|t ∈ T) a V (+, ·t|t ∈ T).

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

Definice. Nechť ρ je relace a α je n-ární operace na množině A. Řekneme, že ρ je slučitelná s α, jestliže pro každý systém prvků a_{1}, …, a_{n}, b_{1} …, b_{n} ∈ A, pro které (a_{i}, b_{i}) ∈ ρ, i = 1, …, n, platí, že (α(a_{1}, …, a_{n}), α(b_{1}, …, b_{n})) ∈ ρ. Je-li A(α_{i}| i ∈ I) algebra a ρ ekvivalence na množině A, pak ρ nazveme kongruencí, je-li ρ slučitelná se všemi operacemi α_{i}, i ∈ I.

Příklad 3.3. (1) id a A × A jsou kongruence na libovolné algebře A.

(2) Každá ekvivalence je slučitelná s libovolnou nulární operací.

(3) Ekvivalence slučitelná s operací · na grupě G(·) je kongruencí algeber G(·), G(·,^{−1} ) a G(·,^{−1} , 1).

Připomeňme, že je-li f : A → B zobrazení, rozumíme jeho jádrem kerf relaci danou předpisem: (a, b) ∈ ker f ⇔ f(a) = f(b). Nyní jsme připraveni vyslovit obdobu Poznámky 1.17 pro obecné algebry:

Poznámka 3.4. Nechť A_{1}(α_{i}| i ∈ I), A_{2}(α_{i}| i ∈ I) a A_{3}(α_{i}| i ∈ I) jsou algebry stejného typu, f : A_{1} → A_{2} a g : A_{2} → A_{3} jsou homomorfismy a B je podalgebra algebry A_{2}(·).

(1) gf je také homomorfismus,

(2) je-li f bijekce, pak f^{−1} je izomorfismus,

(3) obraz g(B) je podalgebra algebry A_{3}(α_{i}| i ∈ I) a úplný vzor f^{−1}(B) je podalgebra algebry A_{1}(α_{i}| i ∈ I),

(4) kerf je kongruence na algebře A_{1}(α_{i}| i ∈ I).

Důkaz. Důkaz je snadným zobecněním důkazu příslušných bodů 1.17.

(1) Je-li α_{i} n-ární operace na A_{1}, A_{2} a A_{3} a vezmeme-li a_{1}, … a_{n} ∈ A_{1}, pak gf(α_{i}(a_{1}, … a_{n})) = g(α_{i}(f(a_{1}), … f(a_{n}))) = α_{i}(gf(a_{1}), … gf(a_{n})).

(2) Stačí opět ověřit, že f^{−1} je homomorfismus. Zvolíme-li libovolně n-ární operaci α_{i} a prvky a_{1}, … a_{n} ∈ A_{2}, potom f(α_{i}(f^{−1}(a_{1}), …, f^{−1}(a_{n}))) = α_{i}(a_{1}, … a_{n}), proto α_{i}(f^{−1}(a_{1}), …, f^{−1}(a_{n})) = f^{−1}(α_{i}(a_{1}, … a_{n})).

(3) Nechť je opět α_{i} libovolná n-ární operace na A_{2} i A_{3}. Vezměme nejprve c_{1}, … c_{n} ∈ g(B), tj. existují b_{1}, … b_{n} ∈ B, pro která g(b_{j}) = c_{j}, j = 1, …, n. Protože α_{i}(b_{1}, … b_{n}) ∈ B, dostáváme bezprostředně z definice, že α_{i}(c_{1}, … c_{n}) = α_{i}(g(b_{1}), … g(b_{n})) = g(α_{i}(b_{1}, … b_{n})) ∈ g(B).

Nyní zvolme a_{1}, … a_{n} ∈ f^{−1}(B), tj. f(a_{j}) ∈ B. Potom f(α_{i}(a_{1}, … a_{n})) = α_{i}(f(a_{1}), … f(a_{n})) ∈ B.

(4) Vezměme n-ární operaci α_{i} na A_{1} a A_{2} a prvky a_{1}, … a_{n}, b_{1}, … b_{n} ∈ A_{1}, o nichž víme, že (a_{j}, b_{j}) ∈ kerf, tedy f(a_{j}) = f(b_{j}), pro každé j = 1 … n. Potom z definice homomorfismu dostaneme rovnost

f(α_{i}(a_{1}, … a_{n})) = α_{i}(f(a_{1}), … f(a_{n})) = α_{i}(f(b_{1}), … f(b_{n})) = f(α_{i}(b_{1}, … b_{n})),

čímž jsme ověřili, že (α_{i}(a_{1}, … a_{n}), α_{i}(b_{1}, … b_{n})) ∈ kerf. Že se jedná o ekvivalenci je snadné cvičení. □

Poznámka 3.5. Nechť A(α_{i}| i ∈ I) je algebra a A_{j} jsou podalgebray A a ρ_{j} ekvivalence na A pro každé j ∈ J.

(1) ⋂_{j∈J} A_{j} je podalgebra A,
(2) jsou-li ρ_{j} kongruence na A, pak i ⋂_{j∈J} ρ_{j} je kongruence.

Důkaz. (1) Obdoba Poznámky 1.9(3). Nechť α_{i} je libovolná n-ární operace na A a a_{1}, … a_{n} ∈ ⋂_{j∈J} A_{j}. Protože ⋂_{j∈J} A_{j} ⊆ A_{k} pro každé k ∈ J a A_{k} je podalgebra A(α_{i}| i ∈ I) máme α_{i}(a_{1}, … a_{n}) ∈ A_{k}, tedy α_{i}(a_{1}, … a_{n}) ∈ ⋂_{j∈J} A_{j}.

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

Mějme α_{i} nějakou n-ární operaci na A a vezměme prvky a_{1}, … a_{n}, b_{1}, … b_{n} ∈ A, pro něž platí, že (a_{k}, b_{k}) ∈ ⋂_{j∈J} ρ_{j} (⊆ ρ_{j} pro všechna j ∈ J). Potom pro všechna j ∈ J máme (α_{i}(a_{1}, … a_{n}), α_{i}(b_{1}, … b_{n})) ∈ ρ_{j} , tedy (α_{i}(a_{1}, … a_{n}), α_{i}(b_{1}, … b_{n})) ∈ ⋂_{j∈J} ρ_{j}. □

Definice. Nechť je A množina a C ⊆ P(A) je nějaký systém podmnožin množiny A. Řekneme, že C je uzávěrovým systémem nad A, pokud

(1) A ∈ C,

(2) pro každý podsystém {B_{i}| i ∈ I} ⊆ C, je ⋂{B_{i}| i ∈ I} ∈ C.

Důsledek 3.6. Nechť A(α_{i}| i ∈ I) je algebra. Pak všechny podalgebry algebry A(α_{i}| i ∈ I) tvoří uzávěrový systém na A a všechny kongruence na algebře A(α_{i}| i ∈ I) tvoří uzávěrový systém na A × A.

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

Nyní zobecníme definici ze začátku 2.kapitoly.

Definice. Buď A algebra a X ⊆ A. Potom podalgebru ⟨X⟩ algebry A, kterou dostaneme jako průnik všech podalgeber A obsahujících množinu X nazveme podalgebrou generovanou X (nebo budeme říkat, že X generuje podalgebru ⟨X⟩).

Poznámka 3.7. Buď f, g : A → B dva homomorfismy algeber stejného typu a nechť X ⊆ A generuje algebru A. Jestliže f(x) = g(x) pro všechna x ∈ X, potom f = g.

Důkaz. Nejprve ukážeme, že je množina C = {a ∈ A| f(a) = g(a)} podalgebrou algebry A. Vezměme n-ární operaci α algebry A a nechť a_{1}, …, a_{n} ∈ C. Pak f(α(a_{1}, …, a_{n})) = α(f(a_{1}), …, f(a_{n})) = α(g(a_{1}), …, g(a_{n})) = g(α(a_{1}, …, a_{n})), proto α(a_{1}, …, a_{n}) ∈ C. Všimneme-li si, že X ⊆ C, dostaneme A = ⟨X⟩ ⊆ C, čímž jsme dokončili důkaz. □

Příklad 3.8. (1) Uvažujme grupu celých čísel Z(+) a G(+) nějaký grupoid, tedy algebru s jednou binární operací +. Nechť f, g : Z → G je homomorfismus. Uvědomme si, že nejmenší podalgebra Z(+) obsahující množinu {−1, 1} je už rovna celému Z tj. ⟨{−1, 1}⟩ = 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 → 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 → G je homomorfismus. Potom ⟨{−1, 1}⟩ = Z, a podle 3.7 jsou f a g shodné, jestliže f(1) = g(1).

Definice. Nechť ρ je ekvivalence a α je n-ární operace na množině A. Je-li ρ slučitelná s α, definujeme operaci α na faktoru A/ρ předpisem α([a_{1}]_{ρ}, …, [a_{n}]_{ρ}) = [α(a_{1}, …, a_{n})]_{ρ}. Je-li ρ kongruence na algebře A, pak tímto způsobem definujeme na A/ρ strukturu algebry stejného typu.

Věta 3.9. Je-li ρ kongruence na algebře A, pak je definice algebry A/ρ korektní, jde o algebru stejného typu jako A a přirozená projekce π_{ρ} : A → A/ρ je homomorfismus.

Důkaz. Vezměme libovolnou n-ární operaci α algebry A a nechť [a_{j}]_{ρ} = [b_{j}]_{ρ}, j = 1, … n. Potom (a_{j}, b_{j}) ∈ ρ, kde j = 1, … n, proto [α(a_{1}, …, a_{n})]_{ρ} = [α(b_{1}, …, b_{n})]_{ρ}, tedy definice operací na A/ρ je korektní. Zbytek tvrzení je přímý důsledek definice. □

Definice. Nechť ρ ⊆ σ jsou dvě ekvivalence na A. Definujme relaci σ/ρ na A/ρ následovně: ([a]_{ρ}, [b]_{ρ}) ∈ σ/ρ ⇔ (a, b) ∈ σ.

Poznámka 3.10. Buď ρ kongruence na algebře A.

(1) Je-li σ kongruence na A obsahující ρ, je σ/ρ dobře definovaná kongruence na algebře A/ρ.

(2) Je-li η kongruence na algebře A/ρ, potom existuje právě jedna kongruence σ na algebře A obsahující ρ, pro níž η = σ/ρ.

Důkaz. (1) Stačí ověřit, že je σ/ρ dobře definovaná, zbytek je okamžitým důsledkem definice σ/ρ a operace na faktorové algebře A/ρ. Mějme [a_{1}]_{ρ} = [a_{2}]_{ρ} [b_{1}]_{ρ} = [b_{2}]_{ρ}. Potom (a_{1}, a_{2}), (b_{1}, b_{2}) ∈ ρ ⊆ σ, tedy díky tranzitivitě a symetrii σ platí, že (a_{1}, b_{1}) ∈ σ ⇔ (a_{2}, b_{2}) ∈ σ.

(2) Jediný možný způsob, jak definovat σ nám dává předpis (a, b) ∈ σ ⇔ ([a]_{ρ}, [b]_{ρ}) ∈ η. Nyní stačí přímočaře nahlédnout, že jsme takto zavedli kongruenci na A. □

Nyní už můžeme vyslovit obecné verze Věty o homomorfismus a Vět o izomorfismus:

Poznámka 3.11. (Věta o homomorfismu) Buď f : A → B homomorfismus dvou algeber stejného typu a nechť ρ je kongruence na algebře A. Pak existuje homomorfismus g : A/ρ → B splňující podmínku gπ_{ρ} = f právě tehdy, když ρ ⊆ kerf. Navíc, pokud g existuje, je g izomorfismus, právě když f je na a kerf = ρ.

Důkaz. Tvrzení dokážeme stejně jako Větu o homomorfismu pro grupy (1.20).

Nejprve předpokládejme, že existuje homomorfismus g : A/ρ → B splňující podmínku gπ_{ρ} = f, tedy g([a]_{ρ}) = f(a) a vezměme (a_{1}, a_{2}) ∈ ρ. Pak [a_{1}]_{ρ} = [a_{2}]_{ρ}, a proto f(a_{1}) = g([a_{1}]_{ρ}) = g([a_{2}]_{ρ}) = f(a_{2}). Tedy (a_{1}, a_{2}) ∈ kerf.

Je-li naopak ρ ⊆ kerf, ověřujeme, že definice g daná předpisem g([a]_{ρ}) = f(a) je korektní. Vezmeme-li [a_{1}]_{ρ} = [a_{2}]_{ρ} ⊆ kerf, pak g([a_{1}]_{ρ}) = f(a_{1}) = f(a_{2}) = g([a_{2}]_{ρ}). Že je g homomorfismus je zjevné z jeho definice.

Konečně dokážeme závěrečnou ekvivalenci. Protože g(G_{1}/ρ) = f(G_{1}), opět 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}) ∈ kerf, pak g([a_{1}]_{ρ}) = f(a_{1}) = f(a_{2}) = g([a_{2}]_{ρ}), a proto (a_{1}, a_{2}) ∈ ρ. Ověřili jsme, že kerf ⊆ ρ, a protože už víme, že ρ ⊆ kerf, máme rovnost ρ = kerf. Konečně předpokládejme, že g([a_{1}]_{ρ}) = g([a_{2}]_{ρ}). Potom f(a_{1}) = f(a_{2}), a proto (a_{1}, a_{2}) ∈ ρ a [a_{1}]_{ρ} = [a_{2}]_{ρ}, čímž jsme ověřili, že je g prosté. □

Věta 3.12 (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. Rozmyslíme si, že podle 3.4(3) je f(A) je podalgebra B a poté stejně jako v důkazu 1.21 použijeme Větu o homomorfismu 3.11 na ρ = kerf. □

Věta 3.13 (2. věta o izomorfismu). Nechť ρ ⊆ σ jsou dvě kongruence na algebře A. Pak algebra A/σ je izomorfní algebře (A/ρ)/(σ/ρ).

Důkaz. I tentokrát postupujeme stejně jako v důkazu Věty o izomorfismu pro grupy 1.23: nejprve použijeme 3.11 pro homomorfismy π_{σ} : A → A/σ a π_{ρ} : A → A/ρ, která nám dává homomorfismus g : A/ρ → A/σ splňující vztah g([a]_{ρ}) = [a]_{σ}. Zbývá spočítat kerg = σ/ρ a použít 3.12. □

4. Svazy

Definice. Relaci ≤ na množině M budeme říkat uspořádání, je-li reflexivní a tranzitivní a splňuje-li podmínku a ≤ b, b ≤ a ⇒ a = b pro každé a, b ∈ M (tj. jde o slabě antisymetrickou relaci).

Příklad 4.1. Následující relace jsou uspořádáním:

(1) / na množině všech přirozených čísel N,

(2) ≤ na množině všech celých (reálných, racionálních) čísel Z (R, Q),

(3) ⊆ na množině všech podmnožin P(X) množiny X,

(4) id na libovolné neprázdné množině M.

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

Příklad 4.2. (1) (N, /), kde sup_{/}(n, m) = nsn(n, m) a inf_{/}(a, b) = NSD(n, m), je příkladem svazu

(2) (Z, ≤), (R, ≤), (Q, ≤), kde sup_{≤}(a, b) = max(a, b) a inf_{≤}(a, b) = min(a, b), je rovněž (dokonce lineárně uspořádaný) svaz.

(3) (P(X), ⊆), je úplný svaz, kde sup_{⊆}(B) = ⋃ B a inf_{⊆}(B) = ⋂ B pro každou podmnožinu B ⊆ P(X).

Definice. Nechť (M, ≤) je svaz. Pro každé dva prvky m, n ∈ M označme m ∨ n = sup_{≤}(m, n) a m ∧ n = inf_{≤}(m, n). Potom binární operaci ∨ nazveme spojení a ∧ průsek.

Poznámka 4.3. Buď (M, ≤) svaz. Pak pro všechna a, b, c ∈ M platí:

(S1) a ∨ b = b ∨ a, a ∧ b = b ∧ a,

(S2) a ∨ a = a = a ∧ a,

(S3) a ∨ (b ∨ c) = (a ∨ b) ∨ c, a ∧ (b ∧ c) = (a ∧ b) ∧ c, (S4) a ∨ (b ∧ a) = a = a ∧ (b ∨ a).

Důkaz. Vlastnosti (S1) a (S2) jsou okamžitým důsledkem definice ∧ a ∨.

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

(S4) Protože b ∧ a ≤ a a a ≤ a, máme a ∨ (b ∧ a) ≤ a. Naopak a ≤ a ∨ (b ∧ a), tedy ze slabé antisymetrie plyne, že a = a ∨ (b ∧ a). I tentokrát pro ověření druhé podmínky stačí zaměnit spojení průsekem a relaci ≤ relací ≥. □

Poznámka 4.4. Nechť M(∧, ∨) je algebra s dvěma binárními operacemi, které splňují podmínky (S1) – (S4). Definujme na M relaci ≤ předpisem: a ≤ b ⇔ b = a ∨ b. Pak (M, ≤) je svaz, kde sup_{≤}(a, b) = a ∨ b a inf_{≤}(a, b) = a ∧ b.

Důkaz. Nejprve ukážeme, že je ≤ uspořádání. Protože a = a ∨ a díky (S2), máme podle definice a ≤ a. Vezmeme-li a ≤ b a b ≤ c, tj. b = a ∨ b, c = b ∨ c, pak c = (a ∨ b) ∨ c = a ∨ (b ∨ c) = a ∨ c díky (S3), tedy a ≤ c. Konečně platí-li, že a ≤ b a b ≤ a, dostáváme z (S2), že b = a ∨ b = b ∨ a = a.

Nyní ověříme, že b = a ∨ b ⇔ a = a ∧ b. Za symetrie podmínek pro ∧ a ∨ plyne, že stačí abychom ověřili jen jednu implikaci. Nechť například b = a ∨ b. Potom a ∧ b = a ∧ (a ∨ b) = a ∧ (b ∨ a) = a podle (S1) a (S4). Vidíme, že je definice ≤ symtericky formulovatelná pomocí podmínky a ≤ b ⇔ a = a ∧ b.

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

Předchozí dvě poznámky ukazují vzájemně jednoznačnou korespondenci mezi svazy a algebrami M(∧, ∨) splňujícími podmínky (S1) – (S4). Proto budeme svazem nazývat i algebru M(∧, ∨) a na množině M budeme zároveň používat operace ∧ a ∨ i odpovídající relaci ≤. Všimněme si, že je-li M(∧, ∨) svaz, pak i M(∨, ∧) tvoří svaz (mluvíme o opačném svazu s opačným uspořádáním ≥).

Příklad 4.5. U příkladů svazů uvedených v 4.2 máme tedy dva způsoby jak na svaz nahlížet:

(1) (N, /) odpovídá algebře N(NSD, nsn),

(2) (Z, ≤) (respektive (R, ≤), (Q, ≤)) odpovídá algebře Z(min, max) (respektive R(min, max), Q(min, max)).

(3) (P(X), ⊆) odpovídá algebře P(X)(∩, ∪),

Věta 4.6. Nechť C je uzávěrový systém. Pak (C, ⊆) tvoří úplný svaz, kde sup_{⊆}(B) = ⋂{C ∈ C| ⋃ B ⊆ C} a inf_{⊆}(B) = ⋂ B pro každé B ⊆ C .

Důkaz. ⊆ je uspořádání a ⋂ B je zjevně infimem. Protože je C uzavřené na průniky, je ⋂{X ∈ C| ⋃ B ⊆ X} nejmenším prvkem C obsahujícím všechna B ∈ B, což je podle definice právě supremum vzhledem k inkluzi. □

Důsledek 4.7. Systém všech podalgeber i systém všech kongruencí na algebře spolu s inkluzí je díky 3.6 svazem.

Definice. Nechť (M, ≤) je svaz a a, b, c ∈ M. Řekneme, že prvek b pokrývá prvek a (píšeme a < · b), jestliže a ≤ b, a ≠ b a a ≤ c ≤ b ⇒ c = a nebo c = b. Hasseovým diagramem svazu (M, ≤) 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.

Poznámka 4.8. Nechť M(∧, ∨) je svaz, a, b, c ∈ M a a ≤ c. Potom a ∨ (b ∧ c) ≤ (a ∨ b) ∧ c.

Důkaz. Protože a ≤ a∨b a b∧c ≤ b ≤ a∨b, máme z definice suprema a∨(b∧c) ≤ a∨b. Podobně a ≤ a∨c a b∧c ≤ c, proto a∨(b∧c) ≤ c. Využijeme-li nyní definici infima množiny {a ∨ b, c}, pak dostaneme a ∨ (b ∧ c) ≤ (a ∨ b) ∧ c. □

Definice. O svazu S(∧, ∨) řekneme, že je modulární, jestliže pro každá taková a, b, c ∈ S, že a ≤ c, platí rovnost a ∨ (b ∧ c) = (a ∨ b) ∧ c a svaz je distributivní, platí-li pro každé a, b, c ∈ S rovnost a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Poznámka 4.9. Každý distributivní svaz je modulární.

Důkaz. Předpokládejme, že a ≤ c, tj. (a ∨ c) = c. Potom nám distributivita dává rovnost a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) = (a ∨ b) ∧ c. □

Příklad 4.10. (1) Svaz P(X)(∩, ∪), kde P(X) je množina všech podmnožin množiny X, je distributivní.

(2) Množina všech podprostorů vektorového prostoru je uzávěrový systém, a proto tvoří díky Větě 4.6 spolu s inkluzí svaz. Tento svaz je modulární.

(3) Svaz (N_{5}, ≤), kde N_{5} = {0, 1, a, b, c}, daný relacemi: 0 < · a < · c < · 1, 0 < · b < · 1 (tzv. pentagon, N_{5}) není modulární, protože a ≤ c a a ∨ (b ∧ c) = a ≠ c = (a ∨ b) ∧ c.

(4) Nechť M_{5} = {0, 1, u, v, w}, buď 0 nejmenší prvek, 1 největší prvek a u ∨ v = u ∨ w = v ∨ w = 1 a u ∧ v = u ∧ w = v ∧ w = 0. Protože u ∨ (v ∧ w) = u ∨ 0 ≠ 1 = 1 ∧ 1(u ∨ v) ∧ (u ∨ w), není M_{5}(∧, ∨) distributivní svaz. Elemntárními prostředku můžeme dokázat, že je modulární. (říká se mu obvykle diamant a značí se M_{5}).

Poznámka 4.11. Svaz S(∧, ∨) je distributivní, právě když pro každé a, b, c ∈ S platí, že a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), tedy svaz S(∧, ∨) je distributivní, právě když je opačný svaz S(∨, ∧) distributivní.

Důkaz. Ze symetrie vlastností operací plyne, že stačí dokázat pouze jednu implikaci. Nechť je svaz distributivní. Budeme s využitím definice distributivity a 4.3 upravovat: (a ∧ b) ∨ (a ∧ c) = ((a ∧ b) ∨ a) ∧ ((a ∧ b) ∨ c) = (a ∨ a) ∧ (b ∨ a) ∧ (a ∨ c) ∧ (b ∨ c) = a ∧ (b ∨ c), kde poslední rovnost plyne ze vztahů a ≤ (b ∨ a) a a ≤ (a ∨ c). □

Definice. Nechť f : A → B je zobrazení a (A, ≤) a (B, ≤) jsou svazy. Řekneme, že je f homomorfismus (izomorfismus) jde-li o homorfismus (izomorfismus) algeber A(∧, ∨) a B(∧, ∨) a f nazveme monotónním zobrazením, platí-li implikace a_{1} ≤ a_{2} ⇒ f(a_{1}) ≤ f(a_{2}).

Příští semestr dokážeme, že je svaz modulární, právě když neobsahuje podsvaz izomorfní svazu N_{5}, a že je distributivní, právě když neobsahuje ani podsvaz izomorfní N_{5}, ani podsvaz izomorfní M_{5}.

Poznámka 4.12. Homomorfismus svazů je monotónní zobrazení.

Důkaz. Je-li f : A → B homomorfismus svazů a a_{1} ≤ a_{2} ∈ A, pak a_{2} = a_{1} ∨ a_{2}. Proto f(a_{2}) = f(a_{1} ∨ a_{2}) = f(a_{1}) ∨ f(a_{2}) a tedy f(a_{1}) ≤ f(a_{2}). □

Příklad 4.13. Uvažujme svazy (S_{1}, ≤) a (S_{2}, ≤), kde S_{1} = {0, 1, a, b}, S_{2} = {0, 1, A, B} a daný relacemi: 0 < · a < · 1, 0 < · b < · 1 a 0 < · A < · B < · 1. Potom zobrazení f(0) = 0, f(1) = 1, f(a) = A, f(b) = B je monotónní, ale není to homomorfismus svazů, protože f(a ∧ b) = f(0) = 0 ≠ A = f(a) ∧ f(b).

Věta 4.14. Bijekce svazů f je izomorfismus, právě když jsou f i f^{−1} monotónní zobrazení.

Důkaz. Díky 4.12 stačí dokázat zpětnou implikaci. Ověříme slučitelnost f například s ∨. Mějme f : A → B takovou bijekci svazů, že f i f^{−1} jsou monotónní, a zvolme a, b ∈ A. Protože a, b ≤ a ∨ b, je f(a), f(b) ≤ f(a ∨ b), tudíž f(a) ∨ f(b) ≤ f(a ∨ b). Podobně f(a), f(b) ≤ f(a)∨f(b), proto a, b ≤ f^{−1}(f(a)∨f(b)) a a∨b ≤ f^{−1}(f(a)∨ f(b)). Použijeme-li na poslední vztah znovu monotonii f, dostaneme f(a ∨ b) ≤ f(a) ∨ f(b). Ze slabé antisymetrie ≤, potom plyne, že f(a ∨ b) = f(a) ∨ f(b). □

Definice. Nechť má svaz S(∧, ∨) nejmenší prvek 0 a největší prvek 1. Prvek a ∈ S nazveme atomem (resp. koatomem), jestliže a pokrývá 0 (resp. 1 pokrývá a). Komplementem prvku a ∈ S nazveme takový prvek a′ ∈ S, že a∨a′ = 1 a a∧a′ = 0.

Poznámka 4.15. Každý prvek distributivního svazu má nejvýše jeden komplement.

Důkaz. Nechť a∨b_{i} = 1 a a∧b_{i} = 0 pro i = 1, 2. Pak b_{i}∧(a∨b_{j}) = (b_{i}∧a)∨(b_{i}∧b_{j}) = 0 ∨ (b_{i} ∧ b_{j}) = b_{i} ∧ b_{j}, tedy b_{i} ≤ b_{j} pro všechna i, j ∈ {1, 2}, což znamená, že b_{1} = b_{2}. □

Definice. Booleovou algebrou nazveme takovou algebru S(∨, ∧, 0, 1, ′), že S(∧, ∨) je distributivní svaz s největším prvkem 1 a nejmenším prvkem 0 a unární operace ′ přiřadí každému prvku jeho komplement. Homomorfismem (izomorfismem) Booleových algeber rozumíme homorfismus (izomorfismus) algeber v obvyklém smyslu.

Příklad 4.16. Nechť P(X) je množina všech podmnožin množiny X a pro každou podmnožinu Y ⊆ X definujme Y′ = X \ Y. Pak P(X)(∪, ∩, ∅, X, ′) je Booleova algebra.

Poznámka 4.17. Nechť S(∨, ∧, 0, 1, ′) je Booleova algebra. Pak pro každé a, b ∈ S platí:

(1) (a′)′ = a,
(2) (1)′ = 0 a (0)′ = 1,
(3) (a ∨ b)′ = a′ ∧ b′,
(4) (a ∧ b)′ = a′ ∨ b′.

Důkaz. (1) a (2) plyne přímo z definice a 4.15 a (4) je symetrické k (3).

(3) (a ∨ b) ∧ (a′ ∧ b′) = (a ∧ a′ ∧ b′) ∨ (b ∧ a′ ∧ b′) = 0 ∨ 0 = 0 a podobně (a ∨ b) ∨ (a′ ∧ b′) = (a ∨ b ∨ a′) ∧ (a ∨ b ∨ b′) = 1 ∨ 1 = 1. □

Vezmeme-li M = {m_{1}, …, m_{n}} neprázdnou konečnou podmnožinu Booleovy algebry, pak značme ⋀ M = m_{1} ∧ m_{2} ∧ ⋯ ∧ m_{n} a ⋁ M = m_{1} ∨ m_{2} ∨ ⋯ ∨ m_{n}. Dále ⋀ ∅ = 1 a ⋁ ∅ = 0.

Věta 4.18. Buď S(∨, ∧, 0, 1, ′) konečná Booleova algebra a A buď množina všech atomů svazu S. Potom zobrazení ϕ : P(A) → S dané předpisem ϕ(B) = ⋁ B je izomorfismus Booleových algeber S(∨, ∧, 0, 1, ′) a P (A)(∪, ∩, ∅, X, ′).

Důkaz. Definujme nejprve zobrazení ψ : S → P(A) předpisem ψ(s) = {a ∈ A| a ≤ s}. Okamžitě vidíme, že zobrazení ϕ i ψ jsou monotónní vzhledem k inkluzi a ϕ(∅) = 0. Ukážeme-li navíc, že je ϕ bijekce slučitelná s průsekem a spojením, pak nutně ϕ(A) = 1 a ϕ(B′) = ϕ(B)′ pro každé B ∈ P(A). Podle 4.14 tedy zbývá ověřit, že ϕ ∘ ψ = Id_{S} i ψ ∘ ϕ = Id_{P(A)}, tedy že ϕ je bijekce a ϕ^{−1} = ψ.

Položme t = ϕψ(s) = ⋁{a ∈ A| a ≤ s}. Potom t = ⋁{a ∈ A| a ≤ s} ≤ s. Všimněme si, že díky distributivitě s = s∧1 = s∧(t∨t′) = (s∧t)∨(s∧t′) = t∨(s∧t′). Předpokládáme-li, že t ≠ s, pak z předchozího vidíme, že (s ∧ t′) ≠ 0, a díky konečnosti S najdeme nějaký atom a_{0}, který leží pod prvkem s ∧ t′, tedy a ≤ t′ a a ∈ ψ(s), a proto a ≤ t. Zjistili jsme, že a ≤ t ∧ t′ = 0, což je spor, tudíž s = t.

Nyní položme C = ψϕ(B) = {a ∈ A| a ≤ ⋁ B}. Vezmeme-li b ∈ B, pak b ≤ ⋁ B, a proto b ∈ C, čímž jsme ověřili inkluzi B ⊆ C. Zvolme tedy c ∈ C a uvažme, že 0 ≠ c = c ∧ ⋁ B = ⋁{c ∧ b| b ∈ B} díky distributivitě a konečnosti B. To ovšem znamená, že existuje b ∈ B, pro něž c ∧ b ≠ 0. Protože jsou oba prvky b a c atomy, máme b = c, čímž jsme dokázali, že B = C. □

Poznámka 4.19. Buď C uzávěrový systém obsažený v systému všech ekvivalencí na množině A. Nechť pro N ⊆ P(A) a e ∈ A platí:

(a) [e]_{ρ} ∈ N pro každé ρ ∈ C, (b) pro každé N ∈ N existuje takové ρ ∈ C, že N = [e]_{ρ},

(c) pro každé ρ, η ∈ C platí, že [e]_{ρ} ⊆ [e]_{η} ⇒ ρ ⊆ η. Pak N je uzávěrový systém na A (a tedy svaz) a zobrazení φ : C → N dané předpisem φ(ρ) = [e]_{ρ} je izomorfismus svazů.

Důkaz. Nejprve ukážeme, že je N uzávěrový systém. Protože A × A ∈ C, máme A = [e]_{A×A} ∈ N díky (a). Vezmeme-li N_{i} ∈ N, i ∈ I, pak podle (b) existuje pro každé i ∈ I taková ekvivalence ρ_{i} ∈ C, že N_{i} = [e]_{ρ_{i}}. Protože je C uzávěrový systém, tedy ⋂_{i∈I} ρ_{i} ∈ C, dostáváme ⋂_{i∈I} N_{i} = ⋂_{i∈I}[e]_{ρ_{i}} = [e]_{⋂_{i∈I} ρ_{i}} ∈ N opět díky (a).

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

Věta 4.20. Všechny normální podgrupy libovolné grupy G(·) tvoří svaz izomorfní svazu všech kongruencí na grupě G(·).

Důkaz. Označme symbolem C množinu všech kongruencí na G(·), tj. ekvivalencí slučitelných s operací · (viz 3.3(3)), symbolem N množinu všech normálních podgrup G(·) a symbolem e neutrální prvek G(·). Z 4.7 plyne, že je C uzávěrový systém a 1.15 zaručuje, že jsou splněny předpoklady (a), (b), (c) Poznámky 4.19, odkud plyne závěr. □

5. Okruhy a ideály

Definice. Okruhem budeme nazývat každou takovou algebru R(+, ·, −, 0, 1), že R(+) je komutativní grupa s neutrálním prvkem 0 a operací opačného prvku −, R(·) je monoid s neutrálním prvkem 1 a pro každé a, b, c ∈ R platí, že a·(b+c) = a·b+a·c a (a + b) · c = a · c + b · c. Okruh se nazývá komutativní, je-li operace · komutativní.

Příklad 5.1. (1) Z(+, ·, −, 0, 1) a Z_{n}(+, ·, −, 0, 1) pro každé přirozené n > 1 jsou komutativní okruhy.

(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)(+, ·, −, 0_{n}, I_{n}) je okruh.

Poznámka 5.2. Nechť R(+, ·, −, 0, 1) je okruh. Pak pro každé a, b ∈ R platí: (1) 0 · a = a · 0 = 0,

(2) (−a) · b = a · (−b) = −(a · b),

(3) (−1) · a = a · (−1) = −a,

(4) 1 ≠ 0, právě když |R| > 1 (tj. R je netriviální okruh).

Důkaz. U bodů (1)–(3) dokážeme jen jednu rovnost, důkaz druhé je symetrický.

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

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

(3) Dostáváme přímo z (2) pro b = 1.

(4) Přímá implikace je triviální, předpokládejme tedy, že 1 = 0 a vezměme libovolné a ∈ R. Potom a = a · 1 = a · 0 = 0 podle definice a (1). □

Definice. Nechť R(+, ·, −, 0, 1) je okruh. Řekneme, že množina I ⊆ R je pravý (resp. levý) ideál okruhu R, jestliže je I podgrupa grupy R(+) a pro každé i ∈ I a r ∈ R platí, že i · r ∈ I (resp. r · i ∈ I). Množinu I nazveme ideálem, je-li pravým a zároveň levým ideálem. Homomorfismus (izomorfismus) okruhů bude homorfismus (izomorfismus) příslušných algeber.

Příklad 5.3. (1) {0} a R jsou (tzv. triviálními) ideály každého okruhu R.

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

(3) Podle (2) a 2.5 jsou ideály okruhu celých čísel Z(+, ·, −, 0, 1) právě tvaru kZ a ideály okruhu Z_{n}(+, ·, −, 0, 1) tvaru kZ_{n}, kde k < n je 0 nebo dělitel čísla n.

O (levém, pravém) ideálu I okruhu R(+, ·, −, 0, 1) řekneme, že je vlastní, jestliže I ≠ {0} a I ≠ R.

Věta 5.4. Nechť R(+, ·, −, 0, 1) je okruh. Všechny kongruence a všechny ideály okruhu R tvoří spolu s inkluzí svazy a zobrazení ρ → [0]_{ρ} je izomorfismus svazu všech kongruencí na svazu všech ideálů okruhu R. Přitom ekvivalence ρ je kongruence na R(+, ·, −, 0, 1), právě když [0]_{ρ} je ideál a (a, b) ∈ ρ ⇔ a − b ∈ [0]_{ρ}.

Důkaz. Nejprve dokážeme závěrečnou ekvivalenci. Je-li ρ je kongruence na okruhu R, pak jde také o kongruenci grupy R(+), proto je [0]_{ρ} podle 1.15 podgrupou R(+) a (a, b) ∈ ρ ⇔ a − b ∈ [0]_{ρ}. Zbývá ověřit, že jde o ideál. Zvolme i ∈ [0]_{ρ} a r ∈ R, tedy (i, 0) ∈ ρ a (r, r) ∈ ρ, proto (ir, 0) = (ir, 0r) ∈ ρ a (ri, 0) = (ri, r0) ∈ ρ, tedy ir, ri ∈ I.

Předpokládejme, že je I je ideál a definujme (a, b) ∈ ρ ⇔ a − b ∈ I. Potom I = [0]_{ρ} a podle 1.15 je ρ slučitelné s +. Zvolme (a, b), (c, d) ∈ ρ. Pak a − b, c − d, (a − b)c, b(c − d) ∈ [0]_{ρ}, a tudíž −a + b ∈ [0]_{ρ} a ac − bd = (a − b)c + b(c − d) ∈ [0]_{ρ}, proto (−a, −b), (a·c, b·d) ∈ ρ, čímž jsme ověřili, že je ρ kongruence na R(+, ·, −, 0, 1).

Nyní stejným způsobem jako v důkazu 4.20 nahlédneme že jsou pro e = 0, C množinu všech kongruencí a N množinu všech ideálů okruhu R(+, ·, −, 0, 1) splněny předpoklady 4.19, odkud dostáváme závěr. □

Obdobně jako v případu faktorizace grup podle normálních podgrup budeme faktor okruhu R podle kongruence jednoznačně odpovídající ideálu I značit R/I. Poznamenejme, že faktorová algebra R/I je opět okruh.

Definice. Řekneme, že prvek okruhu R(+, ·, −, 0, 1) je invertibilní, jedná-li se o invertibilní prvek monoidu R(·). Řekneme, že okruh R je tělesem, jsou-li všechny prvky množiny R \ {0} invertibilní. Konečně ideál okruhu R(+, ·, −, 0, 1) je maximální, je-li koatomem svazu všech ideálů okruhu R.

Poznámka 5.5. Je-li R(+, ·, −, 0, 1) okruh a I jeho pravý nebo levý ideál, pak I = R, právě když 1 ∈ I.

Důkaz. Přímá implikace je triviální. Jestliže 1 ∈ I a r ∈ R, potom r = 1 · r = (r · 1) ∈ I, je-li I pravý (levý) ideál. □

Věta 5.6. V netriviálním okruhu R(+, ·, −, 0, 1) je ekvivalentní:

(1) R je těleso,

(2) R neobsahuje žádné vlastní pravé ideály,

(3) R neobsahuje žádné vlastní levé ideály.

Důkaz. 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 ≠ i ∈ I a k němu inverzní prvek i^{−1} ∈ R, tedy 1 = i · i^{−1} ∈ I a proto I = R podle 5.5.

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

Věta 5.7. Nechť R(+, ·, −, 0, 1) je komutativní okruh a I jeho ideál. Potom faktorový okruh R/I je těleso právě tehdy, když I je maximální ideál.

Důkaz. Připomeňme, že podle 5.4 je svaz ideálů izomorfní svazu kongruencí okruhu, označme ρ_{I} kongruenci, která v tomto izomorfismu odpovídá ideálu I. Dále si uvědomme, že díky tomuto izomorfismu je I maximální ideál, právě když je ρ_{I} koatom svazu kongruencí a to je podle 3.10 ekvivalentní tomu, že faktorokruh R/ρ_{I} = R/I obsahuje pouze triviální kongruence. Tato podmínka ovšem díky 5.6 a opětovnému použití 5.4 tentokrát na okruh R/I nastává právě tehdy, když je R/I těleso. □

Definice. Komutativní okruh R(+, ·, −, 0, 1) nazveme oborem integrity, platí-li, že a · b = 0 implikuje a = 0 nebo b = 0. Prvek c ∈ R nazveme ireducibilním prvkem, jestliže c není invertibilní ani nulový a c = a·b implikuje, že a nebo b je invertibilní.

Poznamenejme, že každé komutativní těleso stejně jako okruh Z(+, ·, −, 0, 1) jsou obory integrity.

Označme N_{0} množinu nezáporných celých čísel.

Poznámka 5.8. Jestliže je R(+, ·, −, 0, 1) obor integrity, jehož každý ideál je hlavní, a a je ireducibilní prvek, pak aR je maximální ideál.

Důkaz. Vezměme libovolný (hlavní) ideál uR, pro který aR ⊂ uR a aR ≠ uR. Potom a ∈ uR, tedy existuje v ∈ R, pro nějž a = u·v. Protože je a ireducibilní musí být buď u nebo v invertibilní. Kdyby bylo invertibilní v, potom by u = u · v · v^{−1} = a · v^{−1} ∈ aR, což je ve sporu s předpokladem. Tedy je invertibilní u, a proto 1 = u · u^{−1} ∈ uR a uR = R díky 5.5 □

Definice. Buď R(+, ·, −, 0, 1) okruh. Položme R[x] = {p : N_{0} → R| {n|p(n) ≠ 0} je konečné}. Prvek p ∈ R[x] budeme zapisovat také ve tvaru p = ∑_{n∈N_{0}} p_{n}x^{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 ·, unární operaci − a nulární operace 0 a 1 pro p = ∑_{n∈N_{0}} p_{n}x^{n} a q = ∑_{n∈N_{0}} q_{n}x^{n}:

p + q = ∑_{n∈N_{0}} (p_{n} + q_{n})x^{n}, p · q = ∑_{n∈N_{0}} (∑_{i=0}^{n}p_{i} · q_{n−i})x^{n},

−p = ∑_{n∈N_{0}} −p_{n}x^{n}, 0 = ∑_{n∈N_{0}} 0x^{n}, 1 = 1x^{0} + ∑_{n>0} 0x^{n}.

Je-li p ≠ 0, budeme největší takové n ∈ N_{0}, že p_{n} ≠ 0, nazývat stupněm polynomu p. Stupeň polynomu 0 položíme roven −1. Stupeň polynomu p budeme označovat stp.

Poznámka 5.9. Nechť R(+, ·, −, 0, 1) je okruh a p, q ∈ R[x].

(1) R[x](+, ·, −, 0, 1) je okruh a množina {sx^{0}| s ∈ R} jeho podokruh izomorfní okruhu R(+, ·, −, 0, 1),

(2) stp + q ≤ max(stp, stq),

(3) je-li p, q ≠ 0, pak stp · q ≤ stp + stq, je-li navíc R oborem integrity, potom stp · q = stp + stq,

(4) R[x] je obor integrity právě tehdy, když je R obor integrity,

Důkaz. Mějme p = ∑_{n∈N_{0}} p_{n}x^{n}, q = ∑_{n∈N_{0}} q_{n}x^{n}, r = ∑_{n∈N_{0}} r_{n}x^{n} ∈ 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 = ∑_{n∈N_{0}} (p_{n} + q_{n})x^{n} = ∑_{n∈N_{0}} (q_{n} + p_{n})x^{n} = q + p,

(p + q) + r = ∑_{n∈N_{0}} ((p_{n} + q_{n}) + r_{n})x^{n} = ∑_{n∈N_{0}} (p_{n} + (q_{n} + r_{n}))x^{n} = p + (q + r).

Protože 0 je zjevně neutrální prvek operace + a vidíme, že p + (−p) = 0, je R(+, −, 0) komutativní grupa. Podobně

r · (p + q) = r · ∑_{n∈N_{0}} (p_{n} + q_{n})x^{n} = ∑_{n∈N_{0}} (∑_{i=0}^{n}r_{i} · (p_{n−i} + q_{n−i}))x^{n} =

= ∑_{n∈N_{0}} (∑_{i=0}^{n}r_{i} · p_{n−i})x^{n} + ∑_{n∈N_{0}} (∑_{i=0}^{n}r_{i} · q_{n−i})x^{n} = p · r + q · r,

důkaz druhé distributivity je symetrický. Konečně zbývá ověřit, že je R(·, 1) monoid:

(p · q) · r = ∑_{n∈N_{0}} ( ∑_{i+j=n} p_{i} · q_{j})x^{n}) · r = ∑_{n∈N_{0}} ( ∑_{i+j+k=n} p_{i} · q_{j} · r_{k})x^{n}) = p · (q · r).

a

p · 1 = ∑_{n∈N_{0}} (∑_{i=0}^{n}p_{i} · 1_{n−i})x^{n} ∑_{n∈N_{0}} (p_{n} · 1)x^{n} = p = 1 · p,

kde 1 = ∑_{n} 1_{n}x^{n}, tedy 1_{0} = 1 a 1_{n} = 0 pro všechna n > 0. Bezprostředně z konstrukce okruhu R[x] vidíme, že zobrazení ν : R → R[x] dané vztahem ν(r) = rx^{0} je prostý okruhový homomorfismus, proto díky 3.12 dostáváme izomorfismus okruhu R(+, ·, −, 0, 1) s podokruhem ν(R) = {sx^{0}| s ∈ R}.

(2) Plyne z inkluze {n| p_{n} + q_{n} ≠ 0} ⊆ {n| p_{n} ≠ 0} ∪ {n| q_{n} ≠ 0}.

(3) Označme ν = stp a μ = stq a uvědomme si pro každé n > ν +μ, že koeficient u x^{n} v polynomu p·q je ∑_{k=0}^{n} (p_{k} ·q_{n−k}) = ∑_{k=0}^{n−μ}(p_{k} ·0)+∑_{k=n−μ+1}^{n} (0·q_{n−k}) = 0, proto stp · q ≤ ν + μ.

Je-li R obor integrity, máme koeficient polynomu p · q u x^{ν+μ} :

∑_{k=0}^{ν+μ}(p_{k} · q_{n−k}) = ∑_{k=0}^{n−μ−1}(p_{k} · 0) + p_{ν} · q_{μ} + ∑_{k=n−μ+1}^{n} (0 · q_{n−k}) = p_{ν} · q_{μ} ≠ 0,

neboť p_{ν} ≠ 0 a q_{μ} ≠ 0.

(4) Je-li R[x] obor integrity, je každý jeho podokruh oborem integrity, tedy i okruh R podle (1). Je-li R obor integrity a p, q ≠ 0, máme podle (3) stp · q = stp + stq ≥ 0, proto p · q ≠ 0. □

Okruhu R[x](+, ·, −, 0, 1) budeme říkat okruhem polynomů jedné neurčité) a jeho prvkům polynomy.

Věta 5.10 (Dělení se zbytkem). Nechť R(+, ·, −, 0, 1) je obor integrity, a, b ∈ R[x], kde b = ∑ b_{n}x^{n}. Předpokládejme, že m = stb ≥ 0 a b_{m} je invertibilní v R. Pak existují takové jednoznačně určené polynomy q, r ∈ R[x], že a = b·q+r a str < stb.

Důkaz. Tvrzení dokážeme indukcí podle n = sta − stb. Jestliže sta < stb, a tedy n < 0, stačí položit q = 0 a r = a. Platí-li existenční tvrzení pro všechna i < n, dokážeme ho pro n. Buď a = ∑ a_{n}x^{n} a položme q_{0} = a_{n+m} b_{m}^{−1}x^{n} a t = a − q_{0} · b. Podle 5.9(2) a (3) je stt ≤ max(sta, stq_{0} + stb) = n + m a koeficient polynomu t u mocniny x^{n+m} je a_{n+m} − a_{n+m} b_{m}^{−1}b_{m} = 0, tedy stt − stb < n a můžeme pro polynom t užít indukčního předpokladu, podle nějž existují takové polynomy q_{1} a r, že t = b · q_{1} + r a str < stb. Položíme-li nyní q = q_{0} + q_{1}, dostáváme

b · q + r = b · q_{0} + b · q_{1} + r = b · q_{0} + t = a.

Konečně předpokládejme, že a = b · q′ + r′ a str′ < stb. Potom b · (q − q′) = r′ − r a podle 5.9(3) a protože st(r′ − r) < stb, dostáváme r′ − r = 0, a proto q − q′ = 0 □

Věta 5.11. Nechť T (+, ·, −, 0, 1) je komutativní těleso. Pak je každý ideál okruhu T [x](+, ·, −, 0, 1) hlavní.

Důkaz. 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] ⊆ I. Nechť i ∈ I. Pak podle 5.10 existují takové polynomy q, r ∈ T [x], že i = p · q + r a st(r) < st(p). Protože r = i − p · q ∈ I a st(p) byl minimální, je nutně r = 0 a pT [x] = I. □

Uvážíme-li, že podle 5.7 je faktor komutativního okruhu podle maximálního ideálu těleso, dostáváme s využitím 5.8 důsledek předchozí věty:

Důsledek 5.12. Je-li T (+, ·, −, 0, 1) komutativní těleso a p ∈ T [x] ireducibilní polynom, pak T [x]/pT [x] je komutativní těleso.

Příklad 5.13 (Konstrukce tělesa o p^{n} prvcích). Buď p prvočíslo a uvažujme těleso Z_{p}(+, ·, −, 0, 1). Najdeme-li ireducibilní polynom u ∈ Z_{p}[x] stupně n, pak je podle 5.12 okruh Z_{p}[x]/uZ_{p}[x] tělesem. Označíme-li si [a]_{u} rozkladové třídy faktoru Z_{p}[x]/uZ_{p}[x], pak díky 5.4 snadno nahlédneme, že Z_{p}[x]/uZ_{p}[x] = {[a]_{u}| sta < n} a že |Z_{p}[x]/uZ_{p}[x]| = p^{n}.

Vezmeme-li polynom x^{3} + x + 1 ∈ Z_{2}[x] snadno ověříme, že není součinem polynomu stupně 1 a polynomu stupně 2, tedy že je ireducibilní. Rozkladové třídy [a]_{x^{3} +x+1} tělesa T = Z_{2}[x]/(x^{3} + x + 1)Z_{p}[x] budeme značit [a]. Vidíme, že rozkladové třídy T reprezentuje množina polynomů P = {0, 1, x, x + 1, x^{2}, x^{2} + 1, x^{2} + x, x^{2}+x+1}, t.j. T = {[a]| a ∈ P }. Připomeňme, že [a]±[b] = [a±b], tedy vezmeme-li a, b ∈ P, pak a±b ∈ P. Díky 5.4 snadno nahlédneme, že [a] = [(a)mod (x^{3}+x+1)], kde (a)mod (x^{3}+x+1) znamená zbytek po dělení polynomu a polynomem x^{3}+x+1 podle 5.10. Proto [a]·[b] = [a·b] = [(a·b)mod (x^{3}+x+1)], tedy vezmeme-li a, b ∈ P, pak (a · b)mod (x^{3} + x + 1) ∈ P, čímž jsme kompletně popsali okruhovou strukturu pomocí reprezentantů P.