Ú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é.
[Kl -1] ano - ne   Obsahuje-li typ Cl alespoň jeden nulární operační symbol, pak je každá O-algebra neprázdná.
[K2 -1] ano - ne   Obsahuje-li typ Cl alespoň jeden unární operační symbol, pak je každá O-algebra neprázdná.
[K3 -2] ano - ne   Množina všech podalgeber dané univerzální algebry A typu Cl uspořádaná inkluzí tvoří úplný svaz.
[K4-2] ano - ne    Složením homomorfismů fž-algeber je opět homomorfismus O-algeber.
[K5 -3] ano - ne   Projekce ze součinu O-algeber je surjektivní homomorfismus O-algeber.
[K6-3] ano - ne    Součin O-algeber přes prázdnou množinu indexů je prázdná O-algebra.
[K7 -4] ano - ne Jádro homomorfismů O-algeber A —> B je podalgebra O-algebry A.
[K8-4] ano - ne    Projekce z O-algebry na faktorovou algebru je surjektivní homomorfismus fž-algeber.
[K9 -4] ano - ne   Každá kongruence na fž-algebře A je jádrem vhodného homomorfismů fž-algeber vycházejícího z fž-algebry A.
[K10-5] ano - ne   Jestliže typ Cl nebsahuje žádný nulární operační symbol, pak neexistuje žádný nulární term typu Cl.
[Kil-5] ano - ne   Jestliže typ Cl nebsahuje žádný unární operační symbol, pak neexistuje žádný unární term typu Cl.
[K12-6] ano - ne   Každá varieta O-algeber je neprázdná. [Do každé variety Cl-algeber patří všechny jednoprvkové Cl-algebry.]
[K13-6] ano - ne    Pro libovolný typ Cl tvoří třída všech O-algeber varietu Cl-algeber.
[K14-6] ano - ne Pro libovolný typ Cl tvoří třída všech jednoprvkových fž-algeber varietu O-algeber.
[K15-7] ano - ne    Pro každý typ Cl je volná O-algebra generovaná prázdnou množinou konečná fž-algebra.
[K16-7] ano - ne    Pro každý typ Cl je volná O-algebra generovaná prázdnou množinou nekonečná fž-algebra.
[K17-8] ano - ne   Pro každou varietu V typu Cl platí: libovolná rovnost typu Cl
platí ve volné algebře F (V) variety V právě tehdy, když tato rovnost platí v každé O-algebře variety V.
[Úl-2] Je dán typ Cl = {*}, kde * je unární operační symbol. Uvažme O-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) Popište všechny podalgebry O-algebry Z.
(b) Rozhodněte, zda zobrazení <p : Z —> Z určené předpisem <p(a) = l — a pro libovolné a € Z je homomorfismus O-algeber.
Svá tvrzení zdůvodněte.
[Ú2 -3] Je dán typ Cl = {•, '}, kde • je nulární a' unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •% = 0 a pro libovolné a; € Z klademe x' = x + 1.
(a) Určete všechny podalgebry této O-algebry.
(b) Popište součin dvou kopií této O-algebry, tj. O-algebru Z x Z.
(c) Popište všechny homomorfismy O-algeber Z —> Z.
Svá tvrzení zdůvodněte.
[Ú3-4] Je dán typ Cl = {/}, kde / je unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace /z 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 O-algebře Z.
(b) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem <p(x) = x + 1, kde + značí obvyklé sčítání celých čísel, je homomorfismem O-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 O-algebře Z.
Svá tvrzení zdůvodněte.
Úlohy - zadání
a — 1 pro a > 0, 0 pro a = 0, a + 1   pro a < 0.
[Ú4-7] Je dán typ Cl = {•, '}, kde • je nulární a' unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •% = 0 a pro libovolné liché 2; € Z klademe i' = la pro libovolné sudé 2; € Z klademe x' = 0 .
(a) Rozhodněte, zda zobrazení <p : Z —> Z určené předpisem <p(x) = x2 je homomorfismem fž-algeber.
(b) Určete, pro které M C Z tvoří M podalgebru O-algebry Z.
(c) Popište volnou O-algebru generovanou prázdnou množinou.
Svá tvrzení zdůvodněte.
[Ú5-7] Je dán typ Cl = {*, '}, kde * i ' jsou unární operační symboly. Uvažme O-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 + 1 pro a > 0, 0 pro a = 0, a — 1   pro a < 0.
(a) Popište všechny podalgebry O-algebry Z.
(b) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem
{a — l   pro a € Z, a > 0, 0        pro a = 0, a + 1   pro a € Z, a < 0.
je homomorfismus O-algeber.
(c) Popište volnou O-algebru generovanou prázdnou množinou.
Svá tvrzení zdůvodněte.
[Ú6-7] Je dán typ Cl = {*}, kde * je unární operační symbol. Uvažme O-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+(-l)a.
(a) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem <p(a) = l — a pro libovolné a € Z je homomorfismus O-algeber.
(b) Rozhodněte, zda O-algebra Z patří do variety V určené teorií {a;** =
Xi}.
(c) Popište volnou O-algebru F3(V) variety V generovanou množinou {x1,x2,x3}.
Svá tvrzení zdůvodněte.
[Ú7-7] Je dán typ Cl = {•,'}, kde • je nulární a' unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •% = 0 a pro libovolné liché a; € Z klademe i' = la pro libovolné sudé a; € Z klademe x' = 0 .
(a) Rozhodněte, zda O-algebra Z patří do variety V typu Cl určené teorií
K = .}.
(b) Popište volnou algebru typu Cl generovanou množinou {xi, x-i, X3, X4 }.
(c) Popište volnou algebru variety V generovanou množinou {xi, X2, X3, x4}.
Svá tvrzení zdůvodněte.
[Ú8-7] Je dán typ Cl = {*, '}, kde * i ' jsou unární operační symboly. Uvažme O-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*=(-l)a-a.
(a) Rozhodněte, zda zobrazení <p : Z —> Z určené předpisem
<p(a) = —a
je homomorfismus O-algeber.
(b) Rozhodněte, zda O-algebra Z patří do variety V určené teorií {a;** =
(c) Určete počet prvků volné O-algebry i*i(V) variety V generované množinou {xi}.
Svá tvrzení zdůvodněte.
[Ú9-7] Je dán typ Cl = {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(l) = gA{2) = 3, gA(3) = gA(4) = 5, gA(5) = 4,
a
nB = <?b(6) = 7, gB(7) = gB(8) = 8. Tím jsme vytvořili fž-algebry A, B. Uvažme teorii
T= {g(g(g(xi))) =g(n)} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda O-algebra A patří do V.
(b) Rozhodněte, zda O-algebra B patří do V.
(c) Popište volnou algebru F0(V) variety V generovanou prázdnou množinou.
(d) Popište volnou algebru Fi (V) variety V generovanou množinou {xi}.
Svá tvrzení zdůvodněte.
[Ú10-7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: nz(a) = a + 1 pro libovolné a € Z (kde + značí obvyklé sčítání). Dále je dána O-algebra A = {A, O} s unární operací nA definovanou takto: nA(Q) = A, nA(A) = Q. Uvažme teorii T = {n(n(n(n(xi)))) = x\} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda existuje homomorfismus O-algebry Z do O-algebry A.
(b) U obou O-algeber A a, I* rozhodněte, zda patří do V.
(c) Popište volnou algebru F0(Cl) typu Cl generovanou prázdnou množinou.
(d) Popište volnou algebru i*í (V) variety V generovanou množinou {xi}.
Svá tvrzení zdůvodněte.
11 -7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: nz(a) = a — l pro libovolné a € Z (kde — značí obvyklé odčítání). Dále je dána O-algebra A = {A, O} s unární operací n a definovanou takto: n ,4 (O) = A, n^A) = O- Uvažme teorii T = {n(n(n(x\))) = n(x\)} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda existuje homomorfismus O-algebry A do O-algebry
(b) U obou O-algeber A a Z rozhodněte, zda patří do V.
(c) Popište volnou algebru i*i(fi) typu Cl generovanou množinou {x\}.
(d) Popište volnou algebru F2 (V) variety V generovanou množinou {xi, £2 }.
Svá tvrzení zdůvodněte.
12-7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: pro libovolné a € Z klademe
Dále jsou dána zobrazení / : Z —> Z a j : 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 Ví typu Cl je určená teorií Ti = {n(n(n(x\))) = n(n(xi))} a varieta V2 typu Cl je určená teorií T2 = {n(n(xi))) =n(n(x2))} typu Cl.
(a) Rozhodněte, zda zobrazení / je homomorfismem fž-algeber.
(b) Rozhodněte, zda zobrazení g je homomorfismem fž-algeber.
(c) Rozhodněte, zda O-algebra Z patří do variety Ví.
(d) Rozhodněte, zda O-algebra Z patří do variety Ví-
(e) Popište volnou algebru F\ (Ví) variety Ví generovanou množinou {xi}.
(f) Popište volnou algebru Fi (V"2) variety V2 generovanou množinou {xi}.
(g) Rozhodněte, zda variety Ví a V2 jsou stejné.
Svá tvrzení zdůvodněte.
Z
1     pro a > 1,
O     pro — 1 < a < 1,
— 1   pro a < —1.
Kontrolní otázky - řešení
[Kl -1] ano Obsahuje-li typ Cl alespoň jeden nulární operační symbol, pak je každá O-algebra neprázdná. [Plyne přímo z definice.]
[K2 -1] ne Obsahuje-li typ Cl alespoň jeden unární operační symbol, pak je každá O-algebra neprázdná. [Pro každý typ, který neobsahuje žádný nulární operační symbol, existuje prázdná Cl-algebra.]
[K3 -2] ano Množina všech podalgeber dané univerzálni algebry A typu Cl uspořádaná inkluzí tvoří úplný svaz. [Jde o jeden z důsledků věty 2.1.]
[K4 -2] ano Složením homomorfismů fž-algeber je opět homomorfismus fž-algeber. [Jde o větu 2.2.]
[K5 -3] ne Projekce ze součinu O-algeber je surjektivní homomorfismus O-algeber. [Protože Cl-algebry mohou být i prázdné, nemusí být obecně projekce ze součinu surjektivní, uvažte součin prázdné Cl-algebry s neprázdnou Cl-al-gebrou a projekci z tohoto součinu do oné neprázdné Cl-algebry.]
[K6 -3] ne Součin O-algeber přes prázdnou množinu indexů je prázdná O-algebra. [Součin Cl-algeber přes prázdnou množinu indexů je vždy jednoprvková Cl-algebra. Toto tvrzení nemohlo být pravdivé i proto, že v případě, kdy typ Cl obsahuje alespoň jeden nulární operační symbol, je každá Cl-algebra neprázdná.]
[K7-4] ne Jádro homomorfismů O-algeber A —> B je podalgebra O-algebry A. [Podle definice je jádrem homomorfismů Cl-algeber A —»• B kongruence na Cl-algebře A.]
[K8 -4] ano Projekce z O-algebry na faktorovou algebru je surjektivní homomorfismus O-algeber. [Plyne z věty 4-3 - viz definici projekce.]
[K9 -4] ano Každá kongruence na fž-algebře A je jádrem vhodného homomorfismů O-algeber vycházejícího z O-algebry A. [Jde o důsledek věty 4-3-]
[K10-5] ano Jestliže typ Cl nebsahuje žádný nulární operační symbol, pak neexistuje žádný nulární term typu Cl. [Plyne přímo z definice termu.]
[Kil -5] ne Jestliže typ Cl nebsahuje žádný unární operační symbol, pak neexistuje žádný unární term typu Cl. [Pro libovolný typ je x\ unární term.]
[K12-6] ano Každá varieta O-algeber je neprázdná. [Do každé variety Cl-algeber patří všechny jednoprvkové Cl-algebry.]
[K13-6] ano Pro libovolný typ Cl tvoří třída všech O-algeber varietu O-algeber. [Jde o varietu Cl-algeber určenou prázdnou teorií.]
[K14-6] ne Pro libovolný typ Cl tvoří třída všech jednoprvkových O-algeber varietu O-algeber. [Nebsahuje-li typ Cl žádný nulární operační symbol, existuje i prázdná Cl-algebra, ve které platí všechny rovnosti typu Cl, a tedy patří do každé variety Cl-algeber.]
[K15-7] ne    Pro každý typ Cl je volná O-algebra generovaná prázdnou množi-
nou konečná O-algebra. [Obsahuje-li například typ Cl nekonečně mnoho nulárních operačních symbolů, je volná Cl-algebra generovaná prázdnou množinou nekonečná.]
[K16-7] ne   Pro každý typ Cl je volná O-algebra generovaná prázdnou množinou
nekonečná O-algebra. [Obsahuje-li typ Cl jen nulární operační symboly, je nosnou množinou volné Cl-algebry generované prázdnou množinou právě typ Cl.]
[K17-8] ano Pro každou varietu V typu Cl platí: libovolná rovnost typu Cl platí ve
volné algebře F (V) variety V právě tehdy, když tato rovnost platí v každé O-algebře variety V. [Viz poznámku za větou 8.6 (tj. na konci textu).]
[Úl-2] Je dán typ Cl = {*}, kde * je unární operační symbol. Uvažme O-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) Popište všechny podalgebry O-algebry Z.
(b) Rozhodněte, zda zobrazení <p : Z —> Z určené předpisem <p(a) = l — a pro libovolné a € Z je homomorfismus O-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í <p(l)* = 0* = 0, kdežto <p(l*) = ip(0) = 1, proto <p není homomorfismus Cl-algeber.]
[Ú2 -3] Je dán typ Cl = {•, '}, kde • je nulární a' unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •% = 0 a pro libovolné a; € Z klademe x' = x + 1.
(a) Určete všechny podalgebry této O-algebry.
(b) Popište součin dvou kopií této O-algebry, tj. O-algebru Z x Z.
(c) Popište všechny homomorfismy O-algeber Z —> Z.
Svá tvrzení zdůvodněte.
[Každá podalgebra musí obsahovat •% = 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í Cl-algebry Z je Cl-algebra Z x Z (tj. na množině všech uspořádaných
Úlohy - řešení
a — 1 pro a > 0, 0 pro a = 0, a + 1   pro a < 0.
dvojic celých čísel), kde jsou operace definovány takto: «zxz = (0,0) a pro každé (i,j)eZxZ je (x, y)' = (x + 1, y + 1). Homomorfismus Z —> Z je zobrazení <p : Z —> Z splňující <p(»z) = *z> tedy <p(0) = 0, a také pro každé iEZ splňuje <p(x') = <p{x)', tj. ip(x + 1) = <p(x) + 1. Snadno se dokáže indukcí, že pak <p(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 <p(n — 1) = n — 1, a dokažme tvrzení pro n. Pak <p(n) = <p((n - 1) + 1) = <p(n -l) + l = n- l + l = n.
5. Předpokládejme, že n je přirozené číslo takové, že dokazované platí pro — (n — 1), tj. je <p(l — n) = 1 — n, a dokažme tvrzení pro —n. Pak 1 — n = <p(l — n) = <p(—n + 1) = <fi(—n) + 1. Odečtením 1 dostaneme potřebné.
Jediným homomorfismem Cl-algeber Z —> Z je tedy identita.]
[Ú3-4] Je dán typ Cl = {/}, kde / je unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž je odpovídající operace /z definována takto: pro libovolné a € Z klademe /z(a) = \a\ —10, kde \a\ značí obvyklou absolutní hodnotu celého čísla a.
(a) Popište podalgebru ({—53}) generovanou jednoprvkovou podmnožinou {—53} v O-algebře Z.
(b) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem <p(x) = x + 1, kde + značí obvyklé sčítání celých čísel, je homomorfismem O-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 O-algebře Z.
Svá tvrzení zdůvodněte.
[Platí ({—53}) = {—53,43,33,23,13,3,-7,-3}. Zobrazení <p není homomorfismem Cl-algeber, nebotnapříklad ip(fz(—l)) = <p(—9) = —8 ^ —10 = /z(0) = fz(f(—I))- Relace ~ není kongruence na Cl-algebře Z, neboť například 4 ~ —6, úwsúiA; /z(4) = —6^—4 = fz(—6).]
[Ú4-7] Je dán typ Cl = {•, '}, kde • je nulární a' unární operační symbol. Uvažme O-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é a; € Z klademe a/ = la pro libovolné sudé a; € Z klademe x' = 0 .
(a) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem <p(x) = x2 je homomorfismem fž-algeber.
(b) Určete, pro které M C Z tvoří M podalgebru O-algebry Z.
(c) Popište volnou O-algebru generovanou prázdnou množinou.
Svá tvrzení zdůvodněte.
[Platí <p(»z) = y(0) = O2 = 0 = «z, pro libovolné liché celé číslo a je i a2 liché, tedy <p(a') = <p(l) = l2 = 1 = (a2)' = <p(a)', pro libovolné sudé a je i a2 sudé, a proto <p(a') = <p(Q) = O2 = 0 = (a2)' = <p(a)'. Je tedy <p homomorfismus Cl-algeber. Podalgebra je libovolná podmnožina M množiny
Z, která obsahuje •% a s každým a G M též je a' € M. Podalgebrami jsou tedy právě všechny podmnožiny množiny všech sudých čísel obsahující O a všechny podmnožiny množiny všech celých čísel obsahující O i 1. Volná algebra typu Cl generovaná prázdnou množinou je podle definice algebra F0(Cl) všech O-árních termů typu Cl, tj.
F0(Cl) = {.,.',.",."',...},
kde je unární operace ' definována takto: k libovolnému termu připíše apostrof.]
[Ú5-7] Je dán typ Cl = {*, '}, kde * i ' jsou unární operační symboly. Uvažme O-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 + 1 pro a > 0, 0 pro a = 0, a — 1   pro a < 0.
(a) Popište všechny podalgebry O-algebry Z.
(b) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem
{a — 1   pro a € Z, a > 0, 0        pro a = 0, a + 1   pro a € Z, a < 0.
je homomorfismus O-algeber.
(c) Popište volnou O-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} U {0}. Platí ip(l)* = 0* = 0, kdežto ip(l*) = <p(2) = 1, proto ip není homomorfismus Cl-algeber. Protože typ Cl neobsahuje žádný nulární operační symbol, je volná Cl-algebra generovaná prázdnou množinou prázdná Cl-algebra.]
[Ú6-7] Je dán typ Cl = {*}, kde * je unární operační symbol. Uvažme O-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+{-l)a.
(a) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem tp(a) = l — a pro libovolné a € Z je homomorfismus O-algeber.
(b) Rozhodněte, zda O-algebra Z patří do variety V určené teorií {a;** =
Xi}.
(c) Popište volnou O-algebru F3(V) variety V generovanou množinou
{X!,X2,X3}.
Svá tvrzení zdůvodněte.
[Zobrazení <p je homomorfismus Cl-algeber, neboť pro libovolné a € Z platí
<p(a*)   =   l-a* = l-(a+(-l)a) = l-a-(-l)a, (<p(a))*   =   (l-o)* = l-a + (-l)1-a = l-a-(-l)a.
Cl-algebra Z patří do variety V, protože pro libovolné a € Z platí
a** = (a + (-l)a)* = a + (-l)a + (-l)a+(-1)" =a + (-l)a - (-l)a = a.
Volná Cl-algebra F3(Cl) generovaná množinou {xi,x2,x3} se skládá ze všech 3-árních termů typu Cl, tedy
F3{Cl) = {xi, Xi, Xi ,..., X2, X2, X2 , ■ ■ ■, x3, x3, x3 ,...}.
Pro každý term t € F3(Cl) platí, že term t** určuje v každé Cl-algebře variety V stejnou operaci jako term t, proto
F3(V) = {{xux?,...}, {z*,****,...}, {x2,xf,...}, {xl,xf\...}, {x3,x3 ,...}, {x3,x3 ,...}},
kde operace * je definována takto: pro libovolné i = 1,2,3 platí
f       /v.** \* _       St*  /v.*** \ St*  t*** \* _       St    t** \ 1
[Ú7-7] Je dán typ Cl = {•, '}, kde • je nulární a' unární operační symbol. Uvažme O-algebru Z (tj. jejími prvky jsou právě všechna celá čísla), na níž jsou odpovídající operace definovány takto: •% = 0 a pro libovolné liché a; € Z klademe x' = 1 a pro libovolné sudé a; € Z klademe x' = 0 .
(a) Rozhodněte, zda O-algebra Z patří do variety V typu Cl určené teorií
K = •}•
(b) Popište volnou algebru typu Cl generovanou množinou {xi, x2,23, X4}.
(c) Popište volnou algebru variety V generovanou množinou {xi, x2, x3, x4}.
Svá tvrzení zdůvodněte.
[Cl-algebra Z nepatří do variety V,neboť například platí (ar")z(l) = 1" = 1^0 = «z(l)- Volná algebra typu Cl generovaná množinou {xi,x2,x3,X4} je podle definice algebra F^Cl) všech 4-árních termů typu Cl, tj.
f 4 (O) = {•, • • , . . . , X\ , Xi, Xi,..., x2, x2, x2,..., x3, x3, x3,..., •^4)       «£4 )•••}")
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 F±(V) = F^iCl)/ ~y, kde pro h,t2 € F^Cl) platí t\ ~y t2, právě když pro každou Cl-algebru A variety V oba termy t\, t2
určují stejnou operaci, tj. platí (h)a = (t2)a- Ovšem pro libovolný prvek a G A je a" = »a, tedy pro každý term t € F^íl) je t" ~y •. Protože v Cl-algebře A platí »a = »a, plyne odtud aplikací operace ', že «™ = »'A, ovšem také •'^ = (•'A)" = »a, proto »'a = »a- Je tedy
Fi(V) = {{Xl}, {x[}, {x2}, {x'2}, {x3}, {x'3}, {Xi}, {x'4}, T},
kde třída T = F^Cl) — {xi,x'1,X2,x2,X3,x'3,X4,x'4}. Výsledkem nulární operace • je zde třída T, dále T" = T a pro libovolné i = 1,2,3,4 platí
[Ú8-7] Je dán typ Cl = {*, '}, kde * i ' jsou unární operační symboly. Uvažme O-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*=(-l)a-a.
(a) Rozhodněte, zda zobrazení tp : Z —> Z určené předpisem
<p(a) = —a
je homomorfismus O-algeber.
(b) Rozhodněte, zda O-algebra Z patří do variety V určené teorií {a;** =
(c) Určete počet prvků volné O-algebry Fi(V) variety V generované množinou {xi}.
Svá tvrzení zdůvodněte.
[Zobrazení <p není homomorfismus Cl-algeber, neboť například
<p{{-l)')=<p{l) = -l,
kdežto
(^(-1))' = ľ = 1. Cl-algebra Z patří do variety V, protože pro libovolné a € Z platí
a** = ((-l)a • a)* = (-ljC-1)"-" • (-l)a • a = a, a" = ||a|| = |a| = a', a*' = |(-l)a -a| = \a\=a'.
Volná Cl-algebra Fi(Cl) generovaná množinou {xi} se skládá ze všech unárních termů typu Cl, což jsou termy x\, x*, x[, x**, x*', x'*, x'{, atd. Vždy tedy jde o x\, na které jsou aplikovány v libovolném (konečném) počtu v libovolném pořadí oba operační symboly. Rovnosti x'{ = x[ a x*' = x[ způsobují, že každý term, na který je naposledy aplikován symbol', určuje v každé Cl-algebře variety V stejnou operaci jako term x[. Rovnost x** = x\ způsobuje, že každý term, na který je naposledy aplikován dvakrát symbol *, určuje v každé Cl-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ů x\, x*, x[, x'*. Žádné dva z těchto čtyř vyjmenovaných termů nemusejí určovat stejné operace, proto volná Cl-algebra Fi(V) variety V generovaná množinou {xi} má čtyři prvky.]
[Ú9-7] Je dán typ Cl = {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{l) = gA{2) = 3, gA(3) = gA(4) = 5, gA(5) = 4,
a
nB = <?b(6) = 7, gB(7) = gB(8) = 8. Tím jsme vytvořili fž-algebry A, B. Uvažme teorii
T = {s(g(g(xi))) = g(n)} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda O-algebra A patří do V.
(b) Rozhodněte, zda O-algebra B patří do V.
(c) Popište volnou algebru F0(V) variety V generovanou prázdnou množinou.
(d) Popište volnou algebru Fi (V) variety V generovanou množinou {xi}. Svá tvrzení zdůvodněte.
[Cl-algebra A nepatří do V, neboť například gA(gA(gA(l))) = gA(gA(3)) = gA(5) =4^5 = 5^(3) = gA(nA). Naproti tomu Cl-algebra B patří do V, neboť 5b (5b (5b (6))) = 9b(9b(9b(7))) = 9b(9b(9b(&))) = gB(nB) = &■ Podle definice je F0(Cl) množina všech nulárních termů typu Cl, platí tedy F0(Cl) = {n,g(n),g(g(n)),g(g(g(n))),...}. Přitom rovnost 5(5(5(^1))) = 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 = {Ti,T2}, kde Ti = {n}, T2 = {g(n),g(g(n)),g(g(g(n))),...}, přičemž nc = Tlt 9c(Ti) = gc(T2) = T2. PodobněFi(Cl) je množina všech unárních termů typu Cl, tedy
ri(íí) = {n,g(n),g(g(n)),g(g(g(n))),...,
xi, p(a;i), 5(5(2:1)), g(g(g(xi))),...}
a volná algebra D = F\ (V) variety V generovaná množinou {xi} je pěti-prvková: D = {T1,T2,T3,Ti,T5}, kde 7\ = {n},
T2 = {g(n),g(g(n)),g(g(g(n))),5(5(5(^1))), 5(5(5(5(^1)))), • • • },
T3 = {Xl}, T4 = {5(zi)}> T5 = {gigixí))}, přičemž nD = Tu gD{T{) = gD(T2) = T2, gD(T3) = T4, gD(T4) = T5, gD(T5) = T2.j
[Ú10-7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: nz(a) = a + 1 pro libovolné a € Z (kde + značí obvyklé sčítání). Dále je dána O-algebra A = {A, O} s unární operací nA definovanou takto: nA(Q) = A, nA(A) = Q. Uvažme teorii T = {n(n(n(n(xi)))) = x\} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda existuje homomorfismus O-algebry Z do O-algebry A.
(b) U obou O-algeber A a, I* rozhodněte, zda patří do V.
(c) Popište volnou algebru F0(Cl) typu Cl generovanou prázdnou množinou.
(d) Popište volnou algebru Fi (V) variety V generovanou množinou {xi}. Svá tvrzení zdůvodněte.
[Snadno se ověří, že zobrazení <p : Z —> A, které lichá čísla zobrazí na A a sudá čísla na Q, je homomorfismus Cl-algeber. Dosazením obou prvků Cl-algebry A ověříme, že v ní je identita teorie T splněna, a tedy Cl-algebra A patří do variety V. Naproti tomu Cl-algebra Z nepatří do variety V, neboť například nz(nz(nz(nz(0)))) =4^0. Protože typ Cl nemá žádný nulární operační symbol, neexistuje žádný nulární term typu Cl, a tedy volná algebra F0(Cl) typu Cl, generovaná prázdnou množinou, je prázdná Cl-algebra. Volnou algebrou Fi(Cl) typu Cl, generovanou množinou {xi}, je množina všech unárních termů typu Cl, tedy
Fi(O) = {x1,n(x1),n(n(x1)),n(n(n(x1))),...}.
Faktorizací dostaneme volnou algebru B = F\ (V) variety V generovanou množinou {xi}. Platí B = {Mi,M2, M3, M4}, kde
Mi = {x1,n(n(n(n(x1)))),n(n(n(n(n(n(n(n(x1)))))))),...},
M2 = {n(xi),n(n(n(n(n(xi))))),... },
M3 = {n(n(a;i)),n(n(n(n(n(n(a;i)))))),...},
M4 = {n(n(n(a;i))),n(n(n(n(n(n(n(a;i))))))),...}.
Přitom riij(Mi) = M2, nB(M2) = M3, nB(M3) = M4, nB(M4) = Mx.]
[Úll-7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: nz(a) = a—l pro libovolné a € Z (kde — značí obvyklé odčítání). Dále je dána O-algebra A = {A, 0} s unární operací n a definovanou takto: «^(0) = A, n^A) = O- Uvažme teorii T = {n(n(n(x\))) = n(x\)} a varietu V typu Cl určenou teorií T.
(a) Rozhodněte, zda existuje homomorfismus O-algebry A do O-algebry Z.
(b) U obou O-algeber A a Z rozhodněte, zda patří do V.
(c) Popište volnou algebru Fi(Cl) typu Cl generovanou množinou {xi}.
(d) Popište volnou algebru F2 (V) variety V generovanou množinou {xi ,x2}-
Svá tvrzení zdůvodněte.
[Dokažme sporem, že žádný homomorfismus Cl-algeber <p : A —»• Z neexistuje. Předpokládejme tedy jeho existenci. Pak A = n^O) = ^aÍJia(A)) a tedy z toho, že <p je homomorfismus Cl-algeber, plyne
<p{A) = <p{nA{nA{A))) = nz(nz(¥>(A))) = <p(A) - 2,
což nesplňuje žádné celé číslo <p(A), spor. Dosazením obou prvků Cl-algebry A ověříme, že v ní je identita teorie T splněna, a tedy Cl-algebra A patří do variety V. Naproti tomu Cl-algebra Z nepatří do variety V, neboť například nz(nz(nz(0))) = —3^—1 = nz(0). Volnou algebrou i*i(fi) typu Cl, generovanou množinou {xi}, je množina všech unárních termů typu Cl, tedy Fi (Cl) = {xi,n(xi),n(n(xi)),n(n(n(xi))),...}. Podobně volnou algebrou F2(Cl) typu Cl, generovanou množinou {xi,X2}, je množina všech binárních termů typu Cl, tedy
Faktorizací dostaneme volnou algebru B = F2(V) variety V generovanou množinou {xi,x2}. Platí B = {Mx, M2, M3, M4, M5, M6}, kde
Ml = {Xl},
M2 = {n(xi),n(n(n(xi))),n(n(n(n(n(xi))))),...},
M3 = {n(n(xi)),n(n(n(n(a;i)))),...},
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 riij(Mi) = M2, nB(M2) = M3, nB(M3) = M2, nB(M4) = M5, nB(M5) = M6, nB(M6) = M5~]
[Ú12-7] Je dán typ Cl = {n}, kde n je unární operační symbol. Je dána O-algebra Z (tj. jejími prvky jsou tedy právě všechna celá čísla), na níž je unární operace n% definována předpisem: pro libovolné a € Z klademe
Dále jsou dána zobrazení / : Z —> Z a j : 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 V\ typu Cl je určená teorií Ti = {n(n(n(x\))) = n(n(x\))} a varieta V2 typu Cl je určená teorií T2 = {n(n(xi))) =n(n(x2))} typu Cl.
(a) Rozhodněte, zda zobrazení / je homomorfismem fž-algeber.
(b) Rozhodněte, zda zobrazení g je homomorfismem fž-algeber.
(c) Rozhodněte, zda O-algebra Z patří do variety V\.
(d) Rozhodněte, zda O-algebra Z patří do variety V2.
(e) Popište volnou algebru Fi (Ví) variety Ví generovanou množinou {x\}.
(f) Popište volnou algebru Fi (V2) variety V2 generovanou množinou {xi}.
(g) Rozhodněte, zda variety Ví a V2 jsou stejné.
Svá tvrzení zdůvodněte.
F2(Cl) = {x1,n(x1),n(n(x1)),n(n(n(x1))),
x2, n(x2), n(n(x2)), n(n(n(x2))),...}.
1     pro a > 1,
0     pro — 1 < a < 1,
— 1   pro a < —1.
[Zobrazení f není homomorfismem Cl-algeber, neboť například nz(/(l)) = nz(3) = 1, avšak /(nz(l)) = /(O) = 0. Dokazme, že zobrazení g je homomorfismem Cl-algeber. Pro libovolné a € Z takové, že a > 1 platí také a2 > 1, a tedy nz(g(a)) = nz(a2) = 1 = g(l) = 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(—l) = g(nz(a)). Konečné pro a € {—1,0,1} platí nz(g(a)) = nz(a2) = O = g(0) = g(nz(a)). Dvojnásobnou aplikací nz na libovolný prvek Cl-algebry Z dostaneme O, proto jak varieta V\ určená teorií Ti tak i varieta Vi určená teorií T2 obsahují Cl-algebru Z. Volnou algebrou ŕi(fi) typu Cl, generovanou množinou {xi}, je množina všech unárních termů typu Cl, tedy ŕi(fi) = {xi, n(xi),n(n(xi)),... }. Protože rovnost n(n(n(x\))) = n(n(x\)) 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 = -Fi(Vi) variety V\ generovaná množinou {xi} tři prvky: A = {Mi, M2, M3}, kde Mx = {ari}, M2 = {n(ari)}, M3 = {n(n(xi)),n(n(n(xi))),n(n(n(n(xi)))),...}. Přitom je operace na A definovaná takto: nj4(Mi) = M2, nA(M2) = M3, nA(M3) = M3. Protože rovnost n{n{x\))) = n(n(x2)) znamená, že dvojnásobnou aplikací operace n na libovolný prvek dostaneme vždy tentýž prvek, je výše popsaná Cl-algebra A také volnou algebrou -F\(V2) variety Ví generovanou množinou {xi}. Variety V\ a Ví nejsou stejné, uvažte Cl-algebru B = {1,2} s operací ns(l) = 1, ns(2) = 2. Tato Cl-algebra B patří do variety Ví, ale nepatří do variety Ví-]