ALGEBRA I. Mgr. Jan Žemlička, Ph.D. cvičení

ALGEBRA I. Mgr. Jan Žemlička, Ph.D. cvičení

6.10.

Euklidův algoritmus a ekvivalence Nechť a0 > a1 jsou dvě přirozená čísla. Připomeňme Euklidův algoritmus hledání největšího společného dělitele (NSD) čísel a0 a a1: Známe-li ai a ai + 1 spočteme ai + 2 = (ai) mod ai + 1, algoritmus skončí, pokud ai + 2 = 0, potom ai + 1 = NSD(a0, a1). 1. Najděte pomocí Euklidova algoritmu největší společný dělitel čísel 72 a 93. Najděte dále taková celá čísla x a y, aby NSD(72, 93) = x.72 + y.93.

První část úkolu je snadná, sepišme si i jakým způsobem jednotlivé zbytky po celočíselném dělení získáme: o o o o o o

a0 = 93, a1 = 72 a2 = 93-72 = 21, a3 = 72-3.21 = 9, a4 = 21-3.9 = 3 = NSD(93, 72), a5 = 0.

Druhou část úlohy vyřešíme rovněž pomocí Euklidova algoritmu, stačí si uvědomit, že každé z čísel ai + 2 dostaneme jako celočíselnou lineární kombinaci dvou předchozích hodnot ai a ai + 1. Jednoduchou indukční úvahou zjistíme, že každé číslo ai + 2 je celočíselnou lineární kombinaci hodnot a1 a a2. Konkrétně: o o o

a2 = 93-72 = 21, a3 = 9 = 72-3.21 = 72-3.(93-72) = 4.72-3.93, a4 = 3 = NSD(93, 72) = 21-2.9 = (93-72)-2.(4.72-3.93) = 7.93-9.72,

2. Najděte takové číslo x∈{0,1,2,...,99,100}, pro nějž (x.63) mod 101 = 1

Všimneme-li si, že 101 je prvočíslo, pak zřejmě NSD(63, 101) = 1. Umíme proto (pomocí Euklidova algoritmu) najít dvě celá čísla a, b tak, že 1 = 63.a + 101.b. Konečně jednoduchou úvahou dostáváme, že x = (a) mod 101. Konkrétně: o o o o o

38 = 101-63, 25 = 63-38 = 2.63-101, 13 = 38-25 = 2.101-3.63, 12 = 25-13 = 5.63-3.101, 1 = 13-12 = 5.101-8.63,

Tedy x = (-8) mod 101 = 93.

–2–

3. Zvolme celé kladné číslo n. Zaveďme na množině všech celých čísel Z relaci ~ předpisem: k~l právě když n dělí (k-l) (tj. (k-l) mod n = 0). Dokažte, že ~ je ekvivalence na Z. Kolik prvků má faktorová množina Z/~?

Ověřujme, že je ~ ekvivalence: 1) zřejmě k~k pro každé k, tedy ~ je reflexivní. 2) Neboť n dělí (k-l) právě tehdy, když n dělí (l-k), je relace ~ symetrická. 3) Pokud k-l = a.n a l-m = b.n. potom k-m = k-l + l-m = (a + b).n. Tedy pokud n dělí (k-l) i (l-m), potom n dělí k-m. Tím máme ověřeno, že je relace ~ tranzitivní. Snadno nahlédneme, že Z/~ = {[0]~, [1]~, …, [n-1]~} a že se žádný prvek v tomto zápisu neopakuje (tedy [i]~ je různé od [j]~ pro každou dvojici různých hodnot nezáporných čísel i, j < n). To znamená, že Z/~ má právě n prvků. 4. Nechť R[x] je množina reálných polynomů o jedné neurčité. Najděte největší společný dělitel polynomů. Najděte největšího společného dělitele polynomů x4 + x3 + 2x2 + x + 1 a x3 + x2 + x + 1.

I tentokrát můžeme k hledání největšího společného dělitele (tj. polynomu, který oba uvedené polynomy dělí a je největšího možného stupně) použít Euklidův algoritmus. Místo celočíselného dělení se zbytkem budeme ovšem používat dělení polynomů se zbytkem (připomeňme, že zbytek po takovém dělení musí být buď nulový nebo musí mít stupeň menší než dělitel). Tedy počítejme: o o o o

x4 + x3 + 2x2 + x + 1, x3 + x2 + x + 1, x2 + 1 = x4 + x3 + 2x2 + x + 1-x.(x3 + x2 + x + 1), 0 = x3 + x2 + x + 1-(x + 1)(x2 + 1).

Největším společným dělitelem polynomů x4 + x3 + 2x2 + x + 1 a x3 + x2 + x + 1 je tedy polynom x2 + 1 (ale také jakýkoli jeho nenulový reálný násobek). 13.10. Nechť T je libovolné těleso (s operacemi + a .). Označme T[x] množinu všech (formálních) polynomů tj. T[x] = {a0x0 + a1x1 + ... + akxk| k∈N, ai∈T}. Na této množině definujme pomocí sčítání a násobení v tělese T operace sčítání ( + ) a násobení (.) stejným způsobem jako je máme definovány na reálných polynomech: •

•

a0x0 + a1x1 + … + akxk + b0x0 + b1x1 + … + bmxk = = (a0 + b0)x0 + (a1 + b1)x1 + … + (amax(k,m) + bmax(k,m))xmax(k,m), kde nedefinované hodnoty ai resp. bi dodefinujeme nulami tělesa T. (a0x0 + a1x1 + … + akxk) . (b0x0 + b1x1 + … + bmxk) = = (a0.b0)x0 + (a1.b0 + a0.b1)x1 + … + (ai.b0 + ai-1.b1 + ai-2.b2 + ... + a0.bi)xi + … + + (an + m.b0 + an + m-1.b1 + ... + a0.bn + m)xi, kde opět dodefinujeme nedefinované hodnoty ai resp. bi nulami.

–3–

5. Ověřte, že sčítání a násobení na T[x] pro libovolné těleso T jsou komutativní a asociativní, dále ,že sčítání je distributivní vůči násobení a že ke každému polynomu p existuje polynom -p∈T[x], pro nějž p + (-p) = 0 (nulovému polynomu).

Věc se dokazuje stejným postupem jako u "obyčejných" polynomů nad reálnými čísly. Uvědomme si, že nad algebrou T[x]( + , . ) můžeme obdobně jako nad reálnými polynomy R[x]( + , . ) dělit se zbytkem. Potřebujeme k tomu znát pojem stupně polynomu, což je obdobně jako v R[x] největší k takové, že koeficient ak u xk je nenulový. Přesně řečeno, možnost dělit se zbytkem znamená, že pro každou dvojici polynomů p a q existují polynomy r a z tak, že p = r.q + z a z je buď nulový polynom nebo je stupně menšího než stupeň polynomu q (zkuste dokázat, že takové polynomy pro každé p a q existují!).

6. Vydělte se zbytkem polynom x4 + x + 1 polynomem x2 + x nad algebrou Z2[x]( + , . )(tj uvažujeme polynomy nad tělesem Z2).

Dělení provádíme stejnou procedurou jako dělení se zbytkem reálných polynomů, jen aritmetiku reálných čísel nahradíme aritmetikou na Z2: x4 -( x4 + x3)

+

x3 + 3 -( x + x2)

x + 1 : x2 + x = x2 + x + 1

x + 1

x2 + x + 1 -( x2 + x) 1 Zjistili jsme, že x4 + x + 1 = (x2 + x).(x2 + x + 1) + 1, tedy zbytek po dělení polynomu x4 + x + 1 polynomem x2 + x + 1 je 1.

7. Najděte pomocí Euklidova algoritmu největší společný dělitel polynomů x4 + x + 1 a x2 + x nad Z2[x]. Dále najděte polynomy r a s tak, aby r.(x4 + x + 1) + s.(x2 + x) = NSD(x4 + x + 1, x2 + x).

Hned v prvním kroku Euklidova algoritmu dostáváme polynom stupně nula (nad Z2 existuje právě jediný) 1, který už samozřejmě dělí všechny polynomy. Tedy NSD(x4 + x + 1, x2 + x) = 1. Stejně jako u Euklidova algoritmu na celých číslech dostáváme zpětným chodem: 1.(x4 + x + 1) + (x2 + x + 1).(x2 + x) = 1.

–4–

8. Buď p = x2 + x + 1 polynom nad Z2[x]. Zaveďme na množině Z2[x] relaci ~ předpisem: q~r právě když p dělí (q-r) (tj. existuje polynom s∈Z2[x] tak, že (q-r) = s.p). Dokažte, že ~ je ekvivalence na Z2[x]. Kolik prvků má faktorová množina Z2[x]/~?

Postupujeme podobně jako ve 3. příkladě. Téměř identickou argumentací dokážeme, že je ~ ekvivalence: 1) zřejmě q~q pro každý polynom q, tedy ~ je reflexivní. 2) Pokud u.p = q-r, potom (-u).p = r-q, tedy relace ~ je symetrická. 3) Pokud r-s = u.p a s-q = v.p, potom r-q = r-s + s-q = (u + v).p, proto je relace ~ tranzitivní. Dále si uvědomme, že všechny prvky faktorové množiny tvoří třídy Z2[x]/~ = {[0]~, [1]~, [x]~, [x + 1]~}, protože zbytek z po dělení libovolného polynomu q polynomem x2 + x + 1 je stupně menšího než dva a jistě platí, že z~q. Konečně je rozdíl dvou různých polynomů z množiny {[0]~, [1]~, [x]~, [x + 1]~} zjevně polynomem stupně 0 nebo 1, proto ho nemůže dělit polynom stupně 2 (víte pro reálné polynomy, zkuste dokázat pro polynomy nad obecným tělesem!). Tím jsme ověřili, že Z2[x]/~ má právě čtyři prvky. 20.10. 9. Dokažte, že ekvivalence z příkladu 3 tvoří kongruenci na algebře Z( + , . ).

Potřebujeme pro celá čísla a1, a2, b1, b2 splňující podmínku a1~b1 a a2~b2 ukázat, že (a1 + a2)~(b1 + b2) a (a1.a2)~(b1.b2). Předpokládáme tedy, že a1-b1 = k1n a a2-b2 = k2n a upravujme: (a1 + a2)-(b1 + b2) = a1-b1 + a2-b2 = (k1 + k1).n, (a1.a2)-(b1.b2) = a1.a2-a1.b2 + a1.b2-b1.b2 = a1.k2.n + b2.k1.n = (a1.k2 + b2.k1).n. Tím jsme ověřili, že n dělí (a1 + a2)-(b1 + b2) i (a1.a2)-(b1.b2), tedy ~ je slučitelná s oběma operacemi na algebře Z( + , . ). Víme-li, že je relace ~ z příkladu 3 kongruence na Z( + , . ), můžeme na faktoru Z/~ zavést faktorové operace, dostáváme tak algebru Z/~( + , . ). Připomeňme konstrukci algebry Zn( + , . ) známou z přednášky lineární algebry. Na množině Zn = {0,1,...,n-2, n-1} je sčítání i násobení zavedeno modulo n, tedy a + b resp. a.b je zbytek po celočíselném dělení součtu a + b resp. a.b∈Z.

–5–

10.

Mějme kongruenci ~ definovanou v příkladě 3 a definujme zobrazení f množiny Zn do Z/~ předpisem f(k) = [k]n. Dokažte, že f je vzájemně jednoznačný (tj. prostý a na) homomorfismus.

V příkladu 3 už jsme dokázali, že zobrazení je vzájemně jednoznačné, když jsme ověřili, že množina Z/~ je tvořena právě prvky [0]~, [1]~, ..., [n-1]~. Přímo z definice se ukáže, že jsou operace + a . slučitelné se zobrazením f: f(k + l) = [k + l]~ = [k]~ + [l]~ = f(k) + f(l) f(k.l) = [k.l]~ = [k]~ . [l]~ = f(k).f(l)

11.

Dokažte, že Z/~ tvoří těleso (kde ~ je kongruence z příkladu 3) právě tehdy, když je n prvočíslo.

Většina bodů axiomatiky tělesa pro Z/~( + , . ) plyne okamžitě z toho, že jsou příslušné podmínky splněny operacemi na Z (asociativity, komutativity, distributivita, nulový a jednotkový prvek, existence opačného prvku). Zbývá ověřit jen podmínku existence inverzního prvku vzhledem k násobení (kterou algebra celých čísel nesplňuje). Předpokládejme, že n je prvočíslo. Nechť [k]~ je nenulový prvek. Neboť n je prvočíslo, je NSD(n, k) = 1. Tedy existují prvky x a y tak, že x.k + y.n = 1. To ovšem znamená, že [x]~ . [k]~ = [1]~. Pokud n není prvočíslo, existují dvě čísla 1 < a, b < n tak, že a.b = n. Potom ovšem [a]~ . [b]~ = [n]~ = [0]~, což pro žádné těleso není možné. Poznamenejme, že jsme díky existenci vzájemně jednoznačného homomorfismu (izomorfismu) mohli řešit problém v (algebraicky totožné) algebře Zn( + , . ).

12.

Dokažte, že ekvivalence z příkladu 8 tvoří kongruenci na algebře Z2[x]( + , . ).

Postup je totožný s postupem důkazu v příkladu 9.

13.

Buď ~ kongruence z příkladu 8. Dokažte, že Z2[x]/~ tvoří těleso.

Postupujme jakov úloze 11. Asociativity, komutativity, distributivita, existence nulového a jednotkového prvku, existence opačného prvku jsou splněny už operacemi na algebře Z2[x]( + , . ), proto platí i ve faktorové algebře Z2[x]/~( + , . ). Zbývá ověřit existenci inverzního prvku vzhledem k násobení pro každý nenulový prvek Z2[x]/~. Předně si uvědomme, že polynom x2 + x + 1 je nad Z2[x] nerozložitelný, tj. nelze ho napsat jako součin dvou polynomů stupně aspoň jedna. Kdyby tomu tak nebylo, pak

–6–

by p = x2 + x + 1 = (x + a)(x + b). To by ovšem znamenalo, že p(-a) = p(-b) = 0, tedy polynom by měl nad Z2 kořen. To ovšem není pravda, neboť p(0) = 0.0 + 0 + 1 = 1, p(1) = 1.1 + 1 + 1 = 1. Z toho, že je polynom x2 + x + 1 nerozložitelný, plyne, že je zcela jistě nesoudělný z každým nenulovým polynomem nižšího stupně. Proto nám Euklidův algoritmus dává pro každý polynom q stupně 0 nebo 1 (viz příklad 7 a 2) polynomy r a s: 1 = NSD(q, x2 + x + 1) = r.q + s.(x2 + x + 1). Tím jsme dokázali, že [q]~ . [r]~ = [1]~, tedy jsme k libovolnému nenulovému prvku Z2[x] nalezli inverzní prvek, čímž jsme dokázali, že Z2[x]/~( + , . ) je těleso.

14.

Buď ~ kongruence z příkladu 8. Najděte v tělese Z2[x]/~( + , . ) inverzní prvek k prvkům [x]~ a [x + 1]~.

Snadno (i bez použití Euklidova algoritmu) nahlédneme, že [x]~ . [x + 1]~ = [x2 + x]~ = [1]~. Tedy [x]~-1 = [x + 1]~ a [x + 1]~-1 = [x]~. 27.10. Zopakujme, že o polynomu p řekneme, že je nerozložitelný, pokud p = r.s implikuje, že r nebo s je polynom stupně nula. 15.

Nechť p je nerozložitelný polynom stupně k a nechť n je prvočíslo. Definujme relaci ~ na Zn[x] tak, že q~r právě tehdy, když existuje polynom s∈Zn[x], pro nějž (q-r) = s.p. Dokažte, že Zn[x]/~( + , . ) je tělesem o nk prvcích.

Nedokazujeme nic nového oproti příkladům 11 a 13. Zjevně stačí ověřit existenci inverzního prvku pro každý nenulový prvek. Obdobně jako v příkladech 3 a 8 nahlédneme, že Zn[x]/~ tvoří právě ekvivalenční třídy příslušné všem polynomům menšího stupně než má polynom p (tj. Zn[x]/~ = {[q]~| stupeň(q) < stupeň(p)}). Takových polynomů je zjevně nk. Tím máme ověřeno, že Zn[x]/~ obsahuje právě nk prvků. Vezmeme-li libovolný polynom q∈Zn[x] stupně menšího než k, potom nám Euklidův algoritmus zaručuje existenci polynomů r a s tak, že r.q + s.p = NSD(p, q) = 1. Proto [q]~-1 . [r]~ = [1]~, a tudíž [q]~-1 = [r]~.

–7–

16.

Definujme kongruenci ~ na algebře Z3[x] jako v předchozí úloze pro polynom p = x3 + 2x + 1. Dokažte, že je p nerozložitelný a v tělese Z3[x]/~ najděte inverzní prvek k prvku [x2]~.

Byl-li by polynom p = x3 + 2x + 1 rozložitelný, musel by být součinem polynomu stupně 1 a polynomu stupně 2, tj. p = (x-a).q. To by znamenalo, že p(a) = 0, tedy p by musel mít v Z3 nějaký kořen. Dosadíme-li postupně všechny prvky tělesa Z3 zjistíme, že p žádný kořen nemá, a proto je nerozložitelný: p(0) = 0.0.0 + 2.0 + 1 = 1, p(1) = 1.1.1 + 2.1 + 1 = 1, p(2) = 2.2.2 + 2.2 + 1 = 1. Nyní hledáme pomocí Euklidova algoritmu polynomy r a s tak, aby r.x2 + s.p = NSD(x2, p), přičemž už víme, že NSD(x2, p) = 1: o o o o o

x3 + 2x + 1, x2 , 2x + 1 = x3 + 2x + 1-x.x2 = x3 + 2x + 1 + 2x.x2, 1 = x2-(2x + 2)(2x + 1) = x2 + (x + 1)(x3 + 2x + 1 + 2x.x2) = = (x + 1)(x3 + 2x + 1) + (2x2 + 2x + 1).x2, 0.

Zjistili jsme, že [x2]~-1 = [2x2 + 2x + 1]~.

17.

Najděte těleso o 125 prvcích.

Protože 125 = 53, stačí nám podle příkladu 15 najít nerozložitelný polynom stupně 3 nad tělesem Z5. Poté obvyklým způsobem sestrojíme kongruenci ~ na algebře Z5[x]( + , . ), aby hledaným tělesem byl faktor Z5[x]/~. Podobně jako v příkladu 16 uvážíme, že hledáme polynom stupně 3, který nemá žádný kořen. Vezměme například polynom p = x3 + x + 1. Potom p(0) = 1, p(1) = 3, p(2) = 1, p(3) = 1, p(4) = 1. Našli jsme tedy nerozložitelný polynom stupně 3.

18.

Nechť T( + , . ) je konečné těleso. Definujme pro každé přirozené číslo k prvek k.1 tělesa T jako součet k jednotek tělesa T. Položme P = {k.1| k∈N}∪ ∪{0}. Dokažte, že je P podalgebrou T o prvočíselném počtu prvků, na níž restringované operace + a . dávají strukturu tělesa a tudíž T můžeme chápat jako vektorový prostor nad tělesem P.

–8–

19.

Dokažte, že každé konečné těleso má pk prvků, kde p je prvočíslo a k nějaké přirozené číslo.

Je-li T konečné těleso a P jeho podtěleso definované v předchozím příkladu. Neboť T je vektorovým prostorem konečné dimenze nad P musí mít právě |P|dim T prvků. v předchozím příkladu jsem dokázali, že |P| je prvočíslo. 3.11.

Algebry, podalgebry, kongruence 1. Najděte všechny podalgebry algebry A(*) s binární operací * na množině A = {a, b, c} danou tabulkou:

* a b c

a c b a

b b a b

c a b c

Předně si uvědomme, že prázdná množina { } je podalgebrou každé algebry bez nulárních operací a celá nosná množina A je podalgebrou každé algebry (s nosnou množinou A). Dále budeme postupně probírat podalgebry podle počtu prvků. Je-li {x} jednoprvková algebra na A pak zřejmě musí platit x*x = x (neboť množina {x} musí být uzavřená na operaci *). Snadno z tabulky nahlédneme, že takovou vlastnost (mluvíme o idempotenci) splňuje pouze prvek c. Tedy máme právě jednu jednoprvkovou podalgebru {c} algebry A(*). Dále uvažme, které z dvou prvkových podmnožin {a, b}, {a, c} a {b, c} jsou podalgebry. Zjevně podalgebra obsahující prvek a už musí obsahovat i prvek a*a = c, tedy {a, b} není podalgebrou. Podobně podalgebra obsahující prvkek musí obsahovat i prvek b*b = a, tedy {b, c} také není podalgebrou. Konečně z tabulky okamžitě vidíme, že je množina {a, c} uzavřená na operaci *, tedy {a, c} je podalgebra algebry A(*). Dostáváme uzávěrový systém všech podalgeber: { {}, {c}, {a, c}, {a, b, c} }.

2. Najděte všechny kongruence na algebře A(*) z předchozího příkladu.

Snadno nahlédneme, že Id a A×A tvoří kongruenci na každé algebře s nosnou množinou A. Budeme nyní probírat všechny zbývající ekvivalence na A, přičemž využijeme jednoznačné korespondence ekvivalence na A a rozkladu A. Snadno nahlédneme, že Id a A×A tvoří kongruenci na každé algebře s nosnou množinou A. Budeme nyní probírat všechny zbývající ekvivalence na A, přičemž využijeme jednoznačné korespondence ekvivalence na A a rozkladu A. Existují tedy právě tři ekvivalence odpovídající rozkladu na ekvivalenční třídy { {a}, {b, c} }, { {b}, {a, c} } a { {c}, {a, b} }.

–9–

Nechť ~ je kongruence na A taková, že a~b. Uvědomíme-li si, že a~a a že * má být slučitelná s ~, pak a*a~a*b, tedy c~b. Všimněme si, že tuto informaci můžeme vyčíst z prvního řádku tabulky operace * (tj. všechny sloupce odpovídající kongruentním prvkům musí obsahovat vzájemně kongruentní hodnoty). Podobně i a*a~b*a (tj. stejnou úvahu můžeme provést i pro sloupce tabulky). V každém případě to znamená, že všechny prvky kongruence obsahující dvojici {a, b} leží v jedné ekvivalenční třídě, tedy dostáváme už zmíněnou kongruenci A×A. Nyní uvažujme kongruenci ~ na A takovou, že b~c. Z tabululky okamžitě dostáváme, že b = a*b~a*c = a, tedy a~b~c, což znamená, že opět ~ = A×A. Konečně, pokud uvažujeme kongruenci splňující podmínku a~c, pak předchzím postupem nedostáváme žádnou novou nutnou podmínku. Zbývá nám nahlédnout, že rozklad { {b}, {a, c} } skutečně určuje kongruenci. k tomu ovšem stačí zjistit, zda na množině A/~ = { {b}, {a, c} } můžeme zavést faktorovou operaci * předpisem [x]~*[y]~ = [x*y]~. Jinak řečeno potřebujeme zjistit, zda všechny součiny prvků z každých dvou pevně zvolených rozkladových tříd leží vždy právě v jedné rozkladové třídě. To snadno nahlédneme z tabulky operace *, kde poněkud přeházíme řádky a sloupce: * b a c

b a b b

a b c a

c b a c

Vidíme, že v každém bloku tabulky máme jen prvky jedné rozkladové třídy, tedy rozkladu { {b}, {a, c} } opravdu odpovídá kongruence. Snadno můžeme nahlédnout, že ~ = {(a, a), (b, b), (c, c), (a, c), (c, a) }. 10.11. 3. Najděte všechny podalgebry algebry B(.) s binární operací . na množině B = {1, 2, 3, 4} danou tabulkou:

. 1 2 3 4

1 2 1 4 3

2 1 4 1 4

3 1 1 4 4

4 3 1 1 2

Postupujeme stejně jako v 1. příkladu. Prázdná množina {} i celá nosná množina B je podalgebrou B. Algebra B(.) zjevně neobsahuje žádný idempotent (tj. prvek s vlastností x.x = y), tedy žádná jednoprvková podalgebra neexistuje.

– 10 –

Snadno nahlédneme, že každá množina uzavřená na operaci obsahující dva prvky z {1, 2, 3, 4} musí obsahovat další prvek, tedy B(.) neobsahuje ani žádnou dvouprvkovou podalgebru. Podobně každá trojice prvků z B už generuje celé B, tedy B neobsahuje žádnou tříprvkovou podalgebru. Zjistili jsme, že B(.) obsahuje jen dvě podalgebry {} a B.

4. Najděte všechny kongruence na algebře B(.) z předchozího příkladu.

Tentokrát postupujeme analogicky jako v příkladu 2. Id a B×B samozřejmě tvoří kongruenci na B(.). Uvažujeme-li nejmenší kongruenci ~ obsahující dvojici (1, 2) pak 1 = 1.2~2.2 = 4 a 3 = 1.4~2.4 = 1, proto 1~2~3~4 a tedy ~ = B×B. Nejmenší kongruence obsahující dvojici (1, 4) zřejmě nutně obsahuje i dvojici (1.1, 4.1) = (2, 3). Na faktoru B podle ekvivalence dané rozkladem {1, 4} a {2, 3} už ovšem můžeme dobře definovat faktoroperaci, jak je vidět například z tabulky operace s permutovanými řádky a sloupci (každý z "bloků" obsahuje jen prvky jedné rozkladové třídy): . 1 4 2 3

1 2 3 1 4

4 3 2 1 1

2 1 4 4 1

3 1 4 1 4

Obdobně nahlédneme, že nejmenší kongruence obsahující dvojici (2, 3) je táž jako předchozí. Konečně vezmeme-li kongruenci s trojicí kongruentních prvků, pak díky předchzím úvahám dostáváme maximální kongruenci B×B.

5. Najděte všechny podalgebry a všechny kongruence algebry B( . , 1 ) s binární operací . danou v příkladu 3 a s nulární operací 1 (tj. vybíráme prvek 1).

Každá podalgebra algebry B( . , 1 ) musí nutně být podalgebrou algebry B(.), proto nám stačí zjistit, zda nalezené podalgebry B(.) jsou i podalgebrami B( . , 1 ). Vzhledem k tomu, že každá podalgebra algebry s nějakými nulárními operacemi musí (podle definice) obsahovat všechny nulární operace (tj. prvky, které nulární operace určuje), není prázdná množina podalgebrou B( . , 1 ). Na B( . , 1 ) tedy nalázáme pouze triviální podalgebru B.

– 11 –

Neboť každá kongruence na B( . , 1 ) musí opět být kongruencí algebry B(.), stačí znovu prozkoumat kongruence algebry B(.). Slučitelnost s nulární operací 1 ovšem neznamená nic jiného, než podmínu, že (1, 1) leží v kongruenci, která je ovšem splněna pro každou ekvivalenci. Proto všechny kongruence na B(.) tvoří všechny kongruence na B( . , 1 ).

6. Dokažte, že každá konečná pologrupa P(*) obsahuje prvek e, pro nějž e*e = e (tzv. idempotent).

Binární operace * na pologrupě je asociativní. To nás opravňuje k následující definici mocniny prvku: a1 = a, an + 1 = a*an. Z asociativity operace * okamžitě plyne, že ak * an = ak + n. Zvolme nějaký prvek a∈P a položme A = {an; n>0}. Neboť P je konečná množina musí taková být i její podmnožina (mimochodem dokonce podalgebra algebry P) A. To znamená, že existují taková dvě kladná čísla i < j, pro něž ai = aj. Proveďme nyní několik jednoduchých pozorování aritmetiky mocniny na P: ai = aj = ai + j-i = ai * aj-i aj * aj-i = aj + j-r, indukční rozšíření nám dává: ai = aj = ai + r(j-i), a proto asi = a(s-1)i * ai = asi + r(j-i) Nyní stačí položit s = (j-i) a r = i a dostáváme, že ai(j-i) = a2i(j-i). Položíme-li e = ai(j-i) snadno spočítáme, že e2 = (ai(j-i))2 = a2i(j-i) = ai(j-i) = e.

– 12 –

24.11. 7. Najděte všechny podalgebry (tj. podsvazy) svazu {0,1,a,b,c,d}(A,V) s Hasseovým diagramem:

Budene obvyklým způsobem vyšetřovat podmnožiny svazu. Uvědomme si, že každý nenulový podsvaz je zároveň svazem, tedy můžeme namalovat jeho Hasseův diagram. Předně zřejmě je prázdná množina {} podsvazem. Dále všech prvky svazu jsou vzhledem k oběma binárním operacím idempotentní, proto jsou všechny jednoprvkové podmnožiny daného svazu podsvazy. Podsvazem je dále každá dvojice prvků spojených cestou vedoucí ze shora dolů. Jde o dvojice {1, a}, {1, d}, {1, 0}, {1, b}, {1, c}, {a, d}, {a, 0}, {b, d}, {b, 0}, {c, 0} a {d, 0}. Žádný další dvouprvkový podsvaz neexistuje. Hasseův diagram příslušného svazu má tvar:

Podobně, jedinými podsvazy o třech prvcích jsou právě tři prvky ležící na cestě, která vede ze zhora dolů. dále každá dvojice prvků spojených cestou vedoucí shora dolů. Konkrétně dostáváme {1, a, d}, {1, a, 0}, {1, b, d}, {1, b, 0}, {1, d, 0}, {a, d, 0}, {b, d, 0}, {1, c, 0}. Hasseův diagram příslušného svazu má tvar:

Podsvazy o čtřech prvcích mohou být dvojího typu, který můžeme vyjádřit Hasseovými diagramy:

Tedy čtyři vrcholy ležící na cestě vedoucí shora dolů tvoří podsvazy {1, a, d, 0} a {1, b, d, 0} a čtverec je Hasseovým diagramem podsvazů {1, a, b, d}, {1, a, 0, c}, {1, b, 0, c} a {1, d, 0, c}.

– 13 –

Podsvazy o pěti prvcích mohou být v daném svazu opět dvojího typu, který popisují Hasseovy diagramy (například cestu shora dolů obsahující pět vrcholů už v Hasseově diagramu našeho svazu nenajdeme):

Snadno zjistíme, že pětiprvkové podsvazy tvoří množiny {1, a, b, d, 0}, {1, a, d, 0, c} a {1, b, d, 0, c}. Konečně celá nosná množina svazu {0, 1, a, b, c, d} je samozřejmě podsvazem.

8. Spočítejte ve svazu z předchozího příkladu hodnoty a∧ ∧b, a∨ ∨b, a∧ ∧c, a∨ ∨c, b∧ ∧d, b∨ ∨d.

Podle definice je spojení nejmenší horní odhad, tedy a∨b = 1, a∨c = 1, b∨d = b. Průsek je naopak největším dolním odhadem, proto a∧b = d, a∧c = 0, b∧d = d. Připomeňme, že pro permutace na množině {1, 2, …, n} (tj. bijekce na této množině) používáme tzv. cyklický zápis: p = (…) … (…) (a … b p(b) … p-1(a)) …, kde se každý prvek z množiny {1, 2, …, n} vyskytuje v zápisu právě jednou. Jednocykly, tj. cykly tvaru (c), které dostaneme pro c = p(c), se v cyklickém zápisu zpravidla vynechávají. Konečně poznamenejme, že cyklus (a tím pádem ani permutace) nemá jednoznačný zápis, například (123) = (231) = (312).

9. Napište v cyklickém zápisu permutace p a q z grupy S7( . , -1 , Id ) a spočítejte součiny (tj. složení daných bijekcí) p.q, q.p, p-1 a q-1, pokud p(1) = 3, p(2) = 4, p(3) = 1, p(4) = 6, p(5) = 5, p(6) = 7, p(7) = 2, q(1) = 4, q(2) = 6, q(3) = 3, q(4) = 5, q(5) = 1, q(6) = 7, q(7) = 2.

Snadno zjistíme, že p = (13)(2467)(5) = (13)(2467) a q = (145)(267)(3) = (145)(267). Dále p.q = (13)(2467) . (145)(267) = (1627453) a q.p = (145)(267) . (13)(2467) = (1347625). Konečně p-1 = (31)(7642) = (13)(2764) a q-1 = (541)(762) = (154)(276).

– 14 –

10.

Určete Hasseův diagram svazu všech podgrup grupy permutací na třech prvcích S3( . , -1 , Id ).

Hledáme standardním postupem podalgebry algebry S3( . , -1 , Id ). Zřejmě množina {Id} tvoří nejmenší podgrupu grupy S3 a množina S3 je největší podgrupou grupy S3. Poznamenejme, že každá podgrupa musí být uzavřena na nulární operaci, tj. musí obsahovat neutrální prvek Id. Dále snadno nahlédneme, že množiny {Id, (12)}, {Id, (13)} a {Id, (23)} jsou podgrupy, protože (ab) * (ab) = Id pro každou dvojici různých čísel a, b z množiny {1, 2, 3}, z čehož plyne, že {id, (ab)} je uzavřena na binární i unární operaci. Tím jsme probrali grupy generované transpozicemi (12), (13) a (23). Snadno rovněž nahlédneme, že množina {Id, (123), (132)} je podgrupou generovanou prvkem (123) nebo (132), čímž máme probrány všechny jednogenerované podgrupy. Uvažujme podgrupu H obsahující dvě různé transpozice (ab) a (ac). Potom H obsahuje také součin (bc) = (ab)(ac)(ab), tedy H už nutně obsahuje všechny transpozice grupy S3. Věta z přednášky lineární algebry, která říká, že každou permutaci dostaneme jako součin transpozic, nám zaručuje, že H obsahuje všechny permutace (protože H je uzavřené na skládání), tedy H = S3. Uvažujme nyní podgrupu H obsahující jedu transpozici (ab) a jeden trojcyklus např. (abc). Potom H obsahuje i transpozici (ac) = (abc)(ab). Obsahuje-li podgrupa H dvě různé transpozice, obsahuje podle předchozí úvahy všechny prvky, tedy opět dostáváme H = S3. Podgrupou obsahující dva různé trojcykly je, jak už víme, množina {Id, (123), (132)}. Tím jsme ovšem probrali všechny pogrupy a zbývá nám namalovat Hasseův diagram dané (inkluzí) uspořádaníé množiny:

11.

Najděte všechny normální podgrupy grupy permutací S3( . , -1 , Id ).

Na každé nenulové grupě najdeme dvě triviální normální podgrupy, v tomto případě grupy {id} a S3.

– 15 –

Na přednášce lineární algebry bylo dokázáno, že množina všech sudých permutací je uzavřená na skládání, inverzní permutace a obsahuje neutrální prvek. Navíc sgn g sgn h sgn g-1 = sgn h. Proto je množina všech sudých permutací A3 = {id, (123), (132)} (alternující grupa) normální podgrupou S3. Protože s prvkem tvaru (ab) musí normální podgrupa obsahovat i prvek tvaru (ac)(ab)(ac)-1 = (ac)(ab)(ac) = (bc), musí už se taková normální podgrupa rovnat celému S3 (viz předchozí úloha). Proto žádná další normální podgrupa na S3 neexistuje. 1.12.

12.

Rozhodněte, zda je svaz z příkladu 7 modulární.

Snadno nahlédneme, že d ≤ a a že d∨(c∧a) = d∨0 = d, zatímco (d∨c) ∧a = 1∧a = a. Tedy tento svaz není modulární.

13. Dokažte, že svaz obsahující jako podsvaz svaz M5, není modulární, kde svaz M5 má Hasseův diagram:

Označme si vrcholy podsvazu M5 tak, že 0 je jeho nejmenší prvek, 1 jeho největší prvek, b buď prvek, který je pokrýván 1 a pokrývá 0 a a budiž druhý atom svazu M5 a c jeho druhý koatom. Potom zjevně právě pro prvky a, b, c platí, že a∨(b∧c) = a, (a∨b)∧c = c. Protože a je různé od c, není splněna identita modularity.

14.

Dokažte, že svaz, který není modulární, obsahuje jako podsvaz svaz M5.

Pokud svaz není modulární obsahuje trojici prvků a, b, c tak, že a ≤ c a platí, že a∨(b∧c) je různé od (a∨b)∧c. Předně si uvědomme, že nemůže nastat, že by celá trojice a, b, c byla srovnatelná (tedy, že by tvořila lineárně uspořádaný podsvaz): o o o

Pokud by b ≤ a≤ c, pak by a∨(b∧c) = a = (a∨b)∧c. Pokud by a ≤ b≤ c, pak by a∨(b∧c) = b = (a∨b)∧c. Pokud by a ≤ c≤ b, pak by a∨(b∧c) = c = (a∨b)∧c.

Podobně si uvědomíme, že b není srovnatelné s a ani b (znamenalo by to, že b∧c = a resp. b∨a = c). Konečně označme 0 = a∧c a 1 = b∨c. Snadno ověříme, že 0 i 1 jsou další nové prvky, konečně {0, 1, a, b, c} je zřejmě množina uzavřená na průsek i spojení, tedy jde o podsvaz. Konečně tento podsvaz je právě tvaru M5. – 16 –

15.

Nechť X je neprázdná množina. Dokažte, že svaz všech podmnožin P(X) spolu s inkluzí je modulární.

Potřebujeme dokázat, že pro každou trojici podmnožin A, B a C množiny X takovou, že A⊆C platí inkluze (A∪B)∩C⊆A∪(B∩C). Vezměme tedy nějaký prvek x∈(A∪B)∩C. Potom x∈C a zároveň x∈(A∪B). Pokud x∈C a x∈A potom samozřejmě x∈A∪(B∩C). Pokud x∈C a zároveň x∈B, pak x∈B∩C, tedy opět x∈A∪(B∩C).

16.

Nechť H1 a H2 jsou dvě normální podgrupy grupy G(.,-1,1). Dokažte, že H1H2 = {h1h2| h1∈H1 a h2∈H2} = H2H1 = {h2h1| h1∈H1 a h2∈H2}.

Stačí nám dokázat jednu implikaci (druhou implikaci dostaneme symetrickým argumentem). Nechť tedy h1h2∈H1H2. Položme h'2 = h1h2h1-1. Protože je H2 normální, potom opět h'2∈H2, tudíž h1h2 = h'2h1∈H2H1.

17.

Nechť H1 a H2 jsou dvě normální podgrupy grupy G(.,-1,1). Dokažte, že H1H2 je nejmenší normální podgrupa obsahující H1 a H2.

Potřebujeme ověřit, že množina H1H2 je uzavřená na všechny operace. Zjevně 1 = 1.1∈H1H2. Nechť h1, h'1∈H1 a dále h2, h'2∈H2. Potom (h1h2)-1 = h2-1 h1-1, což leží v H2H1 = H1H2. Konečně h1h2h'1h'2∈H1H2H1H2 = H1H1H2H2 = H1H2 podle předchozího cvičení. Dále vezmeme-li g∈G a h1h2∈H1H2, pak gh1h2g-1 = (gh1g-1)(gh2g-1), což je prvkem H1H2, neboť H1 i H2 jsou normální podgrupy. Konečně H1 i H2 v H1H2 zjevně leží. Každá podgrupa obsahující H1 i H2 musí být uzavřená na všechny součiny prvků z H1 a H2, tedy musí obsahovat H1H2.

18.

Dokažte, že svaz všech normálních podgrup grupy G(.,-1,1) je modulární.

Nechť A, B, C jsou normální podgrupy grupy G a nechť A⊆C. Potřebujeme spočítat (AB)∩C⊆A(B∩C). Nechť tedy x∈(AB)∩C, tedy x = ab, kde a∈A a b∈B. Potom b = a-1x což je prvek podgrupy C., tedy b∈B∩C, a proto ab∈A(B∩C).

19.

Dokažte, že svaz všech kongruencí na grupě G(.,-1,1) je modulární.

Z přednášky víme, že svazy všech normálních podgrupy a všech kongruencí jsou izomorfní, proto svaz všech kongruencí je podle předchozího příkladu modulární. – 17 –

8.12.

Grupy 1. Nechť G( . ,-1,1) a H( . ,-1,1) jsou grupy a nechť f je homomorfismus G do H. Označme Ker f = {g z G| f(g) = 1}. Dokažte, že Ker f je normální podgrupa G.

Nejrychlejší bude, když si uvědomíme, že Ker f = [1] ker f, což je podle Věty 2.10 (pro každou kongruenci) normální podgrupa. Tvrzení bychom snadno mohli dokázat i přímočaře.

2. Nechť T( + ,.) je těleso a GLn(T)( . ,-1,In) grupa regulárních čtvercových matic řádu. Dokažte, že determinant je homomorfismem grupy GLn(T)( . ,-1,In) do grupy T-{0}( . ,-1,1).

Podle Poznámky 4.1. nám stačí ověřit, že zobrazení det je slučitelné s binární operací. Ovšem na přednášce lineární algebry bylo dokázáno, že det(A.B) = det(A).det(B), tedy determinant je homomorfismus grup.

3. Nechť Sn( . ,-1,Id) je grupa permutací na n prvcích. Dokažte, že znaménko sgn je homomorfismem grupy Sn( . ,-1,Id) do grupy {1,-1}( . ,-1,1).

Podobně jako v předchozí úloze se můžeme odvolat na tvrzení z lineární algebry, které říká, že sgn p.q = sgn p . sgn q. Tedy znaménko je opět homomorfismus.

4. Dokažte, že množina všech matic s determinantem 1 je normální podgrupou grupy GLn(T) a že množina An všech sudých permutací je normální podgrupou grupy Sn.

Snadno nahlédneme, že {M z GLn(T)| det(M) = 1} = Ker det a An = Ker sgn. Tedy podle tvrzení dokázaného v úloze 1 jsou obě množiny normálními podgrupami.

5. Nechť G je grupa a H její podgrupa indexu 2. Dokažte, že H je normální podgrupa G.

Je-li H podgrupa G indexu 2, snadno si uvědomíme, že pro každé g∈G-H je gH = G-H = Hg, tj. lmod H = rmod H. Potřebujeme ukázat, že xhx-1∈H ∀h∈H a x∈G. Leží-li x v H je tvrzení triviální, předpokládejme tedy, že x∈G-H. Už jsme si uvědomili, že xH = Hx, proto xHx-1 = H. Tím máme tvrzení dokázané.

– 18 –

15.12. 6. Nechť p a s jsou permutace na Sn a nechť p(a) = b. Dokažte, že (sps-1)(s(a)) = s(b).

Důkaz tvrzení je zcela přímočarý. Důležitým důsledkem je ovšem pozorování, že permutace p a sps-1 mají stejný počet stejných cyklů, neboť jsme právě dokázali, že s [...(...ab...)...] s-1 = ...(...s(a)s(b)...)... .

7. Mějme permutace p = (1346)(27)(589) a q = (16)(29)(345) dvě permutace z S9. Spočítejte hodnoty pqp-1 a qpq-1.

Postupujeme podle předchozího pozorování: [(1346)(27)(589)] [(16)(29)(345)] [(1346)(27)(589)]-1 = (31)(75)(468), [(16)(29)(345)] [(1346)(27)(589)] [(16)(29)(345)]-1 = (6451)(97)(382).

8. Mějme permutace p1 = (126)(37)(458) a p2 = (12)(345)(678) dvě permutace z S8. Rozhodněte, zda existuje permutace q s vlastností qp1q-1 = p2 a případně takovou permutaci q najděte.

Využijeme opačný postup k postupu v předchozím příkladu. Obě permutace jsou stejného typu (což je zřejmě nutná podmínka, aby permutace q existovala). Seřaďme stejnými n-cykly pod sebe, například: (126)(37)(458) (345)(12)(678) Zřejmě potom permutace q = (13)(24657)(8) splňuje podmínku qp1q-1 = p2. 9. Ukažte, že grupa sudých permutací na čtyřech prvcích A4 neobsahuje žádnou podgrupu řádu 6.

Uvědomme si, že A4 = {Id, (12)(34), (13)(24), (14)(23), (123), (132), (124), (142), (134), (143), (234), (243)}. Předpoládejme, že máme podgrupu H řádu alespoň 6. To určitě znamená, že H obsahuje alespoň dva trojcykly, tj. permutace tvaru (abc). Podle Lagrangeovy věty je index podgrupy H v grupě A4 nejvýše 2. Tedy podle tvrzení z úlohy 5 je H normální podgrupa A4. To ovšem znamená, že p(abc)p-1 = (p(a)p(b)p(c))∈H ∀p∈A4. Nyní už snadno nahlédneme, že H nutně obsahuje všechny trojcykly, tj řád H je alespoň 8. Z Langrangeovy věty plyne, že |H| = 12, tedy H = A4. Poznamenejme, že automorfismy (tj. vzájemně jednoznačná zobrazení, které "zachovávají strukturu objektu") nějakých algebraických či jiých matematických struktru tvoří grupu. Takovou grupou je například množina symetrií nějakého pravidelného rovinného nebo prostorového obrazce spolu se skládáním, případně automorfismy grafů apod.

– 19 –

10.

Jakou má strukturu grupa všech symetrií čtverce D8?

Nalezení množiny všech symetrií čtverce je geometricky velmi názorné a nevyžaduje další formální důkaz. Tato množina obsahuje identitu, otočení o 90, 180 a 270 stupňů, osové symetrii podle dvou diagonál a dvě osové symetrie podle spojnice středů dvou protilehlých stran. Tedy je osmiprvková. Protože jde vlastně o permutaci vrcholů s jistými dodatečnými podmínkami, můžeme tuto grupu chápat jako podgrupu grupy všech permutací na 4 bodech. Přesněji řečeno můžeme definovat prostý homomorfismus naší grupy do S4 (a to přesně tak, že nějak pevně očíslujeme vrcholy, a každé symetrii přiřadíme právě tu permutaci, jakou provede daná symetrie na vrcholech). Označíme-li vrcholy například proti směru hodinových ručiček postupně čísly 1,2,3,4, pak je grupa D8 izomorfní podgrupě {Id, (1234), (13)(24), (1423), (13), (24), (14)(23), (12)(34)} grupy S4.

11.

Ověřte, že množiny H1 = {Id, (13)}, H2 = {Id, (13), (24), (13)(24)} a H3 = {Id, (1234), (13)(24), (1423), (13), (24), (14)(23), (12)(34)} tvoří podgrupy S4, přičemž H1 je normální v H2, H2 je normální v H3, ale H1 není normální v H3

H1 i H2 jsou zjevně podgrupy. O množině H3 jsme v předchozím příkladu ukázali, že je homomorfním odkazem grupy, tedy podgrupa. Dále podle Lagrangeovy věty dostáváme, že [H2:H1] = [H3:H2] = 2. Využijeme-li 5. příklad, vidíme, že H1 je normální v H2 a H2 je normální v H3. Konečně [(14)(23)] [(13)] [(14)(23)]-1 = (24)∉H1, tedy H1 není normální podgrupa H3.

12.

Buď G( . ,-1,1) grupa, ověřte, že zobrazení Lg(h) = g.h je ∀g∈G bijekce na G.

Pokud Lg(h1) = Lg(h2), pak g.h1 = g.h2, a tedy h1 = h2. Tím jsme ověřili, že je Lg prosté. Vezměme libovolné h∈G. Potom Lg(g-1.h) = g.g-1.h = h, tedy Lg je i zobrazení na. 22.12. 13.

Dokažte, že zobrazení f libovolné grupy G do grupy všech permutací S(G) množiny G dané předpisem f(g) = Lg (viz předchozí příklad) je prostý grupový homomorfismus.

Víme, že ověříme-li slučitelnost zobrazení f s binární operací, bude to už zaručovat, že je f homomorfismus. Mějme, tedy g1, g2∈G a nechť h probíhá celé G. Pak [f(g1.g2)](h) = (g1.g2).h = g1.(g2.h) = [f(g1).f(g2)](h).

– 20 –

Tím jsme dokázali, že je f homomorfismus. Dále, pokud f(g1) = f(g2), pak g1 = [f(g1)](1) = [f(g2)](1) = g2. Tedy f je prosté zobrazení.

14.

Nechť G je konečná grupa řádu n. Dokažte, že G je izomorfní nějaké podgrupě permutační grupy Sn.

Nejdřív zvolme nějakou bijekci množiny G do množiny {1,2,...,n}, označme ji b. Nyní budeme definovat pomocí homomorfismu f z předchozí úlohy zobrazení F z grupy G do grupy Sn: [F(g)](k) = b([f(g)](b-1(k))), kde k∈{1,2,...,n}. Snadno nahlédneme, že je F prosté zobrazení. Dále nám stačí dokázat, že je F zobrazení slučitelné s binární grupovou operací: [F(g1.g2)](k) = b([f(g1.g2)](b-1(k))) = b([f(g1).f(g2)](b-1(k))) = [b.f(g1).b-1.b.f(g2).b-1](k) = [F(g1).F(g2)](k). Podle 1. věty o izomorfismu je G/Id izomorfní F(G). Neboť F(G) je podgrupa Sn a G/Id je izomorfní G, dostáváme požadovaný izomorfismus grupy G a podgrupy F(G) grupy Sn.

15.

Najděte Hasseův diagram svazu všech podgrup a svazu všech kongruencí na cyklické grupě řádu 126.

Předně poznamenejme, že cyklická grupa řádu 126 je izomorfní grupě Z126, tedy stačí vyšetřit všechny podgrupy a kongruence na Z126. Připomeňme si, že podle Lagrangeovy věty existují v Z126 jen podgrupy řádu, který dělí číslo 126, přičemž 126 = 2.32.7. Navíc v cyklické grupě pro každé k, které dělí řád grupy tj. 126, existuje právě jedna podgrupa řádu k, jež je generována právě prvkem 126/k. Konečně si zbývá uvědomit, že každá podgrupa i faktorgrupa cyklické grupy je cyklická, proto jsou dvě podgrupy H1 a H2 spojeny v Hasseově diagramu hranou, právě když |H1| dělí |H2| a |H2|/|H1| je prvočíslo (to znamená, že mezi H1 a H2 neleží žádná další podgrupa). Tedy uvědomíme-li si, že H1 = k1Z126 a H2 = k2Z126, pak H1 a H2 jsou spojeny hranou, přičemž H1 leží pod H2, právě když k2 dělí k1 a k1/k2 je prvočíslo (v našem případě tedy 2, 3 nebo 7). Víme, že podgrupy grupy Z126 jsou generovány prvky 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 0. Zbývá mezi příslušnými podgrupami nakreslit hrany a uspořádat je do Hasseova diagramu:

– 21 –

Neboť grupa Z126 je komutativní, je každá její podgrupa normální, tedy svaz všech normálních podgrup grupy Z126 je izomorfní svazu všech jejích podgrup. Konečně svaz všech kongruencí na libovolné grupě je izomorfní svazu všech normálních podgrup, tedy v našem případě je izomorfní svazu všech podgrup na Z126, jehož Hasseův diagram už jsme nakreslili.

16.

Spočítejte počet všech generátorů cyklické grupy G o 126 prvcích, tj. počet všech takových prvků g, pro něž < g > = G.

Víme, že grupa G je izomorfní (tj. je z algebraického hlediska stejná) grupě Z126. Počet generátorů grupy Z126 spočítáme pomocí Eulerovy funkce. k tomu nám stačí znát prvočíselný rozklad 126 = 2.32.7. Tedy počet všech generátorů = (2-1).(3-1).3.(7-1) = 36. 5.1. 17.

Najděte Hasseův diagram svazu všech kongruencí na cyklické grupě řádu 44.

Postupujeme stehně jako v úloze 15. Uvědomíme se, že svaz všech kongruencí je izomorfní svazu všech normálních podgrup, tj. v komutativní grupě (kterou každá cyklická grupa je) svazu všech podgrup. Navíc nám stačí vyšetřovat svaz všech podgrup izomorfní cyklické grupy Z44. Z Poznámky 4.7 (2) plyne, že Z44 obsahuje právě 6 podgrup: {0}, 2Z44, 4Z44, 11Z44, 22Z44 a Z44, které už snadno uspořádáme do Hasseova diagramu.

18.

Buď A nějaká algebra. Dokažte, že množina všech izomorfismů algebry A do sebe (označme ji Aut(A)) je podgrupou permutační grupy S(A) všech bijekcí na množině A.

Potřebujeme ukázat, že je množina Aut(A) uzavřená na všechny operace grupy S(A), tj. na skládání (značme ho .), inverzní izomorfimsus (-1) a identicé zobrazení (nulární operace Id). Pro každé f, g∈Aut(A), je zjevně f.g opět bijekce na A a podle Poznámky 2.2 (2) z přednášky je to opět homomorfismus, tedy izomorfismus A do A. Podobně plyne z téže poznámky, že f-1 je izomorfismus A do A. Konečně identické zobrazení je zjevně bijektivní homomorfismus, proto Id∈Aut(A).

19.

Dokažte, že každý homomorfismus f grupy Zn( + ,-,0) do sebe je tvaru f(a) = k.a, kde k∈Zn a . je násobení modulo n (tj. násobení v okruhu Zn( + , . ,- ,0,1)).

Nechť nejprve máme nějaký homomorfismus f grupy Zn( + ,-,0) do sebe. Označme k = f(1). Potom zjevně f(1 + 1) = k + k = 2.k, f(1 + 1 + 1) = k + k + k = 3.k, atd. Indukcí snadno dostáváme, že f(k) = k.n. Potřebujeme ještě ukázat, že každé zobrazení fk dané předpisem fk(a) = k.a je grupovým homomorfismem.

– 22 –

Víme (dle Poznámky 4.1), že stačí ověřit slučitelnost fk s binární operací + . Neboť je Zn( + , . ,- ,0,1) okruh, platí pro něj distributivita, tedy fk(a + b) = k.(a + b) = k.a + k.b = fk(a) + fk(b). Tím jsme dokázali, že {fk| k∈Zn} tvoří množinu všech homomorfismů grupy Zn( + ,-,0) do sebe.

20.

Dokažte, že homomorfismus fk(a) = k.a (viz předchozí příklad) je izomorfismem právě tehdy, když jsou k a n nesoudělná.

Protože je fk zobrazení konečné množiny do sebe, je fk bijekce, právě když je to zobrazení na, tj. < k > = < fk(1) > = fk(Zn) = Zn. To zřejmě nastává právě tehdy, když je k generátor grupy Zn, což je (podle Poznámky 4.12(2)) právě tehdy, když je NSD(k,n) = 1.

21.

Definujme zobrazení F, které každému prvku k grupy Zn*(.,-1,1) všech invertibilních prvků monoidu Zn(.,1) přiřadí homomorfismus fk grupy Zn( + ,-,0) do sebe z předchozího příkladu. Ověřte, že je F izomorfismus grupy Zn*(.,-1,1) a grupy Aut(Zn( + ,-,0))(.,-1,Id).

Připomeňme, že číslo a∈Zn je invertibilní, právě když je NSD(a,n) = 1. v úloze 20 už jsme dokázali, že je F dobře definované bijektivní zobrazení. Zbývá tedy ověřit, že se jedná o homomorfismus, tj. že F(k.l) = F(k).F(l) pro každé k a l nesoudělné s n. Pro každé a z Zn potřebujeme tedy ukázat, že [F(k.l)](a) = [F(k).F(l)](a), dokazujme: [F(k.l)](a) = fk.l(a) = (k.l).a = k.(l.a) = fk(l.a) = fk(fl(a)) = [F(k).F(l)](a). Tím jsme dokázali, že jsou grupy Zn* a Aut(Zn) izomorfní.

22.

Popište svaz podgrup grupy Aut(Z9( + ,-,0))(.,-1,Id).

Použijeme tvrzení dokázané v úloze 21 a budeme místo Aut(Z9) vyšetřovat izomorfní grupu Z9*(.,-1,1). Předně Z9* = {1,2,4,5,7,8}. Dále si uvědomíme, že v cyklické podgrupě < 2 > leží určitě prvky 1, 2, 4 = 2.2, 8 = 2.2.2, to znamená, že řád podgrupy < 2 > je větší nebo roven 4 a zároveň musí podle Lagrangeovy věty dělit řád grupy Z9*, tedy 6. To znamená, že Řád < 2 > je 6 a < 2 > = Z9*. Zjistili jsme, že grupa Z9* je šestiprvková cyklická grupa (s generátorem 2), proto je (podle Věty 4.8) izomorfní grupě Z6( + ,-,0). Stačí nám tedy popsat podgrupy grupy Z6( + ,-,0). Víme, že ∃! 1-prvková, 2-prvková, 3-prvková a 6-prvková podgrupa Z6( + ,-,0) a proto i Z9*(.,-1,1). Konečně jednoduchou úvahou zjistíme, že 1-prvkovou podgrupou Z9* je {1}, 2-prvkovou < 8 > = {1,8}, 3-prvkovou < 4 > = {1,4,7} a 6-prvkovou Z9*.

– 23 –