Algebra II – jaro 2024 – 1. termín
Všechna svoje tvrzení precizně zdůvodněte.
1. (10 bodů) Popište svaz podalgeber algebry (N, ∗) kladných celých čísel spolu
s binární operací ∗ definovanou předpisem
a ∗ b =



2a, pokud a = b = 1 a (a | b nebo b | a),
1, pokud a b a b a,
a + 1, pokud b = 1,
b, pokud a = b = 1.
2. (5 bodů) Uvažujme množinu L, jejímiž prvky jsou všechny relace ekvivalence ∼
na množině N takové, že všechny třídy rozkladu N podle ∼ mají stejnou mohutnost.
Rozhodněte, zda uspořádaná množina (L, ⊆) je svaz.
3. (5 bodů) Na množině Pfin(N) všech konečných podmnožin množiny přirozených
čísel je definováno uspořádání ≤, kde A ≤ B platí právě tehdy, když existuje
injektivní zobrazení f : A → B takové, že pro všechna a ∈ A je splněno a ≤ f(a).
Rozhodněte, zda přidáním největšího prvku k uspořádané množině (Pfin(N), ≤)
získáme úplný svaz.
4. (5 bodů) Uvažujme množinu L ⊆ P(N), jejímiž prvky jsou právě množiny kladných
celých čísel M ⊆ N takové, že pro všechna a, b ∈ M platí podmínka a+b /∈ M
a současně platí alespoň jedna z podmínek a+2b /∈ M a a+6b ∈ M. 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ů) Na množině P(N × N) uvažujme unární operace f, g a h dané pro
libovolnou relaci ρ ⊆ N × N předpisy
f(ρ) = ρ−1
, g(ρ) = ρ−1
◦ ρ, h(ρ) = { (2m, 2n) | (m, n) ∈ ρ }.
Dále na množině P(N × N) uvažujme relaci ekvivalence ∼, kde ρ ∼ σ platí právě
tehdy, když relace ρ a σ generují stejnou relaci ekvivalence na N. Pro každou
z následujících algeber rozhodněte, zda ∼ je její kongruencí:
a) A = (P(N × N), f, g)
b) B = (P(N × N), ∪, h)
6. (10 bodů) Uvažujme typ algeber sestávající z binárních operačních symbolů •,
a a unárního operačního symbolu f. Pro každou z následujících identit rozhodněte,
zda je splněna v algebře
A = (P({a, b}∗
), •A
, A
, A
, fA
),
jejíž operace jsou pro libovolné jazyky K a L nad abecedou {a, b} definovány předpisy
K•A
L = K∪L, K A
L = K·L, K A
L = { v ∈ {a, b}∗
| (∃u ∈ K)(uv ∈ L) }
a fA
(L) = { vR
| v ∈ L }, kde vR
značí obrácení slova v, tj. (c1 . . . cn)R
= cn . . . c1.
a) x (x • f(x)) = (x x) • f(x x)
b) ((x x) x) • ((x x) x) = x (x x)
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 každé dva nesrovnatelné prvky a, b ∈ L jsou pokryty svým
supremem, tj. neexistuje prvek c ∈ L splňující a < c < a ∨ b.