Algebra II, 1. termín, úloha 1, 2.6. 2011 Jméno: Identity v podalgebrách (Žádné a g S !) Uvažujeme jazyk unárních operačních symbolů f\,..., fm, m přirozené číslo, a v něm algebry A = (A, gľ,..., gm) a B = (B, h,..., hm). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. b) Termy lze zavést i bez použití induktivní definice - jak ? c) Definujte (induktivně) realizaci tA'n termu t g Tn v algebře A. d) Algebra B je podalgebrou algebry A, platí-li e) Je-li navíc t g Tn, b1}... ,bn g B, máme íB'n(61;..., bn) = f) Dokažte tvrzení z e). g) Nechť dále je u g Tn, nechť A \= t ~ u. Pak též h) Dokažte tvrzení z g). i) Identity v našem jazyce jsou dvou typů. Popište je. j) Nechť m = 2, A = g±(a) = a + 1 (mod k), #2(0) = a — 2 (mod k). Které identity v naší algebře platí ? Algebra II, 1. termín, úloha 2, 2.6. 2011 Jméno: Uzáverový operátor n& množině A je zobrazení C : 2A —>• 2^, které pro libovolná X,Y C A splňuje (i) X C C(X), (ii) C(C(X)) C C(X), (iii) ICľ implikuje C (X) C C(F). -X" ^ ^4 je C-uzavřená (stručně uzavřená), je-li C {X) = X. Množinu všech uzavřených množin značíme Lq a klademe Cc = {Lq, C). Doplňte a dokažte: Věta 1. Nechť C je uzáverový operátor na množině A. Pak Cc je úplný svaz a pro Y C 2^ je supF =...................., inf F =........................ Důkaz......je nej......................prvek. Nechť Xi je uzavřená pro i G /, / 7^ 0. Pak C{.................) ........C{.......) pro každé i E I, a tedy....................je uzavřená. Proto supréma jsou ................................ a infima jsou Dokažte: Věta 2. Nechť C = (L, <) je úplný svaz. Pak existuje vhodná množina A a uzáverový operátor C na této množině tak, že £ je izomorfní s Cc- Důkaz. Položíme A = L a C(X) = {a G L | a < ................}. Postupně ověříme axiomy (i) - (iii): (i) : (ii) : (iii) : Nechť a : L —> Lc, a {b G L \ b < .................}. a(a) je uzavřená: ........................................... a je surjektivní: ........................................... Zřejmě: a < b právě když ....................................... a tedy a je hledaný izomorfismus. Nechť C = (L, A, V) je svaz. Prvek a G L je kompaktní, existuje-li pro libovolné A C L vlastnosti a < sup A takové konečné B C A, že a < sup B. Svaz C je kompaktně generovaný, je-li libovolné a E L supremem vhodné množiny kompaktních prvků. Konečně svaz C je algebraický, je-li úplný a kompaktně generovaný. Uzáverový operátor C na množině A je algebraický, platí-li (iv) pro libovolné X C A máme C(X) = (j { C(Y) | Y C X, Y konečná }. Dokažte: Věta 3. Nechť C je algebraický uzáverový operátor na množině A. Pak Cc je algebraický svaz a jeho kompaktní prvky jsou právě C(X) pro konečné množiny X. Důkaz, a) Nejprve dokážeme, že pro konečnou X je C(X) kompaktní v CC- Nechť tedy X = {au...,am}1C(X)Csnp{C(Ai)\ieI} = C([j{A\zeI}). Podle (iv) pro každé a j existuje konečné Xj c ...................tak, že a j g ........................ X j je konečná a proto X j c Ajtl u • • • u Ajj., kde každé Ajtk: je některé Aj. Pak aj g ...................................................., X — Ul 1 identitu fn{x) = x, je varieta. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) a ■ b f((a,b)) = (b,a) a g((a,b)) = (-a,b). Záporné body se počítají pouze v rámci úlohy 3, 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 1, 13.6. 2011 Jméno: Identity ve faktorových algebrách (Žádné a e S !) Uvažujeme jazyk unárních operačních symbolů /i, ...,/& a nulárních operačních symbolů Ci,..., q, k,l přirozená čísla, a v něm algebru A = (A, g±,..., gk, di,..., di). a) Definujte (induktivně) množinu Tn všech n-árních termů našeho jazyka. b) Termy lze zavést i bez použití induktivní definice - jak ? c) Definujte (induktivně) realizaci tA'n termu t g Tn v algebře A. d) p je kongruencí algebry A, platí-li e) Definujeme A/p = ................................................. kde .......................................................... Je-li navíc t g Tn, ............... g ....., máme tAl'^n{.......................; f) Dokažte tvrzení z konce e). g) Nechť t,ue Tn. Pak A \= t ~ u, je-li ....... h) Nechť t, u g Tn, A \= t ~ u. Pak též A/p i) Dokažte tvrzení z h). j) Identity v našem jazyce jsou pěti typů. Popište je. 1) .................................................. 2) .................................................. 3) ..................................................4) .................................................. 5) .................................................... k) Dáno m g N. Nechť k = 1, / = m, A = Zm, gi(a) = a + 1 (mod m), dj = [j] j = 1,... ,m. Které identity jednotlivých typů v naší algebře platí ? 1) ......................................................................... 2) ......................................................................... 3) ......................................................................... 4) ......................................................................... 5) ......................................................................... Algebra II, 2. termín, úloha 2, 13.6. 2011 Jméno: 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 p, a na množině A je poa = {(a,c)EAxA \ existuje b E A splňující a p b a c} . Relace p, a jsou záměnné, je-li a o p = p o a. a) Dokažte, že (Con A, C) je úplný svaz. b) Pro p,a G Con A máme p A a = ................... p Vo- = ................... c) Pro záměnné kongruence p, a máme p V o = ................... d) Dokažte : Nechť algebra A má libovolné dvě kongruence záměnné. Pak je svaz (Con A, A, V) modulární. Skutečně, nechť p,, která má svaz kongruencí (Con £>, C) izomorfní s (Con A,C.), přičemž ............................................................ Algebra II, 2. termín, úloha 3, 13.6. 2011 Jméno: a) Na množině A = {(a,b,c) eN xN xN \ a>b> c} definujme binární operaci / předpisem /((a, b, c), (d, e, /)) = (max(a, d), min(6, e), c). Rozhodněte, zda relace ~ definovaná na A předpisem (a, b, c) ~ (d, e, /) •<=>- (a > e & d > b) je kongruencí algebry {A, /). (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) b) Nechť L je množina všech relací ekvivalence na množině N a nechť -ří je podmnožina L obsahující právě relace p, které splňují implikaci (1,2) ip =^ (3,4) £p. Rozhodněte, zda je K podalgebrou svazu (L, V, A), kde V a A jsou obvyklé operace odpovídající uspořádání C. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Nechť A = N U {oo}. Na množině A x A definujme unární operace / a g předpisy /((a, b)) = (min(a, b), min(a, b)) a g((a, b)) = (max(a, b), max(a, &)). Rozhodněte, zda jsou algebry (A x A, /) a (A x A,g) izomorfní. (Odpověď ano/ne: ± 4 body, uvedení izomorfismu/uvedení vlastnosti zachovávané izo-morfismy, v níž se tyto algebry liší: 6 bodů.) Záporné body se počítají pouze v rámci úlohy 3, 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 1, 29.6. 2011 Jméno: Identity v součinech Uvažujme jazyk jediného unárního operačního symbolu /. (Veškeré výrazy typu o G S budou při opravě ignorovány !) a) Definujte množinu Tn všech n-árních termů našeho jazyka. c) Definujte realizaci tB,n termu t G Tn v algebře B = (B, h). c) Připomeňte definici součinu systému množin (Ai)iej. ( I je libovolná množina ! ) d) Algebra A = (A,g) je součinem systému (Ai = (Ai,Qi))iei , jestliže e) Pro t G Tn a (a})ieI,«)ie/ G A máme tAn((a])ieI,«)ie/) f) Dokažte tvrzení z e). g) Nechť C = (C, k). Popište všechny vztahy, které obecně platí mezi ld(£> x C), Id (i?) a ld(C). h) Dokažte tvrzení z g). i) Identity v našem jazyce jsou dvou typů. Popište je. j) Nechť B = {a,b}, h(a) = b, h{b) = a, C = {p,q,r}, k(p) = q, k{q) = r, k (r) = r. Uveďte diagram algebry B x C. k) Charakterizujte identity platné v B, C a B x C, Algebra II, 3. termín, úloha 2, 29.6. 2011 Jméno: Doplnění uspořádání do lineárního. a) V důkazu věty budeme potřebovat tzv. Zornovo lemma. Doplňte: Nechť (M, <) je uspořádaná množina, v níž má libovolná lineárně uspořádaná podmnožina horní závoru. Pak pro libovolné a G M existuje b E M takové, že................................................................ b) Pro uspořádanou množinu ({a,b,c,d},<), kde v < jsou právě (a, b), (d, b), (d, c), najděte všechna lineární uspořádání na {a, b, c, d} mající < za podmnožinu. Pro další úvahy fixujme libovolnou uspořádanou množinu (A, <). c) Nechť a, b G A jsou nesrovnatelná v relaci <. Položme <' = { (x,y) G A x A | x < a, b• množiny N/p a N/a mají stejnou mohutnost. Rozhodněte, zdaje ~ kongruencí svazu (L, V, A), kde V a A jsou obvyklé operace odpovídající uspořádání C. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.) c) Rozhodněte, zda třída všech monoidů, které splňují pro některé n > 2 identitu xi''' xn = xn ''' xi, je varieta. (Odpověď ano/ne: ± 4 body, důkaz/protipříklad: 6 bodů.)