Algebra II, 1. termín, úloha A, 3.6. 2003 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 0 a b c 1 d e f g h 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, 3.6. 2003 Jméno : UČO : Volná algebra Levý normální band je idempotentní pologrupa splňující identitu xyz = xzy. a) Identita xi1 . . . xik = xj1 . . . xjl je splněna ve všech levých normálních bandech právě když ..................................................................... b) Dokažte, že množina F = { (a, A) | a ∈ A ⊆ M, A konečná } spolu s operací (a, A) ◦ (b, B) = (a, A ∪ B) je volný levý normální band nad množinou M vzhledem k ι : a → (a, {a}). (i) (F, ◦) je levý normální band : .................................................................... .................................................................... .................................................................... (ii) Množina ι(M) generuje (F, ◦), neboť libovolný prvek množiny F lze psát jako .................................................................... (iii) Nechť (S, ) je levý normální band a nechť α : M → S je zobrazení. Položme β : F → S, ........................................................ → ................................................................ Zobrazení β je definováno korektně, neboť .........................................................................., je to homomorfismus, neboť ........................................................................... .......................................................................... Konečně βι = ...................................................., neboť ....................................... c) Kolik má pologrupa F prvků pro |M| = n ∈ N ? ............................................................................ Algebra II, 1.termín, úloha C, 3.6. 2003 Jméno : UČO : a) Je třída všech unárních algeber (A, f), kde f : A → A je bijekce, uvažovaná v jazyku jediného unárního operačního symbolu uzavřená na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Nechť P (N) značí množinu všech neprázdných podmnožin množiny N. Rozhodněte, zda zobrazení α : P (N) → N, X → minX je grupoidový homomorfismus (P (N), ∪) → (N, min) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině R definujeme relaci ρ vztahem a ρ b ⇐⇒ a − b ∈ Z . Je tato relace kongruencí okruhu (R, +, ·) ? (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, 10.6. 2003 Jméno : UČO : Identity v monounárních algebrách Uvažujeme jazyk jediného unárního operačního symbolu f a v něm algebry A = (A, g) a B = (B, h). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. (Žádné σ ∈ Σ !) ........................................................................ V našem případě je lze psát ve tvaru .............................................. b) Definujte (induktivně) realizaci t ∈ Tn v algebře A. ........................................................................ c) Zobrazení α : .................... je homomorfismem algebry A do algebry B, platí-li ........................................................................ d) Je-li navíc a1, . . . , an ∈ A, máme α(tA,n (a1, . . . , an)) = ..................................... e) Dokažte tvrzení z d). .......................................................................... .......................................................................... f) Nechť dále je u ∈ Tn, nechť A |= t u a nechť α je ...................................................................... Pak ......................................................................... g) Dokažte tvrzení z f). ......................................................................... ......................................................................... h) Nechť algebra A je konkretizována takto: A = {a, b, c, d, e}, g(a) = b, g(b) = c, g(c) = d, g(d) = e, g(e) = d. Charakterizujte identity, které jsou v A splněny ......................................................................... ......................................................................... i) Nechť A je jako v bodě h), nechť p ∈ B. Kdy lze přiřazení a → p rozšířit do homomorfismu algebry A do algebry B ? Právě když ................................................................... Algebra II, 2. termín, úloha B, 10.6. 2003 Jméno : UČO : Pseudokomplementární svazy Svaz L = (L, ∧, ∨) s nejmenším prvkem, ozn. 0, se nazývá pseudokomplementární jestliže pro libovolné a ∈ L existuje a∗ ∈ L tak, že ( ∀ b ∈ L ) a ∧ b = 0 ⇐⇒ b ≤ a∗ . Dokažte (týká se to bodů a) - c) ): a) Každá Booleova algebra (L, ∧, ∨, 0, 1, ) je pseudokomplementárním svazem. Důkaz: Pro a ∈ L položíme a∗ = ..................... Nechť b ∈ L, a ∧ b = 0, pak ............................................................................ Nechť naopak b ≤ a∗ . Pak ........................................................................... b) Každý omezený řetězec je pseudokomplementární. ........................................................................... ........................................................................... c) Každý konečný distributivní svaz je pseudokomplementární. (Návod: asi se Vám bude hodit množina C = {b ∈ L | a ∧ b = 0}.) .......................................................................... .......................................................................... Dejte příklad (týká se to bodů d) a e) ): d) Konečného omezeného svazu, který není pseudokomplementární. .......................................................................... e) Distributivního svazu, který není pseudokomplementární. .......................................................................... .......................................................................... .......................................................................... Algebra II, 2. termín, úloha C, 10.6. 2003 Jméno : UČO : a) Je třída všech konečných těles v jazyce binárních operačních symbolů +, · a nulárního operačního symbolu 1 uzavřená na operátor P ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Uvažujme algebru N = (N, +, ), kde a = a + 1. Je zobrazení α : a → a + 1 jejím endomorfismem ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině Z definujeme relaci ρ vztahem a ρ b ⇐⇒ a2 = b2 . Je tato relace kongruencí grupoidu (Z, ·) ? (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, 2.7. 2003 Jméno : UČO : Identity v biunárních algebrách Uvažujeme jazyk dvojice unárních operačních symbolů f a g a v něm algebry A = (A, p, q) a B = (B, r, s). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. (Žádné σ ∈ Σ !) ........................................................................ b) Nechť M = {f, g}∗ je volný monoid nad množinou {f, g}. Prvky Tn lze psát ve tvaru ........................................................................ c) Definujte (induktivně) realizaci tA,n termu t ∈ Tn v algebře A. ........................................................................ d) Zobrazení α : .................... je homomorfismem algebry A do algebry B, platí-li ........................................................................ e) Je-li navíc a1, . . . , an ∈ A, máme α(tA,n (a1, . . . , an)) = ..................................... f) Dokažte tvrzení z d). .......................................................................... .......................................................................... g) Nechť dále je u ∈ Tn, nechť A |= t u a nechť α je ...................................................................... Pak ......................................................................... h) Dokažte tvrzení z f). ......................................................................... ......................................................................... i) Nechť algebra A je konkretizována takto: A = {0, 1, 2}, p(0) = 1, p(1) = 2, p(2) = 0, q(0) = 2, q(1) = 0, q(2) = 1. Charakterizujte identity, které jsou v A splněny ......................................................................... j) Nechť A je jako v bodě i). Charakterizujte identity, které nejsou v A splněny ......................................................................... Algebra II, 3. termín, úloha B, 2.7. 2003 Jméno : UČO : Vztahy mezi uspořádanými množinami a distributivními svazy Pro uspořádanou množinu A = (A, ≤) nechť H (A) značí množinu všech jejích dědičných podmnožin. Nechť pro svaz L = (L, ∧, ∨) je J(L) množinou všech jeho spojově ireducibilních prvků s (eventuální) výjimkou nejmenšího. Dokážeme, že pro konečné A platí : A je izomorfní s (J(H (A), ⊆), ≤) . Definujeme zobrazení β : a → ........................................................., a ∈ A. β skutečně vede tam, kam potřebujeme .................................................................... .................................................................... .................................................................... Dále : β splňuje a ≤ b ⇐⇒ ................................ neboť .......................... dá ............................. a ............................ dá ............................. Odtud zejména plyne, že β je .................................. Zbývá ukázat, že β je ......................................... Skutečně, ....................................................... ................................................................ ................................................................ ................................................................ ................................................................ Demonstrujte tvrzení pro A = {0, a, b, 1}, 0 < a, b < 1, a, b nesrovnatelná. Platí tvrzení pro (Q, ≤)? Analyzujte situaci. Pokračujte na opačné straně Algebra II, 3. termín, úloha C, 2.7. 2003 Jméno : UČO : a) Množina P (A) všech podmnožin množiny A tvoří vzhledem k “přirozeným” operacím Booleovu algebru. Je P (N) podalgebrou algebry P (Q) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Uvažujme algebru N = (N, s), kde s(a) = a + 1. Je relace (a, b) ρ (c, d) ⇐⇒ a + b = c + d kongruencí algebry N × N ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Je zobrazení α : Z[x, y] → Z, f → absolutní člen f homomorfismem okruhu (Z[x, y], +, ·) do okruhu (Z, +, ·) ? (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.5. 2004 Jméno : UČO : Uvažujme jazyk binárního operačního symbolu ◦. a) Definujte termy. ...................................................................... ...................................................................... ...................................................................... b) Definujte realizace termů. ...................................................................... ...................................................................... ...................................................................... c) Definujte identity a jejich splňování. ...................................................................... ...................................................................... d) Definujte kongruenci grupoidu A = (A, ·); ozačujme ji ρ. ...................................................................... ...................................................................... e) Definujte příslušnou faktorovou algebru A/ρ a tzv. přirozený homomorfismus ρ . Ukažte, že se skutečně jedná o homomorfismus. ...................................................................... ...................................................................... f) Nechť ρ je kongruence grupoidu A = (A, ·), nechť p je n-ární term a nechť a1, . . . , an ∈ A. Dokažte, že ρ (pA,n (a1, . . . , an)) = pA/ρ,n (ρ (a1), . . . , ρ (an)) . ...................................................................... ...................................................................... ...................................................................... g) Nechť grupoid A = (A, ·) splňuje identitu p = q a nechť ρ je jeho kongruence. Dokažte, že též A/ρ splňuje identitu p = q. (Můžete využít bod f).) ...................................................................... ...................................................................... ...................................................................... h) Pro A = (Z, +) a ρ definované vztahem aρb ⇐⇒ a ≡ b (mod 2) najděte identitu platnou v A/ρ, která neplatí v A. ...................................................................... Algebra II, 1. termín, úloha B, 26.5. 2004 Jméno : UČO : Nechť A = (A, ≤) je uspořádaná množina. Pro X ⊆ A klademe ↑ X = { a ∈ A | pro vš. x ∈ X je x ≤ a }, ↓ X = { a ∈ A | pro vš. x ∈ X je a ≤ x } . Pro X ⊆ A klademe C(X) = ↓↑ X. Dále AC = { C(X) | X ⊆ A } a AC = (AC, ⊆). a) Pro X ⊆ A platí X........... ↓↑ X. Důkaz : ...................................................................... ...................................................................... b) Podobně pro X ⊆ A platí X........... ↑↓ X. c) Pro X, Y ⊆ A, X ⊆ Y platí ↑ X........... ↑ Y . Důkaz : ...................................................................... d) Podobně pro X, Y ⊆ A, X ⊆ Y platí ↓ X........... ↓ Y . e) Pro X ⊆ A platí ↑ X = ↑↓↑ X. Skutečně, ...................................................................... ...................................................................... ...................................................................... f) Z bodu e) plyne, že pro lib. X ⊆ A máme C(C(X)) = C(X). Důkaz : ...................................................................... g) Pro a ∈ A zjednodušte ↓↑ {a} : ...................................................................... ...................................................................... h) Dokažte, že ξ : a → C({a}) je vnořením A do AC. ...................................................................... ...................................................................... i) Dokažte, že pro lib. neprázdný systém (Xi)i∈I platí ↓ ( i∈I Xi) = i∈I (↓ Xi). ...................................................................... ...................................................................... j) Ukažte, že AC je uzavřené na průniky neprázdných systémů. ...................................................................... ...................................................................... k) Ukažte, že AC je úplný svaz. ...................................................................... ...................................................................... l) Jak vypadají prvky (Z, ≤)C ? ...................................................................... ...................................................................... Algebra II, 1.termín, úloha C, 26.5. 2004 Jméno : UČO : a) V pologrupě (S, ·) lze krátit zleva, platí-li ( ∀ a, b, c ∈ S ) ( a · b = a · c ⇒ b = c ) . Je třída všech pologrup s krácením zleva uzavřená na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou svazy (Z, ≤) a (Q, ≤) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině S3 = { id, (1, 2), (1, 3), (2, 3), (1, 2, 3), (1, 3, 2) } definujeme relaci ρ vztahem a ρ b ⇐⇒ a · { id, (1, 2) } = b · { id, (1, 2) } . Je tato relace kongruencí grupy (S3, ·) ? (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, 2. 6. 2004 Jméno : UČO : Uvažujme jazyk binárního operačního symbolu ◦. (Veškeré výrazy typu σ ∈ Σ budou při opravě ignorovány !) a) Definujte homomorfismus. ...................................................................... ...................................................................... b) Definujte podalgebru. ...................................................................... ...................................................................... c) Definujte kongruenci. ...................................................................... ...................................................................... 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 podalgebrou algebry .......... Skutečně, ...................................................................... ...................................................................... g) Doplňte a dokažte : lib. homomorfismus α : (A, ·) → (B, ·) lze psát ve tvaru α = ι β (ker α) , kde ...................................................................... ...................................................................... Skutečně, ...................................................................... ...................................................................... ...................................................................... ...................................................................... h) Vše ilustrujte pro A = množina všech čtvercových matic řádu 2 nad R, B = C a α(X) je determinant matice X. ...................................................................... ...................................................................... Algebra II, 2. termín, úloha B, 2. 6. 2004 Jméno : UČO : Nechť A = (A, ≤) je uspořádaná množina. ∅ = P ⊆ A se nazývá usměrněná, ex.-li pro libovolná a, b ∈ P prvek c ∈ P takový, že a ≤ c, b ≤ c. Samo A se naz. CPO (complete partially ordered set), má-li nejmenší prvek, který značíme ⊥, a má-li lib. usměrněná podmnožina v A suprémum. Nechť B = (B, ≤) je další CPO. Zobrazení α : A → B se naz. spojité, je-li pro lib. usměrněnou množinu P v A splněno α( P) = {α(a) | a ∈ P}. a) Dokažte, že každé spojité zobrazení je izotonní. ..................................................................... ..................................................................... b) Nechť A je CPO a nechť α je izotonní zobrazení A do A. Ukažte, že existuje α = { αn (⊥) | n ∈ N }. ..................................................................... ..................................................................... c) Ukažte, že je-li α pevný bod α (t.j. α(α) = α), je nejmenším pevným bodem α. ..................................................................... ..................................................................... d) Ukažte, že pro spojité α je α pevný bod zobrazení α. ..................................................................... ..................................................................... e) Nechť T značí množinu všech parciálních transformací množiny N0 (t.j. všech zobrazení podmnožin N0 do množiny N0). Pro f, g ∈ T klademe f ≤ g, je-li dom f ⊆ dom g a f a g souhlasí na dom f. Ukažte, že (T, ≤) je CPO. ..................................................................... ..................................................................... f) Definujme α : T → T vztahem (α(f))(k) =    1, k = 0 k · f(k − 1), k ≥ 1 a f(k − 1) definováno nedefinováno, jinak Ukažte, že α je spojité. ..................................................................... ..................................................................... g) Spočtěte α. ..................................................................... ..................................................................... Algebra II, 2. termín, úloha C, 2. 6. 2004 Jméno : UČO : a) Je třída všech úplných svazů uvažovaná v jazyce binárních ∧ a ∨ uzavřená na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou svazy (Z, ∧, ∨) a (Z, ∨, ∧) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině Z definujeme relaci ρ vztahem a ρ b ⇐⇒ a + b = 0 . Je tato relace kongruencí grupy (Z, +) ? (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, 16.6. 2004 Jméno : UČO : Uvažujme jazyk unárního operačního symbolu o. (Veškeré výrazy typu σ ∈ Σ budou při opravě ignorovány !) a) Nechť Ai = (Ai, fi), i ∈ I, je systém monounárních algeber. Na množině i∈I Ai = ................................................. definujeme operaci f vztahem ......................................................................... b) Nechť A a B jsou algebry s neprázdnými nosiči a nechť A × B splňuje identitu σ. U jednotlivých tvrzení vyznačte zda platí či nikoliv. (i) A nebo B splňuje σ, (ii) A i B splňuje σ, (iii) ani A ani B nemusí splňovat σ. c) Vyznačte co platí a co neplatí (i) Nechť A nebo B splňuje σ. Pak i A × B splňuje σ. (ii) Nechť A i B splňuje σ. Pak i A × B splňuje σ. d) Doplňte a dokažte. Nechť (ρi)i∈I, I = ∅ je systém kongruencí algebry A = (A, f) takový, že .................................................................... Pak A je izomorfní s podpřímým součinem systému .......................... e) Jak poznáme podle svazu Con A podpřímou nerozložitelnost konečné algebry A ? ................................................................... f) Pro která n ∈ N je (Zn, f), f(a) = a + 1 (mod n) podpřímo nerozložitelná ? ................................................................... Algebra II, 3. termín, úloha B, 16.6. 2004 Jméno : UČO : Nechť L = (L, ∧, ∨) je svaz, nechť I je jeho ideál (t.j. (i) I ⊆ L, (ii) a, b ∈ I dá a ∨ b ∈ I, (iii) a ∈ I, b ∈ L, b ≤ a dá b ∈ I) a F je jeho filtr (duální pojem k pojmu ideál). Nechť platí I ∪ F = L, I ∩ F = ∅. a) Dokažte : Je-li K podsvaz svazu L izomorfní s M5, pak K ⊆ I nebo K ⊆ F. ........................................................................... ........................................................................... ........................................................................... b) Nechť p ∈ I, q ∈ F, p ≤ q. Pak existuje r ∈ I ∩ F takové, že p ≤ r ≤ q. Návod : uvažte p ∨ (q ∧ s) pro s ∈ I ∩ F. ........................................................................... ........................................................................... ........................................................................... c) Dokažte : Je-li N podsvaz svazu L izomorfní s N5, pak buď I nebo F má podsvaz izomorfní s N5. Návod : ukažte, že stačí uvažovat případ a, b ∈ I, c ∈ F, zvolte r z bodu b) pro p = b, q = 1 a uvažujte dvě možnosti (i) a ∨ (c ∧ r) = b ∨ (c ∧ r). ........................................................................... ........................................................................... ........................................................................... (ii) neplatí (i). ........................................................................... ........................................................................... ........................................................................... d) Dokažte, že L je modulární právě tehdy když I i F jsou modulární. (Můžete použít větu “L je modulární právě tehdy když neobsahuje podsvaz izomorfní s .........”). ........................................................................... ........................................................................... ........................................................................... ........................................................................... Algebra II, 3. termín, úloha C, 16.6. 2004 Jméno : UČO : a) Je třída všech těles uvažovaná v jazyce binárních + a · uzavřená na operátor P ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Nechť M2(R) značí množinu všech čtvercových matic řádu 2 nad R. Je zobrazení A → |A| homomorfismem (M2(R), +) do (R, +) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině R[x] definujeme relaci ρ vztahem f ρ g ⇐⇒ 1 0 f(x)dx = 1 0 g(x)dx . Je tato relace kongruencí grupy (R[x], +) ? (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, 31.5. 2005 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 0 a b c 1 d e f g h 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, 31.5. 2005 Jméno : UČO : 1. Kongruence grup a) Relace ρ je kongruencí grupy G = (G, ·, e, −1 ) jestliže ..... b) Jak přecházíme od kongruencí k normálním podgrupám ? Dokažte korektnost. c) Jak přecházíme od normálních podgrup ke kongruencím ? Dokažte korektnost. d) Dokažte, že uvedené přechody jsou vzájemně inverzní. e) Dokažte, že v obou případech dostáváme stejnou faktorovou strukturu. f) Najděte všechny kongruence grupy (S3, ◦, id, −1 ). Algebra II, 1. termín, úloha C, 31.5. 2005 Jméno : UČO : a) Je třída všech biunárních algeber tvaru (A, f, f) uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou uspořádané množiny (Z, ≤) a (Q, ≤) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Nechť Pf (N) značí množinu všech konečných podmnožin množiny N. Je zobrazení α : Pf (N) → N0, X → |X| homomorfismem svazu (Pf (N), ⊆) do svazu (N0, ≤) ? (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, 9.6. 2005 Jméno : UČO : Identity v biunárních algebrách Uvažujeme jazyk dvojice unárních operačních symbolů f a g a v něm algebry A = (A, p, q) a B = (B, r, s). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. (Žádné σ ∈ Σ !) ........................................................................ b) Nechť M = {f, g}∗ je volný monoid nad množinou {f, g}. Prvky Tn lze psát ve tvaru ........................................................................ c) Definujte (induktivně) realizaci tA,n termu t ∈ Tn v algebře A. ........................................................................ d) Zobrazení α : .................... je homomorfismem algebry A do algebry B, platí-li ........................................................................ e) Je-li navíc a1, . . . , an ∈ A, máme α(tA,n (a1, . . . , an)) = ..................................... f) Dokažte tvrzení z e). .......................................................................... .......................................................................... g) Nechť dále je u ∈ Tn, nechť A |= t u a nechť α je ...................................................................... Pak ......................................................................... h) Dokažte tvrzení z g). ......................................................................... ......................................................................... i) Nechť algebra A je konkretizována takto: A = {0, 1, 2}, p(0) = 1, p(1) = 2, p(2) = 0, q(0) = 2, q(1) = 0, q(2) = 1. Charakterizujte identity, které jsou v A splněny ......................................................................... j) Nechť A je jako v bodě i). Charakterizujte identity, které nejsou v A splněny ......................................................................... Algebra II, 2. termín, úloha B, 9.6. 2005 Jméno : UČO : Pseudokomplementární svazy Svaz L = (L, ∧, ∨) s nejmenším prvkem, ozn. 0, se nazývá pseudokomplementární jestliže pro libovolné a ∈ L existuje a∗ ∈ L tak, 6e a ∧ b = 0 ⇐⇒ b ≤ a∗ . Dokažte (a) Každý Booleovský svaz je pseudokomplementární. (b) Každý omezený řetězec je pseudokomplementární. (c) Každý konečný distributivní svaz je pseudokomplementární. (Návod: asi se Vám bude hodit množina C = { b ∈ L | a ∧ b = 0 }.) (d) Dejte příklad konečného omezeného svazu, který není pseudokomplementární. (e) Dejte příklad omezeného distributivního svazu, který není pseudokomplementární. Algebra II, 2. termín, úloha C, 9.6. 2005 Jméno : UČO : a) Je třída všech unárních algeber tvaru (A, f) s prostým f uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou pologrupy (R, ·) a ({a ∈ R | a ≤ 0}, +) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Na množině Z definujeme relaci ρ vztahem a ρ b ⇐⇒ |a| = |b| . Je tato relace kongruencí grupoidu (Z, +) ? (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, 17.6. 2005 Jméno : UČO : Dvojí definice polosvazů a) A = (A, ρ), ρ ⊆ A × A je průsekový polosvaz jestliže ... b) L = (L, ·), · : L × L → L je polosvaz jestliže ... c) Jak se polosvaz podle a) modifikuje na polosvaz podle b) ? - vše dokažte. d) Jak to konkrétně vypadá pro (Z, ≥) ? e) Jak se polosvaz podle b) modifikuje na polosvaz podle a) ? - vše dokažte. f) Jak to konkrétně vypadá pro (N, nsn) ? g) Ukažte, že vaše přechody z c) a e) jsou vzájemně inverzní. Algebra II, 3. termín, úloha B, 17.6. 2005 Jméno : UČO : Volná algebra Rektangulární band je idempotentní pologrupa splňující identitu xyz = xz. a) Identita xi1 . . . xik = xj1 . . . xjl je splněna ve všech rektangulárních bandech právě když ..................................................................... b) Dokažte, že množina F = M × M spolu s operací (a, b) ◦ (c, d) = .................... je volný rektangulární band nad množinou M vzhledem k ι : a → .................. (i) (F, ◦) je rektangulární band : .................................................................... .................................................................... .................................................................... (ii) Množina ι(M) generuje (F, ◦), neboť libovolný prvek množiny F lze psát jako .................................................................... (iii) Nechť (S, ) je rektangulární band a nechť α : M → S je zobrazení. Položme β : F → S, ........................................................ → ................................................................ Zobrazení β je homomorfismus, neboť ........................................................................... .......................................................................... Konečně βι = ...................................................., neboť ....................................... c) Kolik má pologrupa F prvků pro |M| = n ∈ N ? ........................................................................... Algebra II, 2. termín, úloha C, 17. 6. 2005 Jméno : UČO : a) Je třída všech unárních algeber tvaru (A, f) se surjektivním f uzavřená na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Pro a, b ∈ C klademe a ρ b ⇐⇒ |a| = |b| . Je relace ρ kongruencí pologrupy (C, ·) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Nechť Pf (N) značí množinu všech konečných podmnožin množiny N. Je zobrazení α : Pf (N) → N0, X → |X| izotonním zobrazením svazu (Pf (N), ⊆) do svazu (N0, ≤) ? (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, 31.5. 2006 Jméno : UČO : Identity v biunárních algebrách (Žádné σ ∈ Σ !) Uvažujeme jazyk dvojice unárních operačních symbolů f a g a v něm algebry A = (A, p, q) a B = (B, r, s). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. ........................................................................ b) Nechť M = {f, g}∗ je volný monoid nad množinou {f, g}. Prvky Tn lze psát ve tvaru ........................................................................ c) Definujte (induktivně) realizaci tA,n termu t ∈ Tn v algebře A. ........................................................................ d) Zobrazení α : .................... je homomorfismem algebry A do algebry B, platí-li ........................................................................ e) Je-li navíc t ∈ Tn, a1, . . ., an ∈ A, máme α(tA,n (a1, . . . , an)) = ..................................... f) Dokažte tvrzení z e). .......................................................................... .......................................................................... g) Nechť dále je u ∈ Tn, nechť A |= t u a nechť α je ...................................................................... Pak ......................................................................... h) Dokažte tvrzení z g). ......................................................................... ......................................................................... i) Nechť algebra A je konkretizována takto: A = {0, 1, 2}, p(0) = 1, p(1) = 2, p(2) = 0, q(0) = 2, q(1) = 0, q(2) = 1. Charakterizujte identity, které jsou v A splněny ......................................................................... j) Nechť A je jako v bodě i). Charakterizujte identity, které nejsou v A splněny ......................................................................... Algebra II, 1. termín, úloha B, 31.5. 2006 Jméno : UČO : Polomodulární svazy. Pro uspořádanou množinu A = (A, ≤) označujeme relaci pokrývání symbolem . Řetězec x0 < x1 < · · · < xn je maximální, je-li x0 x1 . . . xn. Výškou prvku a konečné uspořádané množiny A = (A, ≤) s nejmenším prvkem 0 nazýváme maximální z délek řetězců mezi 0 a a. Graduací uspořádané množiny A = (A, ≤) rozumíme zobrazení g : A → Z takové, že (i) a < b ⇒ g(a) < g(b) a (ii) a b ⇒ g(a) g(b) . Svaz A = (A, ≤) je polomodulární, platí-li ( ∀ a, b, c ∈ A ) ( a = b, c a, c b ⇒ a a ∨ b, b a ∨ b ) . Dokažte : a) Libovolný modulární svaz je polomodulární. b) V konečném polomodulárním svazu mají libovolné dva maximální řetězce mezi danými a < b stejnou délku. (Pozorně formulujte výrok P(n), n ∈ N, který posléze řádně dokážete indukcí.) c) V konečném polomodulárním svazu je funkce výšky graduací. Pro labužníky : d) Konečný svaz je polomodulární, právě když jeho funkce výšky je graduací splňující ( ∀ a, b ∈ A ) h(a) + h(b) ≥ h(a ∧ b) + h(a ∨ b) . Algebra II, 1. termín, úloha C, 31.5. 2006 Jméno : UČO : a) Množina P (A) všech podmnožin množiny A tvoří vzhledem k “přirozeným” operacím Booleovu algebru. Je P (Q) podalgebrou algebry P (R) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Uvažujme algebru N = (N, s), kde s(a) = a + 1. Je relace (a, b) ρ (c, d) ⇐⇒ a = d kongruencí algebry N × N ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Je zobrazení α : Z[x, y] → Z, f → absolutní hodnota absolutního členu f homomorfismem okruhu (Z[x, y], +, ·) do okruhu (Z, +, ·) ? (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, 13.6. 2006 Jméno : UČO : Uvažujme jazyk dvou binárních operačních symbolů ∧, ∨. (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, ∧, ∨) je součinem systému (Ai = (Ai, ∧i, ∨i))i∈I , jestliže ................................................................ ................................................................ c) Algebra A = (A, ∧, ∨) je podpřímým součinem systému (Ai = (Ai, ∧i, ∨i))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) (A i B splňují σ) =⇒ C splňuje σ, (iii) C splňuje σ =⇒ (A nebo B 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 svaz ({1, . . . , n}, ≤) podpřímo nerozložitelný ? ....................................................................... h) Dokažte tvrzení z g). ....................................................................... ....................................................................... Algebra II, 2. termín, úloha B, 13.6. 2006 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. Ex. 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 lib. 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, 2. termín, úloha C, 13.6. 2006 Jméno : UČO : a) Je třída všech biunárních algeber (A, f, g) splňujících f = g uzavřená na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou struktury ({a ∈ R | a > 0}, · ) a (R, +) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Nechť P (N0) značí množinu všech neprázdných podmnožin množiny N0. Rozhodněte, zda zobrazení α : P (N0) → N0, X → cardX je grupoidový homomorfismus (P (N0), ∩) → (N0, min) ? (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, 23.6. 2006 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) Definujte homomorfismus. b) Definujte podalgebru. c) Definujte kongruenci. d) Definujte faktorovou algebru a tzv. přirozený homomorfismus. e) Dokažte, že pro homomorfismus α : (A, g) → (B, h) je ker α = ..................... kongruencí algebry .................. Skutečně, f) Ukažte, že im α = ......................................... je podalgebrou algebry ................ Skutečně, g) Doplňte a dokažte : lib. homomorfismus α : (A, g) → (B, h) lze psát ve tvaru α = ιβ(ker α) , kde Skutečně, h) Vše ilustrujte na příkladě A = ({0, 1, . . ., 5, a, b}, g), B = ({p, q, r, s}, h), kde g(b) = a, g(a) = 0, g(0) = 1, g(1) = 2, . . ., g(5) = 0, h(p) = q, h(q) = r, h(r) = q, h(s) = r a α je rozšířením b → q. Algebra II, 3. termín, úloha B, 23.6. 2006 Jméno : UČO : a) Dokažte, že každý komplementární modulární svaz L = (L, ∧, ∨) je relativně komplementární (= libovolný jeho interval [ a, b ] = { c ∈ L | a ≤ c ≤ b }, a, b ∈ L, a ≤ b je komplementární). Návod: Dokažte nejprve, že intervaly tvaru [ 0, p ] jsou komplementární. Pak vhodně použijte dualitu. b) Dejte příklad svazu, který je komplementární, ale není relativně komplementární. c) Dokažte, že v omezeném distributivním svazu je množina všech jeho prvků majících komplement podsvazem. d) Dejte příklad 8-mi prvkového omezeného distributivního svazu, v němž právě 4 prvky mají komplement. Body: 10,5,10,5. Algebra II, 3. termín, úloha C, 23.6. 2006 Jméno : UČO : a) Je třída všech cyklů (A, f), f : A → A uzavřená na operátor P ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Jsou svazy (Z, ≤) a (Q, ≤) izomorfní ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Je zobrazení α : Q[x, y] → Q, f → absolutní hodnota absolutního členu f homomorfismem pologrupy (Q[x, y], ·) do pologrupy (Q, ·) ? (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, 28. 5. 2007 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) Nechť algebra A je konkretizována takto: A = {0, 1, 2}, p(0) = 1, p(1) = 2, p(2) = 0, d = 0. Charakterizujte identity, které jsou v A splněny ......................................................................... j) Nechť A je jako v bodě i). Charakterizujte identity, které nejsou v A splněny ......................................................................... Algebra II, 1. termín, úloha B, 28. 5. 2007 Jméno : UČO : Pevné body Knaster-Tarski: Nechť A = (A, ≤) je ..... a nechť α : A → A je ..... . Pak existuje a ∈ A tak, že α(a) = a. (Bylo na přednášce.) Banach: Nechť A, B jsou množiny a nechť α : A → B, β : B → A jsou zobrazení. Pak existuje rozklad množiny A na podmnožiny A1, A2 a rozklad množiny B na podmnožiny B1, B2 tak, že α(A1) = B1, β(B2) = A2. Schröder-Bernstein: Nechť A, B jsou množiny a nechť α : A → B, β : B → A jsou prostá zobrazení. Pak existuje bijekce množiny A na množinu B. Úkoly: (a) Doplňte KT-větu. Nyní dokažte B-větu užitím KT-věty. Můžete použít zobrazení φ : 2A → 2A , X → A \ β(B \ α(X)) . (b) Zřejmě je (2A , ⊆) ............................ Dokažeme, že φ je (c) Skutečně, (d) Položíme (e) Pak skutečně (f) Dokažte SB-větu použitím B-věty. Body : 3, 2, 9, 6, 4, 6 Algebra II, 1. termín, úloha C, 28. 5. 2007 Jméno : UČO : a) Je třída všech svazů obsahujících nejmenší prvek, uvažovaná v jazyku dvou binárních operačních symbolů, uzavřena na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Na množině Z uvažujeme unární oprace s, t definované takto: s(x) = x+1, t(x) = x−1 pro x ∈ Z. Je 2-unární algebra (Z, s, t) izomorfní algebře (Z, t, s)? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Označme P množinu všech neprázdných konečných podmnožin množiny Q. Je zobrazení ϕ : P → Q definované vztahem ϕ({x1, x2, . . . , xn}) = x1 + x2 + · · · + xn n homomorfismus grupoidů (P , ∪) a (Q, +)? (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, 7. 6. 2007 Jméno : UČO : 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. b) Definujte podalgebru. c) Definujte kongruenci. 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, . . ., 5, a, b}, g, 0), B = ({p, q, r, s}, h, q), kde g(b) = a, g(a) = 0, g(0) = 1, g(1) = 2, . . . , g(5) = 0, h(p) = q, h(q) = r, h(r) = q, h(s) = q. Zvolte si libovolný homomorfismus α. Algebra II, 2. termín, úloha B, 7. 6. 2007 Jméno : UČO : Booleův okruh je okruh (R, +, ·, 0) s idempotentním násobením. V jazyku máme binární + a · a nulární 0. a) Libovolný booleův okruh splňuje identitu xy+yx = 0. Skutečně, pro libovolná a, b ∈ R máme · · · = (a + b)2 = . . . a tedy ..................................................... b) Libovolný booleův okruh splňuje identitu x + x = 0. Skutečně, v a) stačí položit ............................. c) Libovolný booleův okruh je komutativní. Skutečně, ........................................ ........................................ Nechť (B, ∧, ∨, ⊥, , ) je booleova algebra. Pro a, b ∈ B klademe a + b = (a ∧ b ) ∨ (a ∧ b), a · b = a ∧ b, 0 = ... . d) Dokažte, že (B, +, ·, 0) je booleův okruh. (Při ověřování asociativity sčítání upravte pouze jednu ze stran tak, aby tam nebylo + ; zbytek si dopočítáte doma.) Pokud nemůže dojít k nedorozumění, pokročilí algebraici (a to jste přece i Vy !) nerozlišují mezi operačními symboly a jejich realizacemi. Body : 5, 5, 5, 15 Algebra II, 2. termín, úloha C, 7. 6. 2007 Jméno : UČO : a) Je třída všech 2-unárních algeber (A, f, g), takových, že f a g jsou vzájemně inverzní bijekce, uzavřena na operátor S ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Na množině N uvažujeme relaci ρ definovanou takto : (x, y) ∈ ρ ⇐⇒ x a y mají stejný počet cifer v dvojkovém zápise. Je ρ kongruence svazu (N, min, max) ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Označme s unární operaci definovanou na množině Q takto: s(x) = x+1 pro lib x ∈ Q. Je zobrazení ϕ : Z × N → Q dané vztahem ϕ(p, q) = p q homomorfismem unárních algeber (Z, s|Z) × (N, s|N) a (Q, s) ? (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, 26. 6. 2007 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 0 a b c 1 d e f g h 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, 3. termín, úloha B, 26. 6. 2007 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 : 5, 5, 5, 15 Algebra II, 3. termín, úloha C, 26. 6. 2007 Jméno : UČO : a) O prvku a grupoidu (S, ·) řekneme, že je levá nula, pokud platí (∀x ∈ S)(a · x = a). Je třída všech grupoidů, které obsahují levou nulu, uzavřena na operátor H ? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Označme s unární operaci definovanou na množině Z takto: s(x) = x+1 pro lib x ∈ Z. Je relace ρ definovaná na množině Z vztahem (a, b) ∈ ρ ⇐⇒ a = b ∨ ab > 0 kongruencí unární algebry (Z, s)? (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Označme Pf (N) množinu všech konečných podmnožin množiny N. Je svaz (Pf (N), ∪, ∩) izomorfní svazu (Pf (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.