2.10.2007

De�nice: Rekneme, ze mnozina R spolu s binarnimi operacemi " + " a " · " jekomutativni okruh ⇔

(1) operace + a · jsou komutativni a asociativni,(2) a.(b+ c) = ab+ ac pro kazde a, b, c ∈ R,(3) ex. prvek 0 ∈ R, ze a+ 0 = 0 + a = a pro kazde a ∈ R,(4) pro kazde a ∈ R ex. −a ∈ R, ze a+ (−a) = (−a) + a = 0(5) ex. prvek 1 ∈ R, ze a.1 = 1.a = a pro kazde a ∈ R.

Komutativni okruh muzeme de�novat take jako univerzalni algebru (R,+,−, ·, 0, 1),(kde "− " je unarni operace a 0, 1 konstanty - tj. nularni operace), ktera budesplnovat vyse uvedene podminky.

Dale uz budeme misto komutativni okruh rikat strucne jen okruh.Prikladem okruhu jsou telesa, cela cisla Z a polynomy F [x] nad telesem F

a promennou x.Prvky F [x] jsou nekonecne posloupnosti (a0, a1, . . .) , kde ai ∈ F a pouze

pro konecne mnoho i je ai 6= 0. Tyto posloupnosti formalne zapisujeme, jako∑i

aixi. Operace + a · jsou nasledujici:∑

i

aixi +

∑i

bixi :=

∑i

(ai + bi)xi

a(∑

i

aixi).(

∑j

bjxj) :=

∑k

( ∑i+j=k

aibj

)xk.

Protoze x nyni odpovida posloupnosti (0, 1, 0, 0, . . .) a protoze prvky a ∈ Fmuzeme ztotoznit s (a, 0, 0, . . .), tak je snadno videt, ze zapis

∑i

aixi neni jen

formalni, ale skutecne znamena a0+a1 ·x+a2 ·x2+ . . .+an ·xn a xi = x ·x . . . xi-krat.

Jestlize 0 6= f =∑i

aixi ∈ F [x], pak de�nujeme stupen polynomu f (znaceni

deg(f)) jako nejvetsi n takove, ze an 6= 0 (an se pak nazyva vedouci koe�cient).Pro f = 0 se de�nuje stupen jako −1 (pripadne −∞).

Zrejme pro kazde f, g ∈ F [x] takove, ze f 6= 0 a g 6= 0 plati, ze

deg(f · g) = deg(f) + deg(g).

Poznamka: Polynom jako formalni suma∑i

aixi a polynomialni funkce

ϕf : F → F , ϕf (a) :=∑i

aiai nejsou obecne ve vzajemne jednoznacne kore-

spondenci. Staci uvazit konecne teleso F - pak je polynomu nekonecne, zatimcopolynomialnich funkci jen konecne.

Tvrzen�� 1. Necht R = Z nebo R = F [x]. Pak pro kazde a, b ∈ R, b 6= 0 existuji

1

prvky q, r ∈ R, ze a = q.b + r a |r| < |b| pokud R = Z a st(r) < st(b) pokudR = F [x].

D�ukaz: (i) Necht R = Z. Existenci ukazeme indukci podle |a|:Pro a = 0 staci polozit q = r = 0.ind. krok: Jestlize |a| < |b|. Pak staci polozit q = 0 a r = a. Necht je tedy

nyni |a| ≥ |b|. Pak je zrejme bud |a − b| < |a| nebo |a + b| < |a|. Na jeden ztechto prvku tedy staci pouzit ind. predpoklad.

(ii) Necht R = F [x]. Existenci ukazeme indukci podle deg(a):Pro a = 0 opet staci polozit q = r = 0.ind krok: Jestlize deg(a) < deg(b). Pak staci polozit q = 0 a r = a. Necht je

tedy nyni n = deg(a) ≥ deg(b) = m a necht an a bm jsou vedouci koe�cientypolynomu a a b. Pak pro polynom c := a − an

bmxn−mb je zrejme deg(c) < n =

deg(a). Opet staci jen uzit ind. predpoklad na c. �

Toto tvrzeni vede k nasledujici de�nici:

De�nice: Okruh R nazveme Eukleidovym oborem ⇔(1) (∀ a, b ∈ R) a.b = 0⇒ (a = 0 ∨ b = 0) (tj. je to obor integrity),(2) ex. funkce ν : R \ {0} → N0 takova, ze pro kazde a, b ∈ R, b 6= 0 existuji

prvky q, r ∈ R, ze a = qb+ r, kde r = 0 nebo ν(r) < ν(b).

Okruhy Z a F [x] jsou tedy Eukleidovy obory. Dalsim prikladem jsou telesa(s ν(x) = 1 pro x 6= 0) a okruhy Z[i] := {a + bi ∈ C| a, b ∈ Z} a Z[

√−2] :=

{a+ bi√2 ∈ C| a, b ∈ Z}, kde ν(z) = |z| pro z 6= 0.

De�nice: Necht R je okruh a, b ∈ R. Rekneme, ze a deli b (znaceni a | b)⇔ ex.x ∈ R, ze b = ax.

Prvek d ∈ R je nejvetsi spolecny delitel a a b (znaceni gcd(a, b)) ⇔(1) d|a & d|b, (tj. je to spolecny delitel)(2) pro kazde c ∈ R plati: (c|a & c|b)⇒ c|d. (tj. je nejvetsi takovy)

Poznamka: Snadno se dokaze nasledujici;Necht k ∈ R. Pak d je gcd(a, b) ⇔ d je gcd(b, a− kb).

Tvrzen�� 2. Necht R je Eukleiduv obor. Pak pro kazde dva prvky a, b ∈ Rexistuje jejich nejvetsi spolecny delitel d a existuji k, l ∈ R, ze ka+ lb = d.

Vsechny tyto prvky lze nalezt tzv. Eukleidovym algoritmem.

D�ukaz: Jestlize b = 0 pak zrejme a je nejvetsim spolecnym delitelem a a b. Bezujmy na obecnosti tedy muzeme predpokladat, ze b 6= 0 a a 6= 0. Zkonstruujemeposloupnost prvku rn ∈ R, pro n ≥ −1 nasledujicim zpusobem:

(1) Polozme r−1 := a a r0 := b.(2) Necht n ≥ 0 a predpokladejme, ze uz mame r−1, r0, . . . , rn.

2

Jestlize rn 6= 0, pak z predpokladu ex. q, r ∈ R, ze rn−1 = qrn+ r, kde r = 0nebo ν(r) < ν(rn). Polozime tedy rn+1 := r. A pokud je rn = 0, pak polozmern+1 = 0.

Mame tedy soustavu rovnic

a = q1b+ r1

b = q2r1 + r2

r1 = q3r2 + r3

...

rn−2 = qnrn−1 + rn

rn−1 = qn+1rn + rn+1

...

Ukazeme, ze ex. n, ze rn = 0. Predpokladejme opak - pak je rn 6= 0 provsechna n ≥ −1. Z konstrukce pak vyplyva, ze

ν(b) = ν(r0) > ν(r1) > ν(r2) > . . . > ν(rn) > . . . .

Existuje tedy nekonecna ostre klesajici posloupnost nezapornych celych cisel,coz je spor.

Necht je nyni n nejmensi takove, ze rn+1 = 0. Pak je rn 6= 0 a plati, ze rn jenejmensi spolecny delitel a a b.

Podle predchozi poznamky je totiz: rn je gcd(a, b) ⇔ rn je gcd(b, r1) ⇔ rnje gcd(r1, r2) ⇔ . . . ⇔ rn je gcd(rn−2, rn−1) ⇔ rn je gcd(rn−1, rn). A protozern deli rn−1 (nebot rn+1 = 0), tak rn je skutecne gcd(rn−1, rn).

Soucasne postupnym zpetnym dosazovanim dostavame, ze rn = rn−2 −qnrn−1 = (. . .)rn−3 + (. . .)rn−2 = . . . = (. . .)r1 + (. . .)r2 = (. . .)b + (. . .)r1 =ka+ lb pro vhodne k, l ∈ R (zde "(. . .)" znamena vhodne vyrazy ziskane dosa-zenim z rovnic). �

Vyzkousime si to na nasledujicich prikladech:

P�r. Najdete nejvetsi spol. delitel cisel 72 a 93 v Z a jeho vyjadreni jako linearnikombinaci danych prvku.

P�r. Najdete nejvetsi spol. delitel polynomu x4 − 3x2 − 2x+4 a x3 − x2 − x+1v Q[x] a jeho vyjadreni jako linearni kombinaci danych prvku.

Necht R je okruh, a ∈ R. De�nujme si nasledujici relaci ≡a na R×R:

x ≡a x′ ⇔ a|(x− x′).

3

Tvrzen�� 3. (1) Relace ≡a je ekvivalence.(2) Pro kazde x, x′, y, y′ ∈ R plati:(x ≡a x′ & y ≡a y′) ⇒ (x + y ≡a x′ + y & xy ≡a x′y′) (tj. je to tzv.

kongruence vzhledem k " + " a " · ").

Oznacme [x] := {x′ ∈ R| x ≡a x′}. Pomoci ≡a nyni muzeme zkonstruovat

novy okruh R/Ra takto:nosna mnozina bude R/Ra := {[x]| x ∈ R} a operace budou de�novany jako:

[x] + [y] := [x+ y],

[x] · [y] := [xy]

.

De�nice: Polynom f ∈ F [x] stupne alespon 1 se nazyva ireducibilni v F [x] ⇔pro kazde g, h ∈ F [x] plati: f = gh ⇒ (f |g ∨ f |h).

Ireducibilni polynom je tedy takovy, ktery je stupne alespon 1 a neda se v!prislusnem okruhu polynomu! napsat jako soucin polynomu mensich stupnu.

9.10.2006

Tvrzen�� 4. (1) Necht f ∈ F [x] a a ∈ F . Pak a je koren polynomu f (tj.f(a) = 0) ⇔ (x− a)|f .

(2) Polynom f ∈ F [x] stupne 2 nebo 3 je ireducibilni v F ⇔ f nema korenv F (tj. neexistuje prvek a ∈ F , ze f(a) = 0).

D�ukaz: (1) (⇒) Necht f(x) =n∑

i=0aix

i. Pak je f(x) = f(x) − f(a) =n∑

i=0aix

i −n∑

i=0aia

i =n∑

i=0ai(x

i−ai) =n∑

i=0ai(

i∑j=0

xi−jaj)(x−a). Opacna implikace je zrejma.

(2)(⇒) Plyne ihned z casti (1). (⇐) Kdyby polynom nebyl ireducibilni, pakby se dal napsat jako f = gh, kde alespon jeden z polynomu g, h by musel mitstupen 1 a tedy by mel koren. To by byl spor. �

Poznamka: (a) Ireducibilita polynomu zavisi na tom, vzhledem k jakemuokruhu polynomu ji uvazujeme:

polynom x2 + 1 je ireducibilni v R[x] (nebot nema koren v R), ale tentyzpolynom neni ireducibilni v C[x] nebot x2 + 1 = (x− i)(x+ i).

(b) Polynom (x2 + 1)2 neni ireducibilni v R[x], prestoze nema koren v R.

Tvrzen�� 5. Necht F je teleso, ktere ma q prvku a f ∈ F [x] je polynom stupnen ≥ 1. Pak pocet prvku okruhu F [x]/f.F [x] je qn.

4

D�ukaz: Prvky F [x]/f.F [x] tvori tridy ekvivalence [x] a ty jednoznacne odpovi-daji zbytkum po deleni polynomem f , coz jsou polynomy z F [x] stupne nejvysen− 1, a tech je zrejme qn. �

Tvrzen�� 6. (1) Necht n ≥ 0. Pak Z/nZ je teleso ⇔ n je prvocislo.(2) Necht f ∈ F [x]. Pak F [x]/f.F [x] je teleso ⇔ f je ireducibilni polynom.

D�ukaz: (1) (⇒) Pokud je n = 0 pak je Z/0.Z zrejme totez, co Z a to teleso neni.Pro n = 1 je Z/1.Z jednoprvkovy okruh, coz opet neni teleso. Predpokladejmenyni, ze n ≥ 2 a neni to prvocislo. Pak n = kl, pro nejake 0 < k, l < n a tedy[k] 6= [0] 6= [l], ale pritom je [k].[l] = [k.l] = [n] = [0]. Tedy Z/nZ nemuze bytteleso.

(⇐) Necht n je prvocislo. Ukazeme, ze pro kazde [k] 6= [0] existuje inverzniprvek vzhledem k nasobeni. Necht je tedy BUNO 0 < k < n. Pak jsou k a nnesoudelna cisla (tj. gcd(k, p) je 1) a tudiz ex. (podle Tvrzeni 1) a, b ∈ Z, zeak + bn = 1 a tedy [a].[k] = [ak] = [1 − bn] = [1] − [b].[0] = [1]. Mame tak, ze[a] = [k]−1 a soucasne mame zpusob jak nalezt pomoci Eukleidova algoritmuinverzni prvek.

(2) Dukaz je analogicky jako v casti (1) jen se misto cisel berou polynomy av usporadani porovnavame stupne techto polynomu. �

Tvrzen�� 7. (1) Necht F je konecne teleso. Pak |F | = pn pro nejake prvocislo pa n ≥ 1.

(2) Necht p je prvocislo, n ≥ 1. Pak existuje (az na izomor�smus teles) pravejedno konecne teleso, ktere ma pn prvku. Budeme ho oznacovat jako Fpn .

Konstrukce konecneho telesa radu pn:

Necht p je prvocislo a f ∈ Zp je ireducibilni polynom stupne n.Pak Zp[x]/f.Zp[x] je podle Tvrzemi 5 a 6 konecne teleso s pn prvky.

Co tedy potrebujeme mit, je ireducibilni polynom vhodneho stupne.

Tvrzen�� 8. Necht f ∈ F [x] je polynom stupne alespon 1. Pak zobrazeni ψ :F → F [x]/f.F [x], ψ(a) := [a] je prosty homor�smus okruhu (a tedy vnoreni).

Prvky z telesa a jejich prislusne obrazy tak muzeme ztotoznit a teleso Fchapat jako podmnozinu okruhu F [x]/f.F [x].

P�r. Zkonstruujte teleso F4 (tj. se 4 prvky).

�Re�sen��: Polynom x2 + x+ 1 ∈ Z2[x] nema zrejme v Z2 = {0, 1} koren a tedy jepodle Tvrzeni 4 ireducibilni v Z2[x]. Prvky telesa jsou tedy zbytkove tridy podeleni polynomem x2+x+1, tj. F4 = {[0], [1], [x], [x+1]}. Oznacime-li si α := [x],

5

pak vzhledem k predchozimu Tvrzeni muzeme psat F4 = {0, 1, α, α+ 1}. Zapi-seme si tabulku nasobeni v telese F4

· 0 1 α α+ 10 0 0 0 01 0 1 α α+ 1α 0 α α+ 1 1

α+ 1 0 α+ 1 1 α

Vysledky nasobeni zjistime takto: mame, ze 0 = [0] = [x2 + x+ 1] = [x]2 +[x] + [1] = α2 + α+ 1. Odsud uz snadno dostaneme, ze α · α = −α− 1 = α+ 1,α ·(α+1) = α2+α = −1 = 1 a (α+1) ·(α+1) = α2+2α+1 = α2+1 = −α = α.

Pouzili jsme zde, ze pro kazdy prvek a ∈ F4 je a+a = 0 (a tedy a = −a) nebotF4 obsahuje Z2 jako podteleso. Diky tomuto take snadno odvodime tabulkuscitani. �

P�r. Najdete nejvetsi spol. delitel polynomu y3 + αy2 + αy + (α+ 1) a y2 + α vF4[y], kde F4 = {0, 1, α, α+ 1} je teleso z predchoziho prikladu.

Jak najit vsechna reseni (x, y) ∈ R2 rovnice (∗) xa + yb = c , kdea, b, c ∈ R a R = Z nebo R = F [x]:

(1) Rovnice (∗) ma reseni ⇔ gcd(a, b) deli c.

D�ukaz: (⇒) gcd(a, b) deli a i b a proto deli i xa+ yb = c.(⇐) Necht d je gcd(a, b) a necht c = l.d pro nejake k ∈ R. Podle Eukleidova

algoritmu ex. m,n ∈ R, ze ma + nb = d a tedy (lm)a + (ln)b = ld = c. Takze(x, y) := (lm, ln) je reseni (∗). �

(2) Najdeme jedno (partikularni) reseni (x0, y0) rovnice (∗) (jak? - viz dukazpredchoziho bodu)

(3) Najdeme vsechna reseni (x′, y′) rovnice x′a + y′b = 0 . Tato reseni jsoutvaru (x′, y′) = (− b

d · k,ad · k), kde d je gcd(a, b) a k ∈ R.

D�ukaz: Rovnici x′a+ y′b = 0 vydelime d a dostaneme x′ ad = −y′ bd . Protoze

ad a

bd jsou uz nesoudelne prvky (tj. jejich nejvetsi spol. delitel je 1) tak z posledni

rovnice plyne, ze ad musi delit y′ a podobne b

d deli x′. �

(4) Vsechna reseni (∗) jsou tvaru (x, y) = (x0 − bd · k, y0 +

ad · k), kde k ∈ R

a (x0, y0) je nejake reseni (∗).

P�r. Najdete vsechna reseni rovnice k.84 + l.132 = 36 v Z.

P�r. Najdete inverzni prvek k prvku [65] (tj. [65]−1) v Z124.

6

�Re�sen��: Tedy hledame x ∈ Z, tak aby [x].[65] = [1] v Z124, coz podle de�niceznamena, ze x.65−1 = y.124 pro nejake y ∈ Z. Dale uz postupujeme standardne,tj. Eukleidovym algoritmem. Pro nalezene x pak jeste najdeme kanonickehoreprezentanta prislusne zbytkove tridy, tj. x′ ∈ Z takove, ze x′ ≡ x (mod 124) a0 ≤ x′ < 124. �

P�r. Najdete nejvetsi spol. delitel cisel 3 + i a 4 + 2i v Z[i].

16.10.2007

Tvrzen�� 9. Obor Z[i] = {a+ bi ∈ C| a, b ∈ Z} s ν(z) = |z| je Eukleiduv.

D�ukaz: Mejme tedy x, y ∈ Z[i], y 6= 0. Pokud je |x| < |y| pak muzeme pouzit

x = 0.y+x. Necht je tedy |x| ≥ |y|, x = a+bi, y = c+di. Pak xy = (a+bi)(c−di)

(c+di)(c−di) =ac+bd|y|2 + bc−ad

|y|2 i = s+ ti, kde s, t ∈ Q. Necht e je nejblizsi cele cislo k s a podobne

f je nejblizsi cele cislo k t. Polozme q := e+ fi ∈ Z[i] a r := x− qy ∈ Z[i].Nyni mame, ze | ry | = |

x−qyy | = |(s + ti) − q| = |(s − e) + (t − f)i| =√

(s− e)2 + (t− f)2 ≤√( 12 )

2 + ( 12 )2 =

√22 < 1. Tedy |r| < |y|, coz jsme chteli.

�

De�nice: Necht n ≥ 0, A je neprazdna mnozina. Zobrazeni f : An → A senazyva (n-arni) operace na mnozine A a cislo n se nazyva arita operace f .Operace arity 0 se nazyva konstanta a je jednoznacne popsana volbou nejakehoa ∈ A.

Mejme zobrazeni σ : I → N0. Dvojice A = (A, {fi}i∈I) se nazyva (uni-verzalni) algebra se signaturou σ ⇔ A je neprazdna mnozina a fi je σ(i)-arnioperace na A pro kazde i ∈ I.

Pokud je jasne o jakou algebru se jedna, oznacuji se algebra i jeji nosic stejne.

Poznamka: Pro mnozinyX,Y se prirozene de�nujeXY := {f | f je zobrazeni Y → X}a tedy A0 := A∅ = {f | f je zobrazeni ∅ → Y } = {∅}, nebot jedine takove zob-razeni je prazdne zobrazeni. Operace arity 0 na algebre A jsou tedy zobrazenif : {∅} → A z jednoprvkove mnoziny a jsou tedy jednoznacne urceny hodnotouf(∅) ∈ A.

De�nice: Necht A je algebra. Podalgebra B algebry A (znac. B ≤ A) je ne-prazdna podmnozina B ⊆ A uzavrena na vsechny operace fi, i ∈ I.

Necht X ⊆ A je podmnozina. Oznacme

〈X〉 :=⋂{B| B je podalgebra A & X ⊆ B}.

7

Rekneme, ze podalgebra C ≤ A je generovana mnozinou X ⊆ C ⇔ C = 〈X〉.Podobne: Necht X ⊆ A×A je podmnozina. Oznacme

〈X〉eq :=⋂{ρ| ρ je ekvivalence na A & X ⊆ ρ}

a〈X〉cong :=

⋂{ρ| ρ je kongruence na A & X ⊆ ρ}.

Rekneme, ze kongruence (prip. ekvivalence) ρ na A je generovana mnozinouX ⊆ ρ ⇔ ρ = 〈X〉cong (prip. ρ = 〈X〉eq).

Tvrzen�� 10. Necht A je algebra.(1) Necht X ⊆ A a 〈X〉 6= ∅. Pak 〈X〉 je podalgebra v A a

〈X〉 = {t(a1, . . . , an)| t(x1, . . . , xn) je term, n ≥ 1, ai ∈ A}

.(2) Necht X ⊆ A×A. Pak 〈X〉eq je ekvivalence na A a plati, ze:

(a, b) ∈ 〈X〉eq ⇔ existuje posloupnost a = a0, . . . , an = b prvku z A takova,

ze pro kazde 0 ≤ i < n je (ai, ai+1) ∈ X ∪XT .

(3) Necht X ⊆ A×A. Pak 〈X〉cong je kongruence na A a plati, ze:

(a, b) ∈ 〈X〉cong ⇔ existuje posloupnost a = a0, . . . , an = b prvku z A takova,

ze pro kazde 0 ≤ i < n ex. term ti(x1, . . . , xki) a {(ci, di)}kij=1 ⊆ X ∪XT , ze

ai = ti(c1, . . . , cki) a ti(d1, . . . , dki

) = ai+1.

De�nice: Algebra (G, ◦), kde ◦ je binarni operace se nazyva grupoid.

Tvrzen�� 11. Necht (G, ◦) je grupoid. Ekvivalence ≡ na G je kongruence na G⇔ (∀ a, b, c ∈ G) a ≡ b⇒ (c ◦ a ≡ c ◦ b & a ◦ c ≡ b ◦ c).

D�ukaz: (⇒) zrejme. (⇐) necht je navic a′ ≡ b′ pak a ◦ a′ ≡ a ◦ b′ a a ◦ b′ ≡ b ◦ b′

8

a z tranzitivity to mame. �

P�r. Necht G = ({a, b, c, d, e}, ◦) je grupoid, kde operace ◦ je dana tabulkou

◦ a b c d ea a e c a ab e d e b bc a e c a cd c b a e ee a e a d b

Najdete vsechny podalgebry a kongruence teto algebry.

�Re�sen��: Kazda podalgebra je tvaru 〈X〉 pro nejakou X ⊆ G (to je snadne).Podalgebry tedy budeme hledat tak, ze zacneme jednogenerovanymi tj. |X| = 1(pripadne s X = ∅) a postupne budeme zvetsovat mnozinu generatoru. Prvkypodalgebry 〈X〉muzeme najit tak, ze zacneme s prvky mnozinyX a aplikovanimoperaci algebry A ziskavame postupne dalsi prvky. Ve chvili, kdy uz zadnou ope-raci algebry A nedostaneme nic noveho (tj. kdyz uz je zkonstruovana mnozinauzavrena na operace algebry A), mame celou 〈X〉.

Pri hledani podalgeber s vetsim poctem generatoru pak vyuzijeme to, ze uzmame nalezene algebry s mensim poctem generatoru a to zrejme takto: X ⊆ Y⇒ 〈X〉 ⊆ 〈Y 〉.

Vysledne podalgebry zakreslime (zde i spolecne s prazdnou mnozinou) takto:r{a, b, c, d, e}r{a, c}�

��

AA

AA

AA

@@

@ r{b, d, e}r{a} r{c}@

@@

���r∅

Podobne: kazda kongruence je tvaru 〈X〉cong pro nejakou X ⊆ G×G (opetsnadne). Kongruence tedy budeme hledat tak, ze zacneme jednogenerovanymitj. |X| = 1, (zrejme je 〈∅〉cong = idG), a postupne budeme zvetsovat mnozinugeneratoru.

Protoze kongruence je ekvivalence bude vyhodnejsi misto vypisovani jednot-livych dvojic prvku radeji vypsat rozkladove tridy. Budeme postupovat takto:Kazdy graf � = (G,V ) (kde G je mnozina vrcholu a V ⊆ {{a, b}| a, b ∈ G, a 6= b}mnozina hran) jednoznacne urcuje diky komponentam souvislosti nejakou ekvi-valenci na G. Rozkladove tridy kongruence 〈X〉cong muzeme tedy najit tak, zezacneme s grafem �′ = (G, ∅) a aplikovanim implikace (⇒) z prave casti tvr-zeni 11 ziskavame postupne dalsi dvojice (a′, b′), ktere budeme zakreslovat jakohrany mezi body a′ a b′. Pritom nemusime nutne kreslit vsechny dvojice, ktere

9

takto ziskame, ale jen takove, ktere nejdou odvodit z komponent souvislostiuz nakresleneho grafu. Ve chvili, kdy uz nedostaneme nic noveho (tj. kdyz jesplnena prava strana tvrzeni 11), mame celou 〈X〉cong.

Pri hledani kongruenci s vetsim poctem generatoru pak zase vyuzijeme to,ze uz mame nalezene kongruence s mensim poctem generatoru a to opet zrejmetakto: X ⊆ Y ⇒ 〈X〉cong ⊆ 〈Y 〉cong.

Vysledne kongruence zakreslime takto:

rG×GrρridG

kde ρ ma rozkladove tridy {a, c}, {b}, {d}, {e}. �

23.10.2007

Tvrzen�� 12. Necht f, g : A→ B jsou homomor�smy algeber a X ⊆ A podmno-zina takova, ze f |X = g|X a A = 〈X〉. Pak f = g.

P�r. Najdete vsechny endomor�smy algebry (N,+) (tj. vsechny homomor�smyf : (N,+)→ (N,+)).

�Re�sen��: Protoze N = 〈1〉, tak staci prozkoumat obrazy prvku 1. Ukazeme, zevsechny homomor�smy jsou prave tvaru f(n) = a · n, pro nejake a ∈ N.

Necht f je homor�smus. Polozme a := f(1). Pak je f(n) = f(1 + · · ·+ 1) =f(1) + · · · + f(1) = n.f(1) = a.n. A naopak zobrazeni de�novane uvedenympredpisem zrejme je endomor�smus algebry (N,+). �

P�r. Najdete vsechny endomor�smy algebry (N,+, ·).

�Re�sen��: Kazdy endomor�smus f algebry (N,+, ·) je take endomor�smem algebry(N,+). Podle predchoziho prikladu ma f tvar f(n) = a.n pro nejake a ∈ N.Protoze f je homomor�smus vzhledem k " · ", tak musi platit, ze a = f(1) =f(1 · 1) = f(1) · f(1) = a · a a tudiz a = 1. Tedy jedinym endomor�smem jeidentita. �

De�nice: Algebry A a B (stejne signatury σ) jsou izomorfni ⇔ existuje ho-momor�smus f : A → B techto algeber, ktery je soucasne bijekci mezi A a B.

10

Chceme-li dokazat, ze dane dve algebry nejsou izomorfni, obvykle se hledatzv. invariant, tj. vlastnost V takova, ze kdykoliv jsou nejake algebry A,B izo-morfni a A ma vlastnost V , pak B ma vlastnost V .

Touto vlastnosti je napr.- pocet prvku algebry,- splneni nejakych rovnosti (napr. asociativita, komutativita atd.),- existence vyznacnych prvku (napr. neutralni prvek, invertibilni prvky, ani-

hilujici prvek, idempotentni prvky atd.),- rady prvku (! pouze u grup !),- minimalni pocet generatoru,- resitelnost nejakych rovnic (prip. pocet techto reseni),- atd..

De�nice: Necht (G, ·) je grupoid. Prvek e ∈ G se nazyva neutralni ⇔ (∀ a ∈G) ae = ea = a.

Prvek o ∈ G se nazyva anihilujici ⇔ (∀ a ∈ G) ao = oa = o.Prvek f ∈ G se nazyva idempotentni ⇔ f2 = f .Necht e je neutralni prvek v G. Prvek a se nazyva invertibilni ⇔ (∃ b ∈

G) ab = ba = e. Prvek b se pak nazyva inverznim prvkem k prvku a.

P�r. Rozhodnete, zda jsou grupoidy (N, ·) a (Z,+) izomorfni.

�Re�sen��: Grupoidy nejsou izomorfni. Napr. z techto duvodu:(1) V (Z,+) existuje ke kazdemu prvku inverzni prvek, zatimco v (N, ·) ma

inverzni prvek pouze 1.(2) Zrejme Z = 〈−1, 1〉, zatimco (N, ·) neni konecne generovana algebra.

Pro prvky a1, . . . , an ∈ N a prvocislo p, ktere neni v rozkladu zadneho z ai,totiz zrejme plati, ze p 6∈ {ak1

1 . . . aknn | ki ∈ N0, (k1, . . . , kn) 6= (0, . . . , 0)} =

〈a1, . . . , an〉.

�

P�r. Rozhodnete, zda jsou grupoidy (R,+) a (R+, ·) izomorfni.

�Re�sen��: Grupoidy jsou izomorfni. Zobrazeni ϕ : (R,+) → (R+, ·) , ϕ(x) := ex

je izomor�smus. �

P�r. Rozhodnete, zda jsou grupoidy (Q,+) a (Q+, ·) izomorfni.

�Re�sen��: Grupoidy (zde se jedna dokonce o grupy) nejsou izomorfni. Uvazujmenasledujici rovnice (pro neznamou x) v grupoidu (G, ◦): x ◦ · · · ◦ x︸ ︷︷ ︸

n−krat

= a, kde

n ∈ N , a ∈ G.

11

V grupoidu (Q,+) maji tyto rovnice reseni pro kazde n ∈ N a kazde a ∈ Q.Zatimco v (Q+, ·) napr. rovnice x · x = 2 nema reseni (nebot

√2 6∈ Q). �

De�nice: Necht (G, ·) je grupa s neutralnim prvkem e. Prvek a ∈ G ma konecnyrad n ∈ N (znac. |x| = n) ⇔ xn = e a n je nejmensi takove.

V opacnem pripade rikame, ze x ma nekonecny rad (znac. |x| =∞).

De�nice: Necht {(Aα, {fαi }i∈I)}α∈K je mnozina algeber stejne signatury σ.

Soucinem techto algeber (znac.∏

α∈K

Aα) nazveme algebru se signaturou σ, je-

jimz nosicem je kartezsky soucin∏

α∈K

Aα a operace {fi}i∈I jsou de�novany po

slozkach, tj.

πα

(fi(x1, . . . , xσ(i))

)= fα

i

(πα(x1), . . . , πα(xσ(i))

)kde x1, . . . , xσ(i) ∈

∏α∈K

Aα a πα je prirozena projekce na α-slozku pro kazde

α ∈ K.

P�r. Rozhodnete, zda jsou grupy (Z2 × Z2,+) a (Z4,+) izomorfni.

�Re�sen��: Grupy nejsou izomorfni. Vsechny prvky ze Z2 ×Z2 maji rad nejvyse 2,nebot 2× (x, y) = (2× x, 2× y) = (0, 0), zatimco rad prvku [1] v Z4 je 4. �

30.10.2007

De�nice: Necht (G, ·) je grupa a N podgrupa v G. Rekneme, ze N je normalnipodgrupa v G (znac. N E G) ⇔ (∀ h ∈ N)(∀ g ∈ G) ghg−1 ∈ N .

Poznamka: Pro grupu G a g ∈ G je zobrazeni ϕg : G→ G, ϕg(x) = gxg−1

automor�smus grupy G. Je to tzv. vnitrni automor�smus. Podgrupa N ≤ G jetedy normalni prave kdyz je uzavrena na vsechny vnitrni automor�smy grupyG (tj. ϕg(N) ⊆ N pro vsechna g ∈ G).

Tvrzen�� 13.Necht (G, ·) je grupa. Oznacme Cong(G) := {ρ| ρ je kongruence v grupe G},Norm(G) := {N | N je normalni podgrupa v G}. Zobrazeni � a

Cong(G)�−→ Norm(G)

Cong(G)←− Norm(G)

de�novana jako�(ρ) := [1]ρ

12

(tj. trida kongruence ρ obsahujici jednotku) a

(x, y) ∈ (N) ⇔ xy−1 ∈ N

jsou navzajem inverzni (dobre de�novana) zobrazeni.

Kongruence v grupe tedy jednoznacne odpovidaji jejim normalnim podgru-pam.

P�r. Necht (Sn, · ) je grupa vsech permutaci n-prvkove mnoziny a " ·" je skladanipermutaci.

Ukazte, ze An := {σ ∈ Sn| sgn(σ) = 1} je normalni podgrupa v Sn.

�Re�sen��: Necht {−1, 1} ⊆ Z je grupa s operaci nasobeni. Vyuzijeme toho, zezobrazeni znamenko permutace sgn : Sn → {−1, 1} je homomor�smus grup(viz Linearni algebra). Tedy, ze plati: sgn(στ) = sgn(σ)sgn(τ) pro vsechnaσ, τ ∈ Sn.An je podgrupa v Sn (tj. je uzavrena na operace · , −1 a obsahuje identickoupermutaci):

- podle de�nice znamenka (napr. podle poctu inverzi v permutaci) je sgn(id) =1.

- protoze 1 = sgn(id) = sgn(σσ−1) = sgn(σ)sgn(σ−1) tak mame, ze sgn(σ) =sgn(σ−1), a tedy pro σ ∈ An je σ−1 ∈ An.

- a konecne pro σ, τ ∈ An je sgn(στ) = sgn(σ)sgn(τ) = 1 · 1 = 1.An je normalni podgrupa v Sn: necht σ ∈ An, π ∈ Sn, pak sgn(πσπ−1) =sgn(π)sgn(σ)sgn(π−1) = sgn(π) · 1 · sgn(π−1) = sgn(ππ−1) = sgn(id) = 1. �

Tvrzen�� 14. Necht ϕ : G → ~G je homomor�smus grup a ~e neutralni prvek v~G. Pak mnozina ker ϕ := {x ∈ G| ϕ(x) = ~e} je normalni podgrupa v G.

P�r. Necht Gl(n, F ) := {A ∈ Fn×n| A je regularni matice} je grupa regularnichmatic n× n nad telesem F s operaci nasobeni matic.

Ukazte, ze Sl(n, F ) := {A ∈ Fn×n| detA = 1} je normalni podgrupa vGl(n, F ).

�Re�sen��: Pouzijeme predchozi tvrzeni. Mnozina F \ {0} spolu s operaci nasobenitvori grupu. Zobrazeni determinant matice

det : Gl(n, F )→ F \ {0}

je homomor�smus grup (viz Linearni algebra). Tedy ker det = An je normalnipodgrupa v Sn. �

De�nice: Necht G je grupa a N normalni podgrupa v G. Grupu vznikloufaktorizaci G podle kongruence (N) indukovane normalni podgrupou N (tj.(x, y) ∈ (N) ⇔ xy−1 ∈ N) oznacujeme jako G/N .

13

Tvrzen�� 15. Necht ϕ : G→ ~G je epimor�smus grup (tj. homorf., ktery je na).Pak G/kerϕ ∼= ~G (tj. jsou to izomorfni grupy).

P�r. Ukazte, ze:(1) Sn/An

∼= (Z2,+) pro n ≥ 2,(2) Gl(n, F )/Sl(n, F ) ∼= (F \ {0}, · ).

�Re�sen��: Pouzijeme predchozi tvrzeni a predchozi priklady.(1) Zobrazeni sgn : Sn → {−1, 1} je epimor�smus grup nebot napr. pro

transpozici (12) ∈ Sn je sgn(12) = −1. Protoze grupa ({−1, 1}, · ) je izomorfnise (Z2,+), tak to mame.

(2) Staci ukazat, ze zobrazeni det : Gl(n, F ) → F \ {0} je na. Zrejme alenapr. pro diagonalni matici A, ktera ma na diagonale prvek 0 6= a ∈ F a vezbytku jednicky, je detA = a. �

Kazdou permutaci z Sn lze jednoznacne (az na poradi) zapsat jako soucinnavzajem nezavislych cyklu (viz Linearni algebra).

Tvrzen�� 16. Necht (a1 . . . ak) ∈ Sn je cyklus delky k a π ∈ Sn.Pak π(a1 . . . ak)π

−1 = (π(a1) . . . π(ak)) (tj. je to opet cyklus delky n).

D�ukaz: Ukazeme, ze obe strany se jako zobrazeni rovnaji. Oznacme S := {π(a1), . . . , π(ak)}.Pak je

(π(a1 . . . ak)π

−1)(x) = π(ai+1) , x = π(ai) & 1 ≤ i < k

a1 , x = π(ak)x , x /∈ S

a (π(a1) . . . π(ak)

)(x) =

π(ai+1) , x = π(ai) & 1 ≤ i < ka1 , x = π(ak)x , x /∈ S.

�

P�r. Ukazte, ze mnozina K4 := {id, (12)(34), (13)(24), (14)(23)} ⊆ S4 je nor-malni podgrupa v S4 (je to tzv. Kleinova grupa).

�Re�sen��: Prvky K4 jsou tedy prave vsechny permutace z S4, ktere jsou budrovny identite nebo maji v rozkladu na nezavisle cykly prave dve (nezavisle)transpozice (neboli cykly delky 2).

Necht je π ∈ S4 a (ab)(cd) ∈ K4 je soucin dvou nezavislych cyklu. Pak svyuzitim predchoziho tvrzeni je

π(a, b)(c, d)π−1 = π(ab)π−1π(cd)π−1 =(π(a), π(b)

)(π(c), π(d)

)∈ K4

14

a zrejme π id π−1 = id ∈ K4.Dale uz je jen potreba overit, ze K4 je podgrupa. �

Tvrzen�� 17.Necht (Q, · , −1, 1) je algebra s nosnou mnozinouQ = {±1,±i,±j,±k}(s 8 prvky) s operacemi de�novanymi:

· 1 −1 i −i j −j k −k1 1 −1 i −i j −j k −k−1 −1 1 −i i −j j −k ki i −i −1 1 k −k −j j−i −i i 1 −1 −k k j −jj j −j −i i −1 1 i −i−j −j j i −i 1 −1 −i ik k −k j −j −i i −1 1−k −k k −j j i −i 1 −1

a

x−1 =

{(−1) · x , x 6= −1, 1x , x = −1, 1.

Pak (Q, · , −1, 1) je grupa (tzv. grupa kvaternionu) a je izomorfni s pod-

grupou v Gl(2,C) generovanou maticemi

(i 00 −i

)a

(0 −11 0

).

P�r. Najdete vsechny podgrupy grupy kvaternionu Q.

�Re�sen��: Budeme postupovat stejne jako pri hledani podalgeber v algebre s ope-racemi · , −1 a 1. Vysledne podgrupy opet zakreslime do diagramu:rQ

r〈i〉 r〈j〉 r〈k〉���

@@

@

@@

@

���r{−1, 1}

r{1}kde 〈i〉 = {1,−1, i,−i},〈j〉 = {1,−1, j,−j},〈k〉 = {1,−1, k,−k}.

�

6.11.2007

15

Tvrzen�� 18. Necht (G, ·, −1, 1) je grupa a X ⊆ G. Pak

〈X〉 = {ak1i1. . . akn

in| n ∈ N, kj ∈ Z, aij ∈ X}

kde pro a ∈ G a k ∈ Z jeak := a . . . a︸ ︷︷ ︸

k−krat

, pro k > 0

a0 := 1ak := a−1 . . . a−1︸ ︷︷ ︸

(−k)−krat

, pro k < 0.

P�r. Ukazte, ze grupa Sn je pro n ≥ 2 generovana prvky (12) a (1 . . . n) a najdeteminimalni pocet generatoru Sn.

�Re�sen��: n = 1: S1 = {id} = 〈∅〉, tj. 0 generatoru,n = 2: S2 = {id, (12)} = 〈(12)〉, takze 1 generator (mene jich byt nemuze,

protoze grupa neni trivialni - tj. S2 6= 1),n ≥ 3: Pokud by Sn mela jeden generator, pak by Sn = 〈a〉 = {ak| k ∈ Z} a

tedy by byla komutativni, coz neni (napr. (12)(13) = (132) 6= (123) = (13)(12)).Staci tedy ukazat, ze prvky uvedene vyse generuji Sn.

Z Linearni algebry vime, ze kazda permutace se da vyjadrit jako soucin

transpozic a tedy Sn =⟨{(ij)| 1 ≤ i < j ≤ n}

⟩, kde (ij), i 6= j je transpozice

(neboli 2-cyklus) tj. zobrazeni ϕ de�novane takto

ϕ(x) =

i , x = jj , x = ix , x 6= i, j.

Pouzitim jednoho z predchozich tvrzeni mame

(1 . . . n)(12)(1 . . . n)−1 = (23)

(1 . . . n)(23)(1 . . . n)−1 = (34)

...

(1 . . . n)(n− 2, n− 1)(1 . . . n)−1 = (n− 1, n)

tj. pomoci (12) a (1 . . . n) jsme ziskali transpozice (12), . . . , (n−1, n) a pomocinich podobne ziskame ostatni: necht i < j pak

(i+ 1, i+ 2)(i, i+ 1)(i+ 1, i+ 2)−1 = (i, i+ 2)

(i+ 2, i+ 3)(i, i+ 2)(i+ 2, i+ 3)−1 = (i, i+ 3)

...

16

(j − 1, j)(i, j − 1)(j − 1, j)−1 = (i, j)

.Tedy Sn =

⟨{(ij)| 1 ≤ i < j ≤ n}

⟩⊆

⟨(1, 2), (1 . . . n)

⟩⊆ Sn. �

De�nice: Necht A 6= ∅ je mnozina. System S ⊆ P(A) se nazyva uzaverovysystem nad mnozinou A ⇔

(1) A ∈ S,(2) S ′ ⊆ S ⇒ ∩S ′ ∈ SNecht X ⊆ A. Pak pro uzaverovy sytem S nad A de�nujeme uzaver mnoziny

X v S nad A jako clS(X) :=⋂

X⊆B∈SB.

P�r. Overte, ze S = {∅, {a}, {c}, {a, b}, {c, d}, {a, b, c}, {a, b, c, d}} je uzaverovysystem nad A = {a, b, c, d}. Najdete uzavery clS(X) pro

(1) X = {a, b, c},(2) X = {b},(3) X = {b, d}.

�Re�sen��: Protoze S je konecna mnozina staci overit, ze pro B,B′ ∈ S je B∩B′ ∈S. Pro uzavery pak pouzijeme, ze pokud X ⊆ B ∈ S pak clS(X) ⊆ B. (Tj.je potreba najit mnozinu B′ ∈ S takovou, ze zadna B′′ ∈ S mensi nez B′ uzneobsahuje X a pak bude B′ uzaver X.) �

De�nice: Necht A 6= ∅ je mnozina. System τ ⊆ P(A) takovy, ze(1) ∅, A ∈ τ ,(2) S ′ ⊆ τ ⇒ ∩S ′ ∈ τ ,(3) B,B′ ∈ τ ⇒ B ∪B′ ∈ τ

se nazyva kotopologie na mnozine A.

Poznamka: Prikladem kotopologie je system uzavrenych mnozin na realneprimce.

(Presneji: C ⊆ R je otevrena ⇔ (∀ x ∈ C)(∃ otevreny interval I) x ∈ I ⊆ C.B ⊆ R je uzavrena ⇔ R \B je otevrena.)

System z predchoziho prikladu je prikladem uzaveroveho systemu, ktery nenikotopologii.

Kotopologie je pojem "analyticky", zatimco uzaverovy system je pojem spise"algebraicky", jak bude videt z nasledujiciho prikladu.

P�r. Necht G je grupa a A,B ≤ G podgrupy. Pak A ∪B je podgrupa ⇔ A ⊆ Bnebo B ⊆ A.�Re�sen��: (⇐) zrejme. (⇒) predpokladejme, ze A 6⊆ B a B 6⊆ A a A∪B je grupa.Pak existuji x ∈ A \ B a y ∈ B \ A. Protoze A ∪ B je grupa, je xy ∈ A ∪ B.Bud je tedy xy ∈ A a pak y = x−1(xy) ∈ A (coz je spor) nebo je xy ∈ B a pak

17

x = (xy)y−1 ∈ B (coz je opet spor). �

Tvrzen�� 19. Necht ρ je kongruence na grupe (Z,+,−, 0). Pak ex. a ∈ Z, ze(x, y) ∈ ρ ⇔ a|(x− y).

De�nice: Prvek d ∈ Z je nejvetsi spolecny delitel a1, . . . , an ∈ Z (znacenigcd(a1, . . . , an)) ⇔

(1) d|ai pro vsechna i, (tj. je to spolecny delitel)(2) pro kazde c ∈ Z plati: (c|ai pro vsechna i)⇒ c|d. (tj. je nejvetsi takovy)

Tvrzen�� 20. (1) Necht p1, . . . , pk jsou navzajem ruzna prvocisla a ai =n∏

j=1p

mi,j

i

je soubor cisel pro 1 ≤ i ≤ n, kde 0 ≤ mi,j ∈ Z. Pak d :=n∏

j=1p

mj

i , kde

mj = mini{mi,j} je nejvetsi spolecny delitel cisel a1, . . . , an.

(2) Necht X = {(xi, yi)}ni=1 ⊆ Z × Z. Pak nejmensi kongruence ρ na grupe(Z,+,−, 0) generovana mnozinou X (tj. ρ = 〈X〉cong) je tvaru: (x, y) ∈ ρ ⇔d|(x− y), kde d je nejvetsi spolecny delitel cisel x1 − y1, . . . , xn − yn.

D�ukaz: (1) Kazde cislo v Z ma jednoznacny rozklad na prvocisla a prvek −1.Pokud tedy c =

n∏j=1

plji deli vsechna ai musi byt lj ≤ mi,j pro vsechna i a j.

Takze to mame.(2) Oznacme ρd tuto kongruenci: (x, y) ∈ ρd ⇔ d|(x− y).ρ ⊆ ρd: Mame, ze xi − yi = d · ai pro vsechna i a tedy z 0 ≡ρd

d plyne0 ≡ρd

ai × d = xi − yi a prictenim yi dostaneme xi ≡ρdyi pro vsechna i. Tedy

X ⊆ ρd a tudiz ρ = 〈X〉cong ⊆ ρd.

ρd ⊆ ρ: Neni tezke ukazat, ze opet existuji bi ∈ Z, ze d =n∑

i=1bi(xi−yi). Tedy

z xi ≡ρ yi odectenim yi dostaneme 0 ≡ρ xi−yi a odsud 0 ≡ρ

∑i bi×(xi−yi) = d.

Jestlize je nyni (x, y) ∈ ρd pak x − y = d · a a tedy 0 ≡ρ a × d = x − y a dalex ≡ρ y. Takze ρd ⊆ ρ. �

P�r. Najdete nejmensi kongruenci na grupe (Z,+,−, 0) generovanou mnozinou{(−1, 11), (5, 23), (−12, 18)}.

13.11.2007

P�r. Najdete nejmensi kongruenci na grupe (Z,+,−, 0) generovanou mnozinou

18

X = {(−145, 1472), (12, 1090), (−265,−4038)}.

Tvrzen�� 21. Necht ≡ je kongruence na (N,+). Pak existuji k ≥ 1 a n ≥ 0takova, ze a ≡ b ⇔ (a, b < k & a = b) nebo (a, b ≥ k & n|(b− a)).

Kongruence ≡ je pak zrejme generovana dvojici (k, k + n).

D�ukaz: Necht x ≡ y pro nejake x 6= y (jinak je ≡ rovno identite na N a stacizvolit k = 1, n = 0). Polozme k := min{a ∈ N| (∃ b ∈ N) a 6= b & a ≡ b} an := min{b ∈ N| k ≡ k + b}. Oznacme ρ relaci de�novanou takto:

(a, b) ∈ ρ ⇔ (a, b < k & a = b) nebo (a, b ≥ k & n|(b− a)).

Zrejme ρ je kongruence na (N,+) a ρ = 〈(k, k + n)〉cong a tedy ρ ⊆≡ (nebotk ≡ k + n). Pro spor nyni predpokladejme, ze ρ 6=≡.

Polozme k′ := min{a ∈ N| (∃ b ∈ N) a ≡ b & (a, b) 6∈ ρ} a l′ := min{b ∈N| k ≡ b & (k, b) 6∈ ρ}. Zrejme je k ≤ k′ < l′.

Necht x ≥ k, pak x − k = qn + r pro nejake q ≥ 0 a 0 ≤ r < n. Polozmex := k+ r. Podle de�nice ρ je tedy (x, x) ∈ ρ. Takze pro kazde x ≥ k ex. nejakek ≤ x < k + n, ze (x, x) ∈ ρ.

Musi tedy byt k ≤ k′ < l′ < k + n. Polozme ted m := k + n − l′ ∈ N. Pakz k′ ≡ l′ plyne k′ +m ≡ l′ +m = k + n. Soucasne je take k + n ≡ k a tedy ztranzitivity je k ≡ k′ +m, kde k < k′ +m < k+ n, coz je spor s volbou cisla n.

�

Tvrzen�� 22. Necht X = {(xi, yi)}ni=1 ⊆ N × N, xi < yi pro vsechna i. Paknejmensi kongruence ρ na algebre (N,+) generovana mnozinou X (tj. ρ =〈X〉cong) je tvaru: (a, b) ∈ ρ ⇔ (a, b < k & a = b) nebo (a, b ≥ k & n|(b − a)),kde k = min

i{xi} a n je nejvetsi spolecny delitel cisel y1 − x1, . . . , yn − xn.

D�ukaz: Oznacme σ kongruenci takovou, ze (a, b) ∈ σ ⇔ (a, b < k & a = b) nebo(a, b ≥ k & n|(b− a)).

ρ = 〈(xi, yi)| i = 1, . . . , n〉cong ⊆ σ: Zrejme je k ≤ xi, yi a n|(yi − xi) provsechna i a tedy (xi, yi) ∈ σ.

σ = 〈(k, k + n)〉cong ⊆ ρ: Podle predchozi vety ex. ~k ≥ 1 a ~n ≥ 1, ze (a, b) ∈ ρ⇔ (a, b < ~k & a = b) nebo (a, b ≥ ~k & ~n|(b − a)). Z de�nice k je tedy ~k ≤ ka k tomu, aby (k, k + n) ∈ ρ staci ukazat, ze ~n deli (k + n) − k = n. Protoze(xi, yi) ∈ ρ, xi < yi, musi ~n delit yi − xi a protoze n je nejvetsi spol. deliteltechto cisel, ~n deli n. �

P�r. Najdete nejmensi kongruenci v algebre (N,+) generovanou mnozinouX = {(71, 3104), (120, 183), (71, 386), (20, 4007)}.

19

De�nice: Grupoid (P, ·), kde · je asociativni operace se nazyva pologrupa.

Tvrzen�� 23. (1) Necht ≡ je kongruence na (N,+) generovana dvojici (k, k+n),k, n ≥ 1. Polozme P := N/ ≡ (tj. faktor (N,+) podle ≡).

Pak (P,+) je pologrupa s k + n− 1 prvky a ex. prvek x ∈ P , ze x+ x = x,specialne [kn] (rozkl. trida podle ≡) je takovy prvek.

(2) Necht (S, ∗) je konecna pologrupa. Pak ex. prvek x ∈ S, ze x ∗ x = x(tzv. idempotentni prvek).

D�ukaz: (1) (N,+) je pologrupa a (P,+) je jeji homomorfni obraz, tedy takepologrupa. Snadno se ukaze, ze prvky [1], . . . , [k + n − 1] jsou navzajem ruznea ze je to cele P . Zbyva jen ukazat, ze kn + kn ≡ kn, coz ale plyne z toho, zea ≡ b ⇔ (a, b < k & a = b) nebo (a, b ≥ k & n|(b− a)).

(2) Bud (S, ∗) konecna pologrupa a necht a ∈ S. Polozme A := 〈a〉 ={ak| k ∈ N}. Uvazujme zobrazeni ϕ : (N,+) → (A, ∗), ϕ(k) = ak. Zrejme ϕ jehomomor�smus a je na. Z vety o izomor�smu mame, ze A ∼= N/ker(ϕ). ProtozeA je konecna, tak podle bodu (1) ex. x ∈ N/ker(ϕ), ze x + x = x a tedy ipologrupe A ⊆ S ex. prvek b, ze b ∗ b = b. �

P�r. V pologrupe (N,+)/ ≡, kde ≡ je kongruence z predchoziho prikladu najdeteidempotentni prvek.

Poznamka: Necht (P, ·) je pologrupa a a ∈ P je jeji generator. Na prvcichP pak muzeme zavest relaci E := {(x, y) ∈ P × P | y = ax}, ktera predstavujemnozinu hran orientovaneho grafu s mnozinou vrcholu P .

Bud jeste ϕ : (N,+) → (P, ·), ϕ(i) = ai epimor�smus pologrup a (k, k + n)dvojice generujici kongruenci ker(ϕ). Vysledny graf pak bude vypadadat takto:

k ≥ 1, n = 0: ra ra2 ra3 . . . ram. . .

k > 1, n > 1: ra ra2 ra3 . . . rak = an+k��

rak+1. . .

@@ran+k−1

k > 1, n = 1: ra ra2 ra3 . . . rak = ak+1

20

k = 1, n > 1: ra = an+1��ra2 . . .

@@ran

k = 1, n = 1: ra = a2

Je dobre si rozmyslet, ze graf nezavisi na vyberu generatoru a ∈ P .

P�r. Najdete 3 neizomorfni (komutativni) grupy, ktere maji 27 = 33 prvku.

D�ukaz: Uvazujme grupy (Z27,+), (Z3 × Z3 × Z3,+) a (Z9 × Z3,+). Ze jsouneizomorfni muzeme zduvodnit napr. takto:

- v Z27 ex. prvek radu 27 a sice [1]27 (dolni index znamena kongruenci modulo27) neboli je to cyklicka (tj. jednogenerovana) grupa,

- v Z9×Z3 maji vsechny prvky rad nejvyse 9 (nebot 9×(a, b) = (9×a, 9×b) =([0]9, [0]3)) a ex. tu prvek radu 9 a sice ([1]9, [0]3),

- v Z3 × Z3 × Z3 maji vsechny prvky rad nejvyse 3 (nebot 3 × (a, b, c) =(3× a, 3× b, 3× c) = ([0]3, [0]3, [0]3)).

Neizomorfnost muzeme take zduvodnit pomoci nejmensiho poctu genera-toru:

- Z9 je cyklicka tj. ma 1 generator a mene jich byt nemuze, nebot grupa nenitrivialni,

- Z3 × Z3 × Z3 ma 3 generatory (napr. (1, 0, 0), (0, 1, 0), (0, 0, 1) (tady uzkongruence nepisu) a protoze tuto grupu muzeme chapat jako vekt. prostor nadZ3, je nejmensi pocet generatoru roven dimenzi, coz je zrejme 3,

- Z9 × Z3 ma generatory (1, 0), (0, 1) a nemuze byt cyklicka (tj. nema jedengenerator) jak uz jsme ukazali vyse pomoci radu prvku. �

P�r. Uvazujme algebry (An,+), kde An := {k ∈ N| k ≥ n} a + je scitani naprir. cislech, n ≥ 1. Ukazte, ze An 6∼= Am pro n 6= m.

D�ukaz: Polozme An + An := {a + b| a, b ∈ An}. Zrejme je {n, . . . , 2n − 1} ∩(An +An) = ∅. Necht nyni X generuje An, pak musi nutne obsahovat mnozinu{n, . . . , 2n−1}. Navic zrejme {n, . . . , 2n−1} generuje An. Tedy nejmensi pocetgeneratoru An je n. Proto algebry nejsou izomorfni. �

20.11.2007

De�nice: Prvek c ∈ L je in�mem mnoziny X ⊆ L v L (znaceni c = infLX,pripadne jen infX pokud bude mnozina L zrejma) ⇔ c je nejvetsi dolni zavoraX v L tj.

21

(1) (∀ x ∈ X) c ≤ x , (tj. je to dolni zavora X)(2) (∀ d ∈ L)(d je dolni zavora X ⇒ c ≤ d). (tj. je nejmensi takova)

(Analogicky se de�nuje supremum X v L.)Usporadana mnozina (L,≤) se nazyva svaz ⇔ pro kazde a, b ∈ L existuje

infL{a, b} a supL{a, b}.

Napr. kazda linearne usporadana mnozina (tj. kazde dva prvky jsou porov-natelne) je svaz.

De�nice: Algebra (L,∧,∨) se dvema binarnimi operacemi se nazyva svaz ⇔(1) (∀ a ∈ L) a ∧ a = a & a ∨ a = a (idempotence),(2) operace ∧,∨ jsou asociativni a komutativni,(3) (∀ a, b ∈ L) a ∧ (b ∨ a) = a & a ∨ (b ∧ a) = a (absorbce).

Tvrzen�� 24. (1) Necht (L,≤) je svaz, pak (L,∧,∨), kde a∧ b = infL{a, b}, a∨b = supL{a, b}, je svaz.

(2) Necht (L,∧,∨) je svaz, pak (L,≤), kde a ≤ b ⇔ a ∧ b = a, je svaz.Navic aplikaci (1) a (2) dostaneme puvodni usporadani a aplikaci (2) a (1)

dostaneme puvodni operace.

Poznamka: Necht' (L,≤) je svaz. Pak (L∗,≤∗), kde

L∗ = L, a ≤∗ b⇔ a ≥ b

je tzv. dualni (opacny) svaz ke svazu L.V pripade, ze na svaz nahlizime jako na algebraickou strukturu (L,∧,∨),

de�nujeme opa�cn�y svaz jako (L∗,∧∗,∨∗), kde

L∗ := L, a ∧∗ b := a ∨ b, a ∨∗ b := a ∧ b.

Uvedomte si, ze obe de�nice jsou skutecne svazy a ze jsou v souladu.

De�nice: Necht (S,∧,∨) a (L,∧,∨) jsou svazy. Algebra s nosnou mnozinouS × L a operacemi de�novanymi po slozkach tj.

(a, b) ∧ (a′, b′) = (a ∧ a′, b ∧ b′)

(a, b) ∨ (a′, b′) = (a ∨ a′, b ∨ b′)

se nazyva soucin svazu S a L.

P�r. Ukazte, ze soucin svazu je opet svaz a ze odpovidajici usporadani je danopo slozkach, tj. (a, b) ≤ (a′, b′)⇔ (a ≤ a′ & b ≤ b′).

�Re�sen��: 1) Je potreba overit, ze jsou splneny podminky na operace ∧ a ∨, cozje ale ihned zrejme z toho, ze operace jsou de�novany po slozkach a a v kazdeslozce jsou dane rovnice splneny.

22

2) Podle vyse uvedeneho tvrzeni je usporadani nasledujici: (a, b) ≤ (a′, b′)⇔ (a, b) = (a, b) ∧ (a′, b′) = (a ∧ a′, b ∧ b′) ⇔ (a = a ∧ a′ & b = b ∧ b′ )⇔(a ≤ a′ & b ≤ b′). �

De�nice: Necht (L,≤) je usporadana mnozina, a, b ∈ L. Rekneme, ze b pokryvaa (znac. al b) ⇔

(1) a < b,(2) (∀ c ∈ L) a < c ≤ b⇒ c = b.

(Tedy mezi prvky a a b uz zadny dalsi neni.)

Tvrzen�� 25. Necht' S × L je sou�cin svaz�u a (x, y), (x′, y′) ∈ S × L.Pak (x, y) l (x′, y′) ⇔ (x = x′ & y l y′) nebo (xl x′ & y = y′).

Tato veta nam dava navod jak zakreslit soucin svazu S × L Hasseovymdiagramem:

Namalujeme svaz L, ale spise sikmo ke smeru, ve kterem bychom ho zakreslo-vali obvykle. Na opacnou stranu pak "nad kazdym prvkem" svazu L namalujeme(opet sikmo) svaz S. Pak uz jen domalujeme spojovaci carky, tj. posunute kopiesvazu L.

Priklad: Soucinem svazurcrbra ar1r0 je svaz

r(a, 0)��

@@

r(b, 0)r(a, 1) ��

@@

r(c, 0)r(b, 1)r(c, 1)�

��

�@

@

P�r. Uvazujme algebru (P(n),∩,∪), kde P(n) je potencni mnozina n prvkovemnoziny a ∩,∪ jsou obvykla prunik a sjednoceni. Pak P(n) je svaz a plati, zeP(n) ∼= P(1)× · · · × P(1)︸ ︷︷ ︸

n−krat

.

�Re�sen��: Usporadana mnozina (P(n),⊆), kde ⊆ je inkluze mnozin, je zrejmesvaz, kde inf{A,B} = A ∩ B a sup{A,B} = A ∪ B. Tedy podle predchoziho jealgebra (P(n),∩,∪) svaz.

Svaz P(1) je izomorfni s dvouprvkovym svazem L = {0, 1}, kde 0 < 1, aP(n) je potencni mnozina mnoziny {1, . . . , n}. Uvazujme nyni zobrazeni

ϕ : P(n)→ {0, 1} × · · · × {0, 1}︸ ︷︷ ︸n−krat

A 7→ χA

kde χA je charakteristicka funkce mnoziny A, tj.

χA(x) =

{1 , x ∈ A0 , x 6∈ A

23

Snadno se overi, ze ϕ je bijekce a homomor�smus svazu. �

De�nice: Necht (L,∧,∨) je svaz, ∅ 6= K ⊆ L je podsvaz v L ⇔ K je uzavrenana ∧ a ∨ (tj. je to podalgebra v L).

Pokud mame svaz jako usporadanou mnozinu (L,≤), pak ∅ 6= K ⊆ L jepodsvaz v L ⇔ (∀ a, b ∈ K) infL{a, b} ∈ K & supL{a, b} ∈ K.

(tj. kdyz (K,≤) je svaz a kdyz infK{a, b} = infL{a, b} a supK{a, b} =supL{a, b} pro vsechny prvky a, b ∈ K).

Tvrzen�� 26. Necht (L,≤) je usporadana mnozina, I ⊆ L, a, b ∈ I, a < b.Polozme I◦ := I \ {a, b}. Necht je dale splneno:

(i) a je nejmensi prvek a b je nejvetsi prvek v (I,≤),(ii) (∀ x ∈ I◦)(∀ y ∈ L \ I) (x ≤ y ⇒ b ≤ y) & (x ≥ y ⇒ a ≥ y).

Pak (L,≤) je svaz⇔ (I,≤) a (L\I◦,≤) jsou svazy. Navic, pokud je toto splneno,jsou I a L \ I◦ podsvazy v L.(Zde usporadani na podmnozinach je vzdy zuzeni puvodniho usporadani na L).

D�ukaz: (⇒) Ukazeme pouze existenci in�ma v obou mnozinach, supremum sepak udela dualne. Protoze L je svaz, tak pro kazde dva prvky L existuje jejichin�mum v L.

(I,≤) je svaz: Staci ukazat, ze pro x, x′ ∈ I je c := infL{x, x′} ∈ I. Prospor predpokladejme, ze c ∈ L \ I. Nyni mame bud, ze x, x′ 6∈ I◦ a tedy x, x′ ∈I ∩ (L \ I◦) = {a, b}, takze c = infL{x, x′} ∈ {a, b} ⊆ I, coz je spor s tim, zec ∈ L \ I. Anebo alespon jeden z prvku, rekneme x, lezi v I◦. Pak je x > c apodle (ii) musi byt a > c, coz je ale spor (a je vetsi dolni zavora mnoziny {x, x′}v L nez c).

(L\I◦,≤) je svaz: Staci ukazat, ze pro y, y′ ∈ L\I◦ je c := infL{y, y′} ∈ L\I◦.Pro spor predpokladejme, ze c ∈ I◦. Ukazeme, ze pak b bude dolni zavoramnoziny {y, y′} (coz bude spor, nebot c < b):

Bud je y ∈ L \ I a pak podle (ii) z c < y plyne, ze b ≤ y, anebo y ∈ I a pakmusi byt y = b (protoze je y ∈ I ∩ (L \ I◦) = {a, b} a a < c). To same plati proy′ a tudiz b ≤ y, y′.

(⇐) Opet ukazeme existenci in�m v L (suprema se udelaji dualne). Ne-cht z, z′ ∈ L. Pokud prvky jsou porovnatelne, napr. z ≤ z′, pak je zrejmeinfL{z, z′} = z. Staci tedy BUNO uvazovat jen neporovnatelne prvky. Budd ∈ L dolni zavora {z, z′}. Zbytek rozdelime na nasledujici pripady:

(a) a ∈ {z, z′}, napr. z = a: pak musi byt d ∈ L \ I◦ a tedy infL\I◦{z, z′} jetake in�mum v L.

(b) b ∈ {z, z′}, napr. z = b: prvky z, z′ jsou neporovnatelne a tedy musi bytz′ ∈ L \ I (jinak by bylo z′ ≤ b = z) a dale d ∈ L \ I◦ (jinak bychom podle (ii)meli, ze z = b ≤ z′) a tedy infL\I◦{z, z′} je take in�mum v L.

(c) z, z′ ∈ I◦: pokud je d ∈ L \ I, pak podle (ii) musi byt d ≤ b ≤ infI{z, z′}

24

a tedy infI{z, z′} je take in�mum v L.(d) z, z′ ∈ L \ I: pokud je d ∈ I◦, pak podle (ii) musi byt b ≤ z, z′ a tedy

d ≤ b ≤ infL\I◦{z, z′}, takze infL\I◦{z, z′} je take in�mum v L.(e) z ∈ I◦, z′ ∈ L \ I: pak podle (ii) musi byt d ≤ a, takze je d ∈ L \ I◦ a

tudiz d ≤ infL\I◦{a, z′} ≤ z, z′. Tedy infL\I◦{a, z′} je in�mem prvku z, z′ v L.

�Pouziti:

Mejme Hasseuv diagram usporadane mnoziny (L,≤). Zvolime si v nempodmnozinu I ⊆ L tak, aby (I,≤) byl svaz a byly splneny podminky (i) a(ii) z predchozi vety (pricemz podminka (ii) vlastne rika, ze zadny prvek z I◦

nesmi byt v diagramu spojen carkou s zadnym prvkem z L \ I). Mnozina I seobvykle voli linearne usporadana. Podle predchozi vety pak bude (L,≤) svazprave kdyz (L \ I◦,≤) bude svaz.

A jak najdeme Hasseuv diagram pro (L \ I◦,≤)?Z diagramu pro L vymazeme mnozinu I◦ a vsechny carky, ktere z ni vedou.

Body a a b z predchozi vety (tj. nejvetsi a nejmensi prvek I) pak spojime carkouprave kdyz neexistuje c ∈ L \ I, ze a < c < b. (Pokud bychom toto neudelali,mohlo by se stat, ze se nam z diagramu ztrati relace a < b.)

Opakovanym pouzitim tohoto postupu pak L zmensime natolik, ze uz budesnazsi rozhodnout, zda to svaz je nebo neni.

27.11.2007

De�nice: Necht (L,≤) je usporadana mnozina, a, b ∈ L. Nasledujici mnozinyse nazyvaji intervaly :

[a, b] := {x ∈ L| a ≤ x ≤ b}[a,→) := {x ∈ L| a ≤ x}(←, a] := {x ∈ L| x ≤ a}

Tvrzen�� 27. Necht (L,≤) je usporadana mnozina a a ∈ L takove, zeL = (←, a] ∪ [a,→).

Pak (L,≤) je svaz ⇔ ((←, a],≤) a ([a,→),≤) jsou svazy. Navic, pokud jetoto splneno, jsou (←, a] a [a,→) podsvazy v L.

P�r. U nasledujicich obrazku urcete, zda se jedna o svaz:rrr r��

@@

QQQ

���

��

��AA

r rr

r@

@�

�r@

@@@

��

��

rr rr rr��@

@

r@

@�

���r r r�

���rr rHHHH

rr

@@

@@

��

25

�Re�sen��: Prvni je svaz - staci odstranit "prostredni prvek" a zbyde soucin svazu.Druhy neni svaz - napr. neexistuje supremum pro prvky tesne nad nejmensimprvkem (tzv. atomy). Treti je svaz - je to soucin dvou linearnich svazu. �

De�nice: Svaz (L,∧,∨) se nazyva modularni ⇔(∀ a, b, c ∈ L) a ≤ c ⇒ a ∨ (b ∧ c) = (a ∨ b) ∧ c.

Svaz s diagramem r@@ r��rr

HH ��rse nazyva pentagon a znaci se N5.Necht (L,≤) je svaz s nejmensim a nejvetsim prvkem (oznacuji se obvykle

po rade 0 a 1). Posloupnost 0 = a0 ≤ a1 ≤ · · · ≤ an = 1 prvku z L se nazyvakompozicni rada ⇔ ai l ai+1 pro vsechny 0 ≤ i < n.

Tvrzen�� 28. (1) Svaz je modul�arn��⇔ neobsahuje svaz N5 (pentagon) jako svujpodsvaz.

(2) Linearne usporadany svaz je modularni.(3) Soucin svazu S × L je modularni ⇔ oba svazy S a L jsou modularni.(4) Svaz vsech normalnich podgrup grupy G je modularni. Tedy specialne

svaz vsech podgrup komutativni grupy je modularni.(5) Necht L je modularni svaz s nejmensim a nejvetsim prvkem. Pak vsechny

kompozicni rady jsou stejne dlouhe.

Poznamka:

Uvazujme svazy(1)

r1@@��rc rbra rdr0��@@

(2)

r0��@@rdra ��@@

rbrc r1��

�� @@

Polozme P = {0, a, b, c, 1}. Pak (P,≤) je v obou pripadech pentagon. Alezatimco u (1) je to podsvaz, a tedy (1) neni modularni (ackoliv ma vsechnykompozicni rady stejne dlouhe), tak u (2) to neni podsvaz (napr. c∧ b = d 6∈ P )a (2) je modularni, nebot je to soucin linearnich modularnich svazu.

De�nice:

Necht n ∈ N0. Oznacme svaz vsech nezapornych delitelu cisla n usporadanydelitelnosti jako Ln, tedy Ln =

({k ∈ N0| k | n}, |

).

Tvrzen�� 29. (1) Necht A je podgrupa grupy (Z,+). Pak A = k.Z = {kn| m ∈Z}.

26

(2) Necht N je normalni podgrupa grupy G a π : G → G/N , a 7→ [a] jeprirozeny homomor�smus. Pak zobrazeni

[N,G] −→ [1, G/N ]H 7→ π(H)

[1, G/N ] −→ [N,G]K 7→ π−1(K)

jsou navzajem inverzni zobrazeni svazu, kde [N,G] je interval ve svazu vsechpodgrup grupy G a [1, G/N ] je svaz vsech podgrup grupy G/N .

(3) Pro podgrupy k.Z a l.Z grupy (Z,+) plati:

k.Z ⊆ l.Z ⇔ l | k

(4) Svaz vsech podgrup grupy Zn = Z/n.Z usporadany inkluzi je izomorfnise svazem L∗n (tj. svazem opacnym k Ln). Specialne zobrazeni

L∗n → {H| H ≤ Zn}k 7→ k.Zn

je izomor�smus.(5) Necht n ∈ N. Pak jsou svazy Ln a L∗n (tj. svaz opacny k Ln) izomorfni.

Specialne zobrazeniLn → L∗nk 7→ n

k

je izomor�smus.

4.12.2007

P�r. U nasledujicich svazu rozhodnete, zda jsou modularni:r1ra rc rb��

@@

@@

��

@@

��

rd rer0

r@

@�

�r rr@@

@@��

��

rr rr��@

@

r1@

@@@

��ra@

@@@

rb rc�

�rd r0 re�

�

�Re�sen��: (1) Neni modularni - obsahuje pentagon {0, a, d, e, 1} jako svuj podsvaz.(2) Tento svaz je ve skutecnosti "krychle" a tedy soucin tri linearne uspora-

danych svazu a proto je modularni.(3) Ukazeme, ze je modularni: sporem: svaz oznacme jako L a predpokla-

dejme, ze obsahuje nejaky pentagon P . Protoze mezi nejvetsim prvkem P anejmensim prvkem P musi existovat kompozicni rada (viz de�nice vyse) v Pobsahujici 4 prvky, tak P musi obsahovat prvky 0 a 1. Dale zrejme L \ {a}je podsvaz v L, ktery je soucinem dvou linearnich svazu a tedy je modularni.Proto nemuze platit, ze P ⊆ L \ {a} a tedy a ∈ P . Ze stejneho duvodu musi

27

byt b ∈ P . Pentagon ma byt podsvaz a tedy d = a∧ b ∈ P . Tudiz dostavame, zeP = {0, a, b, d, 1} (nebot P ma 5 prvku). Tato mnozina ovsem neni pentagon,coz je spor. �

Tvrzen�� 30. (1) Necht gcd(n,m) = 1. Pak zobrazeni

Lnm → Ln × Lm

k 7→ (gcd(k, n), gcd(k,m))

Ln × Lm → Lnm

(a, b) 7→ a.b

jsou navzajem inverzni homomor�smy svazu.

(2) (Dusledek) Necht n = pk11 . . . p

kj

j , kde pi jsou navzajem ruzna prvocislaa ki ≥ 1 pro vsechna i. Pak

Ln∼= L

pk11

× · · · × Lp

kjj

Pritom Lpk (pro prvocislo p) je linearni svaz tvoreny prvky {1, p, p2, . . . , pk}.

P�r. Nakreslete svaz vsech delitelu cisla 180 (tj. svaz L180).

�Re�sen��: Mame, ze 180 = 22.32.5. Podle predchozi vety staci nakreslit soucin 3linearnich svazu. Pritom jednotlive trojice prvku (a, b, c) v soucinu odpovidajideliteli a.b.c cisla 180. Svaz tedy muzeme nakreslit postupne takto:

L22 : r4�

���

r2r1L22 × L32 :

r4�

���

r2r1

r12�

���

r6r3

r36@

@@@

��

��

r18@

@@@

r9@

@@@

L22 × L32 × L5 :

r20�

���

r10r5

r60�

���

r30r15

r180@

@@@

��

��

r90@

@@@

r45@

@@@

r4�

���

r2r1

r12�

���

r6r3

r36@

@@@

��

��

r18@

@@@

r9@

@@@

�

P�r. Uvazujme svazy

N5 : r1@@ rc��rbra

HH ��r0M3 : r1

@@ rc��ra rb@@ ��r0

F (2) : r1@@ ry��rx

@@ ��r0a zobrazeni ϕ : N5 → F (2) a ψ : M3 → F (2) de�novana v obou pripadech

stejne0 7→ 01 7→ 1a, b 7→ xc 7→ y

28

Zjistete, zda jsou dana zobrazeni homomor�smy svazu.

�Re�sen��: ϕ je homomor�smus: ϕ zrejme zachovava usporadani (tj. u ≤ v ⇒ϕ(u) ≤ ϕ(v)) a tedy plati ϕ(u ∧ v) = ϕ(u) ∧ ϕ(v) a ϕ(u ∨ v) = ϕ(u) ∨ ϕ(v) prou, v ∈ N5 porovnatelne. Zbyva tedy uz jen overit, ze ϕ zachovava operace ∧ a∨ i pro u, v neporovnatelne, coz je ale snadne.

ψ neni homomor�smus: napr. ψ(a ∨ b) = ψ(1) = 1 6= x = ψ(a) ∨ ψ(b). �

Tvrzen�� 31. (1) Necht (L,∧,∨) je svaz a ≡ kongruence na L. Necht [a]≡ znacirozkladovou tridu kong. ≡. Pak

(a) a ≡ a ∧ b ⇔ b ≡ a ∨ b(b) a ≡ b ⇒ [a ∧ b, a ∨ b] ⊆ [a]≡(c) Necht K je podsvaz v L. Pak ≡ |K×K (tj. zuzeni ≡ na K) je kongruence

na K.

(2) Necht (L,∧,∨) je konecny svaz. Pak ekvivalence ≡ na L je kongruence ⇔(i) rozkladove tridy jsou intervaly - oznacme je jako Ii = [ui, vi] kde i =

1, . . . , n(ii) (∀ i, j)(∃ k, l) ui ∧ uj , vi ∧ vj ∈ Ik & ui ∨ uj , vi ∨ vj ∈ Ik.

11.12.2007

P�r. Najdete vsechny kongruence svazu L:r1@@ ry��rx

@@ ��r0�Re�sen��: Budeme postupovat jako pri hledani kongruenci v obecne algebre (tj.zacneme jednim generatorem a postupne budeme pridavat dalsi dvojice, pokudto bude potreba).〈(0, y)〉cong: podle casti (a) predchoziho tvrzeni mame y ≡ 0 = x ∧ y ⇒

x ≡ x ∨ y = 1 a snadno se podle casti (2) predchoziho tvrzeni presvedcime, zerozkladove tridy I1 = {0, y} a I2 = {x, 1} odpovidaji kongruenci a tedy to musibyt prave 〈(0, y)〉cong.〈(1, y)〉cong: protoze uvedeny svaz je zrejme izomorfni svemu opacnemu svazu,

lze tento pripad prevest na predchozi. Tj. rozkladove tridy teto kongruence bu-dou {y, 1} a {0, x}.〈(x, y)〉cong: podle casti (b) predchoziho tvrzeni bude tato kongruence odpo-

vidat L× L.Pridanim jakekoliv dvojice k vyse uvedenym kongruencim ziskame bud puvodni

kongruenci nebo L× L.

29

Jestlize nyni mame nejakou kongruenci ruznou od id|L, pak musi obsahovatnejakou dvojici (a, b), kde a 6= b. Protoze dale zobrazeni L → L, ktere pouzeprohodi x a y, a zobrazeni L→ L, ktere pouze prohodi 0 a 1, jsou izomor�smyL, lze pripad 〈(a, b)〉cong prevest na jeden z predchozich.

Celkem tedy kongruence na L jsou prave tyto (nakreslene opet jako svaz):tL× L@

@@ t〈(1, y)〉cong���

〈(0, y)〉congt@

@@

���tid|L

�

Poznamka: Necht L je svaz a a, b ∈ L jsou neporovnatelne prvky. Pak〈a, b〉 = {a, b, a∧ b, a∨ b} a tento svaz je izomorfni svazu z predchoziho prikladu.Budeme ho oznacovat jako F (2).

P�r. Najdete vsechny kongruence svazu L:r1@@ rc��rbra

HH ��r0�Re�sen��: Pouzijeme predchozi priklad. Necht ≡ je kongruence na L. OznacmeK1 := 〈a, c〉 a K2 := 〈b, c〉. Oba tyto podsvazy jsou zrejme izomorfni s F (2).Uvazujme nyni ≡ |K1

. Podle predchoziho prikladu mohou byt rozkladove tridy≡ |K1

prave tyto:(1) cele K1: pak je ovsem 0 ≡ 1 a tedy podle tvrzeni 31 (b) je ≡ rovna L×L.(2) {0, c} a {a, 1}: pak podle tvrzeni 31 (2) casti (i) musi byt b ≡ a a

snadno se (pomoci tehoz tvrzeni) overi, ze {0, c} a {a, b, 1} tvori rozkladovetridy kongruence. Tedy to musi byt prave rozkladove tridy ≡ (kdyby to bylo necovetsiho dostali bychom pak uz jinou ≡ |K1

). Zrejme je tedy ≡ rovna 〈(0, c)〉cong

(nebot dvojice (0, c) generuje ≡ |K1).

(3) {0, a} a {c, 1}: staci uvazit jeste ≡ |K2- zde pak musi byt rozkladove

tridy {0, b} a {c, 1}. Ze stejnych duvodu jako v predchozim pripade jsou opetrozkl. tridy ≡ prave {0, a, b} a {c, 1} a ≡ je rovna 〈(c, 1)〉cong.

(4) rozkladove tridy ≡ |K1jsou jednobodove: pak musi byt i rozkladove tridy

≡ |K2jednobodove (to je snadne). Jedina dalsi dvojice, kterou by ≡ mohla

jeste obsahovat je tedy pouze (a, b). A skutecne - ekvivalence urcena tridami{a, b}, {0}, {c} a {1} je podle tvrzeni 31 (2) kongruence. V tomto pripade takdostavame, ze ≡ je budto id|L anebo je to 〈(a, b)〉cong.

Celkem tedy kongruence na L jsou prave tyto (nakreslene opet jako svaz):tL× L@

@@ t〈(0, c)〉cong���

〈(c, 1)〉congt@

@@

���t〈(a, b)〉congtid|L

�

30

P�r. Uvazujme svaz r1����

��

@@

@@

rc@

@�

�

rb@

@@@

ra@

@

rd�

���

rfre rg rh�

�rj�

�

ri@

@r0Najdete podsvaz generovany prvky a, b, g.

�Re�sen��: Postupuje se stejne jako pri hledani podalgebry generovane mnozinou.�

Poznamka: Necht L je svaz. Prvek a ∈ L se nazyva prusekove ireducibilni⇔ (∀ x, y ∈ L) a = x ∧ y ⇒ a = x nebo a = y.

A dualne: Prvek a ∈ L se nazyva spojove ireducibilni ⇔(∀ x, y ∈ L) a = x ∨ y ⇒ a = x nebo a = y.

Pokud L je konecny svaz, pak plati:a 6= 1 je prusekove ireducibilni ⇔ a je pokryt prave jednim prvkem,a 6= 0 je spojove ireducibilni ⇔ a pokryva prave jeden prvek.

JestlizeX je mnozina generujici svaz L a a je spojove a prusekove ireducibilniprvek, pak zrejme musi byt a ∈ X (nebot tento prvek se neda ziskat pomocitermu slozenych z ostatnich prvku).

Budeme-li nyni uvazovat svaz z predchoziho prikladu, pak spojove a pruse-kove ireduc. prvky jsou prave a, b, g, h a soucasne se snadno overi, ze 〈a, b, g, h〉 =L. Tedy minimalni pocet generatoru tohoto svazu je 4.

18.12.2007

Tvrzen�� 32. (Cinska zbytkova veta) (1) Necht n1, . . . , nk ∈ N jsou po dvounesoudelna cisla a a1, . . . , ak ∈ Z. pak ex. prave jedno x ∈ Z, 0 ≤ x < n1 · · ·nk

takove, zex ≡ a1 (mod n1)

...

x ≡ ak (mod nk).

(2) (Ekvivalentni verze) Necht n1, . . . , nk ∈ N jsou po dvou nesoudelna cisla,n = n1 · · ·nk. Pak

Zn∼= Zn1

× · · · × Znk

[a]n 7→ ([a]n1, . . . , [a]nk

)

je izomor�smus okruhu.

31

Tvrzen�� 33. Necht a, b ∈ Z. Rovnice a · x ≡ b (mod n) s neznamou x ∈ Z mareseni ⇔ gcd(a, n) deli b.

Pokud je toto splneno, pak tato reseni jsou tvaru x ≡ bgcd(a,n) · u (mod

ngcd(a,n) ), kde

agcd(a,n) · u ≡ 1 (mod n

gcd(a,n) ).

D�ukaz: Zrejme plati, ze ax ≡ b (mod n) pro nejake x ⇔ ax+ny = b pro nejakey. Z jednoho z predchozich postupu uz vime, kdy je takovato rovnice resitelna(a dokonce zname i vsechna reseni). Je to prave kdyz gcd(a, n) deli b. Necht jeto tedy splneno, pak je posledni rovnice ekvivalentni s a

gcd(a,n)x +n

gcd(a,n)y =b

gcd(a,n) a to je ekvivalentni sa

gcd(a,n)x ≡b

gcd(a,n) (mod ngcd(a,n) ). Protoze

agcd(a,n)

a ngcd(a,n) jsou nyni uz nesoudelne, ma a

gcd(a,n) inverzi modulo ngcd(a,n) a tedy

x ≡ bgcd(a,n)

(a

gcd(a,n)

)−1(mod n

gcd(a,n) ). �

P�r. �C��n�st�� gener�alov�e po�c��tali voj�aky tak, �ze je nechali nastupovat do �rado r�uzn�ych d�elk�ach. Po�cet voj�ak�u pak spo�c��tali z toho, kolik jim p�ri r�uzn�ychn�astupech voj�ak�u p�rebylo. Gener�al m�el p�red bitvou 1200 voj�ak�u. Po bitv�e ne-chal zbyl�e voj�aky nastoupit do �rad po p�eti a vid�el, �ze zbyli t�ri. Pak je nechalnastoupit do �rad po �sesti, to zbyli tak�e t�ri, a pak je je�st�e nechal nastoupit posedmi, to zbyl jeden. Nakonec je nechal nastoupit po jeden�acti a nezbyl �z�adn�y.Kolik gener�alov�ych voj�ak�u p�re�zilo bitvu?

�Re�sen��: Je tedy potreba najit 0 ≤ n ≤ 1200 takove, ze

n ≡ 3 (mod 5)

n ≡ 3 (mod 6)

n ≡ 1 (mod 7)

n ≡ 0 (mod 11).

Pouzijeme predchozi tvrzeni. Mame tedy (odzadu), ze:

n ≡ 0 (mod 11)⇔ n = 11k, k ∈ Z

. Dale pro n = 11k plati (viz predchozi tvrzeni)

n ≡ 1 (mod 7)⇔ 11k ≡ 1 (mod 7)⇔ k ≡ 11−1 ≡ 4−1 (mod 7)

Hodnotu 4−1(mod 7) zjistime napr. pomoci Eukleidova algoritmu (nebo to uhad-neme), tj. 4−1 ≡ 2 (mod 7). Takze k = 7l + 2, l ∈ Z.

Pro n = 77l + 22 plati:

n ≡ 3 (mod 6)⇔ 77l + 22 ≡ 3 (mod 6)⇔ l ≡ 77−1(3− 22) ≡ 5−1(−1) (mod 6)

Takze l ≡ −5−1 ≡ −5 ≡ 1 (mod 6). Tedy l = 6m+ 1, m ∈ Z.

32

Pro n = 11.7.6m+ 99 plati

n ≡ 3 (mod 5)⇔ 11.42m+ (−1) ≡ 3 (mod 5)⇔ 2m ≡ 4 ≡ 2.2 (mod 5)

Takzem ≡ 2 (mod 5) a tedym = 5j+2, j ∈ Z. Celkem tedy n splnuje predchozirovnice prave kdyz n = 11.7.6.5j + 1023 = 2310j + 1023, j ∈ Z. Protoze dalemusi byt 0 ≤ n ≤ 1200, je zrejme n = 1023. �

Tvrzen�� 34.Necht n ≥ 1. Oznacme Z∗n = {x ∈ Zn| x je invertibilni prvek vzhledem k nasobeni}.Pak plati:

(i) Z∗n s operaci nasobeni modulo n je grupa,(ii) Z∗n = {[a]n ∈ Zn| gcd(a, n) = 1},(iii) |Z∗n| = ϕ(n), kde ϕ je Eulerova funkce.

Dusledek: V�eta (Eulerova): Jsou-li a, n nesoud�eln�a, pak aϕ(n) ≡ 1 (mod n).(ii) V�eta (mal�a Fermatova): Je-li p prvo�c��slo a p - a, pak ap−1 ≡ 1 (mod p).(iii) Necht a, n jsou nesoud�eln�a a k ≡ l (mod ϕ(n)). Pak ak ≡ al (mod n).

P�r. Spo�ct�ete 234567

mod 9.

�Re�sen��: Pouzijeme predchozi dusledek. Zjistime tedy kolik je 34567

(mod ϕ(9)).Zrejme je ϕ(9) = ϕ(33) = 3.(3 − 1) = 6. Indukci podle k snadno ukazeme, ze3k ≡ 3 (mod 6) pro kazde k ≥ 1.

Podle predchoziho tedy je 234567

≡ 23 ≡ 8 (mod 9). �

P�r. [Wilsonovo krit�erium] Doka�zte, �ze �c��slo p je prvo�c��slo pr�av�e tehdy, kdy�z

(p− 1)! ≡ −1 (mod p).

�Re�sen��: (⇒): Zrejme pak je Z∗p = {1, . . . , p− 1}. Pritom pro x ∈ Z∗p je

x = x−1 ⇔ x2 = 1⇔ 0 = x2−1 = (x+1)(x−1)⇔ (x+ 1 = 0 nebo x− 1 = 0).

Uvedene ekvivalence plati, protoze Zp je teleso. Dostali jsme tak, ze x 6= x−1

prave kdyz x 6= −1, 1. V Zp tedy plati, ze

(p− 1)! =∏

x∈Z∗p

x = (x1x−11 ) . . . (xkx

−1k )(−1)1 = −1.

(⇐): Z predpokladu snadno dostavame, ze kazde 1 ≤ x ≤ p−1 je invertibilniv Zp. Tedy {1, . . . , p− 1} ⊆ Z∗p = {[a]p ∈ Zp| gcd(a, p) = 1} a proto p musi byt

33

prvocislo. �

8.1.2008

P�r. Necht F je teleso kladne charakteristiky char F = p > 0. Pak p je prvocislo.Necht F je navic konecne teleso. Pak |F | = pn.

�Re�sen��: Pro spor predpokladejme, ze p = kl, kde k, l < p. Pak 0 = p × 1 =(kl) × 1 = (k × 1) · (l × 1) a protoze F je teleso, musi byt bud k × 1 = 0 nebol × 1 = 0, coz je spor s de�nici charakteristiky.

Polozme nyni Fp := {k×1| k ∈ Z}. Snadno se overi, ze Fp je okruh izomorfnise Zp a tedy je to teleso. Teleso F nyni tedy muzeme uvazovat jako vektorovyprostor nad Fp. Ten ma konecnou dimenzi n a tedy |F | = pn. �

P�r. Necht F je teleso, f ∈ F [x] je polynom stupne alespon 1. Pak ex. teleso Utakove, ze F ≤ U a f ma v U alespon jeden koren.

�Re�sen��: Staci BUNO predpokladat, ze f je ireducibilni (jinak si vezmeme nejakyireducibilni polynom z rozkladu f). Nyni polozime U := F [x]/f.F [x]. Z predcho-ziho vime, ze U je teleso a F muzeme chapat jako podteleso v U (pri ztotozneniF → U , a 7→ [a]). Prvek [x] ∈ U je nyni korenem f(x) ∈ F [x] ⊆ U [x], nebot prof(x) =

n∑i=0

aixi je f([x]) =

n∑i=0

ai[x]i = [

n∑i=0

aixi] = [f(x)] = [0] = 0. �

Dusledek: Necht F je teleso, f ∈ F [x] je polynom stupne alespon 1. Pakex. teleso U ′ takove, ze F ≤ U ′ a f se rozklada v U ′ na linearni cinitele, tj

f(x) =n∏

i=1(x − ai), pro nejaka ai ∈ U ′. (Staci opakovane pouzit predchozi

priklad.)

De�nice: Pro polynom f(x) =n∑

i=0aix

i ∈ F [x] de�nujme derivaci

f ′(x) :=n∑

i=1

iaixi−1 ∈ F [x].

(Derivace se vzhledem k "+" a "·" chova stejne jako klasicka derivace z analyzy.)

P�r. Pro kazde p prvocislo a n ≥ 1 existuje konecne teleso F s pn prvky.

�Re�sen��: Uvazujme polynom xpn − x ∈ Zp[x]. Podle predchoziho ex. teleso Uobsahujici Zp takove, ze f se v nem rozklada na linearni cinitele. Polozme F :=

34

{a| f(a) = 0}. Ukazeme, ze F je teleso: necht a, b ∈ F pak

f(ab) = (ab)pn

− ab = apn

bpn

− ab = ab− ab = 0

f(a+ b) = (a+ b)pn

− (a+ b) = (apn

+ bpn

)− (a+ b) = (a+ b)− (a+ b) = 0

a pro a 6= 0 je

f(a−1) = (a−1)pn

− a−1 = (apn

)−1 − a−1 = a−1 − a−1 = 0.

Ted uz jen staci ukazat, ze |F | = pn: protoze f ma nanejvys tolik ruznychkorenu, kolik je jeho stupen, je |F | ≤ pn. Predpokladejme, ze nektery koren jevicenasobny, tedy f(x) = (x − a)2g(x) pro nejake a ∈ F . Po zderivovani pakdostaneme, ze f ′(x) = (xpn − x)′ = pnxpn−1 − 1 = 0 · xpn−1 − 1 = −1 se musi

rovnat((x− a)2g(x)

)′= 2(x− a)g(x)+ (x− a)2g′(x). Tedy (x− a) deli −1, coz

je spor. Polynom f ma tak vsechny koreny navzajem ruzne a tudiz |F | = pn. �

Tvrzen�� 35. Necht F je teleso a G je konecna podgrupa multiplikativni grupy(F \ {0}, ·). Pak G je cyklicka.

Dusledek: Pro kazde p prvocislo a n ≥ 1 existuje alespon jeden ireducibilnipolynom f ∈ Zp[x] nad telesem Zp.�Re�sen��: Necht F je teleso s pn prvky a α ∈ F je generator cyklicke grupy F \{0}.Uvazujme dosazovaci homomor�smus ϕ : Zp[x]→ F , f 7→ f(α). �

De�nice: Necht R je komutativni okruh.Prvek a ∈ R se nazyva ireducibilni ⇔ (∀ x, y ∈ R) a = xy ⇒ a|x nebo a|y.Prvek a ∈ R se nazyva prvocinitel ⇔ (∀ x, y ∈ R) a|xy ⇒ a|x nebo a|y.Prvky a, b ∈ R jsou asociovane (znac. a‖b) ⇔ a | b & b | a.

Zrejme kazdy prvocinitel je ireducibilni. Naopak to platit nemusi.

P�r. Ukazte, ze v okruhu Z[√5] := {a+ b

√5| a, b ∈ Z} ⊆ R (podokruh realnych

cisel) jsou prvky 1 +√5, 1−

√5 a 2 ireducibilni, ale nejsou to prvocinitele.

Mame tak, ze (1 +√5)(1 −

√5) = −4 = 2 · (−2) jsou dva navzajem ruzne

(vzhledem k asociovanosti) rozklady cisla −4 na soucin ireducibilnich prvku (tj.1 +√5 ∦ 2 a 1−

√5 ∦ 2).

�Re�sen��: Pro x = a+ b√5 ∈ Z[

√5] polozme x = a− b

√5 a dale uvazujme funkci

ϕ : Z[√5]→ Z, ϕ(x) = xx. Zrejme ϕ(xy) = ϕ(x)ϕ(y) pro kazde x, y ∈ Z[

√5].

Snadno se ukaze, ze x ∈ Z[√5] je invertibilni prave kdyz ϕ(x) = ±1. Dale

plati, ze pro x = a + b√5 nabyva ϕ(a + b

√5) = a2 − 5b2 pouze hodnot 0, 1, 4

modulo 5. Nyni ukazeme, ze 1 +√5 je ireducibilni (pro zbytek se to pak udela

stejne):Necht 1 +

√5 = xy, pro x, y ∈ Z[

√5]. Pak −4 = ϕ(1 +

√5) = ϕ(x)ϕ(y).

Mame tedy, ze ϕ(x) ∈ {1,−1, 2,−2, 4,−4}. Podle predchoziho nemuze byt ϕ(x)

35

rovno ani 2 ani −2. Tedy vzdy je bud ϕ(x) = ±1 nebo ϕ(y) = ±1. Pokud jenapr. ϕ(x) = ±1, pak je x invertibilni a x−1(1 +

√5) = y a tudiz (1 +

√5) | y.

2 neni prvocinitel: Kdyby ano, musel by delit bud 1 +√5 nebo 1−

√5, coz

zjevne neni pravda.1+√5 neni prvocinitel (1−

√5 se udela podobne): Kdyby ano, musel by delit

2, tj. x(1+√5) = 2 pro nejake x ∈ Z[

√5]. Pak ovsem (−4)ϕ(x) = ϕ(x(1+

√5)) =

ϕ(2) = 4, tedy ϕ(x) = −1 a x je invertibilni. Takze 1 +√5 = 2x−1, coz je spor.

�

P�r. Najdete vsechny idealy (nekomutativniho) okruhu

R =

(R R0 R

)= {

(a b0 c

)| a, b, c ∈ R}

(podokruh vsech matic 2× 2 nad R).

�Re�sen��: Necht

(a b0 c

)∈ R a oznacme J ideal generovany timto prvkem. Pak

zrejme (a 00 0

)=

(1 00 0

) (a b0 c

) (1 00 0

)∈ J(

0 b0 0

)=

(1 00 0

) (a b0 c

) (0 00 1

)∈ J(

0 00 c

)=

(0 00 1

) (a b0 c

)∈ J.

Dale je (ideal generovany)⟨ (1 00 0

) ⟩=

(R R0 0

)= I1

⟨ (0 10 0

) ⟩=

(0 R0 0

)= I2⟨ (

0 00 1

) ⟩=

(0 R0 R

)= I3.

Takze snadno dostavame, ze svaz vsech idealu je nasledujici:tR@

@@ tI3���

I1 t@

@@

���tI2

t0�

36