Algebra II – jaro 2019 – 2. termín
Všechna svoje tvrzení precizně zdůvodněte.
1. (10 bodů) Popište svaz podalgeber algebry (A, ∪, \, m, f), kde množina A sestává
právě z množin přirozených čísel B ⊆ N takových, že jedna z množin B a N \ B
je konečná, unární operace m zobrazuje každou neprázdnou množinu B ⊆ N na
jednoprvkovou množinu obsahující pouze nejmenší prvek množiny B, m(∅) = ∅ a
f je unární operace definovaná předpisem
f(B) = { n ∈ N | ∃ k, ∈ B : k ≤ n ≤ }.
2. (5 bodů) Uvažujme uspořádanou množinu, jejímiž prvky jsou největší prvek ,
nejmenší prvek ⊥ a všechny dvojice (A, a), kde a ∈ A ⊆ N, přičemž (A, a) ≤ (B, b)
platí právě tehdy, když A ⊆ B a a ≤ b. 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 reálných čísel (ai)∞
i=1, které splňují pro
všechna i ∈ N podmínku
(∀j > i: ai ≤ aj) & (∃j > i: 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ů) Na množině
L = { (A, B) ∈ P(N) × P(N) | A ∩ B = ∅ nebo A = N }
je definováno uspořádání předpisem
(A, B) ≤ (C, D) ⇐⇒ A ⊆ C & B ⊆ D.
Rozhodněte, zda uspořádaná množina (L, ≤) je algebraický svaz.
5. (10 bodů) Nechť A je množina všech konečných slov nad nekonečnou abecedou
{a1, a2, . . . }, která obsahují alespoň dvě různá písmena. Na A uvažujme binární
operaci zřetězení · a unární operaci f, která každé slovo zobrazí na jeho podslovo
složené z prvních výskytů písmen. Pro každé slovo w ∈ A definujme P(w) jako
množinu všech podslov slova w délky 2 složených z různých písmen, tj. množina
P(w) obsahuje právě slova ab taková, že a = b a existují slova s, t, u splňující
satbu = w. Rozhodněte, zda relace ∼ definovaná předpisem
v ∼ w ⇐⇒ P(v) = P(w)
je kongruencí algebry a) (A, ·), b) (A, f).
6. (10 bodů) Uvažujme typ algeber sestávající z nulárního operačního symbolu 0
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 je P({a, b}∗
× {a, b}∗
), tj.
množina všech binárních relací na množině všech slov nad dvoupísmennou abecedou
{a, b}, konstanta 0A
je definována jako identita, operace •A
je kompozice,
operace ∗A
je průnik a operace ⊕A
je definována jako zřetězení po složkách, tj.
ρ ⊕A
σ = { (uu , vv ) | (u, v) ∈ ρ, (u , v ) ∈ σ) }.
a) (x ⊕ y) • (x ⊕ y) = (x • x) ⊕ (y • y),
b) (x ⊕ 0) ∗ 0 = (x ∗ 0) ⊕ 0.
7. (15 bodů) Rozhodněte, na které z operátorů H, S a P je uzavřená třída všech
svazů, které buď nemají žádný prvek, nebo obsahují největší a nejmenší prvek a
každý jejich prvek má nejvýše jeden komplement.