Algebra II – jaro 2024 – 2. termín
Všechna svoje tvrzení precizně zdůvodněte.
1. (10 bodů) Popište svaz podalgeber algebry (Z, ∗), kde ∗ je binární operace definovaná
předpisem
a ∗ b =



a + 1, pokud a = b < 0,
−a, pokud a < b ≤ 0,
a − 1, pokud a = b a a > 0,
b, jinak.
2. (5 bodů) Uvažujme množinu L, jejímiž prvky jsou všechna uspořádání ≤ na množině
N taková, že uspořádaná množina (N, ≤) je svaz. Rozhodněte, zda přidáním
největšího a nejmenšího prvku k uspořádané množině (L, ⊆) získáme svaz.
3. (5 bodů) Uvažujme množinu L ⊆ P(N), jejímiž prvky jsou ∅ a všechny množiny
Ma,b = { a + k · b | k ∈ N0 }, kde a a b jsou libovolná kladná celá čísla. Rozhodněte,
zda uspořádaná množina (L, ⊆) je úplný svaz.
4. (5 bodů) Uvažujme množinu L, jejímiž prvky jsou všechny relace ekvivalence ∼
na množině N takové, že tříd rozkladu N podle ∼ je nekonečně mnoho. Rozhodněte,
zda přidáním největšího prvku k uspořádané množině (L, ⊆) získáme algebraický
svaz.
5. (10 bodů) Pro libovolné slovo w ∈ {a, b}∗
označme
• P(w) nejdelší slovo u ∈ {a}∗
∪ {b}∗
takové, že w = uv pro nějaké v ∈ {a, b}∗
,
• S(w) nejdelší slovo u ∈ {a}∗
∪ {b}∗
takové, že w = vu pro nějaké v ∈ {a, b}∗
,
• F(w) největší n takové, že w = ucn
v pro nějaké c ∈ {a, b} a u, v ∈ {a, b}∗
.
Pro každý z následujících předpisů rozhodněte, zda definuje kongruenci volného
monoidu ({a, b}∗
, ·):
w ∼ w ⇐⇒ P(w) = P(w ) & S(w) = S(w ) & F(w) = F(w ),
w ≈ w ⇐⇒
w ∼ w , pokud w, w /∈ {a}∗
∪ {b}∗
,
w = w , jinak.
6. (10 bodů) Uvažujme typ algeber sestávající z unárních operačních symbolů f
a g. Algebra
A = (P({a, b}∗
× {a, b}∗
), fA
, gA
)
má operace pro libovolnou binární relaci ρ na {a, b}∗
definovány předpisy fA
(ρ) =
ρ ◦ ρ a gA
(ρ) = { s t | s, t ∈ ρ }, přičemž značí operaci na součinu volných
monoidů ({a, b}∗
, ·)×({a, b}∗
, ·). Pro každou z následujících podalgeber algebry A
rozhodněte, zda je v ní splněna identita f(g(x)) = g(f(x)).
a) Podalgebra B obsahuje právě všechny podmnožiny identity na {a, b}∗
.
b) Podalgebra C obsahuje právě všechny konečné relace na {a, b}∗
.
7. (15 bodů) Rozhodněte, na které z operátorů H, S a P je uzavřená třída všech
svazů takových, že buď jsou konečné, nebo každý jejich prvek náleží do nekonečného
řetězce.