Algebra II, 1. termín, úloha A, 27. 5. 2009 Jméno : UČO : Identity v podalgebrách (Žádné σ ∈ Σ !) Uvažujeme jazyk unárního operačního symbolu f a nulárního operačního symbolu c a v něm algebry A = (A, p, d) a B = (B, q, e). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. ........................................................................ b) Lze termy psát v nějakém kompaktním tvaru ? ........................................................................ c) Definujte (induktivně) realizaci tA,n termu t ∈ Tn v algebře A. ........................................................................ d) Algebra B je podalgebrou algebry A, platí-li ........................................................................ e) Je-li navíc t ∈ Tn, b1, . . . , bn ∈ B, máme tB,n (b1, . . . , bn) = ..................................... f) Dokažte tvrzení z e). .......................................................................... .......................................................................... g) Nechť dále je u ∈ Tn, nechť A |= t u. Pak též ...................................................................... h) Dokažte tvrzení z g). ......................................................................... ......................................................................... i) Identity v našem jazyce jsou čtyř typů. Popište je. ....................................................................... ....................................................................... j) Nechť algebra A je konkretizována takto: A = {0, 1, 2}, p(0) = 1, p(1) = 2, p(2) = 0, d = 0. Pro každý typ charakterizujte identity, které jsou v A splněny. ......................................................................... ......................................................................... Algebra II, 1. termín, úloha B, 27. 5. 2009 Jméno : UČO : Svazy kongruencí. Je dána monounární algebra A = (A, f). Nechť Con A značí množinu všech jejích kongruencí. Nechť pro relace ρ, σ na množině A je ρ ◦ σ = { (a, c) ∈ A × A | existuje b ∈ A splňující a ρ b σ c } . Relace ρ, σ jsou záměnné, je-li σ ◦ ρ = ρ ◦ σ. a) Dokažte, že (Con A, ⊆) je úplný svaz. b) Pro ρ, σ ∈ Con A máme ρ ∧ σ = ................... ρ ∨ σ = ................... c) Pro záměnné kongruence máme ρ ∨ σ = ................... d) Dokažte : Nechť algebra A má libovolné dvě kongruence záměnné. Pak je svaz (Con A, ∧, ∨) modulární. Skutečně, nechť ρ, σ, τ ∈ Con A, ρ ..................... Máme ukázat, že ρ ∨ (σ ∧ τ) ......................... Nechť tedy (a, b) ∈ .................................................... Existuje c ∈ A tak, že ............................................ Hledáme d ∈ A tak, aby ............................................ Stačí vzít ...................................................... neboť ............... , .............. a ............. plyne z ........... , ............ e) Nechť A = {a, b, p, q}, f(a) = b, f(b) = a, f(p) = q, f(q) = p. Popište (Con A, ⊆). f) Tento svaz je/není (zakroužkujte správnou odpověď) modulární a proto (vyberte) - i) existuje dvojice kongruencí, které nejsou záměnné - ii) ze znalosti svazu na izomorfismus nelze nic usoudit o záměnnosti kongruencí. g) V případě i) takovou dvojici ρ, σ najděte a uveďte jak vypadá ρ ◦ σ a σ ◦ ρ (například namaluje relace jako orientované grafy). V případě ii) dejte příklad algebry B, která má svaz kongruencí (Con B, ⊆) izomorfní s (Con A, ⊆), přičemž .................................. Algebra II, 1. termín, úloha C, 27. 5. 2009 Jméno : UČO : a) Je třída všech unárních algeber (A, f), kde f ◦ f = f, uvažovaná v jazyku jediného unárního operačního symbolu uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Na množině Z uvažujeme binární operaci sčítání a unární operaci f danou předpisem f(x) = x2 . Dále je ρ relace na množině Z definovaná vztahem pro a, b ∈ Z máme a ρ b ⇐⇒ 7 | (a − b) . Je tato relace ρ kongruencí algebry (Z, +, f) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině Q uvažujeme unární operaci f danou předpisem f(x) = x + 1, x ∈ Q. Rozhodněte, zda jsou unární algebry Q = (Q, f) a Q × Q izomorfní. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) Záporné body se počítají pouze v rámci úlohy C, tj. minimální možný počet bodů za tuto úlohu je 0. V případě nedostatku místa pokračujte na zadní stranu. Algebra II, 2. termín, úloha A, 19.6. 2009 Jméno : UČO : Uvažujme jazyk jediného unárního operačního symbolu f. (Veškeré výrazy typu σ ∈ Σ budou při opravě ignorovány !) a) Připomeňte definici součinu systému množin (Ai)i∈I. ( I je libovolná množina ! ) ................................................................. b) Algebra A = (A, g) je součinem systému (Ai = (Ai, gi))i∈I , jestliže ................................................................ ................................................................ c) Algebra A = (A, g) je podpřímým součinem systému (Ai = (Ai, gi))i∈I , jestliže ................................................................ ................................................................ d) Nechť A a B jsou algebry s neprázdnými nosiči a nechť C je jejich podpřímý součin. Nechť σ je identita. U jednotlivých tvrzení vyznačte zda platí či nikoliv. (i) (A nebo B splňuje σ) =⇒ C splňuje σ, (ii) C splňuje σ =⇒ (A nebo B splňuje σ), (iii) (A i B splňují σ) =⇒ C splňuje σ, (iv) C splňuje σ =⇒ (A i B splňují σ). e) Doplňte a dokažte. Nechť A je podpřímým součinem systému (Ai)i∈I. Pak i∈I ker.................. ..................................................................... ..................................................................... .................................................................... f) Algebra A je podpřímo nerozložitelná, platí-li ................................................................... ................................................................... g) Pro která n ∈ N je algebra An = (Zn, g), kde g(a) = a + 1, podpřímo nerozložitelná ? ....................................................................... h) Dokažte tvrzení z g). ....................................................................... ....................................................................... i) Rozložte algebru A12 na podpřímý součin podpřímo nerozložitelných algeber. ....................................................................... ....................................................................... Algebra II, 2. termín, úloha B, 19.6. 2009 Jméno : UČO : Booleovy algebry Booleova algebra je uspořádaná šestice B = (B, ∧, ∨,′ , 0, 1), kde (B, ∧, ∨) je distributivní svaz, ’ je unární a 0,1 jsou nulární operace na množině B splňující : pro libovolné b ∈ B je b ∧ 0 = 0, b ∨ 1 = 1, b ∧ b′ = 0, b ∨ b′ = 1. Pro Booleovu algebru B a a ∈ B nechť B | a = ([0, a], ∧, ∨, ∗ , 0, a), kde [0, a] = {b ∈ B | b ≤ a}, b∗ = a ∧ b′ . a) Dokažte, že B | a je též Booleova algebra. b) Dokažte, že zobrazení αa : B → [0, a], b → a ∧ b je surjektivní homomorfismus B na B | a. c) Dokažte, že algebra B je izomorfní s B | a × B | a′ Použijete-li někde nějaké lemma z přednášky, musíte je zformulovat. Algebra II, 2. termín, úloha C, 19.6. 2009 Jméno : UČO : a) Je třída všech grupoidů (S, ·) v nichž existuje neutrální prvek, uvažovaná v jazyku jediného binárního operačního symbolu, uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Nechť Σ je konečná množina a (Σ∗ , ·) je monoid všech slov nad Σ s operací zřetězení. Nechť ρ je relace na množině Σ∗ definovaná vztahem u ρ v právě když ( ∀ a ∈ Σ ) ( u ∈ Σ∗ aΣ∗ ⇐⇒ v ∈ Σ∗ aΣ∗ ) . Je relace ρ kongruencí monoidu (Σ∗ , ·) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině Z uvažujeme unární operaci f danou předpisem f(x) = x+1. Rozhodněte, zda jsou unární algebry Z = (Z, f) a Z × Z izomorfní. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) Záporné body se počítají pouze v rámci úlohy C, tj. minimální možný počet bodů za tuto úlohu je 0. V případě nedostatku místa pokračujte na zadní stranu. Algebra II, 1. termín, úloha A, 26.6. 2009 Jméno : UČO : Reprezentace konečných distributivních svazů a) Algebraicky definovaný svaz L = (L, ∧, ∨) je svazem ve smyslu uspořádaných množin, klademe-li a ≤ b ⇐⇒ ......................................................... . b) Nechť L = (L, ∧, ∨) je svaz. Prvek a ∈ L je spojově ireducibilní, jestliže ............................................................... Množinu všech spojově ireducibilních prvků svazu L s vyjímkou nejmenšího (pokud existuje) značíme J(L). c) Nakreslete diagram uspořádané množiny (J(K), ≤) pro svaz K d) Nechť A = (A, ≤) je uspořádaná množina. Množina X ⊆ A je dědičná, jestliže .......................................................................... Množinu všech dědičných podmnožin značíme H(A). e) Doplňte větu : Konečný distributivní svaz L = (L, ≤) je izomorfní s množinou ..................................................................... s uspořádáním ....................................................... f) Doplnění důkazu : Uvažujeme zobrazení ξ : L → ................., a → ............................... Vzhledem k tomu, že svaz L je ......................, platí pro lib. a ∈ L, že a = sup ξ(a). Odtud zejména plyne, že zobrazení ξ je ............................. a že platí ξ(a) ≤ ξ(b) implikuje a ≤ b. Zřejmě též a ≤ b dá .............................. Zbývá ukázat, že zobrazení ξ je ............................. Skutečně, nechť X = {.................................} ∈ ................. Položme a = sup X. Pak ξ(a) ⊇ X. Nechť konečně y ∈ ξ(a). Pak ........................................................................ ........................................................................ ........................................................................ g) Uveďte diagram uspořádané množiny, kterou jste doplnili do e), pro náš konkrétní příklad svazu K. h) Sledujte důkaz z f) a uveďte zcela konkrétně, co v případě svazu K neprošlo. Algebra II, 1. termín, úloha B, 26.6. 2009 Jméno : UČO : Syntaktický semiring Nechť A = {a, b}, a = b. Nechť (A∗ , ·) je volný monoid nad A a nechť P je množina všech konečných podmnožin množiny A∗ s násobením {u1, . . . , uk} · {v1, . . . , vl} = {u1v1, . . . , u1vl, . . . , ukv1, . . . , ukvl} . a) Definujte kongruenci algebry P = (P, ·, ∪). b) Nechť L ⊆ A∗ . Ukažte, že relace ∼L definovaná vztahem {u1, . . . , uk} ∼L {v1, . . . , vl} ⇐⇒ ( ∀ p, q ∈ A∗ ) ( pu1q, . . . , pukq ∈ L ⇐⇒ pv1q, . . . , pvlq ∈ L ) je kongruencí algebry P. c) Jak vypadá P/ ∼L pro L = {an | n ≥ 0} ? d) Pro n ∈ N v P určete < {an } >. e) Najděte všechny automorfismy algebry P. f) Pro která r, s, t ≥ 0 algebra P splňuje identitu xr (y ∪ z) = xs y ∪ xt z ? – zdůvodněte Body : vše po 5 Algebra II, 1. termín, úloha C, 26.6. 2009 Jméno : UČO : a) Je třída všech unárních algeber (A, f), kde f : A → A je bijekce, která je sama k sobě inverzní, uvažovaná v jazyku jediného unárního operačního symbolu uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Nechť S je alespoň dvouprvková množina a operace · a ◦ na této množině jsou dány takto: pro libovolná a, b ∈ S platí a · b = a, a ◦ b = b. Rozhodněte, zda jsou grupoidy (S, ·) a (S, ◦) izomorfní. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Předně si uvědomme, že každé přirozené číslo n ∈ N lze jednoznačným způsobem zapsat ve tvaru 2x−1 (2y − 1) kde x, y ∈ N. Rozhodněte, zda zobrazení α : N → N × N definované předpisem α(2x−1 (2y − 1)) = (x, y) je homomorfismus grupoidu N = (N, +) do grupoidu N × N. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) Záporné body se počítají pouze v rámci úlohy C, tj. minimální možný počet bodů za tuto úlohu je 0. V případě nedostatku místa pokračujte na zadní stranu.