Algebra II, 1. termín, úloha A, 9. 6. 2008 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, 9. 6. 2008 Jméno : UČO : Kongruence svazů Dokažte, že svaz (Con L, ⊆) všech kongruencí svazu L = (L, ∧, ∨) je distributivní. Doplňte důkaz. Nechť α, β, γ ∈ Con L, a, b ∈ L, (a, b) ∈ α ∧ (β ∨ γ). Ukážeme, že (a, b) ∈ .......................................................... . Nechť tedy a α b. Existují n ∈ N, c0, . . ., c2n ∈ L tak, že a = c0 β c1 γ ................................................... . Pro x, y, z ∈ L klademe m(x, y, z) = (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x) . Ukažte, že m(x, x, y) = x : ............................................................................ Pro libovolné c je m(a, a, c) α m(a, ...., c). Dále pro lib. c, c platí m(a, b, c).....m(a, b, c ), neboť ........................................................................ Dále c β c dá m(a, b, c) β ................................. a podobně .............................................................. Platí m(a, b, c0) = .............., m(a, b, c2n) = .................... Konečně použijeme posloupnost m(a, b, c0), . . . , m(a, b, c2n) . ........................................................... Algebra II, 1. termín, úloha C, 9. 6. 2008 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. Algebra II, 2. termín, úloha A, 23. 6. 2008 Jméno : UČO : Věta o homomorfismu Uvažujme jazyk unárního operačního symbolu f a nulárního operačního symbolu c. (Veškeré výrazy typu σ ∈ Σ budou při opravě ignorovány ! ) Nechť A = (A, g, d), B = (B, h, e) jsou algebry našeho jazyka. a) Definujte homomorfismus algebry A do algebry B. b) Definujte podalgebru algebry A. c) Definujte kongruenci algebry A. d) Definujte faktorovou algebru a tzv. přirozený homomorfismus. e) Dokažte, že pro homomorfismus α : A → B je ker α = ..................... kongruencí algebry .................. Skutečně, f) Ukažte, že im α = ............................... je nosičem podalgebry algebry .... Skutečně, g) Doplňte a dokažte : libovolný homomorfismus α : A → B lze psát ve tvaru α = ι ◦ β ◦ (ker α) , kde ι, β jsou definovány vztahy : a mají následující vlastnosti : Dokažte korektnost definice zobrazení β : h) Části e) - g) ilustrujte na příkladě A = ({0, 1, 2, 3, a, b}, g, 3), B = ({p, q, r}, h, q), kde g(a) = 0, g(b) = 2, g(0) = 1, g(1) = 2, g(2) = 3, g(3) = 0, h(p) = q, h(q) = r, h(r) = q. Zvolte si libovolný homomorfismus α. Algebra II, 2. termín, úloha B, 23. 6. 2008 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, 2. termín, úloha C, 23.6. 2008 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, 3. termín, úloha A, 1.7. 2008 Jméno : UČO : Uvažujme jazyk jediné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, 3. termín, úloha B, 1.7. 2008 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 isomorfní s B | a × B | a Použijete-li někde nějaké lemma z přednášky, musíte je zformulovat. Algebra II, 3. termín, úloha C, 1.7. 2008 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.