Algebra II – jaro 2019 – 4. termín
Všechna svoje tvrzení precizně zdůvodněte.
Všechna uspořádání posloupností v tomto zadání jsou obvyklá uspořádání po složkách,
tj. (rn)∞
n=1 ≤ (sn)∞
n=1 platí právě tehdy, když rn ≤ sn pro všechna n ∈ N.
1. (10 bodů) Popište svaz podalgeber algebry (N × N, ⊕), kde ⊕ je binární operace
definovaná předpisem
(a, b) ⊕ (c, d) =



(a, b) pokud a = c a b = 1,
(a, b − 1) pokud a = c a b ≥ 2,
(a, b + 1) pokud a < c,
(c + 1, d) pokud a > c.
2. (5 bodů) Uvažujme uspořádanou množinu, jejímiž prvky jsou všechny posloupnosti
reálných čísel (rn)∞
n=1, které jsou zpočátku rostoucí a poté nerostoucí (tj. existuje
n ∈ N takové, že pro všechna k, ∈ N platí implikace k < ≤ n =⇒ rk < r
a n ≤ k < =⇒ rk ≥ r ). Rozhodněte, zda tato uspořádaná množina je svaz.
3. (5 bodů) Nechť A je množina všech nekonečných množin přirozených čísel, které
neobsahují žádná soudělná čísla. Rozhodněte, zda přidáním nejmenšího a největšího
prvku k uspořádané množině (A, ⊆) vznikne úplný svaz.
4. (5 bodů) Uvažujme uspořádanou množinu ({ (A, B) | A ⊆ B ⊆ N } ∪ {⊥}, ≤),
kde ⊥ je nejmenší prvek a na ostatních prvcích je uspořádání dáno předpisem
(A, B) ≤ (C, D) ⇐⇒ A ⊇ C & B ⊆ D.
Rozhodněte, zda tato uspořádaná množina je algebraický svaz.
5. (10 bodů) Na množině N∗
všech konečných slov nad abecedou N uvažujme binární
operaci zřetězení · a binární operaci , která každým dvěma slovům přiřadí
nejdelší slovo, které je prefixem obou. Pro slovo w označme f(w) slovo vzniklé z w
ponecháním pouze prvního výskytu každého písmene. Rozhodněte, zda relace ∼
definovaná předpisem
v ∼ w ⇐⇒ f(v) = f(w)
je kongruencí algebry a) (N∗
, ·), b) (N∗
, ).
(Prefix slova w je libovolné slovo u takové, že existuje slovo v splňující uv = w.)
6. (10 bodů) Uvažujme typ algeber sestávající ze dvou unárních operačních symbolů
f a g a jednoho binárního symbolu ⊗. Rozhodněte, která z následujících identit
je splněna v algebře A, jejíž nosnou množinou je množina P(NN
) všech množin
posloupností přirozených čísel a operace jsou pro libovolné množiny M, N ⊆ NN
definovány předpisy
fA
(M) = { (1, a1, a2, a3, . . . ) | (a1, a2, a3, . . . ) ∈ M },
gA
(M) = { (a2, a3, . . . ) | (a1, a2, a3, . . . ) ∈ M },
M ⊗A
N = { p ∈ NN
| ∃ q ∈ M ∃ r ∈ N : q ≤ p ≤ r }.
a) f(x) ⊗ f(y) = f(x ⊗ y),
b) g(x) ⊗ g(x) = g(x ⊗ x).
7. (15 bodů) Rozhodněte, na které z operátorů H, S a P je uzavřená třída všech
svazů, které neobsahují nekonečný rostoucí řetězec a1 < a2 < a3 < · · · .