Cvičení Algebra II — jaro 2008 — DÚ — Komentáře a řešení
A
Příklad A1 (autor: D. Sehnal)
Je
√
2 = (
√
2+
√
3)+(
√
2−
√
3)
2 a
√
3 = (
√
2+
√
3)−(
√
2−
√
3)
2 , tedy R = Q(
√
2 +
√
3) = Q(
√
2,
√
3).
Nechť φ : R → R je automorfismus R. Potom σ(
√
2)2
= 2, σ(
√
3)2
= 3 a tedy vztahy σ(
√
2) = ±
√
2,
σ(
√
3) = ±
√
3 určují všechny automorfismy R. Jsou dvě možnosti kam poslat
√
2 nebo
√
3 a tedy Aut(R) ≃
(Z2, +) × (Z2, +).
Komentář: Pro všechny 4 možnosti by bylo vhodné ověřit, že předpis
a + b
√
2 + c
√
3 + d
√
6 → a + ǫb
√
2 + ηc
√
3 + ǫηd
√
6,
kde ǫ, η ∈ {1, −1} zadává homomorfismus. A také, že skládání homomorfismů odpovídá násobení v grupě
(Z2, +) × (Z2, +).
Příklad A2 (autor: T. Golembiovský)
Pro x2
1 + x2
2 + x2
3 dostáváme:
x1 x2 x3 s1 s2 s3
2 0 0 2 0 0
1 1 0 0 1 0
x2
1 + x2
2 + x2
3 = As2
1 + Bs2 = A(x1 + x2 + x3)2
+ B(x1x2 + x1x3 + x2x3)
Hodnoty zvolíme následovně:
x1 = 1, x2 = x3 = 0 . . . 1 = A
x1 = x2 = x3 = 1 . . . 3 = 9 + 3B ⇒ −2 = B
Pro x3
1 + x3
2 + x3
3 dostáváme:
x1 x2 x3 s1 s2 s3
3 0 0 3 0 0
2 1 0 1 1 0
1 1 1 0 0 1
x3
1 + x3
2 + x3
3 = As3
1 + Bs1s2 + Cs3 =
= A(x1 + x2 + x3)3
+ B(x1 + x2 + x3)(x1x2 + x1x3 + x2x3) + Cx1x2x3
Hodnoty zvolíme následovně:
x1 = 1, x2 = x3 = 0 . . . 1 = A
x1 = x2 = 1, x3 = 0 . . . 2 = 8 + 2B ⇒ −3 = B
x1 = x2 = 1, x3 = −1 . . . 1 = 1 + 3 − C ⇒ 3 = C
Dostaneme soustavu:
s1 = 0
s2
1 − 2s2 = s3
1 − 3s1s2 + 3s3
s3 = 2
−2s2 = 6
s2 = −3
x1 + x2 + x3 = 0
1
x1x2 + x1x3 + x2x3 = −3
x1x2x3 = 2
x2 + x3 = −x1
x2x3 =
2
x1
x1(x2 + x3) + x2x3 = −3
−x2
1 +
2
x1
= −3
−x3
1 + 3x1 + 2 = 0
Komentář: Polynom f(x) = x3
− 0x2
− 3x − 2 lze z podmínek s1 = 0, s2 = −3, s3 = 2 sestavit rovnou na
základě Vietových vztahů.
Jeden kořen je viditelně x1 = 2. Po vydělení −x3
1 + 3x1 + 2/(x1 − 2) dostáváme x2
1 + 2x1 + 1 = 0 a odtud
pak:
x1 =
−2 ±
√
0
2
= −1
Dosazením do soustavy získáme
x2 + x3 = 1
−x2 − x3 + x2x3 = −3
x2x3 = −2
x2 = 1 − x3
(1 − x3)x3 = −2
−x2
3 + x3 + 2 = 0
x3 =
−1 ±
√
9
−2
x3a = −1
x3b = 2
Nyní pro jednotlivé případy x3:
1. pro x3 = −1 jsou tedy zbylé dva kořeny x1 = −1, x2 = 2 (nebo naopak)
2. a pro x3 = 2 jsou to x1 = −1, x2 = −1.
Komentář: Soustavu není nutné řešit takto. x1, x2, x3 jsou kořeny f, tj. jeden je 2 zbylé −1.
Celkem máme tedy 3 řešení: (−1, −1, 2), (−1, 2, −1), (2, −1, −1).
Příklad A3 (autor: M.Chmelík)
O kubickém polynomu f(x) = x3
− ux2
+ 1 ∈ C[x], kde u ∈ C, víme, že má 3 různé kořeny x1, x2, x3. Sestavte
normovaný kubický polynom, jež má kořeny:
x1 + x2
x3
,
x2 + x3
x1
,
x1 + x3
x2
2
(x − x1)(x − x2)(x − x3) = x3
+ (−x1 − x2 − x3)x2
+ (x1x2 + x1x3 + x2x3)x + (−x1x2x3)
Porovnáním získáme následující rovnosti:
x1 + x2 + x3 = u
x1x2 + x2x3 + x1x3 = 0
x1x2x3 = −1
Rádi bychom polynom tvaru:
x3
−
x1 + x2
x3
+
x2 + x3
x1
+
x1 + x3
x2
x2
+
(x1 + x2)(x2 + x3)
x1x3
+
(x2 + x3)(x1 + x3)
x1x2
+
(x1 + x2)(x1 + x3)
x2x3
x
−
(x1 + x2)(x1 + x3)(x2 + x3)
x1x2x3
Vyjádříme si výraz:
−
(x1 + x2)(x1 + x3)(x2 + x3)
x1x2x3
Víme, že x1x2x3 = −1, proto budeme upravovat výraz:
(x1 + x2)(x1 + x3)(x2 + x3) = (x1 + x2 + x3)(x1x2 + x1x3 + x2x3) − x1x2x3 = u · 0 − (−1) = 1
Vyjádříme si výraz:
(x1 + x2)(x2 + x3)
x1x3
+
(x2 + x3)(x1 + x3)
x1x2
+
(x1 + x2)(x1 + x3)
x2x3
=
x1
3
+ x2x1
2
+ x3x1
2
+ x2
2
x1 + x3
2
x1 + 3x2x3x1 + x2
3
+ x3
3
+ x2x3
2
+ x2
2
x3
x1x2x3
=
−((x1 + x2 + x3)(x1x2 + x1x3 + x2x3) + x1
3
+ x2
3
+ x3
3
) =
−(x1
3
+ x2
3
+ x3
3
)
−(x1
3
+ x2
3
+ x3
3
) = −(σ1
3
− 3σ1σ2 + 3σ3) = −(u3
+ 3(−1)) = −u3
+ 3
Vyjádříme si výraz:
−
x1 + x2
x3
+
x2 + x3
x1
+
x1 + x3
x2
=
(x1 + x2 + x3)(x1x2 + x1x3 + x2x3) − 3x1x2x3
x1x2x3
=
−3(−1) = 3
Proto hledaný polynom bude tvaru:
x3
+ 3x2
+ (3 − u3
)x + 1
Příklad A4 (autor: D. Sehnal)
(Reg(A), ⊆) tvoří svaz, protože regularní jazyky jsou uzavřeny na (konečné) sjednocení a průnik. Tedy sup{X, Y } =
X ∪ Y a inf{X, Y } = X ∩ Y . Největší prvek je A∗
a nejmenši je prázdný jazyk.
(Reg(A), ⊆) netvoří úplný svaz.
Nechť A = {a}. Uvažujme třídu X = {Xi|i ∈ N} regulárních jazyků, kde
Xi =
A∗
je-li i prvočíslo;
A∗
− {ai
} jinak.
3
Nyní L = i∈N Xi = {ap
|p je prvočíslo} není regulární jazyk. Dále inf X musí ležet pod L. Nechť Yi =
{ap
|p je prvočíslo menší než i-té prvočíslo}. Každý Yi je regulární, protože je konečný. Posloupnost Y1 ⊂ Y2 ⊂
Y3 ⊂ · · · tvoří posloupnost dolních závor X. Nutně tedy Yi ⊆ inf X, ovšem i∈N Yi = L, což je spor s předchozím
pozorováním inf X ⊂ L.
Příklad A5 (autor: M.Šmérek)
Nechť (A, ⊆) je neprázdný svaz neobsahující nekonečné podřetězce. Ukážeme, že (A, ⊆) má největší a
nejmenší prvek. Nechť X je libovolný maximální (vzhledem k inkluzi) podřetězec (A, ⊆) a x je jeho největší
prvek. Pak x je maximální prvek (A, ⊆) (jinak spor s maximalitou X). Zároveň (∀a ∈ A)( a ≤ x ), jinak pro
nějaké b ∈ A, které toto porušuje bychom dostali (x ∨ b) > x a X není maximální. Tedy x je největší prvek
(A, ⊆). Obdobně bychom dokázali, že (A, ⊆) má i nejmenší prvek.
Nyní předpokládejme, že existuje M ⊆ A tak, že M nemá supremum v A (M je neprázdná, neboť supremum
prázdné množiny je nejmenší prvek v A). Nechť H je množina horních závor M. Protože (A, ⊆) má největší
prvek (označme jej 1), máme 1 ∈ H. Dále musí existovat x1 ∈ H tak, že x1 ≤ 1 a x1 = 1, jinak je 1 supremum
množiny M. Navíc existuje y1 ∈ H tak, že y1 < x1 nebo x1 a y1 jsou nesrovnatelné. Pokud by takové y1
neexistovalo, tak by x1 bylo supremum M. Pak ale (∀m ∈ M)( m ≤ (x1 ∧ y1) ) a tedy (x1 ∧ y1) ∈ H. Máme
tedy řetězec délky 3, ale obdobně můžeme pokračovat a získat tak nekonečný řetězec, což by byl spor a taková
množina M nemůže existovat. (A, ⊆) je tedy úplný svaz.
Komentář: První čás lze dokázat i tak, že
1. existuje nějaký maximální prvek uspořádané množiny A,
2. každý prvek je menší než nějaký maximální a
3. nemohou existovat dva maximální prvky, protože ve svazu A existuje jejich supremum.
Druhá část důkazu lze dokončit elegantně tak, že konstatujeme, že H je podsvaz svazu A a podle první části
má tedy nejmenší prvek. To je hledané supremum.
Příklad A6 (autor: L. Caha)
Příloha mimo tento soubor.
Příklad A7 (autor: J. Krčál)
(N0, |)
Supremem podmnožiny X ⊆ N0 je nejmenší společný násobek (lcm), nebo 0, pokud lcm X neexistuje.
Prvek 1 je zřejmě kompaktní, je to nejmenší prvek. Ukažme, že lib. prvek x ∈ N\{1} není kompaktní. Každé
číslo je zřejmě součin konečně mnoha prvočísel, tedy existuje prvočíslo p, tak že p ∤ x. Pak sup{pn
| n ∈ N} =
0 ≥ x. Ovšem pro lib. konečnou podmnožinu Y je supY rovno největšímu prvku podmnožiny a pro lib. n máme
x ∤ pn
, tedy neplatí supY ≥ x.
Tedy (N0, |) není algebraický.
(N0, |)d
Supremem je největší společný dělitel (gcd).
Prvek 0 je zřejmě kompaktní, ukažme, že libovolné x ∈ N je kompatní. Nechť X ⊆ N0, supX ≥ x ⇐⇒
gcdX | x.
Vezměme lib. a ∈ X, pouze u konečně mnoha prvočísel má rozklad a na prvočísla vyšší mocninu než gcdX.
Pro každé takové prvočíslo p a mocninu m v gcdX musí existovat y ∈ X, tak že rozklad y na prvočísla obsahuje
právě pm
. Tyto prvky přidáme k prvku a, postupně získáme Y = {a, y1, y2, y3, ..., yk}, tak že gcdY = gcdX.
Všechny prvky jsou kompaktní, tedy zřejmě (N0, |)d
je algebraický.
4
Příklad A8 (autor: O. Klíma dle různých řešení)
Pro n ≤ 2 je svaz distributivní. Pro n ≤ 3 je svaz modulární. Pro n ≥ 3 obsahuje svaz podsvaz izomorfní M5 a
tedy není distributivní. Pro n ≥ 4 obsahuje svaz podsvaz izomorfní N5 a tedy není modularní. Konkrétně: pro
A = {1, 2, 3, . . ., n} je např. podsvaz izomorfní M5 dán prvky △, ρ1 = {(2, 3), (3, 2)}∪△, ρ2 = {(1, 3), (3, 1)}∪△,
ρ3 = {(1, 2), (2, 1)} ∪ △ a ρ = {1, 2, 3} × {1, 2, 3} ∪ △.
Podobně, pro modularitu lze uvažovat △, τ1 = {(1, 2), (2, 1)} ∪ △, τ2 = {(1, 2), (2, 1), (3, 4), (4, 3)} ∪ △,
τ3 = {(1, 3), (3, 1), (2, 4), (4, 2)} ∪ △, τ = {1, 2, 3, 4} × {1, 2, 3, 4} ∪ △.
Příklad A9 (autor: O. Klíma podle A. Hericha)
Svaz podsvazů svazu S je distributivní, právě když S je řetězec.
Důkaz: Pokud je S řetězec, pak každá podmnožina tvoří podsvaz. Tj. Svaz podsvazů svazu S je (P(S), ∩, ∪),
který je distributivní.
Pokud S není řetězec, pak obsahuje dva nesrovnatelné prvky a, b. Potom následujíci podmnžiny tvoří podsvazy
S: ∅, {a}, {b}, {a, a ∨ b}, {a ∧ b, a, b, a ∨ b}. A ty tvoří podsvaz svazu všech podsvazů svazu S, který je
izomorfní svazu N5. (Pardon, neodolal jsem této formulaci.)
Příklad A10 (autor: O. Klíma podle A. Hericha)
Nechť a je ∨-ireducibilní a nechť a ≤ x ∨ y.
Pak a = a ∧ (x ∨ y) a z distributivity máme a = (a ∧ x) ∨ (a ∧ y). Odtud (a je ∨-ireducibilní) máme a = a ∧ x
nebo a = a ∧ y. Čili a ≤ x nebo a ≤ y.
Naopak, nechť a je ∨-primitivní a nechť a = x ∨ y.
Pak 1. a ≥ x a a ≥ y.
2. a ≤ x ∨ y a tedy (a je ∨-primitivní) máme a ≤ x nebo a ≤ y.
Dohromady a = x nebo a = y.
Všimněte si, že distributivita se využila pouze v jedné implikaci.
Příklad A11 (autor: O. Klíma podle mnohých)
Označme b = (a ∨ a). Pak c = a ∧ b = a ∧ (a ∨ a) = a podle absorbčního zákona.
Proto a ∨ c = a ∨ a. Na druhé straně a ∨ c = a ∨ (a ∧ b) = a opět podle absorbčního zákona.
Tzn. a ∨ a = a ∨ c = a.
Stejným způsobem lze dokázat a∧a = a. Případně to lze odvodit pomocí dokázaného: a∧a = a∧(a∨a) = a.
Příklad A12 (autor: O. Klíma podle mnohých)
V obou případech vyjde osmiprvkový svaz izomorfní P3 (krychle postavená na špičku).
Příklad A13 (autor: O. Klíma podle mnohých)
i) Neplatí. Například (nekomplementární) tříprvkový řetězec je podsvazem komplementárního svazu N5.
ii) Platí. Nechť ϕ : S → S′
je surjektivní homomorfismus z komplementárního svazu S do svazu S′
. Pokud 1
je největší prvek S, potom ϕ(1) je největší prvek S′
(plyne z izotonie zobrazení ϕ). Stejně tak ϕ(0) je nejmenší
prvek S′
a svaz S′
je tedy omezený.
Nyní pro libovolný prvek a ∈ S′
existuje prvek s ∈ S tak, že ϕ(s) = a. Pro něj máme komplement s′
ve
5
svazu S. Ukážeme, že ϕ(s′
) je komplement a ve svazu S′
. Stačí ověřit, že
ϕ(s′
) ∧ a = ϕ(s′
) ∧ ϕ(s) = ϕ(s′
∧ s) = ϕ(0).
Podobně ϕ(s′
) ∨ a = ϕ(1).
iii) Pro libovolný svaz S uvažujeme S′
= S ∪ {0, 1, k} kde 0, 1, k jsou nové prvky, tj. 0, 1, k ∈ S. Rozšíříme
definici operací ∧ a ∨ na množinu S′
tak, že 0 bude nejmenší prvek, 1 bude největší prvek a k je prvek
nesrovnatelný se všemi prvky z S. Přesněji, pro libovolné t ∈ S′
resp. s ∈ S definujeme:
t ∧ 0 = 0 ∧ t = 0, t ∧ 1 = 1 ∧ t = t, s ∧ k = k ∧ s = 0,
t ∨ 0 = 0 ∨ t = t, t ∨ 1 = 1 ∨ t = 1, s ∨ k = k ∨ s = 1.
Komentář: Nejmenší a největší prvek musíme přidat, protože nikde nebylo řečeno, že S je omezený.
Příklad A14 (autor: )
Počty postupně 27,29,5,5.
Příklad A15 (autor: O. Klíma)
V libovolné unární algebře (A, f) platí, že sjednocení dvou podalgeber je podalgebra. Skutečně, pokud
B, C ⊆ A jsou nosiče podalgeber, pak pro libovolné x ∈ B ∪ C, máme x ∈ B nebo x ∈ C, tj. f(x) ∈ B nebo
f(x) ∈ C, odkud f(x) ∈ B ∪ C.
Proto supremum ve svazu všech podalgeber algebry (A, f) je sjednocení. Víme, že infimum je průnik (platí
obecně pro libovolnou algebru). Tedy svaz S všech podalgeber (A, f) je podsvaz svazu všech podmnožin množiny
A, který je distributivní, a tedy je i S je distributivní.
Příklad A16 (autor: O. Klíma)
Uvažujeme-li unární algebru (A, idA), pak snadno nahlédneme, že každá relace ekvivalence na množině A
je kongruencí algebry (A, idA). Víme, že svaz všech relací ekvivalencí na čtyřprvkové množině není modulární.
Stačí tedy vzít A = {1, 2, 3, 4} a algebru (A, idA).
Jiné řešení (několik studentů): (A, f), kde A = {1, 2, 3, 4}, f(1) = 2, f(2) = 1, f(3) = 4, f(4) = 3.
Příklad A17 (autor: O. Klíma)
Pro libovolnou kongruenci ρ (různou od ∆) označme n, d ∈ N nejmenší čísla s vlastností nρ(n+d). (Přesněji,
n nechť je nejmenší číslo, pro které existuje k ∈ N takové, že nρ(n + k), a pro toto n nechť d je nejmenší takové
k.) Snadno se nahlédne, že tato dvojice jednoznačně zadává kongruenci.
Platí, že kongruence ρ daná dvojicí (n, d) je menší než kongruence σ daná dvojicí (n′
, d′
) právě tehdy, když
n′
≤ n a d′
| d. Proto je hledaný svaz izomorfní svazu (N, ≤)d
× (N, |)d
∪ {⊥}.
Příklad A18 (autor: O. Klíma podle mnohých)
a) Ne. V součinu dvou těles nemají prvky tvaru (a, 0) inverze. Lze také argumentovat konečností.
b) Ne. α(1) + α(1) = 2 + 2 = 4 = 3 = α(2) = α(1 + 1).
c) Ano. Ověří se že ρ je relace ekvivalence. Poté se ověří, že platí aρa′
∧ bρb′
=⇒ abρa′
b′
.
6
Příklad A19 (autor: O. Klíma)
a) Ano, ano, ano. Jde o varietu danou identitou f(x) = g(x).
b) H: Ne. Obrazem může být triviální algebra, která není v naší třídě.
P: Ne. Zlobí součin přes prázdnou množinu, kdy výsledkem je triviální algebra. Pro neprázné součiny uvažovanou
třídu neopustíme.
S: Ano.
c) H: Ne. Pro (Z, succ) lze uvažovat kongruenci ρ, která má v relaci všechna kladná čísla; přesněji
xρy ⇐⇒ (x = y ∨ (x > 0 ∧ y > 0)).
Potom příslušná faktoralgebra (cyklus délky 1 s nekonečným ocáskem) nemá bijektivní operaci.
P: Ano.
S: Ne. N je podalgebra (Z, succ).
Příklad A20 (autor: O. Klíma)
a) H: Ano; S: Ano; Pf Ano; P Ne.
b) H: Ne!!!! (příklad je netriviální-viz konec); S: Ano — každý minimální automat obsahuje pouze jeden
podautomat, tj. celý automat; P,Pf : Ne — příklad na cvičení.
c) H, S: Ne — viz. A19-c); P, Pf : Ano.
d) H: Ano; S: Ano; Pf Ano; P Ne.
e) H: Ano (automat je generován prázdnou množinou, tj. i homomorfní obraz má tuto vlastnost); S: Ano(viz
b) ); Pf , P Ne (viz b) ).
Příklad k b-H:
Ω = {a, b, c}, L = Ω∗
(ab + bc + ca).
Minimální automat má 7 stavů: {0, 1, 2, 3, 4, 5, 6}, kde 0 je iniciální, a dále a(0) = a(1) = a(2) = a(4) =
a(5) = 1, a(3) = a(6) = 4; b(0) = b(2) = b(3) = b(5) = b(6) = 2, b(1) = b(4) = 5; c(0) = c(1) = c(3) = c(4) =
c(6) = 3, c(2) = c(5) = 6.
Nyní kongruence ρ je dána/generována vztahy 1ρ4, 2ρ5, 3ρ6. Tzn. faktoralgebra má 4 prvky kde všechny tři
unární operace jsou konstantní. O tomto automatu lze ukázat, že není minimální. Ať zvolíme množinu finálních
stavů jakoukoli, vždy půjde faktorizovat. (Např. stav, který je třídou obsahující 1, lze ztotožnit se stavem, který
je třídou obsahující 2, pokud jsou oba tyto stavy finální nebo naopak oba nefinální.)
Příklad A21 (autor: O. Klíma, T.Golembiovský)
Komentář: Při práci s unárními operacemi je možné uvažovat dvě různé interpretace. Buď vše chápeme
klasicky, tj. např a3
b2
(x) znamená a(a(a(b(b(x))))), nebo uvažujeme pohled přes automaty, tj. že na prvek x
postupně aplikuje „písmenka , tj. např a3
b2
(x) znamená, že z x jdeme postupně podle a, a, a, b a na konec b.
Je nutné si předem jednu interpretaci zvolit a té se poté držet po celý příklad- autor předkládaného řešení zvolil
druhou interpretaci.
Rozebereme fk
gl
(x) = gm
fn
(x) ve dvou případech, kdy za x dosazujeme prvek z množiny {1, 2, 3, 4} nebo
{5, 6}.
• Pro s ∈ {1, 2, 3, 4} platí ak
bl
(s) = bm
an
(s) právě když k − l ≡ n − m0(mod4).
• Pro x ∈ {5, 6} musí platit k = 0 ⇔ n = 0.
Je-li k = n = 0 dostáváme podmínku l = 0 ⇔ m = 0.
Je-li k, n > 0 dostáváme podmínku |k − l − n| ≡ 0 (mod 4).
Všechny identity rozdělíme na několik typů. Je vidět, že algebra nesplňuje žádnou identitu s termy v různých
proměnných (viz. cvičení). Podobě nesplňuje žádnou identitu s termy v jedné proměnné, kde f je jen v jednom
termu (stačí dosatit prvek 5). Tj. zbývá diskutovat
7
1. gm
fu(x) = gn
fv(x), kde u, v ∈ {f, g}∗
.
2. gm
(x) = gn
(x)
1. Platí pokud jsou splňeny dvě podmínky
#f (u) + 1 − m − #g(u) ≡ #f (v) + 1 − n − #g(v) (mod 4)
(případ dosazení prvku z množiny {1, 2, 3, 4})
#f (u) − #g(u) ≡ #f (v) − #g(v) (mod 4)
(případ {5, 6})
Tyto dvě podmínky lze tedy ekvivalentně přepsat:
#f (u) − #g(u) ≡ #f (v) − #g(v) (mod 4), m ≡ n (mod 4).
2.
Platí pokud m − n ≡ 0 (mod 4) a m = 0 ⇔ n = 0
Příklad A22 (autor: O. Klíma)
Pokud m | n potom algebra Zm je faktoralgebra Zn (zde zobrazení [x]n → [x]m je surjektivní homomorfismus).
V tomto případě tedy každá identita, která platí v Zn, platí i v Zm a hledaná identita tedy neexistuje.
Pokud m | n pak hledanou identitou je např. fn
(x) = x. Ta jistě platí v Zn, ale neplatí v Zm (za x dosadíme
např. [0]m a rovnost fn
([0]m) = [0]m by znamenala [n]m = [0]m, tj. m | n.)
Příklad A23 (autor: O. Klíma)
i) Intuitivně kontrolujeme první písmenko a množinu všech písmen, které se ve slově objeví. Definujeme h
zobrazení („první písmenko ) z množiny všech termů do množiny proměnných X takto: h(x) = x pro x ∈ X,
h(t1 · t2) = h(t1) pro termy t1, t2.
Podobně c je zobrazení („obsah ) z množiny všech termů do množiny proměnných P(X) definované takto:
c(x) = {x} pro x ∈ X, c(t1 · t2) = c(t1) ∪ c(t2) pro termy t1, t2.
Identita t = s je splněna v uvažované varietě, právě když h(t) = h(s) a c(t) = c(s).
DK: ′
←′
použijí se identity.
′
→′
pokud h(t) = h(s), pak stačí vzít pologrupu levých nul (která je v naší varietě), ve které nebude identita
t = s platit. Pokud c(t) = c(s) pak vhodnou pologrupou je polosvaz (P(X), ∪).
Poznamenejme, že lze také rovnou brát volnou pologrupu v této varietě — viz. doc. Polák-1.termín, úloha
B, 2003.
ii) nemám kapacitu: intuitivně kontrolujeme posloupnost prvních výskytů všech písmen ve slově.
8
B
Příklad B1 (autor: D. Sehnal)
Minimální polynom (s koeficienty v Q) mající α = 21/4
jako kořen je f(x) = x4
− 2. Podobně pro i máme
g(x) = x2
+ 1. Je tedy R = Q(α, i) = Q/ (x4
− 2)(x2
+ 1) . Kořeny f(x) jsou α, −α, αi, −αi a pro g(x) jsou
kořeny i, −i. To znamená, že α můžeme poslat na nějaký prvek z {α, −α, αi, −αi} a i na {i, −i}.
Nechť ϕ : R → R, α → αi, i → i a ψ : R → R, α → α, i → −i jsou automorfismy R. Pak ϕ a φ
generují grupu Aut(R), která není nic jiného než grupa symetrií čtverce tvořeného vrcholy o souřadnicích
kořenů polynomu f(x) v komplexní rovině, kde rotaci o 90 stupňů odpovídá ϕ a φ osové symetrii podle osy
x. Je tedy Aut(R) ≃ D4, kde Dn je dihedralní grupa (grupa symetrií pravidelného n-úhelníku). Prvky Aut(R)
jsou {1, ϕ, ϕ2
, ϕ3
, ψ, ϕψ, ϕ2
ψ, ϕ3
ψ}.
Příklad B2 (autor: O. Klíma)
Pokud není R obor integrity, snadno se takový příklad nalezne. Např. 2x nad Z8.
Pokud R je obor integrity, pak takový polynom neexistuje. Předpokládejme naopak, že f má takovou vlastnost,
tj. f(x, y, z1, . . . , zk) = f(y, x, z1, . . . , zk), pro nějaké x, y, přičemž f3
je symetrický polynom. Uvažujme
g(x, y) = f(x, y, . . . ) jako polynom nad R[z1, z2, . . . , zk]. Pak g(x, y) má také naši vlastnost jako f. Budeme
pracovat s tímto polynomem ve dvou proměnných. Navíc místo oboru integrity přesuneme naše úvahy do příslušného
podílového tělesa. Pro polynom α = g(x,y)
g(y,x) = 1 máme α3
= 1.
Lze dokázat, že pokud α3
= 1 pak α ∈ R. (Není to úplně jednoduché.)
Nyní z g(x, y) = αg(y, x) plyne výměnou x a y, že g(y, x) = αg(x, y) (zde použijeme, že α je konstanta).
Teď již snadno: g(x, y) = αg(y, x) = α2
g(x, y) = α3
g(y, x) = g(y, x). Spor.
Komentář: Zajímavé je, že pro druhou mocninu to funguje. Tj. existuje polynom f nad oborem integrity
který není symetrický ale f2
symetrický je.
Příklad B3 (autor: J. Konečný)
S — množina všech vektorových podprostorů vektorového prostoru Q3
a = (1, 0, 0) , b = (0, 1, 0) , c = (0, 0, 1) , d = (1, 1, 1)
Podsvaz svazu (S, ∧, ∨) generovaný množinou {a, b, c} má osm prvků (M = {{0}, a, b, c, a, b , a, c , b, c , Q3
})
a je izomorfní se svazem (P(a, b, c), ⊆).
Komentář: Zde se zápisem a, b myslí podprostor generovaný a∪b. Bylo by přesnější asi psát sup{a, b} nebo
a ∨ b nebo třeba a ∪ b místo a, b .
(N, ∧, ∨) je podsvaz svazu (S, ∧, ∨) generovaný množinou {a, b, c, d}. Zřejmě M ⊆ N. Pomocí průseků a
spojení lze nagenerovat další prvky náležící do N:
• a, d = a ∨ d = (1, 0, 0), (0, 1, 1)
b, d = b ∨ d = (1, 0, 1), (0, 1, 0)
c, d = c ∨ d = (1, 1, 0), (0, 0, 1)
• e = a, d ∧ b, c = (0, 1, 1)
f = b, d ∧ a, c = (1, 0, 1)
g = c, d ∧ a, b = (1, 1, 0)
• e, f = e ∨ f = (1, 0, 1), (0, 1, 1)
e, g = e ∨ g = (1, 0, −1), (0, 1, 1)
f, g = f ∨ g = (1, 0, 1), (0, 1, −1)
9
• h = e, f ∧ a, b = (1, −1, 0)
i = e, g ∧ a, c = (1, 0, −1)
j = f, g ∧ b, c = (0, 1, −1)
Aplikací průseků a spojení lze generovat do nekonečna další podprostory. Pro popis podsvazu bude třeba
přesně popsat operace spojení jednorozměrných a průseku dvourozměrných podprostorů. Spojení dvou jednorozměrných
podprostorů lze snadno popsat U ∨ V = U ∪ V . Pro popis průseků budou dále dvourozměrné
prostory zapisovány v normovaném tvaru (1, 0, x), (0, 1, y) kde x, y ∈ Q. Kromě a, c a b, c lze takto popsat
všechny dvourozměrné podprostory z Q3
.
Komentář: Kromě všech obsahujících c.
Nechť p = (1, 0, x), (0, 1, y) a q = (1, 0, u), (0, 1, v) . Rovinu p lze parametricky vyjádřit (x1, x2, x3) =
s(1, 0, x) + t(0, 1, y). Rovina q má normálový vektor n = (u, v, −1) a je popsána rovnicí ux1 + vx2 − x3 = 0. Po
dosazení p do q dostaneme s(u − x) = t(y − v), t = s(u−x
y−v ).
Komentář: Přesněji pro y = v. Pro u = x ale nemá smysl průsek počítat.
s(1, 0, x) + t(0, 1, y) = s(1, 0, x) + s(u−x
y−v )(0, 1, y) = s(1, u−x
y−v , x + (u−x)y
y−v ) ∈ p ∧ q, proto
p ∧ q = (1,
u − x
y − v
, x +
(u − x)y
y − v
) .
Způsob, jakým je počítán průsek, dává velké možnosti dalšího generování podprostorů.
Lze dokázat, že (1, 0, x), (0, 1, y) ∈ N pro x, y ∈ Z: Pro x, y ∈ {−1, 0, 1} platí (spojení podprostorů
a, b, e, f, i, j). Předpokládejme, že tvrtení platí pro x, y ∈ {−n, . . . , n}, dokážeme že platí i pro x, y ∈ {−n −
1, . . . , n + 1}.
v = (1, 0, n − 1), (0, 1, −1) ∧ (1, 0, n), (0, 1, 0) = (1, −1, n) .
(v ∨ e) ∧ (c ∨ f) = (1, 0, n + 1) , (v ∨ i) ∧ (c ∨ e) = (0, 1, −n − 1) . Při volbě v = (1, 0, −n + 1), (0, 1, −1) ∧
(1, 0, −n), (0, 1, 0) = (1, 1, −n) dostaneme stejným způsobem i (1, 0, −n − 1) a (0, 1, n + 1) .
Dále lze vygenerovat libovonlý prostor (1, 0, r
s ) , r, s ∈ Z, s = 0. Pak v = (1, 0, 0), (0, 1, 0) ∧ (1, 0, r), (0, 1, s) =
(1, −r
s , 0) a dále (v ∨ e) ∧ (a ∨ c) = (1, 0, r
s ) . Výrazem ( (1, 0, r
s ) ∨ h) ∧ (b ∨ c) dostaneme (0, 1, r
s ) .
Z výše uvedeného plyne, že dokážeme nagenerovat libovolný dvourozměrný podprostor v Q3
. Průsekem
dostaneme libovolný jednorozměrný. Proto (N, ∧, ∨) = (S, ∧, ∨).
Příklad B4 (autor: M. Šmérek)
Jedná se o svaz. Existence spojité funkce, která je supremem definovaným
(∀f, g ∈ C)sup{f, g} = h, kde h(x) = max{f(x), g(x)}
plyne ze spojitosti f a g. Obdobně pro infimum.
Nejedná se o úplný svaz, neboť
sup{fi}i∈N, kde fi =
1
π
arctan(i(x −
1
2
)) +
1
2
neexistuje. Na obrázku je zeleně vyznačeno supremum v nespojitých funkcích. Pro libovolnou funkci f ∈ C
takovou, že (∀i ∈ N)( f ≥ fi ) existuje f′
různé od f tak, že (∀i ∈ N)( f ≥ f′
≥ fi ). Takové f′
začne „stoupat
k jedničce později jak f.
Komentář: Pro uvažované f máme f(x) = 1 pro x ≥ 1
2 . Potom f′
(x) = 1 pro x ≥ 1
2 a pro x < 1
2 lze definovat
f′
(x) například takto: f′
(x) = f1(x)+f(x)
2 .
Možná trochu přehlednější je uvažovat „lineární funkce tvaru f(x) = i(x − 1
2 ) + 1
2 , „ořízlé do intervalu
0, 1 .
Příklad B5 (autor: R. Benkovský)
10
Obrázek 1: Obrázek k příkladu B-4
Nechť (G, +) je libovolná grupa, potom svaz podgrup grupy (G, +) je algebraický svaz.
Tvrzení : Kompaktní prvky svazu podgrup (Sub(G), ⊆) jsou právě konečně generované podgrupy (tedy podgrupy,
které mají konečnou množinu generátorů).
Důkaz: (Jen jedné implikace, kterou pro náš příklad potřebujeme.)
Pokud je S konečně generovaná podgrupa, potom pro libovolnou množinu podgrup X platí : pokud sup X ≥
S, potom tedy sup X ⊇ S, tedy sup X obsahuje všechny prvky podgrupy S, tedy obsahuje i (konečně mnoho)
generátorů podgrupy S =< R >.
Z množiny podgrup X nám tedy stačí vybrat podgrupy Xi, které obsahují prvky množiny R. Dostáváme
tedy (zřejmě konečnou, protože množina R je konečná) množinu indexů I tak, že
i∈I
Xi = sup{Xi ∈ X|i ∈ I} ≥ S
.
Tvrzení : Každý prvek (Sub(G), ⊆) je supremem kompaktních prvků.
Důkaz : Nechť H ∈ Sub(G), rozlišíme 2 případy :
• H je konečně generovaná ⇒ H je kompaktní prvek ⇒ H je tedy zřejmě supremem kompaktních prvků
• H je nekonečně generovaná : Nechť tedy ∀i ∈ H (prvky grupy H) jsou Hi =< i > (podgrupy H generované
prvkem i). Potom zřejmě Hi pro libovolné i ∈ H je podgrupa H a je konečně generovaná. Dále tedy
11
H = sup X, kde X = {Hi | i ∈ H} a tedy H je supremem kompaktních prvků (Hi jsou konečně generované,
tedy jsou kompaktní).
Příklad B6 (autor: T. Golembiovský)
• Součin dvou algebraických svazů je algebraický.
Nechť (A, ≤) a (B, ⊑) jsou algebraické svazy a mějme součin (A × B, ).
Ve svazu (A × B, ) je prvek c ∈ A × B, c = (a, b), kompaktní pokud jsou kompaktní a v (A, ≤) a b v
(B, ⊑).
Je-li sup C ≥ c a c = (a, b) pak vezměme
X = {x ∈ A|(∃b ∈ B)((x, b) ∈ C)} a Y = {y ∈ B|(∃a ∈ A)((a, y) ∈ C})
a pak konečné podmnožiny Xf ⊆ X a Yf ⊆ Y tak, že sup Xf ≥ a a sup Yf ≥ b.
(Komentář: Zde častá chyba: pak sup Xf × Yf ≥ c a Xf × Yf je konečné. To nelze použít, protože Xf × Yf
nemusí být podmnožina C.)
Nyní pro libovolné x ∈ Xf existuje b ∈ B tak, že (x, b) ∈ C; vyberme nějaké takové b a vložme dvojici
(x, b) do množiny X′
f . Podobně zkonstruujeme množinu Y ′
f . Konečně sup(X′
f ∪ Y ′
f ) ≥ c, kde X′
f ∪ Y ′
f ⊆ C.
Potom pro každý prvek c ∈ A × B, c = (a, b) vezměme množiny kompaktních prvků Xa ⊆ A a Yb ⊆ B
takových, že sup Xa = a a sup Yb = b, pak sup Xa × Yb = c a každý prvek je tedy supremem kompaktních
prvků.
• Podsvaz algebraického svazu není algebraický.
(P(N), ⊆) je algebraický svaz, ale podsvaz (P∞(N) ∪ {∅}, ⊆) není algebraický.
Příklad B7 (autor: V. Baisa)
Příloha mimo tento soubor.
Příklad B8,B9,B10,B11 (autor: Nemám kapacitu)
Návody: zkuste B9 idnukcí.
B10ii) funguje obecně, stačí ukázat, že
ρa,b = { ρ | ρ kongruence, (a, b) ∈ ρ }
je kompaktní prvek.
Příklad B12 (autor: O. Klíma, P. Troubil)
Úlohu vyřešíme rovnou obecně. Dokážeme, že pro každou podalgebru A Boolovy algebry (Pn, ∪, ∩, 0, 1,′
)
platí, že ty prvky Pn, které v A pokrývají 0, tvoří rozklad na množině Xn = {1, . . . , n}. Množinu těchto prvků
označme A0. Musíme ukázat, že prvky v A0 jsou neprázdné (zřejmé), disjunktní (část 1) jejichž sjednocení je
rovno Xn (část 2).
1) Nechť existuje takové i ∈ Xn a a = b ∈ A0, tak že i ∈ a ∩ b. Protože a, b jsou různé prvky pokrývající
v A prvek 0, musí v A platit a ∧ b = 0. To je spor s i ∈ a ∩ b = a ∧ b.
2) Předpokládejme, že A0 = C = Xn. Je zřejmé, že (v každém konečném svazu) lze ke každému prvku
x = 0 najít (důkaz indukcí) prvek y ≤ x, který pokrývá 0. V našem případě aplikujme tento poznatek na
12
prvek ( A0)′
= C′
svazu A. Podle předpokladu C′
= 0, tzn. existuje a ∈ A0, a ⊆ C′
. To je spor poněvadž
C′
= b∈A0
b′
⊆ a′
.
Výčet všech prvků, které pokrývají v podalgebře A prvek 0, jednoznačně určuje všechny prvky nosiče
této podlagebry. Podalgeber Boolovy algebry Pn existuje tedy právě tolik, kolik existuje rozkladů množiny
Xn = {1, . . ., n}. Tento počet udává n-té Bellovo číslo B(n). To může být vypočteno např. pomocí rekurzivního
vzorce
B(n + 1) =
n
k=0
n
k
B(k)
nebo formulí
B(n) =
1
e
∞
k=0
kn
k!
.
Konkrétně potom B(5) = 52.
Příklad B13 (autor: Nemám kapacitu)
Příklad B14 (autor: O. Klíma)
H: ne - netriviální příklad je uveden v B13.
S: ne, např N podsvaz (N0, |).
P: ano, lze dokázat, počítáme po složkách.
Příklad B15 (autor: Nemám kapacitu)
Je to jednoduché.
Příklad B16 (autor: Nemám kapacitu)
13