Algebra II – jaro 2019 – 1. termín
Všechna svoje tvrzení precizně zdůvodněte.
1. (10 bodů) Popište svaz podalgeber algebry (N, ∗, •), kde ∗ a • jsou binární operace
definované předpisy
a ∗ b =



a + 2b, pokud je b liché,
a + 2, pokud jsou a i b sudá,
a, pokud je a liché a b sudé,
a • b =



nsd(a, b), pokud jsou a i b lichá,
a − 2, pokud je a sudé, a = 2 a b liché,
b, jinak.
2. (5 bodů) Uvažujme uspořádanou množinu, jejímiž prvky jsou všechny posloupnosti
přirozených čísel (ai)∞
i=1, přičemž (ai)∞
i=1 ≤ (bi)∞
i=1 platí právě tehdy, když
pro všechna i ∈ N platí bi ≥ ai a posloupnost (bi − ai)∞
i=1 je neklesající (tj. pro
všechna i < j platí bi − ai ≤ bj − aj). Rozhodněte, zda tato uspořádaná množina
je svaz.
3. (5 bodů) Uvažujme uspořádanou množinu, jejímiž prvky jsou největší prvek ,
nejmenší prvek ⊥ a všechny posloupnosti celých čísel (ai)∞
i=1, které jsou buď rostoucí
(tj. pro všechna i < j platí ai < aj), nebo klesající (tj. pro všechna i < j
platí ai > aj), přičemž (ai)∞
i=1 ≤ (bi)∞
i=1 platí právě tehdy, když pro všechna i ∈ N
platí ai ≤ bi. Rozhodněte, zda tato uspořádaná množina je úplný svaz.
4. (5 bodů) Uvažujme uspořádanou množinu, jejímiž prvky jsou nejmenší prvek ⊥
a všechny binární relace ρ na množině N takové, že pro všechna a ∈ N existuje
b ∈ N splňující (b, a) ∈ ρ, přičemž tyto relace jsou uspořádané inkluzí. Rozhodněte,
zda tato uspořádaná množina je algebraický svaz.
5. (10 bodů) Nechť A = P({a, b}∗
) je množina všech jazyků nad dvoupísmennou
abecedou. Na A uvažujme unární operace f, g a h, kde jazyk f(L) sestává ze všech
faktorů slov jazyka L ∈ A, jazyk g(L) sestává ze všech prefixů slov jazyka L a jazyk
h(L) sestává ze všech slov z {a, b}∗
, jejichž každý faktor patří do L. Rozhodněte,
zda relace ∼ definovaná předpisem
K ∼ L ⇐⇒ g(K) = g(L)
je kongruencí algebry a) (A, f), b) (A, h).
(Faktorem slova w rozumíme podslovo tvořené po sobě následujícími písmeny
slova w a prefixem rozumíme faktor tvořený několika počátečními písmeny.)
6. (10 bodů) Uvažujme typ algeber sestávající z unárního operačního symbolu f
a tří binárních operačních symbolů •, ∗ a ⊕. Rozhodněte, která z následujících
identit je splněna v algebře A, jejíž nosnou množinou A je množina všech podsvazů
svazu (N, |), operace •A
a ∗A
jsou definovány jako supremum a infimum ve svazu
(A, ⊆), operace fA
je pro libovolný podsvaz K ∈ A definována předpisem
fA
(K) = { a ∈ N | ∃ b ∈ K : a dělí b }
a pro libovolné podsvazy K, L ∈ A je K ⊕A
L definováno jako podsvaz generovaný
množinou { nsn(a, b) | a ∈ K, b ∈ L }, tj. K ⊕A
L obsahuje právě čísla
nsd(nsn(a1, b1), . . . , nsn(an, bn))
pro libovolná n ∈ N, a1, . . . , an ∈ K a b1, . . . , bn ∈ L.
a) (x • y) ∗ z = (x ∗ z) • (y ∗ z),
b) f(x) ⊕ f(y) = f(x ⊕ y).
7. (15 bodů) Rozhodněte, na které z operátorů H, S a P je uzavřená třída všech
svazů L takových, že pro každý prvek a ∈ L, který není nejmenší, existuje prvek
b ∈ L pokrytý a (tj. takový, že b < a a neexistuje c ∈ L splňující b < c < a).