Úlohy k procvičování textu o univerzální algebře Číslo za pomlčkou v označení úlohy je číslo kapitoly textu, která je úlohou procvičovaná. Každá úloha je vyřešena o několik stránek později. Kontrolní otázky - zadání Odpovězte, zda uvedené tvrzení je pravdivé. [K1 -1] ano - ne Obsahuje-li typ Ω alespoň jeden nulární operační symbol, pak je každá Ω-algebra neprázdná. [K2 -1] ano - ne Obsahuje-li typ Ω alespoň jeden unární operační symbol, pak je každá Ω-algebra neprázdná. [K3 -2] ano - ne Množina všech podalgeber dané univerzální algebry A typu Ω uspořádaná inkluzí tvoří úplný svaz. [K4 -2] ano - ne Složením homomorfismů Ω-algeber je opět homomorfismus Ω-algeber. [K5 -3] ano - ne Projekce ze součinu Ω-algeber je surjektivní homomorfismus Ω-algeber. [K6 -3] ano - ne Součin Ω-algeber přes prázdnou množinu indexů je prázdná Ω-algebra. [K7 -4] ano - ne Jádro homomorfismu Ω-algeber A → B je podalgebra Ω-algebry A. [K8 -4] ano - ne Projekce z Ω-algebry na faktorovou algebru je surjektivní homomorfismus Ω-algeber. [K9 -4] ano - ne Každá kongruence na Ω-algebře A je jádrem vhodného homomorfismu Ω-algeber vycházejícího z Ω-algebry A. [K10 -5] ano - ne Jestliže typ Ω nebsahuje žádný nulární operační symbol, pak neexistuje žádný nulární term typu Ω. [K11 -5] ano - ne Jestliže typ Ω nebsahuje žádný unární operační symbol, pak neexistuje žádný unární term typu Ω. [K12 -6] ano - ne Každá varieta Ω-algeber je neprázdná. [Do každé variety Ωalgeber patří všechny jednoprvkové Ω-algebry.] [K13 -6] ano - ne Pro libovolný typ Ω tvoří třída všech Ω-algeber varietu Ω- algeber. [K14 -6] ano - ne Pro libovolný typ Ω tvoří třída všech jednoprvkových Ω-algeber varietu Ω-algeber. [K15 -7] ano - ne Pro každý typ Ω je volná Ω-algebra generovaná prázdnou množinou konečná Ω-algebra. [K16 -7] ano - ne Pro každý typ Ω je volná Ω-algebra generovaná prázdnou množinou nekonečná Ω-algebra. [K17 -8] ano - ne Pro každou varietu V typu Ω platí: libovolná rovnost typu Ω platí ve volné algebře F(V ) variety V právě tehdy, když tato rovnost platí v každé Ω-algebře variety V . Úlohy - zadání [Ú1 -2] Je dán typ Ω = { }, kde je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace definována takto: pro libovolné a ∈ Z klademe a =    a − 1 pro a > 0, 0 pro a = 0, a + 1 pro a < 0. (a) Popište všechny podalgebry Ω-algebry Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = 1−a pro libovolné a ∈ Z je homomorfismus Ω-algeber. Svá tvrzení zdůvodněte. [Ú2 -3] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné x ∈ Z klademe x = x + 1. (a) Určete všechny podalgebry této Ω-algebry. (b) Popište součin dvou kopií této Ω-algebry, tj. Ω-algebru Z × Z. (c) Popište všechny homomorfismy Ω-algeber Z → Z. Svá tvrzení zdůvodněte. [Ú3 -4] Je dán typ Ω = {f}, kde f je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace fZ definována takto: pro libovolné a ∈ Z klademe fZ(a) = |a|−10, kde |a| značí obvyklou absolutní hodnotu celého čísla a. (a) Popište podalgebru {−53} generovanou jednoprvkovou podmnožinou {−53} v Ω-algebře Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(x) = x + 1, kde + značí obvyklé sčítání celých čísel, je homomorfismem Ω-algeber. (c) Definujme relaci ∼ na Z takto: pro libovolné a, b ∈ Z klademe a ∼ b, právě když rozdíl a − b je dělitelný deseti. Rozhodněte, zda ∼ je kongruence na Ω-algebře Z. Svá tvrzení zdůvodněte. [Ú4 -7] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné liché x ∈ Z klademe x = 1 a pro libovolné sudé x ∈ Z klademe x = 0 . (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(x) = x2 je homomorfismem Ω-algeber. (b) Určete, pro které M ⊆ Z tvoří M podalgebru Ω-algebry Z. (c) Popište volnou Ω-algebru generovanou prázdnou množinou. Svá tvrzení zdůvodněte. [Ú5 -7] Je dán typ Ω = { , }, kde i jsou unární operační symboly. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: pro libovolné a ∈ Z klademe a = −a, a =    a + 1 pro a > 0, 0 pro a = 0, a − 1 pro a < 0. (a) Popište všechny podalgebry Ω-algebry Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) =    a − 1 pro a ∈ Z, a > 0, 0 pro a = 0, a + 1 pro a ∈ Z, a < 0. je homomorfismus Ω-algeber. (c) Popište volnou Ω-algebru generovanou prázdnou množinou. Svá tvrzení zdůvodněte. [Ú6 -7] Je dán typ Ω = { }, kde je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace definována takto: pro libovolné a ∈ Z klademe a = a + (−1)a . (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = 1−a pro libovolné a ∈ Z je homomorfismus Ω-algeber. (b) Rozhodněte, zda Ω-algebra Z patří do variety V určené teorií {x1 = x1}. (c) Popište volnou Ω-algebru F3(V ) variety V generovanou množinou {x1, x2, x3}. Svá tvrzení zdůvodněte. [Ú7 -7] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné liché x ∈ Z klademe x = 1 a pro libovolné sudé x ∈ Z klademe x = 0 . (a) Rozhodněte, zda Ω-algebra Z patří do variety V typu Ω určené teorií {x1 = •}. (b) Popište volnou algebru typu Ω generovanou množinou {x1, x2, x3, x4}. (c) Popište volnou algebru variety V generovanou množinou {x1, x2, x3, x4}. Svá tvrzení zdůvodněte. [Ú8 -7] Je dán typ Ω = { , }, kde i jsou unární operační symboly. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: pro libovolné a ∈ Z klademe a = |a|, a = (−1)a · a. (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = −a je homomorfismus Ω-algeber. (b) Rozhodněte, zda Ω-algebra Z patří do variety V určené teorií {x1 = x1, x1 = x1, x1 = x1}. (c) Určete počet prvků volné Ω-algebry F1(V ) variety V generované množinou {x1}. Svá tvrzení zdůvodněte. [Ú9 -7] Je dán typ Ω = {n, g}, kde n je nulární a g unární operační symbol. Označme množiny A = {1, 2, 3, 4, 5} and B = {6, 7, 8}. Položme nA = gA(1) = gA(2) = 3, gA(3) = gA(4) = 5, gA(5) = 4, a nB = gB(6) = 7, gB(7) = gB(8) = 8. Tím jsme vytvořili Ω-algebry A, B. Uvažme teorii T = {g(g(g(x1))) = g(n)} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda Ω-algebra A patří do V . (b) Rozhodněte, zda Ω-algebra B patří do V . (c) Popište volnou algebru F0(V ) variety V generovanou prázdnou mno- žinou. (d) Popište volnou algebru F1(V ) variety V generovanou množinou {x1}. Svá tvrzení zdůvodněte. [Ú10 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: nZ(a) = a + 1 pro libovolné a ∈ Z (kde + značí obvyklé sčítání). Dále je dána Ω-algebra A = { , } s unární operací nA definovanou takto: nA( ) = , nA( ) = . Uvažme teorii T = {n(n(n(n(x1)))) = x1} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda existuje homomorfismus Ω-algebry Z do Ω-algebry A. (b) U obou Ω-algeber A a Z rozhodněte, zda patří do V . (c) Popište volnou algebru F0(Ω) typu Ω generovanou prázdnou množi- nou. (d) Popište volnou algebru F1(V ) variety V generovanou množinou {x1}. Svá tvrzení zdůvodněte. [Ú11 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: nZ(a) = a − 1 pro libovolné a ∈ Z (kde − značí obvyklé odčítání). Dále je dána Ω-algebra A = { , } s unární operací nA definovanou takto: nA( ) = , nA( ) = . Uvažme teorii T = {n(n(n(x1))) = n(x1)} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda existuje homomorfismus Ω-algebry A do Ω-algebry Z. (b) U obou Ω-algeber A a Z rozhodněte, zda patří do V . (c) Popište volnou algebru F1(Ω) typu Ω generovanou množinou {x1}. (d) Popište volnou algebru F2(V ) variety V generovanou množinou {x1, x2}. Svá tvrzení zdůvodněte. [Ú12 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: pro libovolné a ∈ Z klademe nZ(a) =    1 pro a > 1, 0 pro −1 ≤ a ≤ 1, −1 pro a < −1. Dále jsou dána zobrazení f : Z → Z a g : Z → Z předpisy f(a) = 3a, g(a) = a2 (kde užité operace ve výrazech značí obvyklé operace s celými čísly). Nechť varieta V1 typu Ω je určená teorií T1 = {n(n(n(x1))) = n(n(x1))} a varieta V2 typu Ω je určená teorií T2 = {n(n(x1))) = n(n(x2))} typu Ω. (a) Rozhodněte, zda zobrazení f je homomorfismem Ω-algeber. (b) Rozhodněte, zda zobrazení g je homomorfismem Ω-algeber. (c) Rozhodněte, zda Ω-algebra Z patří do variety V1. (d) Rozhodněte, zda Ω-algebra Z patří do variety V2. (e) Popište volnou algebru F1(V1) variety V1 generovanou množinou {x1}. (f) Popište volnou algebru F1(V2) variety V2 generovanou množinou {x1}. (g) Rozhodněte, zda variety V1 a V2 jsou stejné. Svá tvrzení zdůvodněte. Kontrolní otázky - řešení [K1 -1] ano Obsahuje-li typ Ω alespoň jeden nulární operační symbol, pak je každá Ω-algebra neprázdná. [Plyne přímo z definice.] [K2 -1] ne Obsahuje-li typ Ω alespoň jeden unární operační symbol, pak je každá Ω-algebra neprázdná. [Pro každý typ, který neobsahuje žádný nulární operační symbol, existuje prázdná Ω-algebra.] [K3 -2] ano Množina všech podalgeber dané univerzální algebry A typu Ω uspořádaná inkluzí tvoří úplný svaz. [Jde o jeden z důsledků věty 2.1.] [K4 -2] ano Složením homomorfismů Ω-algeber je opět homomorfismus Ω-algeber. [Jde o větu 2.2.] [K5 -3] ne Projekce ze součinu Ω-algeber je surjektivní homomorfismus Ω-algeber. [Protože Ω-algebry mohou být i prázdné, nemusí být obecně projekce ze součinu surjektivní, uvažte součin prázdné Ω-algebry s neprázdnou Ω-algebrou a projekci z tohoto součinu do oné neprázdné Ω-algebry.] [K6 -3] ne Součin Ω-algeber přes prázdnou množinu indexů je prázdná Ω-algebra. [Součin Ω-algeber přes prázdnou množinu indexů je vždy jednoprvková Ωalgebra. Toto tvrzení nemohlo být pravdivé i proto, že v případě, kdy typ Ω obsahuje alespoň jeden nulární operační symbol, je každá Ω-algebra ne- prázdná.] [K7 -4] ne Jádro homomorfismu Ω-algeber A → B je podalgebra Ω-algebry A. [Podle definice je jádrem homomorfismu Ω-algeber A → B kongruence na Ω-algebře A.] [K8 -4] ano Projekce z Ω-algebry na faktorovou algebru je surjektivní homomorfismus Ω-algeber. [Plyne z věty 4.3 - viz definici projekce.] [K9 -4] ano Každá kongruence na Ω-algebře A je jádrem vhodného homomorfismu Ω-algeber vycházejícího z Ω-algebry A. [Jde o důsledek věty 4.3.] [K10 -5] ano Jestliže typ Ω nebsahuje žádný nulární operační symbol, pak neexistuje žádný nulární term typu Ω. [Plyne přímo z definice termu.] [K11 -5] ne Jestliže typ Ω nebsahuje žádný unární operační symbol, pak neexistuje žádný unární term typu Ω. [Pro libovolný typ je x1 unární term.] [K12 -6] ano Každá varieta Ω-algeber je neprázdná. [Do každé variety Ω-algeber patří všechny jednoprvkové Ω-algebry.] [K13 -6] ano Pro libovolný typ Ω tvoří třída všech Ω-algeber varietu Ω-algeber. [Jde o varietu Ω-algeber určenou prázdnou teorií.] [K14 -6] ne Pro libovolný typ Ω tvoří třída všech jednoprvkových Ω-algeber varietu Ω-algeber. [Nebsahuje-li typ Ω žádný nulární operační symbol, existuje i prázdná Ω-algebra, ve které platí všechny rovnosti typu Ω, a tedy patří do každé variety Ω-algeber.] [K15 -7] ne Pro každý typ Ω je volná Ω-algebra generovaná prázdnou množinou konečná Ω-algebra. [Obsahuje-li například typ Ω nekonečně mnoho nulárních operačních symbolů, je volná Ω-algebra generovaná prázdnou množinou nekonečná.] [K16 -7] ne Pro každý typ Ω je volná Ω-algebra generovaná prázdnou množinou nekonečná Ω-algebra. [Obsahuje-li typ Ω jen nulární operační symboly, je nosnou množinou volné Ω-algebry generované prázdnou množinou právě typ Ω.] [K17 -8] ano Pro každou varietu V typu Ω platí: libovolná rovnost typu Ω platí ve volné algebře F(V ) variety V právě tehdy, když tato rovnost platí v každé Ω-algebře variety V . [Viz poznámku za větou 8.6 (tj. na konci textu).] Úlohy - řešení [Ú1 -2] Je dán typ Ω = { }, kde je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace definována takto: pro libovolné a ∈ Z klademe a =    a − 1 pro a > 0, 0 pro a = 0, a + 1 pro a < 0. (a) Popište všechny podalgebry Ω-algebry Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = 1−a pro libovolné a ∈ Z je homomorfismus Ω-algeber. Svá tvrzení zdůvodněte. [Podalgebry jsou podmnožiny uzavřené na operaci , je to tedy celé Z, prázdná množina a pro každá dvě nezáporná celá čísla m, n množiny {a ∈ Z; −m ≤ a ≤ n}, {a ∈ Z; a ≤ n}, {a ∈ Z; −m ≤ a}. Platí ϕ(1) = 0 = 0, kdežto ϕ(1 ) = ϕ(0) = 1, proto ϕ není homomorfismus Ω-algeber.] [Ú2 -3] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné x ∈ Z klademe x = x + 1. (a) Určete všechny podalgebry této Ω-algebry. (b) Popište součin dvou kopií této Ω-algebry, tj. Ω-algebru Z × Z. (c) Popište všechny homomorfismy Ω-algeber Z → Z. Svá tvrzení zdůvodněte. [Každá podalgebra musí obsahovat •Z = 0 a s každým svým prvkem i číslo o jedna větší, tedy podalgebry jsou právě množiny Mn = {x ∈ Z; x ≥ n}, kde n probíhá množinu nekladných celých čísel (tj. n ∈ Z, n ≤ 0). Součin dvou kopií Ω-algebry Z je Ω-algebra Z × Z (tj. na množině všech uspořádaných dvojic celých čísel), kde jsou operace definovány takto: •Z×Z = (0, 0) a pro každé (x, y) ∈ Z × Z je (x, y) = (x + 1, y + 1). Homomorfismus Z → Z je zobrazení ϕ : Z → Z splňující ϕ(•Z) = •Z, tedy ϕ(0) = 0, a také pro každé x ∈ Z splňuje ϕ(x ) = ϕ(x) , tj. ϕ(x + 1) = ϕ(x) + 1. Snadno se dokáže indukcí, že pak ϕ(x) = x: 1. Dokazované platí pro x = 0. 2. Předpokládejme, že n je přirozené číslo takové, že dokazované platí pro n − 1, tj. je ϕ(n − 1) = n − 1, a dokažme tvrzení pro n. Pak ϕ(n) = ϕ((n − 1) + 1) = ϕ(n − 1) + 1 = n − 1 + 1 = n. 3. Předpokládejme, že n je přirozené číslo takové, že dokazované platí pro −(n − 1), tj. je ϕ(1 − n) = 1 − n, a dokažme tvrzení pro −n. Pak 1 − n = ϕ(1 − n) = ϕ(−n + 1) = ϕ(−n) + 1. Odečtením 1 dostaneme potřebné. Jediným homomorfismem Ω-algeber Z → Z je tedy identita.] [Ú3 -4] Je dán typ Ω = {f}, kde f je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace fZ definována takto: pro libovolné a ∈ Z klademe fZ(a) = |a|−10, kde |a| značí obvyklou absolutní hodnotu celého čísla a. (a) Popište podalgebru {−53} generovanou jednoprvkovou podmnožinou {−53} v Ω-algebře Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(x) = x + 1, kde + značí obvyklé sčítání celých čísel, je homomorfismem Ω-algeber. (c) Definujme relaci ∼ na Z takto: pro libovolné a, b ∈ Z klademe a ∼ b, právě když rozdíl a − b je dělitelný deseti. Rozhodněte, zda ∼ je kongruence na Ω-algebře Z. Svá tvrzení zdůvodněte. [Platí {−53} = {−53, 43, 33, 23, 13, 3, −7, −3}. Zobrazení ϕ není homomorfismem Ω-algeber, neboť například ϕ(fZ(−1)) = ϕ(−9) = −8 = −10 = fZ(0) = fZ(ϕ(−1)). Relace ∼ není kongruence na Ω-algebře Z, neboť například 4 ∼ −6, avšak fZ(4) = −6 ∼ −4 = fZ(−6).] [Ú4 -7] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné liché x ∈ Z klademe x = 1 a pro libovolné sudé x ∈ Z klademe x = 0 . (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(x) = x2 je homomorfismem Ω-algeber. (b) Určete, pro které M ⊆ Z tvoří M podalgebru Ω-algebry Z. (c) Popište volnou Ω-algebru generovanou prázdnou množinou. Svá tvrzení zdůvodněte. [Platí ϕ(•Z) = ϕ(0) = 02 = 0 = •Z, pro libovolné liché celé číslo a je i a2 liché, tedy ϕ(a ) = ϕ(1) = 12 = 1 = (a2 ) = ϕ(a) , pro libovolné sudé a je i a2 sudé, a proto ϕ(a ) = ϕ(0) = 02 = 0 = (a2 ) = ϕ(a) . Je tedy ϕ homomorfismus Ω-algeber. Podalgebra je libovolná podmnožina M množiny Z, která obsahuje •Z a s každým a ∈ M též je a ∈ M. Podalgebrami jsou tedy právě všechny podmnožiny množiny všech sudých čísel obsahující 0 a všechny podmnožiny množiny všech celých čísel obsahující 0 i 1. Volná algebra typu Ω generovaná prázdnou množinou je podle definice algebra F0(Ω) všech 0-árních termů typu Ω, tj. F0(Ω) = {•, • , • , • , . . . }, kde je unární operace definována takto: k libovolnému termu připíše apo- strof.] [Ú5 -7] Je dán typ Ω = { , }, kde i jsou unární operační symboly. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: pro libovolné a ∈ Z klademe a = −a, a =    a + 1 pro a > 0, 0 pro a = 0, a − 1 pro a < 0. (a) Popište všechny podalgebry Ω-algebry Z. (b) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) =    a − 1 pro a ∈ Z, a > 0, 0 pro a = 0, a + 1 pro a ∈ Z, a < 0. je homomorfismus Ω-algeber. (c) Popište volnou Ω-algebru generovanou prázdnou množinou. Svá tvrzení zdůvodněte. [Podalgebry jsou podmnožiny uzavřené na obě operace, je to tedy prázdná množina, {0}, a pro každé přirozené číslo n množiny {a ∈ Z; |a| ≥ n} a {a ∈ Z; |a| ≥ n} ∪ {0}. Platí ϕ(1) = 0 = 0, kdežto ϕ(1 ) = ϕ(2) = 1, proto ϕ není homomorfismus Ω-algeber. Protože typ Ω neobsahuje žádný nulární operační symbol, je volná Ω-algebra generovaná prázdnou množinou prázdná Ω-algebra.] [Ú6 -7] Je dán typ Ω = { }, kde je unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace definována takto: pro libovolné a ∈ Z klademe a = a + (−1)a . (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = 1−a pro libovolné a ∈ Z je homomorfismus Ω-algeber. (b) Rozhodněte, zda Ω-algebra Z patří do variety V určené teorií {x1 = x1}. (c) Popište volnou Ω-algebru F3(V ) variety V generovanou množinou {x1, x2, x3}. Svá tvrzení zdůvodněte. [Zobrazení ϕ je homomorfismus Ω-algeber, neboť pro libovolné a ∈ Z platí ϕ(a ) = 1 − a = 1 − (a + (−1)a ) = 1 − a − (−1)a , ϕ(a) = (1 − a) = 1 − a + (−1)1−a = 1 − a − (−1)a . Ω-algebra Z patří do variety V , protože pro libovolné a ∈ Z platí a = a + (−1)a = a + (−1)a + (−1)a+(−1)a = a + (−1)a − (−1)a = a. Volná Ω-algebra F3(Ω) generovaná množinou {x1, x2, x3} se skládá ze všech 3-árních termů typu Ω, tedy F3(Ω) = {x1, x1, x1 , . . . , x2, x2, x2 , . . . , x3, x3, x3 , . . . }. Pro každý term t ∈ F3(Ω) platí, že term t určuje v každé Ω-algebře variety V stejnou operaci jako term t, proto F3(V ) = {x1, x1 , . . . }, {x1, x1 , . . . }, {x2, x2 , . . . }, {x2, x2 , . . . }, {x3, x3 , . . . }, {x3, x3 , . . . } , kde operace je definována takto: pro libovolné i = 1, 2, 3 platí {xi, xi , . . . } = {xi , xi , . . . }, {xi , xi , . . . } = {xi, xi , . . . }. ] [Ú7 -7] Je dán typ Ω = {•, }, kde • je nulární a unární operační symbol. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •Z = 0 a pro libovolné liché x ∈ Z klademe x = 1 a pro libovolné sudé x ∈ Z klademe x = 0 . (a) Rozhodněte, zda Ω-algebra Z patří do variety V typu Ω určené teorií {x1 = •}. (b) Popište volnou algebru typu Ω generovanou množinou {x1, x2, x3, x4}. (c) Popište volnou algebru variety V generovanou množinou {x1, x2, x3, x4}. Svá tvrzení zdůvodněte. [ Ω-algebra Z nepatří do variety V ,neboť například platí (x1 )Z(1) = 1 = 1 = 0 = •Z(1). Volná algebra typu Ω generovaná množinou {x1, x2, x3, x4} je podle definice algebra F4(Ω) všech 4-árních termů typu Ω, tj. F4(Ω) = {•, • • , . . . , x1, x1, x1 , . . . , x2, x2, x2 , . . . , x3, x3, x3 , . . . , x4, x4, x4 , . . . }, kde jsou operace definovány takto: unární operace k libovolnému termu připíše apostrof, výsledkem nulární operace • je prvek •. Hledaná volná algebra variety V je F4(V ) = F4(Ω)/ ∼V , kde pro t1, t2 ∈ F4(Ω) platí t1 ∼V t2, právě když pro každou Ω-algebru A variety V oba termy t1, t2 určují stejnou operaci, tj. platí (t1)A = (t2)A. Ovšem pro libovolný prvek a ∈ A je a = •A, tedy pro každý term t ∈ F4(Ω) je t ∼V •. Protože v Ω-algebře A platí •A = •A, plyne odtud aplikací operace , že •A = •A, ovšem také •A = (•A) = •A, proto •A = •A. Je tedy F4(V ) = {{x1}, {x1}, {x2}, {x2}, {x3}, {x3}, {x4}, {x4}, T}, kde třída T = F4(Ω) − {x1, x1, x2, x2, x3, x3, x4, x4}. Výsledkem nulární operace • je zde třída T, dále T = T a pro libovolné i = 1, 2, 3, 4 platí {xi} = {xi}, {xi} = T. ] [Ú8 -7] Je dán typ Ω = { , }, kde i jsou unární operační symboly. Uvažme Ω-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: pro libovolné a ∈ Z klademe a = |a|, a = (−1)a · a. (a) Rozhodněte, zda zobrazení ϕ : Z → Z určené předpisem ϕ(a) = −a je homomorfismus Ω-algeber. (b) Rozhodněte, zda Ω-algebra Z patří do variety V určené teorií {x1 = x1, x1 = x1, x1 = x1}. (c) Určete počet prvků volné Ω-algebry F1(V ) variety V generované množinou {x1}. Svá tvrzení zdůvodněte. [Zobrazení ϕ není homomorfismus Ω-algeber, neboť například ϕ((−1) ) = ϕ(1) = −1, kdežto (ϕ(−1)) = 1 = 1. Ω-algebra Z patří do variety V , protože pro libovolné a ∈ Z platí a = (−1)a · a = (−1)(−1)a ·a · (−1)a · a = a, a = |a| = |a| = a , a = (−1)a · a = |a| = a . Volná Ω-algebra F1(Ω) generovaná množinou {x1} se skládá ze všech unárních termů typu Ω, což jsou termy x1, x1, x1, x1 , x1 , x1 , x1 , atd. Vždy tedy jde o x1, na které jsou aplikovány v libovolném (konečném) počtu v libovolném pořadí oba operační symboly. Rovnosti x1 = x1 a x1 = x1 způsobují, že každý term, na který je naposledy aplikován symbol , určuje v každé Ω-algebře variety V stejnou operaci jako term x1. Rovnost x1 = x1 způsobuje, že každý term, na který je naposledy aplikován dvakrát symbol , určuje v každé Ω-algebře variety V stejnou operaci jako tento term bez oné aplikace. Proto každý unární term určuje stejnou operaci jako některý z termů x1, x1, x1, x1 . Žádné dva z těchto čtyř vyjmenovaných termů nemusejí určovat stejné operace, proto volná Ω-algebra F1(V ) variety V generovaná množinou {x1} má čtyři prvky.] [Ú9 -7] Je dán typ Ω = {n, g}, kde n je nulární a g unární operační symbol. Označme množiny A = {1, 2, 3, 4, 5} and B = {6, 7, 8}. Položme nA = gA(1) = gA(2) = 3, gA(3) = gA(4) = 5, gA(5) = 4, a nB = gB(6) = 7, gB(7) = gB(8) = 8. Tím jsme vytvořili Ω-algebry A, B. Uvažme teorii T = {g(g(g(x1))) = g(n)} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda Ω-algebra A patří do V . (b) Rozhodněte, zda Ω-algebra B patří do V . (c) Popište volnou algebru F0(V ) variety V generovanou prázdnou mno- žinou. (d) Popište volnou algebru F1(V ) variety V generovanou množinou {x1}. Svá tvrzení zdůvodněte. [ Ω-algebra A nepatří do V , neboť například gA(gA(gA(1))) = gA(gA(3)) = gA(5) = 4 = 5 = gA(3) = gA(nA). Naproti tomu Ω-algebra B patří do V , neboť gB(gB(gB(6))) = gB(gB(gB(7))) = gB(gB(gB(8))) = gB(nB) = 8. Podle definice je F0(Ω) množina všech nulárních termů typu Ω, platí tedy F0(Ω) = {n, g(n), g(g(n)), g(g(g(n))), . . . }. Přitom rovnost g(g(g(x1))) = g(n) způsobí, že každý z uvedených termů, v němž se vyskytují alespoň tři g, je kongruentní s g(n). Ovšem aplikací g na g(g(g(n))) ∼ g(n) dostaneme g(g(g(g(n)))) ∼ g(g(n)), a tedy volná algebra C = F0(V ) variety V generovaná prázdnou množinou je dvouprvková: C = {T1, T2}, kde T1 = {n}, T2 = {g(n), g(g(n)), g(g(g(n))), . . . }, přičemž nC = T1, gC(T1) = gC(T2) = T2. Podobně F1(Ω) je množina všech unárních termů typu Ω, tedy F1(Ω) = {n, g(n), g(g(n)), g(g(g(n))), . . . , x1, g(x1), g(g(x1)), g(g(g(x1))), . . . } a volná algebra D = F1(V ) variety V generovaná množinou {x1} je pětiprvková: D = {T1, T2, T3, T4, T5}, kde T1 = {n}, T2 = {g(n), g(g(n)), g(g(g(n))), . . . , g(g(g(x1))), g(g(g(g(x1)))), . . . }, T3 = {x1}, T4 = {g(x1)}, T5 = {g(g(x1))}, přičemž nD = T1, gD(T1) = gD(T2) = T2, gD(T3) = T4, gD(T4) = T5, gD(T5) = T2.] [Ú10 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: nZ(a) = a + 1 pro libovolné a ∈ Z (kde + značí obvyklé sčítání). Dále je dána Ω-algebra A = { , } s unární operací nA definovanou takto: nA( ) = , nA( ) = . Uvažme teorii T = {n(n(n(n(x1)))) = x1} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda existuje homomorfismus Ω-algebry Z do Ω-algebry A. (b) U obou Ω-algeber A a Z rozhodněte, zda patří do V . (c) Popište volnou algebru F0(Ω) typu Ω generovanou prázdnou množi- nou. (d) Popište volnou algebru F1(V ) variety V generovanou množinou {x1}. Svá tvrzení zdůvodněte. [Snadno se ověří, že zobrazení ϕ : Z → A, které lichá čísla zobrazí na a sudá čísla na , je homomorfismus Ω-algeber. Dosazením obou prvků Ω-algebry A ověříme, že v ní je identita teorie T splněna, a tedy Ω-algebra A patří do variety V . Naproti tomu Ω-algebra Z nepatří do variety V , neboť například nZ(nZ(nZ(nZ(0)))) = 4 = 0. Protože typ Ω nemá žádný nulární operační symbol, neexistuje žádný nulární term typu Ω, a tedy volná algebra F0(Ω) typu Ω, generovaná prázdnou množinou, je prázdná Ω-algebra. Volnou algebrou F1(Ω) typu Ω, generovanou množinou {x1}, je množina všech unárních termů typu Ω, tedy F1(Ω) = {x1, n(x1), n(n(x1)), n(n(n(x1))), . . . }. Faktorizací dostaneme volnou algebru B = F1(V ) variety V generovanou množinou {x1}. Platí B = {M1, M2, M3, M4}, kde M1 = {x1, n(n(n(n(x1)))), n(n(n(n(n(n(n(n(x1)))))))), . . . }, M2 = {n(x1), n(n(n(n(n(x1))))), . . . }, M3 = {n(n(x1)), n(n(n(n(n(n(x1)))))), . . . }, M4 = {n(n(n(x1))), n(n(n(n(n(n(n(x1))))))), . . . }. Přitom nB(M1) = M2, nB(M2) = M3, nB(M3) = M4, nB(M4) = M1.] [Ú11 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: nZ(a) = a − 1 pro libovolné a ∈ Z (kde − značí obvyklé odčítání). Dále je dána Ω-algebra A = { , } s unární operací nA definovanou takto: nA( ) = , nA( ) = . Uvažme teorii T = {n(n(n(x1))) = n(x1)} a varietu V typu Ω určenou teorií T. (a) Rozhodněte, zda existuje homomorfismus Ω-algebry A do Ω-algebry Z. (b) U obou Ω-algeber A a Z rozhodněte, zda patří do V . (c) Popište volnou algebru F1(Ω) typu Ω generovanou množinou {x1}. (d) Popište volnou algebru F2(V ) variety V generovanou množinou {x1, x2}. Svá tvrzení zdůvodněte. [Dokažme sporem, že žádný homomorfismus Ω-algeber ϕ : A → Z neexistuje. Předpokládejme tedy jeho existenci. Pak = nA( ) = nA(nA( )) a tedy z toho, že ϕ je homomorfismus Ω-algeber, plyne ϕ( ) = ϕ(nA(nA( ))) = nZ(nZ(ϕ( ))) = ϕ( ) − 2, což nesplňuje žádné celé číslo ϕ( ), spor. Dosazením obou prvků Ωalgebry A ověříme, že v ní je identita teorie T splněna, a tedy Ω-algebra A patří do variety V . Naproti tomu Ω-algebra Z nepatří do variety V , neboť například nZ(nZ(nZ(0))) = −3 = −1 = nZ(0). Volnou algebrou F1(Ω) typu Ω, generovanou množinou {x1}, je množina všech unárních termů typu Ω, tedy F1(Ω) = {x1, n(x1), n(n(x1)), n(n(n(x1))), . . . }. Podobně volnou algebrou F2(Ω) typu Ω, generovanou množinou {x1, x2}, je množina všech binárních termů typu Ω, tedy F2(Ω) = {x1, n(x1), n(n(x1)), n(n(n(x1))), . . . , x2, n(x2), n(n(x2)), n(n(n(x2))), . . . }. Faktorizací dostaneme volnou algebru B = F2(V ) variety V generovanou množinou {x1, x2}. Platí B = {M1, M2, M3, M4, M5, M6}, kde M1 = {x1}, M2 = {n(x1), n(n(n(x1))), n(n(n(n(n(x1))))), . . . }, M3 = {n(n(x1)), n(n(n(n(x1)))), . . . }, M4 = {x2}, M5 = {n(x2), n(n(n(x2))), n(n(n(n(n(x2))))), . . . }, M6 = {n(n(x2)), n(n(n(n(x2)))), . . . }. Přitom nB(M1) = M2, nB(M2) = M3, nB(M3) = M2, nB(M4) = M5, nB(M5) = M6, nB(M6) = M5.] [Ú12 -7] Je dán typ Ω = {n}, kde n je unární operační symbol. Je dána Ω-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace nZ definována předpisem: pro libovolné a ∈ Z klademe nZ(a) =    1 pro a > 1, 0 pro −1 ≤ a ≤ 1, −1 pro a < −1. Dále jsou dána zobrazení f : Z → Z a g : Z → Z předpisy f(a) = 3a, g(a) = a2 (kde užité operace ve výrazech značí obvyklé operace s celými čísly). Nechť varieta V1 typu Ω je určená teorií T1 = {n(n(n(x1))) = n(n(x1))} a varieta V2 typu Ω je určená teorií T2 = {n(n(x1))) = n(n(x2))} typu Ω. (a) Rozhodněte, zda zobrazení f je homomorfismem Ω-algeber. (b) Rozhodněte, zda zobrazení g je homomorfismem Ω-algeber. (c) Rozhodněte, zda Ω-algebra Z patří do variety V1. (d) Rozhodněte, zda Ω-algebra Z patří do variety V2. (e) Popište volnou algebru F1(V1) variety V1 generovanou množinou {x1}. (f) Popište volnou algebru F1(V2) variety V2 generovanou množinou {x1}. (g) Rozhodněte, zda variety V1 a V2 jsou stejné. Svá tvrzení zdůvodněte. [Zobrazení f není homomorfismem Ω-algeber, neboť například nZ(f(1)) = nZ(3) = 1, avšak f(nZ(1)) = f(0) = 0. Dokažme, že zobrazení g je homomorfismem Ω-algeber. Pro libovolné a ∈ Z takové, že a > 1 platí také a2 > 1, a tedy nZ(g(a)) = nZ(a2 ) = 1 = g(1) = g(nZ(a)). Máme-li libovolné a ∈ Z takové, že a < −1, pak a2 > 1, a tedy nZ(g(a)) = nZ(a2 ) = 1 = g(−1) = g(nZ(a)). Konečně pro a ∈ {−1, 0, 1} platí nZ(g(a)) = nZ(a2 ) = 0 = g(0) = g(nZ(a)). Dvojnásobnou aplikací nZ na libovolný prvek Ω-algebry Z dostaneme 0, proto jak varieta V1 určená teorií T1 tak i varieta V2 určená teorií T2 obsahují Ω-algebru Z. Volnou algebrou F1(Ω) typu Ω, generovanou množinou {x1}, je množina všech unárních termů typu Ω, tedy F1(Ω) = {x1, n(x1), n(n(x1)), . . . }. Protože rovnost n(n(n(x1))) = n(n(x1)) znamená, že trojnásobnou aplikací operace n na libovolný prvek dostaneme vždy totéž jako dvojnásobnou aplikací operace n na tento prvek, má volná algebra A = F1(V1) variety V1 generovaná množinou {x1} tři prvky: A = {M1, M2, M3}, kde M1 = {x1}, M2 = {n(x1)}, M3 = {n(n(x1)), n(n(n(x1))), n(n(n(n(x1)))), . . . }. Přitom je operace na A definovaná takto: nA(M1) = M2, nA(M2) = M3, nA(M3) = M3. Protože rovnost n(n(x1))) = n(n(x2)) znamená, že dvojnásobnou aplikací operace n na libovolný prvek dostaneme vždy tentýž prvek, je výše popsaná Ω-algebra A také volnou algebrou F1(V2) variety V2 generovanou množinou {x1}. Variety V1 a V2 nejsou stejné, uvažte Ω-algebru B = {1, 2} s operací nB(1) = 1, nB(2) = 2. Tato Ω-algebra B patří do variety V1, ale nepatří do variety V2.]