ALGEBRA I PRO INFORMATIKY

Úvod

Tento text si klade za cíl seznámit studenty informatiky s nejzákladnějšími pojmy, koncepty a v neposlední řadě i konkrétními objekty, které jsou předmětem zkoumání současné algebry. Výběr a uspořádání teorie, kterou zde prezentujeme, je zvolen s ohledem na tři základní hlediska. Především se snažíme navázat na koncepty a způsoby uvažování, které jsou pro studenta informatiky přirozené, dále se v rámci velmi omezeného prostoru pokoušíme demonstrovat několik elemntárních algebraických výsledků, které jsou užitečné v informatických aplikacích a konečně za nepominutelné považujeme přístup, který můžeme nepříliš přesně označit jako kontextuální, a jímž míníme seznámení studenta s terminologickými a historickými kontexty současné algebry.

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 algebraických objektech (které se budou zpravidla opírat o nějaký systém axiomatických požadavků na operace), uvedeme několik motivačních příkladů, které by nám pomohly usnadnit porozumění důvodům (at’ už praktickým tak historickým), proč právě tu či onu vlastnost sledujeme.

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.

Příklad 0.1. Uvažujme 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. Zaved’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ásobení ,,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).

Date: 20.12.2013.

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).

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 ·. Navíc množina nZ je uzavřená na operace + i ·.

Připomeňme, že relací na množině A rozumíme libovolnou podmnožinu A × A. Necht’ ρ 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} ⊆ ρ,

- reflexivní, v případě, že id ⊆ ρ a

- tranzitivní, pokud ρ^{+} ⊆ ρ. Ekvivalencí budeme nazývat každou symetrickou, reflexivní a tranzitivní relaci.

Je-li ρ ekvivalence na množině A, připomeňme, že faktorem množiny (často se také mluví o kvocientu) A podle ekvivalence ρ jako množinu A/ρ = {[a]_{ρ}| a ∈ A}, kde [a]_{ρ} = {b ∈ A| (a, b) ∈ ρ} jsou rozkladové třídy (kosety), tedy 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}.

Pro libovolné zobrazení π : A → B je relace ker f = {(x, y) ∈ A×A| π(x) = π(y)} ekvivalence.

Příklad 0.3. Vezměme přirozené číslo n ≥ 2 a označme ≡ (mod n) relaci na množině celých čísel Z danou předpisem: a ≡ b (mod n) ↔ n/(a − b). Není těžké si uvědomit, že se jedná o ekvivalenci (obvykle se jí říká kongruence na Z). Navíc si můžeme všimnout jejího těsného vztahu k zobrazení F_{n} z 0.2, nebot’ platí, že a ≡ b (mod n), právě když F_{n}(a) = F_{n}(b), tedy kongruence ≡ (mod n) je rovná právě ekvivalence ker F_{n}.

Teorie čísel, tedy otázky dělitelnosti na přirozených (nebo celých číslech), je jedním z historických zdrojů algebraických konceptů a terminologie. Dříve než začneme používat termín kongruence v mnohem obecnější situaci, připomeňme si několik jednoduchých vlastností, které kongruence na celých číslech má:

Poznámka 0.4. Pro každé a, b, c, d ∈ Z a k, n ∈ N, kde n > 1, platí:

(1) jestliže a ≡ b (mod n) a c ≡ d (mod n), pak a + c ≡ b + d (mod n),

a − c ≡ b − d (mod n), a · c ≡ b · d (mod n) a a^{k} ≡ b^{k} (mod n),

(2) jestliže c ≠ 0, pak a ≡ b (mod n), právě když a · c ≡ b · c (mod cn),

(3) jestliže NSD(c, n) = 1, pak a ≡ b (mod n), právě když a · c ≡ b · c (mod n).

Důkaz. (1) Předpokládáme-li, že n/(a − b), (c − d), pak

n/(a − b) + (c − d) = (a + c) − (b + d),
n/(a − b) − (c − d) = (a − c) − (b − d),
n/(a − b) · c + b · (c − d) = (a · c) − (b · d)

a poslední kongruenci dostaneme indukčním použitím předchozí pro a = c a b = d. (2) a ≡ b (mod n) ⇔ n/(a − b) ⇔ nc/(ac − bc) ⇔ ac ≡ bc (mod cn).

(3) Přímá implikace plyne okamžitě z (1), protože c ≡ c (mod n). Jakmile n/ac− bc = (a − b)c a c a n jsou nesoudělná čísla, pak nutně n/(a − b). □

Definice. Uvažujme na množině A binární operaci ∗ a ekvivalenci ∼. Ř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 Poznámce 0.4 jsme tedy zjistili, že je kongruence ≡ (mod n) slučitelná s oběma operacemi + i ·.

Příklad 0.5. Mějme kladná celá čísla n_{1}, …, n_{k} a položme n = n_{1}·· · ··n_{k}. Zaved’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 ·.

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

Poznámka 0.6 (Čínská věta o zbytcích). Necht’ 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. V Příkladu 0.5 jsme si uvědomili, ž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é. Necht’ 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. □

Uvedený důkaz Čínské věty o zbytcích sice není konstruktivní, následující příklad ovšem ukazuje, že hledat vzory zobrazení H není těžké.

Příklad 0.7. Uvědomme si, že podle Čínské věty o zbytcích existuje právě jedno x ∈ Z_{35} spňující kongruence x ≡ 2 (mod 5) a x ≡ 3 (mod 7). pokusíme se ho najít. Nejprve si všimněme, že z první kongruence plyne, že x = 5y + 2 pro vhodná y ∈ Z a toto vyjádření dosadíme do druhé kongruence a pomocí Poznámky 0.4 budeme kongruenci upravovat ekvivalentními úpravami:

5y + 2 ≡ 3 (mod 7) ⇔ 5y ≡ 1 (mod 7) ⇔ 3 · 5y ≡ 3 · 1 (mod 7) ⇔ y ≡ 3 (mod 7).

Poznamenejme, že jsme v posledním kroku využili toho, že umíme najít ,,inverz modulo 7”k číslu 5 jímž je 3). Hledaným řešením je tedy x = 5 · 3 + 2 = 17.

Čí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ý při potřebě exaktního počítání s velkými čísly lze použít.

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

Poznámka 0.8. 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ě tehdy, 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.9. Bud’ 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. Položme n = ∏_{i=1}^{k} n_{i} a zvolme libovolné a ∈ Z_{n}. Dále položme n_{i} = p_{i}^{r_{i}} a uvažujme zobrazení f : Z_{n} → ∏_{i=1}^{k} Z_{p_{i}^{r_{i}}} z Poznámky 0.6. Protože jsou n_{1}, …, n_{k} nesoudělná čísla, je f podle 0.6 bijekce. Nyní položme (a_{1}, …, a_{k}) = f(a). 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 bud’ a_{i} = 0 nebo p dělí a_{i}, proto NSD(a_{i}, n_{i}) ≠ 1. Naopak, jestliž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.8 □

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. □

Následující příklad ukazuje, že se v definici neutrálního prvku nemůžeme omezit jen na jednu ze dvou rovností:

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. Necht’ · je binární operace na množině S a 1 je 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.5 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. Uved’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) Necht’ 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. Zaved’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), tedy M(X)(·) je tzv. slovní monoid.

(2) Bud’ 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).

(4) Z_{n}(·) je konečný komutativní monoid, který není grupou, protože prvek 0 není invertibilní.

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 vzhledem k operaci · (a −s bude inverz vzhledem k operaci +).

Poznámka 1.4. Bud’ 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 necht’ α(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. Je-li S(·) monoid a s, t ∈ S jeho invertibilní prvky, pak s · t a s^{−1} jsou také invertibilní. Navíc (s · t)^{−1} = t^{−1} · s^{−1} a (s^{−1})^{−1} = s.

Důkaz. Protože s · s^{−1} = s^{−1} · s = 1, je zřejmě s^{−1} invertibilní a díky 1.4 máme (s^{−1})^{−1} = s. Nyní stačí dokázat, že je prvek t^{−1} · s^{−1} inverzní k s · t:

(s · t) · (t^{−1} · s^{−1}) = s · (t · t^{−1}) · s^{−1} = s · 1 · s^{−1} = s · s^{−1} = 1

a symetricky

(t^{−1} · s^{−1}) · (s · t) = t^{−1} · (s^{−1} · s) · t = t^{−1} · 1 · t = t^{−1} · t = 1.
□

Všimněme si, že jsme v předchozí úvaze dokázali, že množina všech invertibilních prvků monoidu S(·) je uzavřená na operaci ·.

Poznámka 1.7. Necht’ 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ů M(X)(·) obsahuje pouze neutrální prvek ϵ.

(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 (značíme je GL_{n}(T)).

(4) Ukážeme, že Z_{n}^{∗}(·) = {0 < a < n| NSD(a, n) = 1}. Jestliže a ∈ Z_{n}^{∗}, existují x ∈ Z_{n} a y ∈ Z, pro něž ax + by = 1. Je-li s společný dělitel čísel a, n, pak s/(ax + ny) = 1, proto NSD(a, n) = 1. Necht’ naopak NSD(a, n) = 1, potom díky Euklidovu algoritmu existují x ∈ Z_{n} a y ∈ Z, pro které ax + ny = 1, proto a^{−1} = xmod n, tudíž a ∈ Z_{n}^{∗}. Jednoduchým důsledkem tohoto pozorování je fakt, že |Z_{n}^{∗}| = φ(n).

Definice. Podgrupou grupy G(·) budeme rozumět každou podmnožinu H množiny G, která je uzavřená na ·, obsahuje prvek 1 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.

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

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

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

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

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

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

Důkaz. (1) Plyne okamžitě z definice podgrupy a vlastností operace · na G (srovnej s 1.6).

(2) 1 ∈ H_{i} pro všechna i ∈ I podle, tedy 1 ∈ ⋂_{i∈I} H_{i}. 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}.

(3) 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}.

(4) 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ž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 (elementá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 tzv. Kleinova normální podgrupa K = {Id, (12)(34), (13)(24), (14)(23)}). Uved’me 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.

(3) Protože det(A · B) = det(A) · det(B), snadno spočítáme, že množiny S = {A ∈ GL_{n}(T)| det(A) = 1} a P = {A ∈ GL_{n}(T)| det(A) = ±1} jsou normální podgrupy grupy GL_{n}(T)(·).

(4) 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). Naopak, 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, dostaneme 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.

Definice. Necht’ H a K jsou dvě podmnožiny grupy G(·) a g ∈ G. Definujme množiny H · K = {h · k| h ∈ H, k ∈ K}, gH = {g}H a Hg = H{g}.

V případě grup s operací · budeme často psát hk místo h · k a HK místo H · K.

Příklad 1.11. (1) 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ě 1 = 1 · 1 ∈ HK 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}).

(2) Uvažujeme-li komutativní grupu A(+) a H, K její podgrupy, pak H + K = {h + k| h ∈ H, k ∈ K} je podle předchozího pozorování opět podgrupa. Speciálně, vezmeme-li grupu celých čísel Z(+), pak 30Z + 54Z = {30x + 54y| x, y ∈ Z} = NSD(30, 54)Z = 6Z.

Všimněme si také, že 30Z ∩ 54Z = {z ∈ Z| 30/z, 54/z} = nsn(30, 54)Z = 270Z.

Definice. 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).

Poznámka 1.12. Necht’ 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ý. 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í, 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ředpoklá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. Bud’ 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.

Příklad 1.15. Z předchozího důsledku okamžitě plynou následující pozorování: (1) Grupa prvočíselného řádu obsahuje jen triviální podgrupy, tedy G a {1}.

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

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

Věta 1.16. Necht’ 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 (= lmod 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]_{ρ}. 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 ρ ekvivalence 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í ·. □

Všimněme si, že kongruence ≡ (mod n) na množině Z(+) popsaná v Příkladu 0.3 je právě ekvivalencí rmodnZ = lmodnZ.

Poznámka 1.17. Necht’ 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 ker f = {(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.18. Necht’ 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 ker f = rmod Kerf = lmod Kerf,

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

(6) f je prostý homomorfismus, právě když Kerf = {1} a to nastává, právě když ker f = id.

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}(·). Podle 1.17 je 1 = g(1) ∈ g(H). 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.17.

Poznamenejme, že 1 ∈ f^{−1}(H) 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), proto je f^{−1}(H) 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.16.

(6) Je-li f prosté, pak existuje jediný vzor jednotky, tedy Kerf = {1} a jestliže ker f = id, pak je zřejmě f prosté. Konečně, jestliže Kerf = {1}, potom ker f = rmod Kerf = rmod {1} = id podle (4). □

Příklad 1.19. že následující dvojice přirozeně definovaných zobrazení jsou grupové homomorfismy:

(1) V rámci kurzu lineární algebry bylo dokázáno, že znaménko součinu permutací je rovno součinu jejich znamének, tedy, že sgn : S_{n} → {1, −1} je homomorfismus grupp permutací na n prvcích a grupy {1, −1}(·). Snadno nahlédneme, Ker sgn = A_{n}, což je podle 1.18 normální podgrupa grupy S_{n}.

(2) Rovněž v lineární algebře se dokazuje, že determinant det je homomorfismus z grupy regulárních matice n × n nad tělesem T do multiplikativní grupy tělesa T \{0}(·) je homomorfismus a tedy Ker det je díky 1.18 normální podgrupa matice s determinantem 1 .

(3) Uvažujme pro každé k ∈ Z_{n} na grupě Z_{n}(+) zobrazení μ_{k} : Z_{n} → Z_{n} dané předpisem μ_{k}(a) = (k · a)mod n. Potom se jedná opět o grupový homomorfismus.

Je-li G množina a ρ ekvivalence na G, pak přirozenou projekci na faktorovou množinu G/ρ rozumíme zobrazení π_{ρ} : G → G/ρ dané podmínkou π_{ρ}(g) = [g]_{ρ}, kde g ∈ G. Všimněme si, že ker π_{ρ} = ρ.

Poznámka 1.20. Necht’ 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íme 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.16, která říká, že každé ekvivalenci ρ slučitelné s binární operací na grupě jednoznačně odpovídá normální podgrupa H = [1]_{ρ}, nám umožňuje faktorovou množinu zapisovat ve tvaru G/H, tedy G/H := G/rmodH.

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} = aH = Ha (poslední rovnosti platí podle 1.12(4) a (5)).

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

Věta 1.22 (Věta o homomorfismu). Bud’ f : G_{1} → G_{2} homomorfismus grup G_{1}(·) a G_{2}(·) a necht’ 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.17. Tedy a ∈ Kerf, čímž jsme ověřili, že H ⊆ Kerf.

Naopak, necht’ 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.17, 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. Necht’ 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.23 (1. věta o izomorfismu). Necht’ 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.18(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.22 pro H = Kerf a dostaneme přímo požadovaný izomorfismus g : G_{1}/Kerf → f(G_{1}). □

Příklad 1.24. 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.23 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.25 (2. věta o izomorfismu). Necht’ 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.22 pro homomorfismy π_{K} : G → G/K (jako f z 1.22) a π_{H} : G → G/H (jako π_{H} z 1.22). Protože podle předpokladu H ⊆ K = Kerπ_{K}, dává nám 1.22 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.18(4). Nyní pro homomorfismus g využijeme 1.23, abychom dostali G/K = g(G/H) ≅ (G/H)/Kerg = (G/H)/(K/H). □

2. Cyklické grupy

Připomeňme, že podle 1.9(2) 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. Bud’ 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.

Příklad 2.1. (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.

Necht’ 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.2. Necht’ 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.3. Necht’ G(·) je grupa a a ∈ G. Potom pro každé n, m ∈ Z platí, že a^{−n} = (a^{n})^{−1} a (a^{n})^{m} = a^{nm}.

Věta 2.4. Bud’ 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.2 jde o homomorfismus a ϕ(Z) = ⟨g⟩ = G, tedy ϕ je zobrazení na. Nyní podle 1.23 je Z/Kerϕ(+) ≅ G(·). Zbývá si rozmyslet, jak vypadá Z/Kerϕ. Z 1.10(4) víme, že Kerϕ = nZ pro vhodné nezáporné celé n. V případě, ž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.24. □

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(4) 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.24. Zvolíme-li podgrupu H grupy Z_{n}(+), pak f_{n}^{−1}(H) je podle předchozí úvahy a 1.18(3) cyklická podgrupa Z, tedy H = f_{n}(f_{n}^{−1}(H)) je cyklická podgrupa Z_{n}(+). □

Připomeňme, že pro každé přirozené k značíme kZ = ⟨k⟩ = {kz| z ∈ Z}. Podobně budeme pro každé k ∈ Z_{n} označovat kZ_{n} = ⟨k⟩ = {k · z| z ∈ Z_{n}}.

Poznámka 2.6. Necht’ n ∈ N, a ∈ Z_{n} \ {0} a k/n. Pak aZ_{n} = kZ_{n}, právě když NSD(a, n) = k.

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}. □

Uvědomíme-li si, že speciálním případem předchozí poznámky pro k = 1 je tvrzení, že aZ_{n} = Z_{n} (tj. a generuje grupu Z_{n}(+)), právě když NSD(a, n) = 1, okamžitě dostáváme:

Důsledek 2.7. 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}(·).

Poznámka 2.8. Bud’ 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.3. □

Věta 2.9. Necht’ 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. Pak je H podle 2.5 cyklická, a tedy existuje h ∈ H, pro H = ⟨h⟩. Z 2.8 plyne, že (k · h)mod n = 0, a 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. □

Příklad 2.10. (1) Uvažujme konečnou cyklickou grupu G(·). Potom nám 2.7 říká, že G(·) obsahuje právě φ(|G|) generátorů. Protože díky Lagrangeově větě řád podgrupy vždy dělí řád grupy podle 2.9 G(·) pro každý dělitel řádu cyklické grupy existuje právě jedna podgrupoa daného řádu, obsahuje G(·) právě tolik podgrup, kolik existuje dělitelů jejího řádu. Máme-li n = ∏_{i=1}^{k} p_{i}^{r_{i}}, kde p_{1} < p_{2} < ⋯ < p_{k} jsou prvočísla a r_{i} ∈ N, pak dělitely n jsou právě čísla ∏_{i=1}^{k} p_{i}^{s_{i}}, kde 0 ≤ s_{i} ≤ r_{i}, tedy G(·) obsahuje právě ∏_{i=1}^{k}(r_{i} +1) podgrup a podle 0.9 právě ∏_{i=1}^{k}(p_{i} −1)p_{i}^{r_{i}−1} generátorů.

(2) Vezměme cyklickou grupu Z_{50}(+). Protože 50 = 2·5^{2}, dostáváme z bodu (1), že Z_{50}(+) obsahuje φ(50) = 20 generátorů a právě 6 = 2 · 3 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.6 víme, že ⟨42⟩ = ⟨NSD(42, 50)⟩ = ⟨2⟩ = 2Z_{50}, a jedná se tedy o podgrupu řádu 25 = \frac{50}{2}.

Následující tvrzení je pro prvočíselné n známo také jako Malá Fermatova věta:

Věta 2.11 (Eulerova věta). Pro nesoudělná kladná celá čísla a, n > 1 je

a^{φ(n)} ≡ 1 (mod n).

Důkaz. Díky Poznámce 0.4 tvrzení stačí dokázat pro kladné a < n. Použijeme k tomu Poznámku 2.8, kde jako grupu G vezmeme grupu invertibilních prvků Z_{n}^{∗}(·) monoidu Z_{n}(·) tj. prvků nesoudělných s n podle 2.7. Protože a ∈ Z_{n}^{∗}, je (a^{φ(n)})mod n = (a^{|Z_{n}^{∗}|})mod n = 1 díky 2.8 a 2.7. □

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

Důkaz. Nejprve ukážeme, že (a^{m+1})mod pq = a.

Podle Věty 2.11 (x^{m})mod p = 1 a (y^{m})mod q = 1 pro ta x, která nejsou násobkem p a ta y, která nejsou násobkem q. Dále zřejmě platí ((up)^{m+1})mod p = 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 nyní 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.6 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.

Nyní indukcí díky 2.3 dostáváme, ž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}. □

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).

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í podle 2.12 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 dvojice čísel (n, e) a soukromý klíč tvoří tajný exponent d. Chceme-li informaci vyjádřenou posloupností hodnot a_{1}, …, a_{k} ∈ Z_{n} adresovat majiteli soukromého klíče, stačí ji zašifrovat pomocí mocnění veřejně známou hodnotou e v monoidu Z_{n}(·), tj. odeslat zprávu (a_{1}^{e})mod pq, …, (a_{k}^{e})mod pq. K jejímu rozluštění stačí umocnit v Z_{n}(·) 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 n, …, (a_{k}^{d})mod n, mohou si příjemci zprávy stejným způsobem (tj. umocněním na veřejně známý exponent e: ((a_{1}^{d})^{e})mod n, …, ((a_{k}^{d})^{e})mod n = a_{1}, …, a_{k}) ověřit, že odesilatel zprávy opravdu zná tajný exponent (vlastnictví soukromého klíče tedy garantuje pravost elektronického podpisu).

Poznamenejme, že je ze znalosti n = pq a e obtížné najít d (odpovídá to nalezení prvočíselného rozkladu čísla n, což je úloha, pro níž není znám algoritmus polynomiální 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 je elegantnější, využijeme-li jistých znalostí z teorie polynomů nad obecným tělesem, proto ho provedeme až v příštím semestru:

Věta 2.14. Necht’ T (+, ·) je komutativní těleso a necht’ G je konečná podgrupa multiplikativní grupy T \ {0}(·). Potom G je cyklická grupa.

Příklad 2.15. (1) Je-li p prvočíslo, pak Z_{p} je se sčítáním a násobením modulo p těleso, proto je podle předchozí věty Z_{p}^{∗}(·) cyklická grupa řádu p − 1. Je-li p − 1 = ∏_{i=1}^{k} p_{i}^{s_{i}} prvočíselný rozklad, kde p_{1} < p_{2} < ⋯ < p_{k} a r_{i} > 0, pak můžeme generátory a podgrupy grupy Z_{p}^{∗}(·) počítat postupem Příkladu 2.10. Tedy Z_{p}^{∗}(·) obsahuje právě ∏_{i=1}^{k}(p_{i} − 1)p_{i}^{r_{i}−1} generátorů a ∏_{i=1}^{k}(r_{i} + 1) podgrup.

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

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). Je-li I množina, budeme říkat zobrazení Ω : I → N_{0} = N ∪ {0} typ. Řekneme, že A(α_{i}| i ∈ I) je algebra typu Ω, je-li A neprázdná a pro každé i ∈ I je α_{i} právě Ω(i)-ární operací na A.

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.

Všimněme si, že množina A^{0} sestává právě z prázdné posloupnosti, tedy je jednoprvková. Nulární operace tudíž vyznačuje v algebře jeden její prvek, a proto ji můžeme s tímto vyznačeným prvkem ztotožnit.

Definice. Bud’ α 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.

Příklad 3.1. (1) Uvážíme grupu G(·) s unární operací inverzního prvku ^{−1} a nulární operací 1. Pak G(·), G(·,^{−1} ), G(·,^{−1} , 1) tvoří (nejen formálně) různé algebery. Nahlédneme, jak v jednotlivých případech vypadají podalgebry:

(a) Podalgebry G(·,^{−1} , 1) jsou právě podmnožiny G uzavřené na 1 (tj. obsahující prvek 1), na inverzy a součiny, což jsou podle definice právě podgrupy grupy G(·).

(b) Je-li H neprázdná podalgebra G(·,^{−1} ), pak existuje h ∈ H, a proto 1 = h·h^{−1} ∈ H. Tedy neprázdné podlagebry G(·,^{−1} ) jsou právě podgrupy G(·), navíc prázdná množina je v souladu s definicí také podalgebra.

(c) Podalgeber algebry G(·) je obecně mnohem víc než podgrup grupy G(·). Například pro každé g ∈ G a n ∈ N tvoří množina {g^{k}| k ≥ n} podalgebru G(·). V případě G(·) = Z(+) to znamená, že množiny {ak| k ≥ n} jsou podalgebry, speciálně množina všech přirozených čísel, která podgrupou Z(+) určitě není.

(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). Všimněme si, že pro nekonečné těleso potřebujeme uvažovat na V (+, ·t|t ∈ T) nekonečně mnoho unárních operací.

Podalgebrou algebry V (+, ·t|t ∈ T) jsou právě podprostory tohoto vektorového prostoru a prázdná množina.

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. Necht’ 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})). Zobrazení f : A → B mezi dvěma algebrami A(α_{i}| i ∈ I) a B(α_{i}| i ∈ I) stejného typu Ω budeme říkat homomorfismus, je-li slučitelné se všemi operacemi α_{i}, i ∈ I. Bijektivní homomorfismus budeme nazývat izomorfismus.

Příklad 3.2. (1) Bud’ G_{i}(·) pro i = 1, 2 grupy s unární operací inverzního prvku −1 a nulární operací 1. pak každý homomorfismus grup G_{1}(·) a G_{2}(·) je podle 1.17 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) Necht’ 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. Necht’ ρ je ekvivalence 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 ker f relaci danou předpisem: (a, b) ∈ ker f ⇔ f(a) = f(b). Nyní jsme připraveni vyslovit obdobu Poznámky 1.18 pro obecné algebry:

Poznámka 3.4. Necht’ 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) ker f 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.18.

(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) Necht’ 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}) ∈ ker f, 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})) ∈ ker f. Že se jedná o ekvivalenci je snadné cvičení. □

Poznámka 3.5. Necht’ A(α_{i}| i ∈ I) je algebra a A_{j} jsou podalgebry A a ρ_{j} kongruence na A pro každé j ∈ J.

(1) ⋂_{j∈J} A_{j} je podalgebra A,

(2) ⋂_{j∈J} ρ_{j} je kongruence na A.

Důkaz. (1) Obdoba Poznámky 1.9(2). Necht’ α_{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. Necht’ 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. Necht’ 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.

Příklad 3.7. Všechny uzávěrové systémy nad množinou A tvoří uzávěrový systém nad P(A). Zřejmě P(A) obsahuje A a je uzavřené na libovolné průniky, tedy jde o uzávěrový systém. Uvážíme-li průnik množiny uzávěrových systémů na A, pak i ten musí obsahovat A (všechny uzávěrové systémy obsahují A) a rovněž musí obsahovat průnik každého podsystému, nebot’ tato podmínka platí o všech uzávěrových systémech.

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čovat algebru jen její nosnou množinou.

Nyní zobecníme definici ze začátku 2.kapitoly. Všimněme si, že pojem můžeme zavést pro každý uzávěrový systém.

Definice. Bud’ 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⟩).

Příklad 3.8. (1) Uvážíme-li grupu permutací S_{n} na množině {1, …, n} jako algebru S_{n}(∘,^{−1} , Id), pak ⟨(12), (12 … n)⟩ = S_{n} pro každé n > 1.

(2) Uvažujme algebru Z(+). Pak sice ⟨{1}⟩ = N, ale nejmenší podalgebra Z(+) obsahující množinu {−1, 1} je už rovna celému Z tj. ⟨{−1, 1}⟩ = Z.

(3) Uvažujme-li nyní algebru Z(+, −), pak ⟨1⟩ = Z.

Poznámka 3.9. Bud’ f, g : A → B dva homomorfismy algeber stejného typu a necht’ 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 necht’ 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.10. (1) Uvažujme grupu celých čísel Z(+) a G(+) nějaký grupoid, tedy algebru s jednou binární operací +. Necht’ 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í −. Necht’ f, g : Z → G je homomorfismus. Potom ⟨1⟩ = Z, a podle 3.9 jsou f a g shodné, jestliže f(1) = g(1).

Definice. Necht’ ρ 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.

Poznámka 3.11. 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 necht’ [a_{j}]_{ρ} = [b_{j}]_{ρ}, kde 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. Necht’ ρ ⊆ σ jsou dvě ekvivalence na A. Definujme relaci σ/ρ na A/ρ následovně: ([a]_{ρ}, [b]_{ρ}) ∈ σ/ρ ⇔ (a, b) ∈ σ.

Poznámka 3.12. Bud’ ρ 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. □

Podobně jako u grup řekneme, že dvě algebry A(α_{i}| i ∈ I) a B(α_{i}| i ∈ I) stejného typu jsou izomorfní, existuje-li mezi nimi izomorfismus (budeme psát A(α_{i}| i ∈ I) ≅ B(α_{i}| i ∈ I) nebo zjednodušeně A ≅ B bude-li jasné nebo naopak pro další úvahy nepotřebné vědět jaký systém operací na algebrách uvažujeme). Nyní už můžeme vyslovit obecné verze Věty o homomorfismus a Vět o izomorfismus:

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

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

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}) ∈ ker f.

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

Konečně dokažme závěrečnou ekvivalenci. Protože g(G_{1}/ρ) = f(G_{1}), 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}) ∈ ker f, pak g([a_{1}]_{ρ}) = f(a_{1}) = f(a_{2}) = g([a_{2}]_{ρ}), a proto (a_{1}, a_{2}) ∈ ρ. Ověřili jsme, že ker f ⊆ ρ, a protože už víme, že ρ ⊆ ker f, máme rovnost ρ = ker f. 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.14 (1. věta o izomorfismu). Necht’ 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.23 použijeme Větu o homomorfismu 3.13 na ρ = ker f. □

Věta 3.15 (2. věta o izomorfismu). Necht’ ρ ⊆ σ 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.25: nejprve použijeme 3.13 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 ker g = σ/ρ a použít 3.14. □

Připomeňme, že term je jakákoli proměnná a jsou-li t_{1}, …, t_{n} termy a α funkční symboly (operace) četnosti n, pak i α(t_{1}, …, t_{n}), je term, dále je-li P predikát četnosti n a t_{1}, …, t_{n} jsou termy, pak je výraz P (t_{1}, …, t_{n}) atomickou formulí a a jsou-li φ a ψ dvě formule, pak výrazy (φ → ψ), (φ ∧ ψ), (φ ∨ ψ), ¬φ, ∀φ a ∃φ jsou rovněž formule. Jazykem predikátové logiky (prvního řádu) potom rozumíme všechny formule, které vyniknou z daného systémem funkčních a predikátových symbolů.

Dále připomeňme, že formule φ platí ve struktuře A (tedy například v algebře s daným systémem operací, které se v jazyce algeber daného typu objeví jako funkční symboly), právě když je φ splněna každým ohodnocením proměnných nosné množiny A struktury A. Uzavřenou formulí rozumíme formuli, která neobsahuje žádnou volnou proměnnou. V našich úvahách se pro jednoduchost omezíme na jazyk s jediným predikátovým symbolem = a proměnnými jako prvky algebry.

Poznámka 3.16. Necht’ A(α_{i}| i ∈ I) a B(α_{i}| i ∈ I) jsou dvě izomorfní algebry (stejného typu). Potom uzavřená formule φ jazyka algeber platí v algebře A(α_{i}| i ∈ I), právě když platí v algebře B(α_{i}| i ∈ I).

Důkaz. Necht’ f : A → B je nějaký izomorfismus algeber A = A(α_{i}| i ∈ I) a B = B(α_{i}| i ∈ I), φ formule. Vezmeme-li nějaké ohodnocení e formule φ v A, označíme fe, které hodnotě e(x) nějaké proměnné v A přiřadí hodnotu fe(x) téže proměnné v B. Je-li E množina všech ohodnocení formule φ v A, vidíme, že množina {fe| e ∈ E} tvoří právě množinu všech ohodnocení formule φ v B, nebot’ f je bijekce. Dále snadno nahlédneme, že a pro každou uzavřenou formuli φ platí, že bud’ A ⊧ φ nebo A ⊧ ¬φ, a protože f je izomorfismus algeber A a B, stačí indukcí podle počtu kroků, jimiž je φ odvozena z atomický formulí a jimiž jsou v nich vytvořeny zúčastněné termy, dokázat A ⊧ φ implikuje B ⊧ φ.

Nejprve uvážíme jedinou atomickou formuli t = s, kde t = t(x_{1}, …, x_{n}) a s = s(x_{1}, …, x_{n}) jsou termy v proměnných x_{1}, …, x_{n}. Mějme realizaci nějaké funkčního symbolu na obou algebrách, tedy právě n-ární operaci α_{i} pro nějaké i ∈ I a předpokládáme například, že t = α_{i}(t_{1}, …, t_{n}), kde t_{1}, …, t_{n} jsou termy a necht’ e je nějaké ohodnocení formule t = s. Protože e(α_{i}(t_{1}, …, t_{n}) = α_{i}(e(t_{1}), …, e(t_{n})) a z indukčního předpokladu užitého pro termy t_{1}, …, t_{n} víme, že f(e(t_{i})) = fe(t_{i}) (t.j. obraz izomorfismem f termu t_{i} ohodnoceného v algebře A pomocí e je týž jako ohodnocení termu t_{i} ohodnocený v algebře B ohodnocením fe). Protože je f homomorfismus, vidíme, že

f(e(α_{i}(t_{1}, …, t_{n}))) = f(α_{i}(e(t_{1}), …, e(t_{n}))) =
= α_{i}(fe(t_{1}), …, fe(t_{n})) = fe(α_{i}(t_{1}, …, t_{n})).

Tím jsme ověřili, že platnost e(t) = e(s) implikuje platnost fe(t) = fe(s).

Zbytek důkazu už je jen přímočaré indukční ověření platnosti formule na B vzniklé použitím pravidel (φ → ψ), (φ ∧ ψ), (φ ∨ ψ), ¬φ, (∀x)φ a (∃x)φ z kratších formulí φ ψ za předpokladu, že daná dlouhá formule platí na A. □

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

4. Svazy

Připomeňme, že 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). Dvojice (M, ≤) se obvykle nazývá uspořádaná množina.

Definice. Necht’ ≤ 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.1. Připomeňme známé příklady uspořádání:

(1) Relace dělení / je uspořádání na množině všech přirozených čísel N, navíc sup_{/}(n, m) = nsn(n, m) a inf_{/}(a, b) = NSD(n, m), proto je (N, /) svaz.

(2) Přirozené uspořádání ≤ indukuje na množině všech celých (reálných, racionálních) čísel Z (R, Q) strukturu (dokonce lineárně uspořádaného) svazu, kde sup_{≤}(a, b) = max(a, b) a inf_{≤}(a, b) = min(a, b).

(3) Inkluze tvoří na množině všech podmnožin P(X) množiny X uspořádání a (P(X), ⊆) úplný svaz kde sup_{⊆}(B) = ⋃ B a inf_{⊆}(B) = ⋂ B pro každou podmnožinu B ⊆ P(X).

(4) id je na libovolné neprázdné množině M uspořádání, ovšem pro |M| > 1 se jistě nejedná o svaz.

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

Definice. Necht’ (M, ≤) je uspořádaná množina a a, b, c ∈ M. Řekneme, že prvek b pokrývá prvek a (píšeme a < · b), jestliže a ≤ b, a není b a a ≤ c ≤ b ⇒ c = a nebo c = b. Hasseovým diagramem uspořádané množiny (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.

Je-li (M, ≤) svaz, budeme pro každé dva prvky m, n ∈ M značit m ∨ n = sup_{≤}(m, n) a m ∧ n = inf_{≤}(m, n). Zavedené binární operace ∨ nazveme spojení a ∧ průsek.

Věta 4.2. (1) Je-li (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).

(2) Necht’ M(∧, ∨) je algebra s dvěma binárními operacemi, které splňují podmínky (S1) – (S4) a definujme na M relaci ≤ předpisem: a ≤ b ⇔ b = a ∨ b. Pak platí a ≤ b ⇔ a = a ∧ b, dále (M, ≤) je svaz a sup_{≤}(a, b) = a ∨ b a inf_{≤}(a, b) = a ∧ b.

Důkaz. (1) 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í ≥.

(2) 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 (S1), ž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. Necht’ například b = a ∨ b. Potom a ∧ b = a ∧ (a ∨ b) = a ∧ (b ∨ a) = a podle (S1) a (S4). Vidíme, že je definice ≤ symetricky 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. □

Dokázené tvrzení poskytuje dva ekvivalentní pohledy na svaz: bud’ jako na uspořádanou množinu se supremy a infimy nebo algebru spoňující čtveřici axiomů (S1)–(S4).

Příklad 4.3. U příkladů svazů uvedených v 4.1 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.4. Necht’ 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.5. Systém všech podalgeber i systém všech kongruencí na algebře spolu s inkluzí je díky 3.6 svazem.

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

Poznámka 4.6. 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. Necht’ je svaz distributivní. Budeme s využitím definice distributivity a 4.2 upravovat: (a ∧ b) ∨ (a ∧ c) = ((a ∧ b) ∨ a) ∧ ((a ∧ b) ∨ c) = a ∧ (a ∨ c) ∧ (b ∨ c) = a ∧ (b ∨ c), kde druhá rovnost plyne z (S4) a třetí rovnost plyne z (S1) a (S4) a □

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

(2) Necht’ M_{5} = {0, 1, u, v, w}, bud’ 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. (říká se mu obvykle diamant).

Definice. Necht’ f : A → B je zobrazení a (A, ≤) a (B, ≤) jsou svazy. Řekneme, že je f homomorfismus (izomorfismus) jde-li o homomorfismus (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}). Podsvazem svazu A(∧, ∨) budeme rozumět podalgebru algebry A(∧, ∨).

Poznámka 4.8. 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}). □

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

Důkaz. Díky 4.8 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. Necht’ 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.10. Každý prvek distributivního svazu má nejvýše jeden komplement.

Důkaz. Necht’ a ∨ b_{i} = 1 a a ∧ b_{i} = 0 pro i = 1, 2. Pak b_{i} = b_{i} ∧ 1 = 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 homomorfismus (izomorfismus) algeber v obvyklém smyslu.

Příklad 4.11. Necht’ 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.12. Necht’ 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.10 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. □

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

Důkaz. Pro každé M = {m_{1}, …, m_{n}} ⊆ S značme ⋀ M = m_{1} ∧ m_{2} ∧ ⋯ ∧ m_{n} a ⋁ M = m_{1} ∨ m_{2} ∨ ⋯ ∨ m_{n}, dále ⋀ ∅ = 1 a ⋁ ∅ = 0

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.9 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. □

Příklad 4.14. (1) Je-li S(∨, ∧, 0, 1, ′) Booleova algebra o 64 = 2^{6} prvcích, pak je podle předchozí věty izomorfní Booleově algebře P (X)(∪, ∩, ∅, , ′) pro X = {1, 2, 3, 4, 5, 6}.

(2) Neexistuje žádná patnáctiprvková Booleova algebra, protože podle Věty 4.13 musí být každá Booleova algebra izomorfní potenční Booleově algebře, tedy musí mít 2^{n} prvků, kde n je počet atomů.

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. Necht’ 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 je různé od 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. Necht’ 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 homomorfismus (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.

(4) V libovolném komutativním okruhu R(+, ·, −, 0, 1) pro prvky a, b definujeme a|b, a dělí b, standardně vztahem (∃c ∈ R) ac = b. Z definice hlavního ideálu ihned plyne, že a|b ⇔ bR ⊆ aR.

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

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í a 0 ≠ 1. Konečně ideál okruhu R(+, ·, −, 0, 1) je maximální, je-li koatomem svazu všech ideálů okruhu R.

Poznámka 5.4. 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.5. 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.4.

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. □

Následující část byla přednášena v r. 2013/2014.

Poznámka 5.6. Existují okruhy (říká se jim jednoduché), které neobsahují žádné vlastní ideály (tj. oboustranné ideály), a zároveň se nejedná o tělesa. Typickým příkladem jsou maticové okruhy M_{n}(T), kde n > 1 a T je komutativní těleso.

Definice. Je-li R(+, ·, −, 0, 1) okruh a ρ ekvivalence na R, řekneme, že ρ je okruhová kongruence, pokud je ρ slučitelná jak s operací +, tak s operací ·. V případě, že je to zřejmé z kontextu, přívlastek ”okruhová“ se vynechává.

Bud’ nyní R = R(+, ·, −, 0, 1) okruh. Budeme aplikovat Větu 1.16 na grupu R(+, −, 0). Podle této věty jsou H ↦ rmod H a ρ ↦ [0]_{ρ} vzájemně inverzní zobrazení (dokonce jde o svazové izomorfismy) mezi množinou všech podgrup grupy R(+, −, 0) a množinou všech jejích grupových kongruencí. Ukážeme, že jde (po zúžení) o vzájemně inverzní zobrazení mezi množinou všech ideálů okruhu R a množinou všech okruhových kongruencí tohoto okruhu.

At’ je nejprve H ideál okruhu R. Předpokládejme, že (a, b), (c, d) ∈ rmod H, čili a−b, c−d ∈ H. Potom ovšem i (a−b)c+b(c−d) = ac−bd ∈ H, tj. (ac, bd) ∈ rmodH a rmod H je tedy okruhová kongruence.

Opačně mějme dánu okruhovou kongruenci ρ a r ∈ R bud’ libovolný prvek. Triviálně máme (r, r) ∈ ρ. Je-li dále (a, 0) ∈ ρ, potom (ra, r0) = (ra, 0) ∈ ρ a také (ar, 0r) = (ar, 0) ∈ ρ. Jinými slovy: a ∈ [0]_{ρ} implikuje jak ra ∈ [0]_{ρ}, tak ar ∈ [0]_{ρ}, a tedy [0]_{ρ} je ideál okruhu R.

Nyní analogicky modifikujeme pro okruhy i Poznámku 1.20. Je-li I ideál (resp. ρ jemu odpovídající kongruence), potom lze na množině R/I = R/ρ definovat kromě operace + (tj. aplikace Poznámky 1.20 na grupu R(+, −, 0)) i operaci · vztahem (a + I) · (b + I) = ab + I (resp. [a]_{ρ} · [b]_{ρ} = [ab]_{ρ}). Ověření korektnosti se provede stejně jako v grupovém (tj. aditivním) případě. Snadno se nyní nahlédne, že R/I(+, ·, −, I, 1 + I) je rovněž okruh a že kanonická projekce π_{I} : R → R/I, jež je definována vztahem π_{I}(r) = r + I, je (dokonce okruhový) homomorfismus, kde Ker(π_{I}) = {r ∈ R | π_{I}(r) = I} = I. Takto definovanému okruhu říkáme faktorový okruh (nebo krátce faktorokruh) okruhu R podle ideálu I (resp. podle kongruence ρ). Následující příklady analogií z kapitoly o grupách ponecháváme čtenáři k rozmyšlení.

Příklad 5.7. (1) Analogie Poznámky 1.18 pro okruhy. Jsou-li R, S okruhy a ψ : R → S okruhový homomorfismus, potom je Ker(ψ) ideál okruhu R, Im(ψ) je podokruh okruhu S a platí: je-li I ideál v R, pak ψ(I) je ideál v Im(ψ); je-li J ideál v S, pak ψ^{−1}(J) je ideál v R.

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

Před formulací následující věty připomeňme, že ideál I okruhu R(+, ·, −, 0, 1) nazveme maximální, pokud I ≠ R a kdykoliv existuje ideál J takový, že I ⊆ J potom bud’ I = J, nebo J = R.

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

Důkaz. At’ R/I je těleso a bud’ J ⊋ I ideál v R. Potom je π_{I}(J) ideál v R/I, přičemž π_{I}(J) ≠ {I}, tj. nejde o triviální (nulový) ideál. Podle Věty 5.5 musí být již π_{I}(J) = R/I. Musí tedy existovat r ∈ J tak, že r + I = 1 + I, tj. 1 − r ∈ I, z čehož ihned plyne 1 = r + (1 − r) ∈ J, a proto J = R. Dokázali jsme, že I je maximální ideál.

Je-li naopak I maximální ideál a a ∈ R \ I (tj. a + I ≠ I v okruhu R/I), potom z maximality I (je totiž nutně aR + I = R) dostáváme existenci takového r ∈ R a i ∈ I, že ar + i = 1 (a tedy 1 − ar ∈ I). Jinak řečeno (a + I)(r + I) = ar + I = 1 + I v okruhu R/I, což znamená, že r + I je inverz v okruhu R/I k nenulovému prvku a + I. Ověřili jsme, že R/I je těleso. □

Bud’ T komutativní těleso. Ukážeme, jak poznat maximální ideály v okruhu T [x], tj. okruhu polynomů v jedné neurčité (značené x) s koeficienty v T.

Definice. O polynomu f ∈ T [x] stupně alespoň jedna řekneme, že je ireducibilní, pokud neexistují polynomy g, h ∈ T [x] takové, že f = gh a současně deg g, deg h < deg f.

Poznámka 5.9. Bud’ T komutativní těleso. Všechny ideály v T [x] jsou hlavní, tj. pro každý ideál I existuje f ∈ T [x] takové, že I = fT [x].

Důkaz. Je-li I = {0}, položme f = 0. Jinak vezměme nenulové f ∈ I nejmenšího možného stupně. Ukážeme, že I = fT [x].

Bud’ g ∈ I libovolné. Vydělme g polynomem f se zbytkem: existují tedy q, r ∈ T [x] tak, že g = qf + r a deg r < deg f. Jelikož f, g ∈ I a I je ideál, máme rovněž r = g − qf ∈ I, a tedy r = 0 vzhledem k minimalitě stupně f. Jelikož g bylo libovolné, ukázali jsme, že I ⊆ fT [x]. Druhá inkluze je triviální. □

Důsledek 5.10. Ideál I v okruhu T [x] je maximální právě tehdy, když existuje ireducibilní polynom f ∈ T [x] takový, že I = fT [x].

Důkaz. Z Poznámky 5.9 víme, že existuje f ∈ T [x] takový, že I = fT [x]. Dále stačí využít vztahu z Příkladu 5.3(4): pro ideál gT [x] máme fT [x] ⊊ gT [x] ⊊ T [x] ⇔ g|f a současně g |̸ 1 a f |̸ g; pravá strana ekvivalence neříká nic jiného, než g|f a 0 < def g < deg f, tj. f není ireducibilní. □

Kapitolu zakončíme konstrukcí konečných (komutativních) těles, přičemž budeme následující výsledek brát jako fakt (bez důkazu).

Tvrzení. Pro každé prvočíslo p a n ∈ N existuje ireducibilní polynom f ∈ Z_{p}[x] stupně n. Navíc v Z_{p}[x] platí f|(x^{p^{n}} − x).

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

Věta 5.11. (1) Pro každé prvočíslo p a n ∈ N existuje konečné komutativní

těleso mající p^{n} prvků.

(2) Je-li 𝔽 konečné těleso, pak |𝔽| = p^{n} pro p prvočíslo a n ∈ N.

(3) Libovolná dvě konečná komutativní tělesa o témže počtu prvků jsou izomorfní (jakožto okruhy).

Důkaz. (1) Z faktu výše máme existenci ireducibilního polynomu f ∈ Z_{p}[x] stupně n. Definujme 𝔽_{p^{n}} = Z_{p}[x]/fZ_{p}[x]. Potom z Důsledku 5.10 a Věty 5.8 plyne, že 𝔽_{p^{n}} je komutativní těleso. Označíme-li I = fZ_{p}[x], v tomto tělese (pro g, h ∈ Z_{p}[x]) platí g + I = h + I právě tehdy, když f dělí g − h; mj. tedy g + I = (g mod f) + I. Jako zbytky po dělení f figurují právě všechny polynomy nad Z_{p} stupně < n, těch je p^{n}, což je následně i počet prvků 𝔽_{p^{n}}.

(2) Bud’ 𝔽 konečné těleso. Uvažujme cyklickou podgrupu ⟨1⟩ grupy 𝔽(+, −, 0). Ta musí být konečná, a tedy Z_{p}(+) ≅ ⟨1⟩(+) pro nějaké p ∈ N. Uvažujme izomorfismus, který posílá prvek k ∈ Z_{p} na prvek \underbrace{1 + 1 + … + 1}_{k×} tělesa 𝔽, a jak je

v podobných případech zvykem, pro další úvahy ztotožníme prvky tělesa 𝔽 tvaru \underbrace{1 + 1 + … + 1}_{k×}, kde 0 ≤ k < p, a prvky množiny Z_{p}. Z grupy Z_{p} tímto ztotožněním

uděláme podgrupu grupy 𝔽(+, −, 0).

Jelikož z distributivity máme (\underbrace{1 + 1 + … + 1}_{k×})(\underbrace{1 + 1 + … + 1}_{m×}) = \underbrace{1 + 1 + … + 1}_{km×} =

\underbrace{1 + 1 + … + 1}_{(km mod p)×}, tvoří Z_{p} dokonce podokruh tělesa 𝔽.

Dále, p musí být prvočíslo. Jinak by existovaly 0 ≠ k, m ∈ Z_{p} tak, že km = 0, což v žádném tělese (tedy ani v 𝔽) není možné.

Nyní je již snadné si uvědomit, že 𝔽 tvoří vektorový prostor nad svým podtělesem Z_{p}, a tedy dim_{Z_{p}}𝔽 = n ∈ N. V důsledku toho jest |𝔽| = p^{n}.

(3) Ukážeme, že je-li 𝔽 konečné komutativní těleso o p^{n} prvcích, potom 𝔽 ≅ 𝔽_{p^{n}} (z části (1) důkazu). Tak jako v bodu (2) budeme BÚNO předpokládat, že Z_{p} je přímo podtělesem tělesa 𝔽 (nikoliv pouze izomorfní podtělesu generovanému prvkem 1).

Nejprve nahlédneme, že každý prvek tělesa 𝔽 je kořenem polynomu x^{p^{n}} − x ∈ Z_{p}[x]. To pro 0 zřejmě platí a pro nenulové prvky to plyne aplikací Poznámky 2.8 na grupu 𝔽^{∗}(.,^{−1}, 1), která má p^{n} − 1 prvků.

Z faktu výše plyne, že ireducibilní polynom f ∈ Z_{p}[x] použitý ke konstrukci tělesa 𝔽_{p^{n}}, dělí v Z_{p}[x] polynom x^{p^{n}} − x. To ovšem znamená, že ho dělí i v jeho nadokruhu 𝔽[x]. Máme tedy nějaký polynom g takový, že fg = x^{p^{n}} −x. Dosadíme-li nyní libovolný prvek a ∈ 𝔽, máme f(a)g(a) = 0, což znamená, že a je kořen jednoho ze dvou těchto polynomů. Jelikož polynom g má menší stupeň než p^{n} (a tedy méně než p^{n} kořenů), musí existovat nějaké a ∈ 𝔽, které je kořenem polynomu f.

Pro toto a uvažujme (dosazovací) homomorfismus d_{a} : Z_{p}[x] → 𝔽 definovaný vztahem d_{a}(h) = h(a). Výše jsme dokázali, že fZ_{p}[x] ⊆ Ker(d_{a}). Můžeme proto užít Větu o homomorfismu pro okruhy, která nám dá (jediný) okruhový homomorfismus ψ : Z_{p}[x]/fZ_{p}[x] → 𝔽, pro nějž d_{a} = ψπ_{fZ_{p}[x]}. Jelikož d_{a}(1) = 1 ≠ 0, je ψ nenulový homomorfismus. Víme, že Ker(ψ) musí být ideál tělesa 𝔽_{p^{n}}, a tedy nutně Ker(ψ) je triviální (jednoprvkový) ideál (užíváme Větu 5.5). To ovšem znamená, že ψ je prosté, a tedy musí být i na, jelikož jde o zobrazení mezi dvěma stejně velkými konečnými množinami. Ergo ψ je hledaný izomorfismus těles 𝔽_{p^{n}} a 𝔽. □

Poznámka 5.12. Wedderburnova věta říká, že všechna konečná tělesa jsou komutativní. Důkaz ale není nikterak triviální. V důkazu části (3) jsme využili komutativitu tělesa 𝔽, abychom mohli argumentovat, že polynom g nemá v 𝔽 více kořenů, než

30 ALGEBRA I PRO INFORMATIKY

je jeho stupeň; to ovšem nad nekomutativními tělesy neplatí! Stačí uvážit polynom x^{2} + 1 nad tělesem kvaternionů. Ten má za kořeny i, j, k, −i, −j, −k.