ZÁKLADY UNIVERZÁLNÍ ALGEBRY Radan Kučera 1. Operace a -algebry Úvod. V průběhu přednášky z algebry jsme studovali řadu algebraických struktur: grupoidy, pologrupy, grupy, komutativní grupy, okruhy, obory inte- grity, tělesa, polosvazy, svazy, Booleovy algebry. Při zkoumání těchto struk- tur se často některé pojmy a úvahy opakovaly, například ve všech případech jsme hovořili o homomorfismech a vždy platilo, že složením homomorfismů opět dostaneme homomorfismus. Definovali jsme podobjekty (věnovali jsme se hlavně podgrupám, podokruhům, podtělesům a podsvazům) a vždy pla- tilo, že průnikem libovolného neprázdného systému podobjektů je opět po- dobjekt. To nám umožnilo definovat podobjekt generovaný podmnožinou, ve všech případech byly definice v podstatě stejné. V případě grupoidů, grup, okruhů a svazů jsme si definovali součin dvou takových struktur, kterým byla stejná struktura na kartézském součinu. Cílem univerzální algebry je právě tyto společné rysy postihnout a popsat z jednotícího hlediska. Budeme tedy popisovat množiny spolu s několika operacemi na nich. Až dosud jsme operací na množině G měli na mysli zobrazení G×G G, avšak budeme potřebovat tuto definici pozměnit. Vždyť kromě těchto operací, kte- rým v následujícím textu budeme říkat binární operace, jsme se setkali i se zobrazeními G G, kdy byl každému prvku množiny G pevně přiřazen další prvek: například přiřazení inverzního prvku v grupě, opačného prvku v okruhu, či komplementu v Booleově algebře. Toto zobrazení G G budeme nazývat unární operace na množině G. Někdy naše struktura obsahovala ně- jaké význačné prvky, setkali jsme se například s neutrálním prvkem v grupě, s nulou a jedničkou v okruhu, s nejmenším a největším prvkem Booleovy algebry. Tomuto výběru jednoho prvku z množiny G budeme říkat nulární operace na G. Má to určitou logiku: jde totiž vždy o zobrazení z jisté kar- tézské mocniny množiny G do množiny G. Označíme pro přirozené číslo n symbolem Gn kartézský součin n kopií množiny G, tedy Gn je množina všech uspořádaných n-tic prvků množiny G. Jistě lze pak ztotožnit G s G1 (mno- žinou všech uspořádaných 1-tic prvků množiny G). Co by však mělo být G0 ? Jak si představit množinu všech 0-tic prvků množiny G? Podobně jako nul- tou mocninou nenulového čísla rozumíme číslo 1, které je neutrální vzhledem k násobení, nultou kartézskou mocninou nějaké množiny je třeba rozumět množinu, která kartézským vynásobením příliš nezmění násobenou množinu. Vhodnou množinou bude nějaká jednoprvková: ta totiž kartézským součinem nezmění počet prvků násobené množiny (přesněji: je-li A jednoprvková mno- žina, existuje přirozeně definovaná bijekce A × G G pro každou množinu 1 G). Uvědomte si, že to odpovídá i obvyklé definici: pro přirozené číslo n je Gn množina všech uspořádaných n-tic prvků množiny G. Uspořádanou n-tici prvků množiny G lze definovat například jako zobrazení množiny {1, . . . , n} do množiny G. Analogií této konstrukce pro n = 0 je tedy chápat G0 jako množinu všech uspořádaných 0-tic prvků množiny G, přičemž uspořádaná 0- tice prvků množiny G je zobrazení prázdné množiny do množiny G. Takové zobrazení je vždy jedno (ať už je množina G prázdná nebo ne), totiž prázdné zobrazení. Pro libovolnou množinu G budeme proto symbolem G0 rozumět jednoprvkovou množinu; je vhodné si představovat, že tímto jediným prvkem naší jednoprvkové množiny je prázdná množina, tedy že G0 = {}. Pak tedy výběr prvku je zobrazení G0 G. Definice. Nechť G je množina, n nezáporné celé číslo. Pak n-ární operací na množině G rozumíme zobrazení Gn G. Poznámka. Místo 2-ární operace budeme tedy říkat binární operace, místo 1-ární budeme říkat unární. Číslu n z definice říkáme arita dotyčné operace. Při popisu konkrétní operace jsme vždy operaci označovali nějakým symbolem, užívali jsme +, , , pro binární operace, -, -1 , pro unární operace, 0, 1 pro nulární operace. Těmto symbolům budeme říkat operační symboly; je podstatné, že u každého symbolu je dána arita operace, kterou symbolizuje. Definice. Množina spolu se zobrazením a : N{0} se nazývá typ. Prvky množiny se nazývají operační symboly. Pro f se a(f) nazývá arita symbolu f. Operační symbol, jehož arita je n, se nazývá n-ární. Definice. Univerzální algebra typu (neboli stručně -algebra) je mno- žina A, na níž je pro každý n-ární operační symbol z f definována n-ární operace fA : An A. Pro libovolné a1, . . . , an A značíme fA(a1, . . . , an) hodnotu operace fA na uspořádané n-tici (a1, . . . , an). Poznámka. V případě nulárního operačního symbolu f je n = 0, tedy A0 = {} a nulární operací je tedy zobrazení fA : {} A. Zadat takovéto zobrazení je totéž jako vybrat pevně jeden prvek fA() A. Pro zjednodušení označení budeme v dalším textu tento pevně vybraný prvek značit jednoduše fA místo fA(). Poznámka. Obsahuje-li typ alespoň jeden nulární operační symbol, pak je každá -algebra neprázdná. Příklady. 1. Pro prázdný typ, tj. = , je univerzální algebrou typu libovolná množina. 2. Grupoid je množina s jednou binární operací, je to tedy univerzální algebra typu, který má jeden binární operační symbol . 2 3. Grupa je univerzální algebra typu {, -1 , 1}. 4. Okruh je univerzální algebra typu {+, , -, 0, 1}. 5. Svaz je univerzální algebra typu {, }. 6. Booleova algebra je univerzální algebra typu {, , , 0, 1}. 7. Vektorový prostor nad tělesem T lze chápat jako univerzální algebru typu {+, -, 0}T (pro každý prvek tělesa t T máme unární operační symbol pro skalární násobek, což je unární operace na množině vektorů: t(v) = t.v). Poznámka. V předchozích definicích je určitá nepřesnost, správně by- chom totiž měli místo o univerzální algebře A mluvit o univerzální algebře A s nosnou množinou A. Vždyť kupříkladu na jedné a téže nosné množině můžeme mít definovány různé grupoidy, tedy to, o který jde grupoid, není určeno pouze nosnou množinou, ale i operací na ní. Protože to však vždy z kontextu bude patrné, můžeme si snad touto nepřesností usnadnit vyjad- řování: budeme hovořit o -algebře A nebo o nosné množině A. Příklad. Nechť je libovolný typ, A = {a} jednoprvková množina. Pak existuje jediný způsob, jak na nosné množině A definovat -algebru. Pro libovolný n-ární operační symbol f je hodnota operace fA na (jediné existující) n-tici (a, . . . , a) rovna (jediné možné) hodnotě a. 2. Podalgebry a homomorfismy Definice. Nechť A je univerzální algebra typu , H A podmnožina. Řekneme, že H je podalgebra -algebry A, jestliže pro každý n-ární operační symbol f a pro každé a1, . . . , an H platí fA(a1, . . . , an) H. Poznámka. V případě nulárního operačního symbolu f je n = 0, tedy A0 = {}. Obraz tohoto jediného prvku jsme se dohodli značit stručně fA místo (možná přesnějšího) označení fA(). Podmínku z definice je tedy třeba chápat ve smyslu fA H. Poznámka. Obsahuje-li typ alespoň jeden nulární operační symbol, pak je každá podalgebra libovolné -algebry neprázdná. Příklady. V jednotlivých případech příkladu univerzálních algeber z před- chozí kapitoly dostáváme tyto podalgebry: 1. Podmnožina množiny. 2. Pod- grupoid grupoidu. 3. Podgrupa grupy. 4. Podokruh okruhu. 5. Podsvaz svazu. 6. Booleova podalgebra Booleovy algebry. 7. Vektorový podprostor vektoro- vého prostoru. Poznámka. Následující větu jsme v jednotlivých kontextech dokazovali několikrát. 3 Věta 2.1. Nechť A je univerzální algebra typu , I neprázdná množina. Pro každé i I nechť je dána podalgebra Hi A algebry A. Pak jejich průnik iI Hi je podalgebra -algebry A. Důkaz. Zvolme libovolně n-ární operační symbol f a libovolně prvky a1, . . . , an iI Hi. Pak pro každé i I platí a1, . . . , an Hi. Protože Hi je podalgebra -algebry A, platí fA(a1, . . . , an) Hi. To ovšem znamená, že fA(a1, . . . , an) iI Hi, což se mělo dokázat. Důsledek. Obsahuje-li typ alespoň jeden nulární operační symbol, pak je průnik libovolného neprázdného systému podalgeber dané algebry ne- prázdný. Důkaz. V tomto případě není prázdná množina podalgebrou. Důsledek. Nechť P je množina všech podalgeber dané univerzální algebry A typu . Pak platí: (P, ) je úplný svaz. Důkaz. Protože uspořádaná množina (P, ) má největší prvek (je jím celá algebra A jako svá podalgebra), dle příslušné věty o úplných svazech stačí ověřit, že též libovolná neprázdná podmnožina M P má v uspořádané množině (P, ) infimum. Tímto infimem je množinový průnik HM H, který dle předchozí věty je skutečně prvkem množiny P. Poznámka. Předchozí věta 2.1 nám umožňuje definovat podalgebru ge- nerovanou množinou. Definice. Nechť A je univerzální algebra typu , M A podmnožina nosné množiny. Průnik všech podalgeber -algebry A, které obsahují M jako svou podmnožinu, značíme M a nazýváme podalgebrou -algebry A gene- rovanou množinou M. Poznámka. Díky tomu, že alespoň jedna podalgebra -algebry A ob- sahující množinu M existuje (je jí jistě celá -algebra A), podle věty 2.1 je zmíněným průnikem M skutečně podalgebra -algebry A. Zřejmě je to ze všech podalgeber -algebry A obsahujících množinu M ta nejmenší (vzhle- dem k množinové inkluzi). Příklady. V jednotlivých případech příkladu univerzálních algeber z před- chozí kapitoly dostáváme tyto podalgebry generované množinou: 1. V případě -algebry A prázdného typu = je každá podmnožina množiny A podalgebrou, proto v tomto případě pro libovolné M A je podalgebrou -algebry A generovanou množinou M sama množina M. 2. Podgrupoid grupoidu generovaný množinou. Tento pojem jsme v před- nášce nezaváděli. 3. Podgrupa M grupy generovaná množinou M. 4 4. Podokruh M okruhu generovaný množinou M. 5. Podsvaz svazu generováný množinou (nezaváděli jsme). 6. Booleova podalgebra Booleovy algebry generovaná množinou (též jsme nezaváděli). 7. Vektorový podprostor vektorového prostoru generovaný množinou vek- torů, což je jeden z nejdůležitějších pojmů lineární algebry. Poznámka. Díky tomu, že podalgebra -algebry je podmnožina uza- vřená na všechny operace příslušné operačním symbolům typu , lze tyto operace zúžit na podalgebru. Proto každá podalgebra je sama -algebrou. Uvědomte si, že tuto úvahu jsme prováděli v průběhu přednášky několikrát v různých kontextech. Poznámka. Nyní budeme definovat homomorfismus -algeber. Dá se asi čekat, že to bude takové zobrazení nosných množin, které pro každou operaci splní následující podmínku: jestliže zobrazíme výsledek operace, musíme do- stat totéž, jako když zobrazíme každý operand zvlášť a operaci provedeme až ve druhé algebře. Definice. Nechť A, B jsou univerzální algebry téhož typu , : A B zobrazení. Řekneme, že je homomorfismus -algeber, jestliže pro každý operační symbol f arity n a každé prvky a1, . . . , an A platí fB((a1), . . . , (an)) = (fA(a1, . . . , an)). Poznámka. Pro nulární operační symbol předchozí podmínka samo- zřejmě znamená (fA) = fB. Poznámka. Jestliže je -algebra A prázdná (v tomto případě tedy typ nemůže obsahovat žádný nulární operační symbol), pak pro libovolnou - algebru B existuje jediný homomorfismus -algeber A B, totiž prázdné zobrazení. Jestliže naopak -algebra B je prázdná, pak homomorfismus - algeber A B existuje pouze v případě, kdy i -algebra A je prázdná. Příklady. Porovnejme v jednotlivých případech předchozích příkladů tuto definici s definicemi uváděnými dříve pro jednotlivé speciální případy univerzálních algeber: 1. V případě -algeber prázdného typu = je každé zobrazení homo- morfismem. 2. Pro grupoidy je tato definice totožná s obvyklou definicí homomorfismu grupoidů. 3. Pro grupy byl homomorfismus definován stejně jako pro grupoidy, tedy v definici bylo vyžadováno, aby zachovával součin. Právě uvedená de- finice pro případ grup vyžaduje, aby homomorfismus zachovával též 5 inverzní prvky a zobrazil neutrální prvek grupy A na neutrální prvek grupy B. Je asi jasné, proč tyto požadavky nebyly obsaženy v definici homomorfismu grup: jak jsme si dokazovali, to jsou pouhé důsledky toho, že homomorfismus grup zachovává součin. 4. Pro okruhy jsme v definici homomorfismu vyžadovali, aby zachovával sčítání, násobení a převáděl na sebe jedničky okruhů. Jako důsledek jsme dostali další podmínky z právě provedené obecné definice, týkající se opačných prvků a nul okruhů. 5. V případě svazů obě definice splývají: vyžaduje se, aby homomorfismus zachovával a . 6. V případě Booleových algeber jsme požadovali, aby homomorfismus zachovával , , 0 a 1. Jako důsledek jsme pak obdrželi, že už nutně musí zachovávat též komplementy, proto nebylo nutné komplementy zahrnout do definice homomorfismu Booleových algeber. 7. V případě vektorových prostorů odpovídá homomorfismu lineární zob- razení. Poznámka. Následující dvě věty pro jednotlivé speciální případy univer- zálních algeber známe z přednášky: složením dvou homomorfismů opět do- staneme homomorfismus, homomorfním obrazem grupy (grupoidu, okruhu, atd.) je podgrupa (podgrupoid, podokruh, atd.). Věta 2.2. Nechť A, B, C jsou univerzální algebry téhož typu , : A B a : B C homomorfismy -algeber. Pak je též složení homomorfismus -algeber. Důkaz. Protože je homomorfismus -algeber, pro každý operační sym- bol f arity n a každé prvky a1, . . . , an A platí (fA(a1, . . . , an)) = fB((a1), . . . , (an)). Protože je též homomorfismus -algeber, platí (fB((a1), . . . , (an))) = fC(((a1)), . . . , ((an))). Dohromady tedy ( )(fA(a1, . . . , an)) = ((fA(a1, . . . , an))) = = (fB((a1), . . . , (an))) = = fC(((a1)), . . . , ((an))) = = fC(( )(a1), . . . , ( )(an)), což jsme měli dokázat. 6 Věta 2.3. Nechť A, B jsou univerzální algebry téhož typu , : A B homomorfismus -algeber. Pak obraz -algebry A v homomorfismu (A) = {(a); a A} je podalgebra -algebry B. Důkaz. Zvolme libovolně operační symbol f arity n. Pak pro každé prvky b1, . . . , bn (A) existují a1, . . . , an A tak, že (a1) = b1, . . . , (an) = bn. Z definice homomorfismu plyne fB(b1, . . . , bn) = fB((a1), . . . , (an)) = (fA(a1, . . . , an)) (A). Definice. Nechť A, B jsou univerzální algebry téhož typu , : A B zobrazení. Řekneme, že je izomorfismus -algeber, jestliže je bijektivní homomorfismus -algeber. Řekneme, že -algebry A a B jsou izomorfní, jestliže existuje nějaký izomorfismus -algeber A B. Poznámka. Následující věta formuluje očekávanou vlastnost vztahu být izomorfní: je reflexivní, symetrický a tranzitivní. Věta 2.4. Nechť A, B, C jsou univerzální algebry téhož typu . Pak platí: ˇ A je izomorfní s A; ˇ je-li A izomorfní s B, pak je též B izomorfní s A; ˇ jestliže A je izomorfní s B a B je izomorfní s C, pak je též A izomorfní s C. Důkaz. To je snadné, dokažte si sami jako cvičení. Poznámka. Je jasné, že dvě -algebry jsou izomorfní, právě když lze jednu dostat ze druhé přejmenováním prvků. Proto izomorfní -algebry mají všechny algebraické vlastnosti stejné. 3. Součiny Poznámka. Podobně jako jsme definovali součin grup nebo svazů, lze definovat součin libovolných dvou -algeber. Pro každý operační symbol bu- deme definovat operaci na množině všech uspořádaných dvojic po složkách. Definice. Nechť A, B jsou univerzální algebry téhož typu . Na kartéz- ském součinu A × B definujeme novou univerzální algebru typu , kterou nazveme součinem -algeber A a B. Pro každý operační symbol f arity n a každé prvky a1, . . . , an A, b1, . . . , bn B klademe fA×B((a1, b1), . . . , (an, bn)) = (fA(a1, . . . , an), fB(b1, . . . , bn)). 7 Poznámka. Předchozí podmínka v případě nulárního operačního sym- bolu f pochopitelně znamená fA×B = (fA, fB). Poznámka. Vzpomeňte si, že u součinu grup jsme pracovali s projekcemi ze součinu do původních grup, což byly surjektivní homomorfismy. Stejnou situaci máme i nyní obecně pro -algebry. Protože však -algebry mohou být i prázdné, nemusí být obecně projekce ze součinu surjektivní. Definice. Nechť A, B jsou univerzální algebry téhož typu , A×B součin těchto -algeber. Definujme projekce 1 : A × B A, 2 : A × B B ze součinu A × B předpisem: pro každé a A, b B klademe 1((a, b)) = a, 2((a, b)) = b. Věta 3.1. Nechť A, B jsou univerzální algebry téhož typu , A×B součin těchto -algeber. Pak obě projekce 1, 2 jsou homomorfismy -algeber. Důkaz. Ukažme, že projekce 1 je homomorfismus -algeber. Za tím účelem zvolme libovolně operační symbol f arity n a prvky a1, . . . , an A, b1, . . . , bn B. Platí 1 fA×B((a1, b1), . . . , (an, bn)) = 1 (fA(a1, . . . , an), fB(b1, . . . , bn)) = = fA(a1, . . . , an) = = fA(1((a1, b1)), . . . , 1((an, bn))). Zcela analogicky se dokáže, že projekce 2 je homomorfismus -algeber. Věta 3.2. Nechť A, B, C jsou univerzální algebry téhož typu , : C A, : C B homomorfismy -algeber. Pak existuje jediný homomorfismus -algeber : C A × B s vlastností 1 = , 2 = , kde 1 : A × B A, 2 : A × B B jsou projekce ze součinu A × B. Důkaz. Je zřejmé, že podmínky 1 = , 2 = platí právě tehdy, když definujeme : C A × B následujícím předpisem: pro každé c C klademe (c) = ((c), (c)). Ověřme, že je to homomorfismus -algeber. Zvolme libovolně operační symbol f arity n a prvky c1, . . . , cn C, pak platí fA×B((c1), . . . , (cn)) = fA×B(((c1), (c1)), . . . , ((cn), (cn))) = = fA((c1), . . . , (cn)), fB((c1), . . . , (cn)) . Nyní využijeme toho, že : C A, : C B jsou homomorfismy - algeber: fA((c1), . . . , (cn)), fB((c1), . . . , (cn)) = = (fC(c1, . . . , cn)), (fC(c1, . . . , cn)) = = (fC(c1, . . . , cn)), 8 což se mělo dokázat. Poznámka. Nyní můžeme zobecnit součin -algeber takto: místo sou- činu dvou -algeber budeme definovat součin libovolného počtu -algeber. Nejprve potřebujeme zobecnit definici kartézského součinu množin. Definice. Jestliže pro libovolný prvek i množiny I je dána množina Ai, pak kartézským součinem množin Ai rozumíme množinu všech zobrazení z množiny I takových, že (i) Ai pro každé i I: iI Ai = : I iI Ai; i I : (i) Ai . Pro libovolné j I definujeme j-tou projekci j z kartézského součinu A = iI Ai takto: j : A Aj je určeno předpisem j() = (j) pro každé A. Poznámka. Promysleme si, co znamená předchozí definice ve speciálním případě, kdy indexová množina I je prázdná. Pak přestože vlastně žádnou množinu Ai nemáme, jsme oprávněni mluvit o součinu: dle definice je souči- nem i Ai množina všech zobrazení : i Ai. Protože iI Ai je množina všech prvků x, pro které existuje i I tak, že x Ai, je zřejmě i Ai = . Ovšem zobrazení : je jediné, totiž prázdné zobrazení. Proto množina i Ai je jednoprvková; jejím jediným prvkem je prázdné zobrazení. Poznámka. Uvědomte si, že pro I = {1, 2} předchozí definice splývá s obvyklou: pod kartézským součinem množin A1, A2 rozumíme množinu uspořádaných dvojic A1 × A2 = {(a, b); a A1, b A2}. Ovšem zadat uspořádanou dvojici (a, b) není nic jiného než pevně zvolit a A1, b A2, což znamená právě tolik jako definovat zobrazení : {1, 2} A1A2 s vlastností (1) A1, (2) A2: položíme (1) = a, (2) = b. Proto následující definice součinu libovolného počtu -algeber zobecňuje předchozí definici součinu dvou -algeber. Definice. Nechť je typ. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai typu . Součinem těchto -algeber rozumíme novou -algebru definovanou na kartézském součinu A = iI Ai takto: pro každý operační symbol f arity n a každé prvky 1, . . . , n A, klademe fA(1, . . . , n) = , kde A je určeno podmínkou (i) = fAi (1(i), . . . , n(i)) pro každé i I. Poznámka. Ve speciálním případě, kdy indexová množina I je prázdná, je součinem -algebra na jednoprvkové množině, jejímž jediným prvkem je 9 prázdné zobrazení. Tato -algebra je jediná, neboť na jednoprvkové množině pro libovolné nezáporné celé číslo n existuje jen jedna n-ární operace (viz po- známku na konci první kapitoly). Dochází tedy k situaci, která se může zdát na první pohled paradoxní: ačkoli nemáme žádnou -algebru, jako součin dostáváme jednoprvkovou -algebru. Tedy naprosto z ničeho jsme najednou dostali informaci o tom, jak vypadá . Ale to se dá snadno vysvětlit: součin je součin -algeber, lze jej aplikovat pouze na -algebry pro určité . Informace o tom, jak toto vypadá, je tedy uložena v tom, o jaký součin se jedná. Pokud bychom chtěli být naprosto přesní, měli bychom toto nějak v symbolu vyznačit, abychom jednotlivé součiny od sebe odlišili. Jenže nějaký index by jen zbytečně komplikoval zápis, stačí, že víme, že součin je pro dané . Vyplývá odtud i to, co snad bylo jasné už od začátku: součin jsme definovali jen pro univerzální algebry téhož typu. Poznámka. Pro nulární operační symbol f podmínka v předchozí definici samozřejmě znamená fA = , kde A je určeno podmínkou (i) = fAi . Věta 3.3. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai daného typu , nechť A = iI Ai je jejich součin. Pak platí ˇ Pro každé j I je j-tá projekce j : A Aj homomorfismus - algeber. ˇ Nechť C je univerzální algebra téhož typu , a pro každé j I nechť je dán homomorfismus -algeber j : C Aj. Pak existuje jediný homomorfismus -algeber : C A takový, že j = j pro každé j I. Důkaz. Postupujeme naprosto stejně jako při důkazech vět 3.1 a 3.2 pro součin dvou -algeber, odlišnost je pouze formální. Dokažme nejdříve první tvrzení. Zvolme libovolně j I a ukažme, že projekce j je homomorfismus -algeber. Za tím účelem zvolme libovolně operační symbol f arity n a prvky 1, . . . , n A. Označme = fA(1, . . . , n). Přímo z definice plyne j(fA(1, . . . , n)) = j() = (j) = fAj (1(j), . . . , n(j)) = = fAj (j(1), . . . , j(n)), což se mělo dokázat. Dokažme nyní druhé tvrzení. Je zřejmé, že podmínka j = j pro každé j I platí právě tehdy, když definujeme : C A následujícím předpisem. Pro každé c C klademe (c) = , kde A je určeno podmínkou: pro libovolné j I platí (j) = j() = j((c)) = (j )(c) = j(c). 10 Pro (c) A tedy platí: pro každé j I je ((c))(j) = j(c). Ověřme, že takto definované zobrazení : C A je homomorfismus -algeber. Zvolme libovolně operační symbol f arity n a prvky c1, . . . , cn C. Označme = fA((c1), . . . , (cn)), podle definice součinu -algeber pak pro každé i I platí (i) = fAi (((c1))(i), . . . , ((cn))(i)) = fAi (i(c1), . . . , i(cn)) = = i(fC(c1, . . . , cn)), neboť i : C Ai je homomorfismus -algeber. Ovšem i(fC(c1, . . . , cn)) = i (fC(c1, . . . , cn)) = (fC(c1, . . . , cn)) (i). To znamená, že a (fC(c1, . . . , cn)) jsou (jakožto prvky kartézského sou- činu) zobrazení se stejným definičním oborem, oborem hodnot i předpisem, proto platí = (fC(c1, . . . , cn)), tj. fA((c1), . . . , (cn)) = (fC(c1, . . . , cn)), což se mělo dokázat. 4. Kongruence a faktorové algebry Poznámka. V této kapitole zobecníme pojmy faktorgrupa a faktorokruh na případ libovolné -algebry. Nepodaří se nám však nalézt pojem odpoví- dající pojmům normální podgrupa grupy a ideál okruhu. Uvědomme si, jak jsme pojem normální podgrupa dostali: při faktorizaci grupy nebylo nutné si pamatovat celý rozklad nosné množiny užívaný k faktorizaci, stačilo si pamatovat tu třídu, která obsahovala neutrální prvek grupy. Celý rozklad jsme totiž byli schopni ze znalosti této jediné třídy jednoznačně určit, neboť tato třída byla normální podgrupa celé grupy a zmíněný rozklad byl rozkla- dem příslušným této podgrupě. Tato situace se pak opakovala i v případě okruhů, vždyť každý okruh (zapomeneme-li na operaci násobení) je komu- tativní grupa. To ale samozřejmě neplatí pro libovolné -algebry. Proto při faktorizaci -algeber nevystačíme jen se zadáním nějaké vhodné podmno- žiny nosné množiny (jakožto jedné třídy rozkladu), ale bude vždy třeba za- dat rozklad celý. Rozklad samozřejmě lze zadat pomocí jemu odpovídající ekvivalence. Definice. Nechť A je univerzální algebra typu , nechť je relace ekvi- valence na nosné množině A. Řekneme, že je kongruence na -algebře A, jestliže pro každý n-ární operační symbol f a pro každé a1, . . . , an, b1, . . . , bn A platí a1 b1, . . . , an bn = fA(a1, . . . , an) fA(b1, . . . , bn). 11 Poznámka. Následující věta popisuje vztah mezi homomorfismy -algeber a kongruencemi na -algebrách: každý homomorfismus zadává kongruenci. Později dokážeme, že i naopak každá kongruence vzniká tímto způsobem z vhodného homomorfismu. Věta 4.1. Nechť A, B jsou univerzální algebry téhož typu , : A B homomorfismus -algeber. Pak relace na nosné množině A definovaná předpisem: pro každé a, b A platí a b (a) = (b) (1) je kongruence na -algebře A. Důkaz. Zřejmě je ekvivalencí příslušnou zobrazení . Stačí tedy uká- zat, že splňuje implikaci v definici kongruence. Zvolme libovolně n-ární ope- rační symbol f a prvky a1, . . . , an, b1, . . . , bn A tak, že a1 b1, . . . , an bn. Odtud plyne (a1) = (b1), . . . , (an) = (bn). Pak ovšem z definice homomorfismu (fA(a1, . . . , an)) = fB((a1), . . . , (an)) = fB((b1), . . . , (bn)) = = (fA(b1, . . . , bn)), což znamená dokazované fA(a1, . . . , an) fA(b1, . . . , bn). Definice. Nechť A, B jsou univerzální algebry téhož typu , : A B homomorfismus -algeber. Kongruence na -algebře A definovaná před- pisem (1) předchozí věty se nazývá jádro homomorfismu . Poznámka. Na rozdíl od jádra homomorfismu grup, což byla normální podgrupa grupy A, a jádra homomorfismu okruhů, což byl ideál okruhu A, není tedy jádro homomorfismu -algeber podmnožina nosné množiny A, ale ekvivalence na nosné množině A. Je to dáno tím, že (jak jsme již zmiňovali v úvodní poznámce této kapitoly) v obecném případě -algeber není možné charakterizovat celý rozklad (a tedy celou ekvivalenci) pouze jedinou jeho třídou. Poznámka. V následující definici k dané -algebře A a dané kongruenci na ní sestrojíme faktorovou -algebru způsobem známým z faktorizace grup a okruhů: na rozkladu příslušném (vždyť je ekvivalence na nosné množině A) zavedeme operace pomocí reprezentantů. Jako obvykle pak bude potřeba ověřit korektnost této definice, tj. dokázat, že provedená konstrukce nezáleží na naší libovůli při volbě reprezentantů. Definice. Nechť A je univerzální algebra typu , nechť je kongruence na -algebře A. Označme R = A/ rozklad příslušný . Pro každý n-ární operační symbol f definujme n-ární operaci na R takto: pro každé 12 X1, . . . , Xn R zvolme a1 X1, . . . , an Xn a definujme fR(X1, . . . , Xn) tím, že je to třída obsahující prvek fA(a1, . . . , an). Množina R spolu s právě zavedenými operacemi se nazývá faktorová algebra -algebry A podle kon- gruence , značí se A/. Věta 4.2. Předchozí definice je korektní. Důkaz. Je třeba ověřit nezávislost na volbě reprezentantů. Zachovejme veškeré označení z definice a zvolme ještě další reprezentanty: nechť též b1 X1, . . . , bn Xn. Ovšem patřit do stejné třídy rozkladu znamená být ekvivalentní, tedy platí a1 b1, . . . , an bn. Z definice kongruence pak dostáváme fA(a1, . . . , an) fA(b1, . . . , bn), což znamená, že fA(a1, . . . , an) a fA(b1, . . . , bn) patří do stejné třídy rozkladu, totiž do třídy fR(X1, . . . , Xn). Příklad. Příklad faktorgrupy a faktorokruhu je známý. Ukažme si proto něco, co jsme v přednášce z algebry nedělali. Univerzální algebra nám dává návod, jak faktorizovat svazy. Nechť (S, , ) je svaz. Kongruence na něm je ekvivalence na množině S splňující: pro každé a, b, c, d S takové, že a b a c d, platí a c b d a a c b d. Je-li kongruence na svazu (S, , ), pak faktorsvaz je svaz, jehož nosná množina je rozklad S/ a operace na ní jsou definovány pomocí reprezentantů: pro T, R S/ zvolíme a T, b R a definujeme T R jako třídu obsahující a b a T R jako třídu obsahující a b. Věta 4.3. Nechť A je univerzální algebra typu , kongruence na - algebře A. Pak zobrazení : A A/ určené předpisem a (a) pro libovolné a A (tedy (a) je třída obsahující prvek a) je surjektivní homo- morfismus -algeber. Důkaz. Zobrazení je surjekce, neboť každá třída rozkladu X A/ je neprázdná, existuje tedy a X, pro které samozřejmě platí (a) = X. Ukažme, že je homomorfismus -algeber. Zvolme libovolně n-ární operační symbol f a prvky a1, . . . , an A. Označme X1 = (a1), . . . , Xn = (an). Pak tedy a1 X1, . . . , an Xn a fA/(X1, . . . , Xn) je určeno tím, že obsahuje prvek fA(a1, . . . , an), tj. (fA(a1, . . . , an)) = fA/(X1, . . . , Xn) = fA/((a1), . . . , (an)), což se mělo dokázat. Definice. Surjektivní homomorfismus -algeber : A A/ konstruo- vaný v předchozí větě se nazývá projekce -algebry A na faktorovou algebru A/. Důsledek. Nechť A je univerzální algebra typu . Platí, že každá kon- gruence na -algebře A je jádrem vhodného homomorfismu -algeber vychá- zejícího z -algebry A. 13 Důkaz. Nechť je libovolná kongruence na -algebře A. Nechť : A A/ je projekce -algebry A na faktorovou algebru A/. Tvrzení bude dokázáno, ověříme-li, že jádrem je . Označme jádro . Podle definice jádra homomorfismu pro libovolné a, b A platí a b právě tehdy, když (a) = (b), což podle definice projekce znamená, že a a b patří do téže třídy rozkladu A/, neboli a b. Definice. Nechť A je množina, a ekvivalence na množině A. Řek- neme, že ekvivalence je menší nebo rovna ekvivalenci , jestliže pro každé a, b A platí implikace a b = a b. Poznámka. Protože dle definice je ekvivalence na množině A relací na množině A, tedy podmnožinou kartézského součinu A × A, přičemž napří- klad a b je stručnější a přehlednější zápis faktu (a, b) , znamená impli- kace z předchozí definice vlastně množinovou inkluzi . Nemuseli jsme tedy pro ekvivalence pojem menší vůbec zavádět, důvodem byla jen snaha o snadnější porozumění textu. Plyne odtud, že tato relace je uspořádáním na množině všech ekvivalencí na množině A. Nejmenší prvek této uspořá- dané množiny je ekvivalence = (dva prvky jsou ekvivalentní, právě když jsou stejné), největším prvkem je ekvivalence A × A, v níž každé dva prvky mno- žiny A jsou ekvivalentní (tedy jí odpovídající rozklad má ­ v případě A = ­ jedinou třídu rozkladu, totiž celou množinu A). Uvažme libovolnou ne- prázdnou množinu E ekvivalencí na množině A. Průnikem všech ekvivalencí E je tedy relace na množině A, pro kterou platí: pro libovolné a, b A je a b právě tehdy, když pro každé E platí a b. Snadno se ověří, že relace je též ekvivalencí na množině A (promyslete si důkaz sami, je opravdu snadný). Odvodili jsme, že množina všech ekvivalencí na množině A uspořádaná inkluzí je úplný svaz. Rovněž množina všech kongruencí na dané -algebřě A uspořádaná inkluzí tvoří úplný svaz, jak plyne z následující věty, uvědomíte-li si, že relace A × A je vždy kongruencí na -algebřě A. Věta 4.4. Nechť A je univerzální algebra typu , K neprázdná množina kongruencí na -algebře A. Nechť relace na množině A je průnikem všech kongruencí z množiny K, tj. pro libovolné a, b A klademe a b právě tehdy, když pro každé K je a b. ˇ Pak relace je kongruencí na -algebře A. ˇ Uvažme součin -algeber B = K A/. Pro každé K označme : B A/ projekci ze součinu a : A A/ projekci - algebry A na faktorovou algebru A/. Podle věty 3.3 existuje jediný homomorfismus -algeber : A B takový, že = . Pak platí: jádrem homomorfismu je kongruence . 14 Důkaz. První tvrzení je důsledkem druhého, neboť podle věty 4.1 je jádro libovolného homomorfismu kongruencí. Označme jádro homomorfismu . Pro libovolné a, b A platí a b právě tehdy, když (a) = (b), což podle definice součinu -algeber nastane právě tehdy, když pro každé K platí ((a)) = ((b)), což vzhledem k = znamená právě (a) = (b), neboli a b. Dokázali jsme, že pro libovolné a, b A platí a b právě tehdy, když pro každé K je a b, což však podle definice relace nastane, právě když a b. Věta je dokázána. Poznámka. Následující věta je zobecněním vět, které jsme si uváděli pro faktorgrupy a faktorokruhy. Věta 4.5. Nechť A, B jsou univerzální algebry téhož typu , : A B homomorfismus -algeber s jádrem . Nechť je libovolná kongruence na - algebře A menší nebo rovna kongruenci . Označme : A A/ projekci -algebry A na faktorovou algebru A/. Pak platí ˇ Existuje jediné zobrazení ~ : A/ B takové, že ~ = . ˇ Toto zobrazení ~ je homomorfismus -algeber. ˇ Homomorfismus ~ je surjektivní, právě když homomorfismus je surjek- tivní. ˇ Homomorfismus ~ je injektivní, právě když jsou obě kongruence a stejné (tj. = ). Důkaz. Konstruujme zobrazení ~ : A/ B tak, aby ~ = . Zvolme libovolně X A/. Protože X je třída rozkladu, je neprázdná, a tedy existuje a X. Podle definice pak (a) = X. Pak z podmínky ~ = plyne ~(X) = ~((a)) = ( ~ )(a) = (a). To ovšem znamená, že pokud nějaké zobrazení ~ : A/ B splňující ~ = existuje, je jediné. Definujme tedy ~ : A/ B tímto jediným způsobem: pro libovolné X A/ tedy zvolíme a X a klademe ~(X) = (a). Je ale třeba ověřit korektnost této definice, neboli nezávislost na volbě a X. Mějme další b X, pak oba prvky a, b leží v téže třídě X rozkladu A/, odkud a b. Protože kongruence je menší nebo rovna kongruenci , plyne odtud a b. Ovšem je jádrem homomorfismu , proto poslední znamená (a) = (b). Je tedy skutečně definice zobrazení ~ korektní. Dokažme nyní, že zobrazení ~ je homomorfismus -algeber. Za tím účelem zvolme libovolně operační symbol f arity n a prvky X1, . . . , Xn A/. Zvolme libovolně a1, . . . , an A tak, že (a1) = X1, . . . , (an) = Xn. Protože 15 a jsou homomorfismy -algeber, platí ~ fA/(X1, . . . , Xn) = ~ fA/((a1), . . . , (an)) = = ~ (fA(a1, . . . , an)) = = ( ~ )(fA(a1, . . . , an)) = = (fA(a1, . . . , an)) = = fB((a1), . . . , (an)) = = fB(( ~ )(a1), . . . , ( ~ )(an)) = = fB( ~((a1)), . . . , ~((an))) = = fB( ~(X1), . . . , ~(Xn)), což jsme měli dokázat. Jestliže je homomorfismus surjektivní, pak pro každé b B existuje a A tak, že b = (a) = ( ~ )(a) = ~((a)), což znamená, že homomorfismus ~ je surjektivní. Je-li naopak homomorfismus ~ surjektivní, pak též jakožto složení dvou surjekcí je surjektivní (dokažte si sami). Předpokládejme, že = , a ukažme, že homomorfismus ~ je injektivní. Nechť X1, X2 A/ jsou libovolné prvky splňující ~(X1) = ~(X2). Zvolme libovolně a1, a2 A tak, že (a1) = X1, (a2) = X2. Pak platí (a1) = ( ~ )(a1) = ~((a1)) = ~(X1) = = ~(X2) = ~((a2))( ~ )(a2) = (a2), odkud z definice jádra homomorfismu plyne a1 a2, a proto a1 a2, což znamená, že prvky a1 a a2 leží v téže třídě rozkladu, kterou je X1 = X2. Předpokládejme naopak, že homomorfismus ~ je injektivní. Stačí ově- řit, že kongruence je menší nebo rovna kongruenci , neboť opačnou nerovnost máme v předpokladech věty. Nechť tedy jsou a, b A takové, že a b. Pak z definice jádra homomorfismu plyne (a) = (b), tedy ~((a)) = ~((b)). Protože předpokládáme, že ~ je injektivní homomorfis- mus, plyne odtud (a) = (b). Podle definice projekce na faktorovou algebru to znamená, že a a b leží v téže třídě rozkladu A/, tedy a b. Důkaz věty je skončen. Důsledek. Nechť A, B jsou univerzální algebry téhož typu , : A B homomorfismus -algeber s jádrem . Pak obraz -algebry A v homomor- fismu (A) = {(a); a A} je -algebra izomorfní s faktorovou algebrou A/. Důkaz. Stačí užít předchozí větu pro = a uvědomit si, že (A) = ( ~ )(A) = ~(A/), neboť projekce je surjektivní. 16 5. Termy Poznámka. V následující kapitole budeme chtít definovat rovnosti. Pří- kladem těchto rovností jsou komutativní, asociativní, distributivní, absorpční a další identity, se kterými jsme se setkali. Jde vždy o rovnost mezi dvěma výrazy, které obsahují nějaké proměnné spolu svázané operacemi. Tyto vý- razy nazýváme termy. Potřebujeme nyní přesně tyto termy definovat. Jediná cesta je definovat je induktivně, tedy říci, že term je něco, co lze určitými pravidly získat z nejjednodušších termů. Představme si pro určitost nějaké konkrétní rovnosti, například následující rovnosti platné v Booleových alge- brách x x = 1, x x = x. Vidíme, že zde nejjednoduššími termy jsou nulární operace 1 a proměnná x. Z nich se pak konstruují složitější termy x , x x, x x . Obecně nevystačíme s jedinou proměnnou (vzpomeňte si na rovnosti popisující komutativní nebo asociativní zákon). Na druhou stranu je jasné, že vždy máme v rovnosti jen konečně mnoho proměnných. Proto bude stačit pracovat s následujícími proměnnými x1, x2, x3, . . . Definice. Nechť je typ. Termem typu nazveme právě takový výraz, který lze zkonstruovat konečně mnoha aplikacemi následujících pravidel: ˇ Pro libovolné přirozené číslo n je proměnná xn term typu . ˇ Pro libovolný nulární operační symbol f je f term typu . ˇ Pro libovolné přirozené číslo n, libovolný n-ární operační symbol f a libovolné termy t1, . . . , tn typu je výraz f(t1, . . . , tn) term typu . Poznámka. Pokud by měl někdo pocit, že přes veškerou snahu o přes- nost je předchozí definice stejně nepřesná, neboť užívá nedefinovaný pojem výraz, může si předchozí definici opravit tím, že místo o výrazech bude mluvit o konečných posloupnostech symbolů z abecedy, která se skládá z množiny proměnných, množiny , kulatých závorek a čárky, tedy o slovech nad touto abecedou. Poznamenejme též, že striktně podle definice například xx term není, správně bychom jej totiž měli psát ve tvaru (x1, (x1)). Je jasné, že poslední zápis na přehlednosti nepřidal, proto nebudeme užívat dogmaticky jen zápisy termů povolené předchozí definicí. Na druhou stranu je nezbytné, abychom vždy věděli, jak term, který užíváme, má dle této definice vypadat. Definice. Řekneme, že term t typu je n-ární, jestliže se při jeho kon- strukci nevyužilo žádné proměnné xm pro m > n. Příklad. Term x2 je binární, ovšem je též 3-ární a také 4-ární atd. Není však unární, přestože v něm vystupuje jen jedna proměnná. Příklad. Nulární term typu je term, při jehož konstrukci se nepoužila žádná proměnná, byl tedy vytvořen jen pomocí druhého a třetího pravidla 17 z definice termu. Je jasné, že takové termy existují jen pro typy obsahující alespoň jeden nulární operační symbol. Poznámka. Je vcelku patrné, že každý n-ární term t typu nám v libo- volné -algebře A zadává n-ární operaci. Chceme-li tento jasný fakt definovat přesně, je nutné užít opět induktivní definici. Definice. Nechť t je n-ární term typu . Nechť A je univerzální algebra typu . Definujeme n-ární operaci tA určenou termem t na -algebře A následujícím způsobem. Nechť a1, . . . , an A jsou libovolné prvky. ˇ Je-li termem t proměnná xk, pak operací určenou termem t je k-tá projekce z kartézského součinu, tj. pro t = xk klademe tA(a1, . . . , an) = ak. ˇ Je-li termem t nulární operační symbol f , pak operací určenou termem t je operace na -algebře A příslušná symbolu f, tj. pro t = f klademe tA(a1, . . . , an) = fA. ˇ Je-li term t složen pomocí k-árního operačního symbolu f , kde k 1, z termů t1, . . . , tk typu , pak operaci tA určenou termem t defi- nujeme takto: její hodnota v n-tici (a1, . . . , an) je hodnota operace fA na -algebře A příslušné symbolu f v k-tici ((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an)) hodnot operací příslušných termům t1, . . . , tk v n-tici (a1, . . . , an), tj. pro t = f(t1, . . . , tn) klademe tA(a1, . . . , an) = fA((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an)). Poznámka. Protože libovolný n-ární term typu lze považovat též za m-ární term typu pro libovolné m n, dopustili jsme se v předchozí definici jisté nepřesnosti: stejným symbolem tA označujeme různé operace! Je-li k nejmenší takové, že term t je k-ární, pak tA značí n-ární operaci na -algebře A pro každé nezáporné celé číslo n k. Ukažme to na následujícím příkladu. Příklad. Předpokládejme, že obsahuje binární operační symbol +. Jestliže například považujeme term x1 + x2 za binární, pak podle předchozí definice platí (x1 +x2)A(a1, a2) = a1 +a2, pokud tento term však považujeme za 3-ární, pak (x1 + x2)A(a1, a2, a3) = a1 + a2. Obecně, pro libovolné n 2, je-li term x1 + x2 považován za n-ární, pak (x1 + x2)A(a1, . . . , an) = a1 + a2. Poznámka. V předchozím příkladě jsme viděli, že nepřesnost, které se dopouštíme, není nijak fatální. Dokážeme to v následující větě. Věta 5.1. Nechť t je n-ární term typu , nechť přirozené číslo m > n. Pak pro libovolnou univerzální algebru A typu a libovolné a1, . . . , am A platí tA(a1, . . . , an) = tA(a1, . . . , am), 18 kde symbolem tA rozumíme vlevo n-ární operaci určenou termem t na A, kdežto vpravo m-ární operaci určenou termem t na A. Důkaz. Důkaz povedeme indukcí vzhledem k termu t podle definice termu. První krok této indukce spočívá v tom, že tvrzení dokážeme pro termy, které jsou proměnnou nebo nulárním operačním symbolem. Ve druhém kroku předpokládáme, že term t je pomocí nějakého operačního symbolu složen z ji- ných termů a že pro tyto termy bylo tvrzení již dokázáno, a dokážeme tvrzení pro term t. ˇ Je-li termem t proměnná xk, pak k n, neboť t je n-ární term. Platí (xk)A(a1, . . . , an) = ak = (xk)A(a1, . . . , am). ˇ Je-li termem t nulární operační symbol f , pak fA(a1, . . . , an) = fA = fA(a1, . . . , am). ˇ Předpokládejme, že je term t složen pomocí k-árního operačního sym- bolu f , kde k 1, z termů t1, . . . , tk typu , pro které již bylo tvrzení dokázáno, tedy pro každé j = 1, . . . , k platí (tj)A(a1, . . . , an) = (tj)A(a1, . . . , am). Pak platí tA(a1, . . . , an) = fA((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an)) = = fA((t1)A(a1, . . . , am), . . . , (tk)A(a1, . . . , am)) = = tA(a1, . . . , am). Věta je dokázána. Příklad. Nechť = {}, kde je binární operační symbol, nechť A je univerzální algebra typu (tedy grupoid). Uvažme term x1 x2. Pak dle předchozí definice tento term určuje binární operaci (x1 x2)A(a1, a2) = (x1)A(a1, a2) (x2)A(a1, a2) = a1 a2. Podobně (x2 x1)A(a1, a2) = (x2)A(a1, a2) (x1)A(a1, a2) = a2 a1. Naivně lze tedy operaci příslušnou termu t popsat takto: za proměnnou xk dosadíme prvek ak a provedeme všechny operace termu t. 19 Příklad. Uvažme typ = {, , , 0, 1}, kde operační symboly a jsou binární, symbol je unární a symboly 0, 1 jsou nulární. Nechť A je uni- verzální algebra typu (příkladem takové -algebry je libovolná Booleova algebra, ovšem ne každá -algebra je Booleova algebra, je jí jen ta, v níž platí podmínky kladené na Booleovy algebry, tj. asociativita, komutativita, idem- potentnost obou operací, absorpční a distributivní zákony, identity spojené s nejmenším a největším prvkem, identity pro komplement ­ viz následující kapitolu). Uvažme term (x1 x2) (x1 x2), pak hodnota operace na A určené tímto termem v uspořádané dvojici prvků a1, a2 A je ((x1 x2) (x1 x2))A(a1, a2) = (x1 x2)A(a1, a2) (x1 x2)A(a1, a2) = = (x1)A(a1, a2) (x2)A(a1, a2) (x1)A(a1, a2) (x2)A(a1, a2) = = a1 ((x2)A(a1, a2)) ((x1)A(a1, a2)) a2 = = (a1 a2) (a1 a2), což je v případě Booleovy algebry hodnota operace sčítání na odpovídajícím Booleově okruhu. Příklad. Uvažme libovolný typ obsahující n-ární operační symbol f, a term f(x1, . . . , xn). Pak pro libovolnou -algebru A a libovolné a1, . . . , an A platí (f(x1, . . . , xn))A(a1, . . . , an) = fA((x1)A(a1, . . . , an), . . . , (xn)A(a1, . . . , an)) = = fA(a1, . . . , an), a tedy (f(x1, . . . , xn))A = fA. Poznámka. Právě definované operace určené termy umožňují zformulo- vat následující obecnou větu o tom, jak vypadá podalgebra -algebry ge- nerovaná podmnožinou. Se speciálními případy této věty jsme se již něko- likrát setkali, například pro podgrupu grupy generovanou množinou, nebo pro vektorový podprostor vektorového prostoru generovaný danou množinou vektorů. Věta 5.2. Nechť A je univerzální algebra typu , M podmnožina nosné množiny A. Pak podalgebra M -algebry A generovaná množinou M je tvaru M = {tA(a1, . . . , an); n Z, n 0, t je n-ární term typu , a1, . . . , an M}. Důkaz. Označme N množinu na pravé straně uvedené rovnosti. Nejprve dokážeme M N, a to tak, že ukážeme, že N je podalgebra -algebry A obsahující množinu M. Pro inkluzi M N stačí vzít n = 1 a unární term x1, neboť pro libovolné a M je (x1)A(a) = a. Dokažme tedy, že N je 20 podalgebra -algebry A. Zvolme libovolně k-ární operační symbol f a k libovolných prvků b1, . . . , bk N a ukažme, že fA(b1, . . . , bk) N. Ovšem pro každé j = 1, . . . , k existuje nj-ární term tj typu a nj prvků aj,1, . . . , aj,nj M tak, že bj = (tj)A(aj,1, . . . , aj,nj ). Potřebujeme prvky b1, . . . , bk získat jako hodnoty operací příslušných nějakým termům typu na stejné n-tici prvků množiny M. Proto položme n = n1 + +nk a uvažme n-tici (a1,1, . . . , a1,n1 , . . . , ak,1, . . . , ak,nk ) vzniklou poskládáním zmíněných nj- tic za sebe. Označme tj term, který vznikne z termu tj tím, že se indexy všech proměnných v něm použitých zvětší o číslo n1 + + nj-1 (tedy speciálně t1 = t1). Platí tedy pro každé j = 1, . . . , k bj = (tj)A(aj,1, . . . , aj,nj ) = (tj)A(a1,1, . . . , a1,n1 , . . . , ak,1, . . . , ak,nk ), a proto fA(b1, . . . , bk) = (f(t1, . . . , tk))A(a1,1, . . . , a1,n1 , . . . , ak,1, . . . , ak,nk ). To je ale dle definice množiny N prvek N, což se mělo dokázat. Dokažme nyní inkluzi M N, a to tak, že ukážeme, že prvky mno- žiny N leží v každé podalgebře -algebry A obsahující množinu M. Dle definice množiny N je její libovolný prvek tvaru tA(a1, . . . , an), kde t je n- ární term typu a a1, . . . , an M. Nechť H je libovolná podalgebra - algebry A obsahující množinu M a ukažme indukcí podle definice termu, že tA(a1, . . . , an) H. ˇ Je-li termem t proměnná xk, pak tA(a1, . . . , an) = ak M H. ˇ Je-li termem t nulární operační symbol f , pak podle definice po- dalgebry tA(a1, . . . , an) = fA H. ˇ Předpokládejme, že je term t složen pomocí k-árního operačního sym- bolu f , kde k 1, z termů t1, . . . , tk typu , pro které již bylo tvr- zení dokázáno, tedy pro každé j = 1, . . . , k platí bj = (tj)A(a1, . . . , an) H. Pak platí tA(a1, . . . , an) = fA((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an)) = = fA(b1, . . . , bk) H dle definice podalgebry. Věta je dokázána. 6. Variety Definice. Nechť t1, t2 jsou termy typu . Výraz t1 = t2 nazýváme rov- ností typu . 21 Příklad. Nechť = {}, kde je binární operační symbol, pak rovností typu je například rovnost x1 x2 = x2 x1. Tato rovnost psána naprosto formálně je tvaru (x1, x2) = (x2, x1), ale je jasné, že není třeba si zbytečně komplikovat život přehnanou snahou po formálnosti, podstatné je to, že víme, jak formálně rovnost vypadá, a jsme schopni v případě potřeby ji správně formálně přepsat. Příklad. Uvažme typ = {, -1 , 1}, kde operační symbol je binární, symbol -1 je unární a symbol 1 je nulární. Příklady rovností jsou (x1x2)x3 = x1 (x2 x3), x1 x-1 1 = 1, atd. Definice. Nechť t1 a t2 jsou termy typu , nechť A je univerzální algebra typu . Nechť n a m jsou nejmenší přirozená čísla taková, že t1 je n-ární a t2 je m-ární term. Označme k = max{n, m}. Řekneme, že rovnost t1 = t2 platí v -algebře A, jestliže termy t1, t2 určují stejnou k-ární operaci na -algebře A, tj. pro každé prvky a1, . . . , ak A platí (t1)A(a1, . . . , ak) = (t2)A(a1, . . . , ak). Poznámka. Podle věty 5.1 platí, že pokud termy t1 a t2 z předchozí defi- nice určují stejnou k-ární operaci na A, tak pro libovolné přirozené číslo l k tyto termy určují stejnou l-ární operaci na A. Proto v předchozí definici jsme místo k = max{n, m} mohli vzít libovolné přirozené číslo k max{n, m}. Příklad. Nechť t1 = t2 je libovolná rovnost typu . Pak v libovolné jednoprvkové univerzální algebře A typu platí rovnost t1 = t2. Jestliže existuje prázdná -algebra (tj. jestliže typ nemá žádný nulární operační symbol), pak v této prázdné algebře rovnost t1 = t2 také platí. Příklad. Nechť = {}, kde je binární operační symbol, pak rovnost x1 x2 = x2 x1 platí v -algebře A, právě když je A komutativní grupoid. Definice. Libovolnou množinu rovností typu nazýváme teorií typu . Definice. Nechť T je teorie typu . Třídu všech -algeber, v nichž platí všechny rovnosti teorie T, nazýváme varietou -algeber určenou teorií T. Příklad. Nechť T je libovolná teorie typu . Pak platí, že ve varietě ur- čené teorií T leží všechny jednoprvkové -algebry. Jestliže typ nemá žádný nulární operační symbol, pak ve varietě určené teorií T leží také prázdná - algebra. Poznámka. Všimněte si, že v předchozí definici hovoříme o třídě všech - algeber, nikoli o množině všech -algeber. Nelze totiž hovořit o množině všech -algeber stejně jako nelze hovořit o množině všech množin. Důvodem jsou paradoxy naivní teorie množin (pokud by existovala množina všech množin, existovala by i množina M všech těch množin, které nejsou svým prvkem; pak oba případy M M i M / M vedou ke sporu). 22 Poznámka pro ty, kteří znají predikátovou logiku. Uvažíme predi- kátovou logiku v jazyce s operačními symboly z . Pak pro libovolné n-ární termy je rovnost t1 = t2 atomickou formulí predikátové logiky, z níž přidáním kvantifikátorů utvoříme uzavřenou formuli (tj. sentenci) (x1) . . . (xn)(t1 = t2). Provedeme-li to se všemi rovnostmi nějaké teorie T typu , získáme tak množinu uzavřených formulí, tedy teorii predikátové logiky. Varieta určená teorií T je pak právě třída všech modelů takto vzniklé teorie predikátové logiky. Příklad. Nechť = {}, kde je binární operační symbol. Teorie {x1x2 = x2 x1} určuje varietu všech komutativních grupoidů, teorie {(x1 x2) x3 = x1 (x2 x3)} určuje varietu všech pologrup, teorie {x1 x2 = x2 x1, (x1 x2) x3 = x1 (x2 x3), x1 x1 = x1} určuje varietu všech polosvazů. Naproti tomu třídu všech grup nedostaneme jako varietu {}-algeber určenou nějakou teorií typu {}: nevíme totiž, jak zapsat podmínku pro existenci neutrálního prvku nějakými rovnostmi (tato podmínka obsahuje existenční kvantifikátor, kdežto my můžeme zapsat jen podmínky se všeobecnými kvantifikátory). Příklad. Uvažme typ = {, -1 , 1}, kde operační symbol je binární, symbol -1 je unární a symbol 1 je nulární. Teorie {(x1x2)x3 = x1(x2x3), x11 = x1, 1x1 = x1, x1(x1)-1 = 1, (x1)-1 x1 = 1} určuje varietu všech grup, přidáním další rovnosti x1 x2 = x2 x1 získáme teorii určující varietu všech komutativních grup. Tato varieta je samozřejmě též varietou určenou teorií {(x1 x2) x3 = x1 (x2 x3), x1 x2 = x2 x1, x1 1 = x1, x1 (x1)-1 = 1}. Příklad. Uvažme typ = {+, , -, 0, 1}, kde operační symboly + a jsou binární, symbol - je unární a symboly 0, 1 jsou nulární. Varieta všech okruhů je varieta -algeber určená následující teorií typu : {(x1 + x2) + x3 = x1 + (x2 + x3), x1 + x2 = x2 + x1, x1 + 0 = x1, x1 + (-x1) = 0, (x1 x2) x3 = x1 (x2 x3), x1 1 = x1, 1 x1 = x1, x1 (x2 + x3) = (x1 x2) + (x1 x3), (x1 + x2) x3 = (x1 x3) + (x2 x3)}. Není jasné, jak zachytit podmínky oboru integrity a tělesa. Později uvidíme, že ani třídu všech oborů integrity ani třídu všech těles nemůžeme dostat jako varietu univerzálních algeber. 23 Příklad. Uvažme typ = {, }, kde oba operační symboly jsou binární. Pak varieta všech svazů je určená následující teorií T typu : T = {x1 x2 = x2 x1, (x1 x2) x3 = x1 (x2 x3), x1 x1 = x1, x1 x2 = x2 x1, (x1 x2) x3 = x1 (x2 x3), x1 x1 = x1, (x1 x2) x1 = x1, (x1 x2) x1 = x1}. Teorie T1 = T {x1 (x2 x3) = (x1 x2) (x1 x3)} určuje varietu všech distributivních svazů, teorie T2 = T {(x1 x2) (x1 x3) = x1 (x2 (x1 x3))} určuje varietu všech modulárních svazů. Příklad. Uvažme typ = {, , , 0, 1}, kde operační symboly a jsou binární, symbol je unární a symboly 0, 1 jsou nulární. Nechť T1 je teorie z předchozího příkladu. Pak teorie T1 {x1 0 = 0, x1 1 = 1, x1 (x1) = 1, x1 (x1) = 0} určuje varietu všech Booleových algeber. Příklad. Připomeňme definici vektorového prostoru nad tělesem (R, +, ). Pro větší srozumitelnost odlišíme operaci sčítání vektorů od sčítání v tělese a budeme ji značit . Podobně u bude opačný vektor k vektoru u. Odli- šíme také násobení vektorů skaláry od násobení v tělese a budeme jej značit . Vektorový prostor nad tělesem (R, +, ) je komutativní grupa (V, ) a zobrazení : R × V V splňující pro každé u, v V a každé r, s R r (u v) = (r u) (r v) (r + s) u = (r u) (s u) (r s) u = r (s u) 1 u = u. Popišme nyní třídu všech vektorových prostorů jako varietu určenou vhodnou teorií. Uvažme typ = {, , o} R, kde operační symbol je binární, symbol je unární, symbol o je nulární a pro každé r R je r unární operační symbol. Uvažme následující teorii T typu : T = {(x1x2)x3 = x1(x2x3), x1x2 = x2x1, x1o = x1, x1( x1) = o}. Tato teorie (uvažovaná jako teorie typu {, , o}) určuje varietu všech ko- mutativních grup. Přidáme k ní zbylé čtyři axiomy vektorových prostorů. 24 Čtvrtý axiom 1 u = u je nejsnadnější: 1 R je unární operační symbol, tedy odpovídající rovností je rovnost 1(x1) = x1. Pro druhý a třetí axiom uvážíme libovolné r, s R. To jsou unární operační symboly. Ale pak též r+s a r s jsou prvky R, a tedy unární operační symboly. Dostáváme následující rovnosti typu : (r + s)(x1) = r(x1) s(x1), (r s)(x1) = r(s(x1)). První axiom pro libovolné r R dává rovnost r(x1 x2) = r(x1) r(x2). Celkem tedy dostáváme teorii T {1(x1) = x1} rR {r(x1 x2) = r(x1) r(x2)} rR sR {(r + s)(x1) = r(x1) s(x1), (r s)(x1) = r(s(x1))} . Tato teorie určuje varietu všech vektorových prostorů. Poznámka. Následující větu lze stručně zformulovat takto: variety jsou uzavřené na podalgebry algeber. Věta 6.1. Nechť T je teorie typu , V varieta -algeber určená teorií T. Pak pro každou -algebru A V a každou podalgebru B -algebry A platí B V . Důkaz. Uvažme libovolnou rovnost t1 = t2 z teorie T. Protože A V , platí tato rovnost v -algebře A. Ovšem zřejmě pro každý n-ární term t typu a libovolné a1, . . . , an B platí tB(a1, . . . , an) = tA(a1, . . . , an). Proto rovnost t1 = t2 platí i v -algebře B. Dokázali jsme, že každá rovnost teorie T platí v -algebře B a tedy B V . Poznámka. Následující věta ukazuje, že definiční vlastnost homomor- fismu platí nejen pro všechny operační symboly typu , ale dokonce pro libovolné termy typu . Věta 6.2. Nechť A, B jsou univerzální algebry typu , : A B homomorfismus -algeber. Pak pro libovolný n-ární term t typu a libovolné a1, . . . , an A platí tB((a1), . . . , (an)) = (tA(a1, . . . , an)). Důkaz. Větu dokážeme indukcí vzhledem k termu t. ˇ Je-li termem t proměnná xk, pak tA i tB jsou k-té projekce, a tedy (tA(a1, . . . , an)) = (ak) = tB((a1), . . . , (an)). 25 ˇ Je-li termem t nulární operační symbol f , pak tA(a1, . . . , an) = fA, tB((a1), . . . , (an)) = fB. Ovšem (fA) = fB podle definice homo- morfismu. ˇ Předpokládejme, že je term t složen pomocí k-árního operačního sym- bolu f , kde k 1, z termů t1, . . . , tk typu , pro které již bylo tvrzení dokázáno, tedy pro každé j = 1, . . . , k platí (tj)B((a1), . . . , (an)) = ((tj)A(a1, . . . , an)). Podle definice operace určené termem platí tA(a1, . . . , an) = fA((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an)), podobně tB((a1), . . . , (an)) = = fB((t1)B((a1), . . . , (an)), . . . , (tk)B((a1), . . . , (an))). Podle definice homomorfismu a indukčního předpokladu platí (tA(a1, . . . , an)) = (fA((t1)A(a1, . . . , an), . . . , (tk)A(a1, . . . , an))) = = fB(((t1)A(a1, . . . , an)), . . . , ((tk)A(a1, . . . , an))) = = fB((t1)B((a1), . . . , (an)), . . . , (tk)B((a1), . . . , (an))) = = tB((a1), . . . , (an)), což se mělo dokázat. Věta je dokázána. Poznámka. Následující větu lze stručně zformulovat takto: variety jsou uzavřené na obrazy algeber v homomorfismech. Podle důsledku věty 4.5 to znamená, že variety jsou uzavřené na faktoralgebry. S konkrétními případy tohoto tvrzení jsme se tedy setkali již dříve: faktorizací (komutativní) grupy jsme dostali (komutativní) grupu, faktorizací (komutativního) okruhu jsme dostali (komutativní) okruh. Věta 6.3. Nechť T je teorie typu , V varieta -algeber určená teorií T. Nechť A, B jsou -algebry, : A B surjektivní homomorfismus - algeber. Pak platí: je-li A V , pak též B V . Důkaz. Uvažme libovolnou rovnost t1 = t2 z teorie T. Protože A V , platí tato rovnost v -algebře A. Nechť n je takové, že oba termy t1, t2 jsou n-ární. Je třeba ověřit, že pro libovolné b1, . . . , bn B platí (t1)B(b1, . . . , bn) = (t2)B(b1, . . . , bn). 26 Protože je surjekce, existují a1, . . . , an A tak, že b1 = (a1), . . . , bn = (an). Pak z předchozí věty a toho, že rovnost t1 = t2 platí v -algebře A, dostáváme (t1)B(b1, . . . , bn) = (t1)B((a1), . . . , (an)) = ((t1)A(a1, . . . , an)) = = ((t2)A(a1, . . . , an)) = (t2)B((a1), . . . , (an)) = (t2)B(b1, . . . , bn). Dokázali jsme, že každá rovnost teorie T platí v -algebře B a tedy B V . Poznámka. Následující věta ukazuje, že podmínka, kterou byly defino- vány operace na součinu -algeber, platí nejen pro všechny operační symboly typu , ale dokonce pro libovolné termy typu . Věta 6.4. Nechť je typ. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai typu . Označme A součin těchto -algeber, tj. A = iI Ai. Uvažme libovolný n-ární term t typu a libovolné 1, . . . , n A. Označme = tA(1, . . . , n). Pak pro každé i I platí (i) = tAi (1(i), . . . , n(i)). Důkaz. Větu dokážeme indukcí vzhledem k termu t. ˇ Je-li termem t proměnná xk, pak tA i tAi jsou k-té projekce, a tedy = tA(1, . . . , n) = k a tAi (1(i), . . . , n(i)) = k(i) = (i). ˇ Je-li termem t nulární operační symbol f , pak dle definice součinu -algeber platí fA = , kde A je určeno podmínkou (i) = fAi , což je dokazované tvrzení. ˇ Předpokládejme, že je term t složen pomocí k-árního operačního sym- bolu f , kde k 1, z termů t1, . . . , tk typu , pro které již bylo tvrzení dokázáno. Nejprve zformulujme tento indukční předpoklad. Pro každé j = 1, . . . , k označme j = (tj)A(1, . . . , n). Předpokládáme tedy, že t = f(t1, . . . , tk) a že pro každé i I a pro každé j = 1, . . . , k platí j(i) = (tj)Ai (1(i), . . . , n(i)). Podle definice operace určené ter- mem platí tAi (1(i), . . . , n(i)) = = fAi ((t1)Ai (1(i), . . . , n(i)), . . . , (tk)Ai (1(i), . . . , n(i))) = = fAi (1(i), . . . , n(i)) a také = tA(1, . . . , n) = = fA((t1)A(1, . . . , n), . . . , (tk)A(1, . . . , n)) = = fA(1, . . . , n), 27 a tedy podle definice operací na součinu -algeber pro každé i I platí (i) = fAi (1(i), . . . , n(i)). Ovšem výše jsme odvodili, že fAi (1(i), . . . , n(i)) = tAi (1(i), . . . , n(i)). Věta je dokázána. Poznámka. Následující větu lze stručně zformulovat takto: variety jsou uzavřené na libovolné součiny algeber. Věta 6.5. Nechť T je teorie typu , V varieta -algeber určená teorií T. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai typu . Označme A součin těchto -algeber, tj. A = iI Ai. Pak platí: jestliže pro každé i I je Ai V , pak též A V . Důkaz. Uvažme libovolnou rovnost t1 = t2 z teorie T. Protože pro každé i I je Ai V , platí tato rovnost v -algebře Ai. Nechť n je takové, že oba termy t1, t2 jsou n-ární. Je třeba ověřit, že pro libovolné 1, . . . , n A platí (t1)A(1, . . . , n) = (t2)A(1, . . . , n). Označme 1 = (t1)A(1, . . . , n) a 2 = (t2)A(1, . . . , n). Naším cílem je dokázat, že 1 = 2. Podle definice součinu množin jsou 1 a 2 zobrazení se stejným definičním oborem i oborem hodnot. Je třeba ověřit, že mají též stejný předpis, tj. že pro každé i I platí 1(i) = 2(i). Z předchozí věty plyne, že pro každé i I platí 1(i) = (t1)Ai (1(i), . . . , n(i)) a 2(i) = (t2)Ai (1(i), . . . , n(i)). Protože rovnost t1 = t2 platí v -algebře Ai, je (t1)Ai (1(i), . . . , n(i)) = (t2)Ai (1(i), . . . , n(i)), a tedy též 1(i) = 2(i), což jsme chtěli dokázat. Dokázali jsme, že každá rovnost teorie T platí v -algebře A a tedy A V . Příklad. Nyní jsme schopni dokázat slíbené tvrzení, že ani třídu všech oborů integrity ani třídu všech těles nemůžeme dostat jako varietu univerzál- ních algeber typu {+, , -, 0, 1}. Podle předchozí věty k tomu stačí najít dvě tělesa, jejichž součinem není těleso, a dva obory integrity, jejichž součinem není obor integrity. Hledání takových těles je snadné: platí dokonce, že součin libovolných dvou těles (která jsou samozřejmě i obory integrity) není oborem integrity (a tedy ani tělesem). V každém takovém součinu totiž máme dělitele nuly, neboť platí (0, 1) (1, 0) = (0, 0). (Pokud Vám není tento obecný pří- klad jasný, uvažte dvě kopie tělesa o dvou prvcích ­ okruhu zbytkových tříd modulo 2 ­ a vypište si všechny čtyři prvky a sestavte tabulku pro operaci násobení.) Příklad. Třída všech svazů, které jsou řetězci (tj. lineárně uspořádanými množinami) netvoří varietu univerzálních algeber typu {, }, neboť souči- nem dvou dvouprvkových svazů, které jsou řetězci, je čtyřprvkový svaz, který není řetězec. 28 Příklad. Třída všech grup netvoří varietu univerzálních algeber typu {}, neboť tato třída není uzavřena na podalgebry (existují podgrupoidy grup, které nejsou grupami). Přesto jsme dostali třídu všech grup jako varietu uni- verzálních algeber typu {, -1 , 1}. Rozšířením typu jsme totiž dosáhli toho, že zmíněné podgrupoidy už nebyly podalgebrami {, -1 , 1}-algeber. Nabízí se tedy otázka, zda i v případě třídy všech těles nebo třídy všech oborů inte- grity přidáním dalších operačních symbolů k typu {+, , -, 0, 1} nedostaneme varietu -algeber. Zde je však situace odlišná: tyto třídy nejsou uzavřené na součin a součin se přidáním dalších operačních symbolů nezmění (přibudou pouze další operace na téže nosné množině součinu). Dostali jsme tedy, že ani třída všech těles ani třída všech oborů integrity netvoří varietu -algeber pro žádné {+, , -, 0, 1}. Podobně třída všech řetězců netvoří varietu -algeber pro žádné {, }. Poznámka. Následující věta završí popis variet -algeber. Charakteri- zuje, které třídy -algeber jsou varietami, tj. které třídy je možné charak- terizovat nějakou množinou rovností. V tuto chvíli jsme však schopni důkaz jednoho směru pouze naznačit. Kompletní důkaz čtenář nalezne až v osmé kapitole. Věta 6.6. (Birkhoff) Nechť je typ. Třída -algeber je varieta, právě když splňuje všechny tři následující podmínky: ˇ je uzavřená na podalgebry algeber; ˇ je uzavřená na obrazy algeber v homomorfismech; ˇ je uzavřená na libovolné součiny algeber. Důkaz. Již jsme dokázali ve větách 6.1, 6.3 a 6.5, že libovolná varieta -algeber všechny tři uvedené podmínky splňuje. Důkaz opačné implikace přesahuje možnosti této kapitoly, proto jen naznačíme, jak bude veden v ka- pitole 8. Nechť V je třída -algeber splňující všechny tři uvedené podmínky. Označme T množinu všech rovností typu , které platí ve všech -algebrách z třídy V (uvědomte si, že T je vždy nekonečná množina). Označme W va- rietu -algeber určenou teorií T. Je třeba dokázat, že V = W. Z definice T je jasné, že platí inkluze V W. Celá obtížnost důkazu věty spočívá v dů- kazu inkluze W V . Je totiž nutné ukázat, že libovolnou -algebru A W lze vytvořit pomocí tvoření podalgeber, součinů a obrazů v homomorfismech z -algeber z třídy V . To však ukážeme až na konci kapitoly 8. 7. Volné algebry s nejvýše spočetnou množinou generátorů Definice. Nechť je typ. Označme F() množinu všech termů typu . Na této množině definujeme -algebru následujícím způsobem. Pro libovolný 29 n-ární operační symbol f definujeme n-ární operaci fF() na -algebře F() příslušnou operačnímu symbolu f takto: pro libovolné termy t1, . . . , tn F() je fF()(t1, . . . , tn) = f(t1, . . . , tn). Poznámka. Všimněte si, jak se počítají hodnoty operací v právě popsané -algebře. S trochou nadsázky se dá říci, že se vlastně nepočítají. Termy se do operačního symbolu pouze dosadí, čímž vznikne nový term (viz třetí bod definice termu), a to je výsledek. Znamená to, že každý prvek množiny F(), který není proměnnou, je hodnotou právě jedné operace na jednoznačně ur- čených operandech, je jej totiž možné získat jedině tak, jak byl sestrojen dle definice termu. Proto v této -algebře platí jen triviální rovnosti (tj. takové, kde na obou stranách stojí stejný term). Protože tato -algebra není svázána žádnými netriviálními rovnostmi, nazývá se volná (viz definici následující po větě 7.1). Věta 7.1. Označme P množinu všech proměnných: P = {x1, x2, . . . } a uvažme podalgebru P generovanou v algebře F() množinou P. Pak platí P = F(). Důkaz. Stačí ukázat inkluzi F() P , tedy dokázat, že každý term t typu patří do P . To je ale snadné indukcí vzhledem k definici termu: proměnné leží v P, pro nulární symbol f typu platí f = fF(), což je prvek libovolné podalgebry. Konečně pro term f(t1, . . . , tn) vzniklý z n-árního symbolu f a termů t1, . . . , tn patřících dle indukčního předpokladu do P je f(t1, . . . , tn) = fF()(t1, . . . , tn) P dle definice podalgebry. Definice. -algebra F() z předchozí definice se nazývá volná algebra typu generovaná množinou {x1, x2, . . . }. Definice. Nechť je typ, r nezáporné celé číslo. Označme Fr() množinu všech r-árních termů typu . Příklad. Jestliže typ neobsahuje žádný nulární operační symbol, pak platí F0() = . Příklad. Uvažme typ = { }, kde je unární symbol. Pak -algebrami jsou množiny A spolu se zobrazením : A A. Pak platí F1() = {x1, x1, x1, x1 , . . . }, F2() = {x1, x1, x1, x1 , . . . , x2, x2, x2, x2 , . . . }. Příklad. Uvažme typ = { , 1}, kde je unární symbol a 1 nulární sym- bol. Volná algebra typu generovaná prázdnou množinou je pak -algebra F0() = {1, 1 , 1 , 1 , . . . }. To jsou vlastně přirozená čísla. Při konstrukci při- rozených čísel nemůžeme definovat přirozená čísla jako tuto volnou -algebru, neboť jsme v tomto textu mnohokrát existenci přirozených čísel využili. Je ale 30 možné tuto strukturu popsat následující vlastností: je to množina N spolu se zobrazením : N N, které je injektivní a není surjektivní, a splňuje následující podmínku: neexistuje žádná vlastní podmnožina M N, která by pro každé m M obsahovala též m a která by také obsahovala nějaký prvek n, který nelze vyjádřit ve tvaru n = r pro žádné r N. Množinu N a zobrazení : N N, které splňují právě popsanou podmínku, lze vzít v axiomatické konstrukci přirozených čísel za jejich definici. Věta 7.2. Pro libovolné nezáporné celé číslo r je množina Fr() pod- algebra -algebry F() generovaná množinou r proměnných {x1, . . . , xr}, tj. Fr() = {x1, . . . , xr} . Důkaz. Inkluzi Fr() {x1, . . . , xr} dokážeme stejně jako předchozí větu. Opačná plyne z toho, že Fr() je podalgebra -algebry F() obsahující množinu proměnných {x1, . . . , xr}: dosazením r-árních termů do libovolného operačního symbolu totiž zřejmě dostaneme opět r-ární term, a tedy Fr() je skutečně podalgebra. Definice. -algebra Fr() se nazývá volná algebra typu generovaná množinou {x1, . . . , xr}. Poznámka. Následující věta popisuje podmínku, kterou lze volné algebry charakterizovat. Ať si v jakékoli -algebře zvolíme jakkoli obraz pro každý generátor, vždy je možné doplnit toto přiřazení do homomorfismu, a to jedi- ným způsobem. (Avšak to, že tato podmínka je skutečně charakterizační, tj. určuje volnou algebru jednoznačně až na izomorfismus, dokážeme až ve větě 8.5.) Věta 7.3. Nechť A je -algebra, a1, a2, a3, . . . libovolná pevně zvolená posloupnost prvků z A. Pak existuje jediný homomorfismus -algeber : F() A splňující podmínku (xm) = am pro všechna přirozená čísla m. Přitom pro tento homomorfismus platí: pro libovolný k-ární term t F() je (t) = tA(a1, . . . , ak), kde tA je operace určená termem t v -algebře A. Důkaz. Ukažme nejprve, že takto definované zobrazení je homomorfis- mus. Nechť f je libovolný n-ární operační symbol, t1, . . . , tn F() libovolné k-ární termy. Platí tedy (fF()(t1, . . . , tn)) = (f(t1, . . . , tn)) = (f(t1, . . . , tn))A(a1, . . . , ak). Dle definice operace určené termem je (f(t1, . . . , tn))A(a1, . . . , ak) = fA((t1)A(a1, . . . , ak), . . . , (tn)A(a1, . . . , ak)) = = fA((t1), . . . , (tn)), a tedy je homomorfismus. Ukažme indukcí vzhledem k definici termu, že tento homomorfismus je jediný: 31 ˇ je-li t = xm, pak (xm) = am = (xm)A(a1, . . . , ak); ˇ je-li t nulární operační symbol, pak z definice homomorfismu (t) = tA; ˇ nechť tedy k-ární term t = f(t1, . . . , tn) je složen pomocí n-árního operačního symbolu f, kde n 1, z termů t1, . . . , tn F(), pro které platí indukční předpoklad, tj. pro každé j = 1, . . . , n je (tj) = (tj)A(a1, . . . , ak). Pak z definice homomorfismu (t) = (f(t1, . . . , tn)) = (fF()(t1, . . . , tn)) = = fA((t1), . . . , (tn)) = fA((t1)A(a1, . . . , ak), . . . , (tn)A(a1, . . . , ak)) = = (f(t1, . . . , tn))A(a1, . . . , ak). Věta je dokázána. Věta 7.4. Nechť je typ, r nezáporné celé číslo. Nechť A je -algebra, a1, . . . , ar libovolné pevně zvolené prvky z A. Pak existuje jediný homomorfis- mus -algeber : Fr() A splňující podmínku (xm) = am pro všechna m = 1, . . . , r. Přitom pro tento homomorfismus platí: pro libovolný term t Fr() je (t) = tA(a1, . . . , ar), kde tA je operace určená termem t v - algebře A. Důkaz. Tuto větu lze dokázat stejně jako předchozí větu 7.3. Poznámka. Předchozí věta tedy pro r = 0 tvrdí, že -algebra F0() má následující vlastnost: pro každou -algebru A existuje právě jeden homomor- fismus -algeber : F0() A. Poznámka. Naším dalším cílem je nalézt volné -algebry v každé va- rietě -algeber. Volné -algebry F() a Fr() totiž splňují pouze triviální rovnosti, leží proto jen ve varietě všech -algeber. Budeme tedy pro danou teorii T typu konstruovat -algebru, v níž platí všechny rovnosti teorie T a všechny důsledky těchto rovností, ale žádná rovnost, která není důsledkem rovností teorie T, už v konstruované algebře platit nebude. Otázka je, jak ta- kové důsledky popsat. Asi první cesta, která člověka napadne, je pokusit se popisovat nějaká odvozovací pravidla, jak z rovností teorie T odvodit další rovnosti. My ale použijeme jinou cestu: důsledkem rovností teorie T jsou právě ty rovnosti, které platí v každé -algebře z variety určené teorií T. Definice. Nechť V je varieta -algeber. Na množině F() všech termů typu definujeme relaci V takto: pro libovolné termy t1, t2 F() klademe t1 V t2 právě tehdy, když libovolná -algebra z variety V splňuje rovnost t1 = t2. Poznámka. Nechť t1, t2 jsou n-ární termy typu . Pak je tedy t1 V t2 právě tehdy, když na libovolné -algebře A z variety V oba termy t1, t2 určují stejnou n-ární operaci, tj. pro libovolné a1, . . . , an A platí (t1)A(a1, . . . , an) = (t2)A(a1, . . . , an). 32 Věta 7.5. Pro libovolnou varietu -algeber V je relace V kongruencí na -algebře F(). Důkaz. Z předchozí poznámky se snadno vidí, že V je ekvivalence na množině F(). Dokažme, že jde o kongruenci. Za tím účelem zvolme libovolně n-ární operační symbol f a termy t1, . . . , tn, s1, . . . , sn F() takové, že t1 V s1, . . . , tn V sn. Dokážeme, že potom také f(t1, . . . , tn) V f(s1, . . . , sn). Zvolme libovolně -algebru A z variety V . Platí tedy (t1)A = (s1)A, . . . , (tn)A = (sn)A. Nechť přirozené číslo k je takové, že všechny zde vystupující termy jsou k-ární. Pak pro libovolné a1, . . . , ak A platí (f(t1, . . . , tn))A(a1, . . . , ak) = fA((t1)A(a1, . . . , ak), . . . , (tn)A(a1, . . . , ak)) = = fA((s1)A(a1, . . . , ak), . . . , (sn)A(a1, . . . , ak)) = = (f(s1, . . . , sn))A(a1, . . . , ak), což se mělo dokázat. Poznámka. Můžeme tedy hovořit o faktorové algebře -algebry F() podle kongruence V . Tuto faktorovou -algebru budeme značit F(V ) = F()/V . Poznámka. Uvědomte si, že nehrozí nebezpečí záměny F() a F(V ) i kdybychom označili typ jiným písmenem než a varietu jiným písmenem než V . Libovolný typ je přece množina, kdežto libovolná varieta je vlastní třída. Věta 7.6. Pro libovolnou varietu -algeber V je -algebra F(V ) prvkem variety V . Důkaz. Nechť T je teorie určující varietu V , nechť t1 = t2 je libovolná rovnost této teorie. Nechť k je přirozené číslo takové, že oba termy t1 a t2 jsou k-ární. Je tedy třeba ověřit, že pro libovolné v1, . . . , vk F(V ) platí (t1)F(V )(v1, . . . , vk) = (t2)F(V )(v1, . . . , vk). Označme : F() F(V ) pro- jekci na faktorovou algebru. Podle věty 4.3 je surjektivní homomorfismus. Pro každé i = 1, . . . , k zvolme term si F() tak, že (si) = vi. Podle věty 6.2 pro j = 1, 2 platí (tj)F(V )(v1, . . . , vk) = (tj)F(V )((s1), . . . , (sk)) = ((tj)F()(s1, . . . , sk)). Máme tedy dokázat, že ((t1)F()(s1, . . . , sk)) = ((t2)F()(s1, . . . , sk)), což je ekvivalentní s tvrzením (t1)F()(s1, . . . , sk) V (t2)F()(s1, . . . , sk). To bude dokázáno, pokud libovolná -algebra A z variety V splňuje rovnost (t1)F()(s1, . . . , sk) = (t2)F()(s1, . . . , sk). 33 Nechť m je přirozené číslo takové, že všechny termy s1, . . . , sk jsou m-ární. Máme tedy ukázat, že pro libovolnou -algebru A z variety V a pro libovolné její prvky a1, . . . , am A platí ((t1)F()(s1, . . . , sk))A(a1, . . . , am) = ((t2)F()(s1, . . . , sk))A(a1, . . . , am). Doplňme nějak a1, . . . , am do nekonečné posloupnosti prvků z -algebry A, například takto: pro každé n > m klademe an = a1. Podle věty 7.3 existuje homomorfismus -algeber : F() A takový, že pro libovolný l-ární term t F() je (t) = tA(a1, . . . , al). Pro j = 1, 2 tedy platí ((tj)F()(s1, . . . , sk))A(a1, . . . , am) = ((tj)F()(s1, . . . , sk)). Ovšem podle věty 6.2 je ((tj)F()(s1, . . . , sk)) = (tj)A((s1), . . . , (sk)). Máme tedy ukázat, že (t1)A((s1), . . . , (sk)) = (t2)A((s1), . . . , (sk)), to ale plyne z toho, že t1 = t2 je rovnost z teorie určující varietu V , do které patří -algebra A. Poznámka. Ukážeme, že faktorová algebra F(V ) = F()/V z před- chozí věty splňuje charakterizační podmínku volné algebry. Věta 7.7. Nechť V je libovolná varieta -algeber, F(V ) = F()/V faktorová -algebra z věty 7.6, : F() F(V ) projekce na faktorovou algebru. Nechť A je libovolná -algebra z variety V , a1, a2, a3, . . . libovolná pevně zvolená posloupnost prvků z A. Pak existuje jediný homomorfismus -algeber : F(V ) A splňující podmínku ((xm)) = am pro všechna přirozená čísla m. Přitom pro tento homomorfismus platí: pro libovolný k- ární term t F() je ((t)) = tA(a1, . . . , ak), kde tA je operace určená termem t v -algebře A. Důkaz. Podle věty 7.3 existuje jediný homomorfismus -algeber : F() A splňující podmínku (xm) = am pro všechna přirozená čísla m. Přitom pro libovolný k-ární term t F() je (t) = tA(a1, . . . , ak). Označme jádro homomorfismu . Uvažme libovolné n-ární termy t1, t2 takové, že t1 V t2. Podle definice kongruence V je rovnost t1 = t2 splněna v -algebře A, a proto platí (t1) = (t1)A(a1, . . . , an) = (t2)A(a1, . . . , an) = (t2), a tedy t1 t2. Ukázali jsme, že kongruence V je menší nebo rovna kongru- enci . Proto podle věty 4.5 existuje jediný homomorfismus : F(V ) A 34 splňující = . Pro tento homomorfismus tedy pro všechna přirozená čísla m platí am = (xm) = ()(xm) = ((xm)). Podobně pro libovolný k-ární term t F() je tA(a1, . . . , ak) = (t) = ( )(t) = ((t)). Zbývá doká- zat jednoznačnost homomorfismu splňujícího podmínku ((xm)) = am. Předpokládejme, že též pro homomorfismus -algeber : F(V ) A je splněna podmínka ((xm)) = am pro všechna přirozená čísla m. Pak pro homomorfismus : F() A platí ( )(xm) = am, a tedy podle věty 7.3 je = . Podle věty 4.5 odtud plyne = . Definice. Faktorová algebra F(V ) = F()/V z vět 7.6 a 7.7 se nazývá volná algebra variety V typu generovaná množinou {x1, x2, . . . }. Definice. Nechť F(V ) = F()/V je volná algebra variety V typu generovaná množinou {x1, x2, . . . }, : F() F(V ) projekce na fakto- rovou algebru. Pro libovolné nezáporné celé číslo r označme Fr(V ) obraz podalgebry Fr() v homomorfismu , tj. Fr(V ) = (Fr()). Tuto -algebru Fr(V ) nazýváme volnou algebrou variety V typu generovanou množinou {x1, . . . , xr}. Poznámka. Podle věty 2.3 je Fr(V ) podalgebrou -algebry F(V ), podle vět 6.1 a 7.6 patří algebra Fr(V ) do variety V . V následující větě ukážeme, že také splňuje charakterizační podmínku volné algebry (a tedy název, který dostala v předchozí definici, je oprávněný). Zúžením projekce : F() F(V ) dostáváme dle definice Fr(V ) surjektivní homomorfismus Fr() Fr(V ), který budeme pro jednoduchost označovat opět a nazývat projekcí. Věta 7.8. Nechť V je libovolná varieta -algeber, r nezáporné celé číslo, Fr(V ) volná algebra variety V typu generovaná množinou {x1, . . . , xr}, : Fr() Fr(V ) projekce. Nechť A je libovolná -algebra z variety V , a1, . . . , ar A libovolné pevně zvolené prvky. Pak existuje jediný homomor- fismus -algeber : Fr(V ) A splňující podmínku ((xm)) = am pro všechna m = 1, . . . , r. Přitom pro tento homomorfismus platí: pro libovolný term t Fr() je ((t)) = tA(a1, . . . , ar), kde tA je operace určená termem t v -algebře A. Důkaz. Tuto větu lze dokázat stejně jako větu 7.7 (jen místo kongruence V na F() užíváme zúžení kongruence V na podalgebru Fr(), tj. průnik relací V a Fr() × Fr(), neboli jádro projekce : Fr() Fr(V )). Příklad. Uvažme opět typ = { }, kde je unární symbol. Připomeňme, že F0() = , F1() = {x1, x1, x1, x1 , . . . }, F2() = {x1, x1, x1, x1 , . . . , x2, x2, x2, x2 , . . . }. 35 Nechť V je varieta určená teorií T = {x1 = x1}. Pak platí x1 V x1 V x1 V . . . a x1 V x1 V x1 V . . . . Je tedy F1(V ) = {x1, x1, x1 , . . . }, {x1, x1 , x1 , . . . } . V této -algebře se počítá takto: {x1, x1, x1 , . . . } = {x1, x1 , x1 , . . . }, {x1, x1 , x1 , . . . } = {x1, x1, x1 , . . . }. Podobně F2(V ) = {x1, x1, x1 , . . . }, {x1, x1 , x1 , . . . }, {x2, x2, x2 , . . . }, {x2, x2 , x2 , . . . } . Uvažme nyní varietu W určenou teorií {x1 = x1}. Platí F1(W) = {x1}, {x1, x1, x1 , . . . } , přičemž v této -algebře se počítá takto: {x1} = {x1, x1, x1 , . . . } = {x1, x1, x1 , . . . }. Promyslete si sami, že pro varietu U určenou teorií {x1 = x1 } platí F1(U) = {x1}, {x1, x1 , x1 , . . . }, {x1, x1 , . . . } , a určete, jak se v této -algebře počítá. 8. Volné algebry s libovolnou množinou generátorů Poznámka. Jak už napovídá název, tato kapitola pojednává o obecnější situaci než kapitola předchozí. Je tedy otázka, proč jsem vlastně předchozí kapitolu do textu zařadil. Mohl jsem ihned začít s touto kapitolou a výsledky předchozí kapitoly získat jako důsledky výsledků kapitoly této. Opravdu by to tak bylo možné udělat. Důvodem pro tento postup byla však snaha o co největší možnou srozumitelnost. Protože budeme nyní pracovat s libovolnou (tedy i nespočetnou) množinou generátorů X, budeme potřebovat zobecnit definici termu: budeme nyní definovat termy typu nad množinou X, při- čemž připustíme, že termem je libovolný prvek množiny X. Definice. Nechť je typ, X množina. Termem typu nad množinou X nazveme právě takový výraz, který lze zkonstruovat konečně mnoha aplika- cemi následujících pravidel: 36 ˇ Pro libovolný prvek x X je x term typu nad množinou X. ˇ Pro libovolný nulární operační symbol f je f term typu nad množinou X. ˇ Pro libovolné přirozené číslo n, libovolný n-ární operační symbol f a libovolné termy t1, . . . , tn typu nad množinou X je výraz f(t1, . . . , tn) term typu nad množinou X. Množinu všech termů typu nad množinou X budeme značit FX(). Poznámka. Termy typu , které jsme užívali dosud, jsou tedy termy typu nad množinou {x1, x2, . . . }. Definice. Nechť je typ, X množina. Na množině FX() definujeme volnou algebru typu generovanou množinou X následujícím způsobem. Pro libovolný n-ární operační symbol f definujeme n-ární operaci fFX () na -algebře FX() příslušnou operačnímu symbolu f takto: pro libovolné termy t1, . . . , tn FX() je fFX ()(t1, . . . , tn) = f(t1, . . . , tn). Poznámka. Oprávněnost názvu -algebry FX() prokáží věty 8.1 a 8.2. Příklady. -algebru F() z kapitoly 7 dostaneme v předchozí definici pro množinu X = {x1, x2, . . . }, pro libovolné nezáporné celé číslo r dostaneme - algebru Fr() z kapitoly 7 v předchozí definici pro množinu X = {x1, . . . , xr}. Věta 8.1. Nechť je typ, X množina. Uvažme podalgebru X genero- vanou v algebře FX() množinou X. Pak platí X = FX(). Důkaz. Tato věta se dokáže stejně jako věta 7.1. Věta 8.2. Nechť je typ, X množina. Nechť A je -algebra, : X A libovolné zobrazení. Pak existuje jediný homomorfismus -algeber : FX() A splňující podmínku (x) = (x) pro všechny prvky x X. Důkaz. Definujme zobrazení : FX() A indukcí vzhledem k definici termu nad množinou X. ˇ Pro libovolný prvek x X klademe (x) = (x). ˇ Aby zobrazení : FX() A mohlo být homomorfismus -algeber, je třeba pro libovolný nulární operační symbol f položit (f) = fA. ˇ Pro libovolné přirozené číslo n uvažme nyní term t = f(t1, . . . , tn) typu nad množinou X, který vznikl z n-árního operačního symbolu f a termů t1, . . . , tn typu nad množinou X. Aby zobrazení : FX() A mohlo být homomorfismus -algeber, je třeba, aby (t) = (f(t1, . . . , tn)) = (fFX ()(t1, . . . , tn)) = = fA((t1), . . . , (tn)). Klademe proto (t) = fA((t1), . . . , (tn)). 37 Je zřejmé, že pro právě zkonstruované zobrazení platí (x) = (x) pro všechny prvky x X, a že je to jediné zobrazení s touto vlastností, které by mohlo být homomorfismus -algeber. Na druhou stranu lze snadno dokázat, že skutečně homomorfismem -algeber je. Uvědomte si, že to jsme zajistili právě definicemi ve druhém a třetím bodu indukce. Poznámka. Protože naším cílem je důkaz Birkhoffovy věty, nebudeme kongruenci V na -algebře FX() definovat pouze pro varietu V typu , ale zdánlivě obecněji: pro libovolnou tzv. uzavřenou třídu -algeber dle ná- sledující definice. Slovo zdánlivě je v předchozí větě uvedeno proto, že dle Birkhoffovy věty stejně nic obecnějšího nakonec nedostaneme, ukáže se totiž, že každá uzavřená třída -algeber je varietou -algeber. Definice. Nechť V je třída -algeber. O třídě V řekneme, že je uzavřená, právě když splňuje následující tři podmínky z Birkhoffovy věty: ˇ V je uzavřená na podalgebry algeber; ˇ V je uzavřená na obrazy algeber v homomorfismech; ˇ V je uzavřená na libovolné součiny algeber. Poznámka. Snadno je vidět, že ze druhé podmínky plyne, že uzavřená třída -algeber s každou -algebrou A obsahuje i všechny -algebry izo- morfní s A. Definice. Nechť je typ, X množina. Pro libovolnou uzavřenou třídu -algeber V definujeme relaci V na -algebře FX() takto: pro libovolné t1, t2 FX() klademe t1 V t2 právě tehdy, když pro každou kongruenci na -algebře FX() takovou, že FX()/ patří do třídy V , platí t1 t2. Poznámka. Ekvivalentně lze říci, že V je průnikem všech kongruencí na -algebře FX() takových, že FX()/ patří do třídy V . Uvědomte si, že skutečně můžeme o tomto průniku mluvit: všechny relace na dané mno- žině tvoří množinu (tedy ne vlastní třídu), proto tvoří množinu i všechny kongruence na dané -algebře. Označme K množinu všech těch kongruencí na -algebře FX(), pro které faktoralgebra FX()/ patří do třídy V . Li- bovolná uzavřená třída -algeber musí obsahovat kartézský součin prázdné množiny -algeber, což je jednoprvková algebra (viz poznámku za definicí součinu libovolného počtu -algeber). Proto z uzavřenosti na homomorfní obrazy dostáváme, že libovolná uzavřená třída -algeber obsahuje všechny jednoprvkové -algebry. Odtud plyne, že množina K je neprázdná, neboť obsahuje kongruenci FX() × FX(), v níž jsou libovolné dva prvky ekviva- lentní, a tedy příslušná faktoralgebra je jednoprvková. Poznámka. Ukážeme, že právě provedená definice relace V je v pří- padě X = {x1, x2, . . . } ekvivalentní (i když to tak možná na první pohled 38 nevypadá) s definicí kongruence V na -algebře F() uvedenou v kapi- tole 7. Tam jsme kongruenci V definovali podmínkou: pro libovolné termy t1, t2 F() je t1 V t2 právě tehdy, když libovolná -algebra z třídy V (v sedmé kapitole jí byla varieta V ) splňuje rovnost t1 = t2. Tato pod- mínka dle definice znamená (jestliže termy t1, t2 jsou k-ární), že pro li- bovolnou -algebru A z variety V a libovolné prvky a1, . . . , ak A platí (t1)A(a1, . . . , ak) = (t2)A(a1, . . . , ak). Podle věty 7.3 je poslední podmínka ekvivalentní s následující podmínkou: pro libovolnou -algebru A z variety V a libovolný homomorfismus -algeber : F() A platí (t1) = (t2). Protože pro každý homomorfismus -algeber je (F()) podalgebrou - algebry A a protože třída V je uzavřená na podalgebry, stačí se v poslední podmínce omezit jen na surjektivní homomorfismy. Navíc, označíme-li já- dro homomorfismu , platí (t1) = (t2) právě tehdy, když t1 t2. V pří- padě, kdy je homomorfismus surjektivní, je podle důsledku věty 4.5 - algebra A izomorfní s faktoralgebrou F()/, a z toho, že A patří do třídy V , plyne, že též F()/ patří do třídy V . Dostali jsme tedy: pro libovolné termy t1, t2 F() je t1 V t2 právě tehdy, když pro libovolnou kongruenci na -algebře F() takovou, že faktoralgebra F()/ patří do třídy V , platí t1 t2. To je ale právě předchozí definice. Věta 8.3. Nechť je typ, X množina. Nechť V je uzavřená třída - algeber. Pak platí: ˇ Relace V je kongruencí na -algebře FX(). ˇ Faktorová algebra FX(V ) = FX()/V -algebry FX() podle kongru- ence V patří do třídy V . Důkaz. Víme, že V je průnikem neprázdné množiny K všech kongruencí na -algebře FX() takových, že FX()/ patří do V . První tvrzení tedy plyne z prvního tvrzení věty 4.4. Podle druhého tvrzení věty 4.4 existuje homomorfismus -algeber : FX() K FX()/, jehož jádrem je průnik všech kongruencí K, tedy kongruence V . Podle důsledku věty 4.5 je FX(V ) = FX()/V izomorfní s podalgebrou (FX()) -algebry K FX()/. Tento součin -algeber z uzavřené třídy V patří do V a opět z uzavřenosti V plyne, že také jeho podalgebra (FX()) patří do V , a tedy do V patří i s touto -algebrou izomorfní -algebra FX(V ), což se mělo dokázat. Definice. Nechť je typ, X množina, V je uzavřená třída -algeber. Faktorová algebra FX(V ) = FX()/V z věty 8.3 se nazývá volná algebra třídy V generovaná množinou X. Nechť : X FX(V ) je zobrazení určené podmínkou (x) = (x) pro všechny prvky x X, kde : FX() FX(V ) je projekce na faktorovou algebru. Pak zobrazení se nazývá vnoření generátorů do volné algebry FX(V ). 39 Poznámka. Pokud třída V obsahuje nějakou -algebru, která není jedno- prvková nebo prázdná, lze snadno odvodit z následující věty 8.4, že zobrazení je injektivní. Poznámka. Nyní ukážeme, že -algebra FX(V ) z předchozí definice sku- tečně splňuje charakterizační podmínku volné algebry. Věta 8.4. Nechť je typ, X množina. Nechť V je uzavřená třída - algeber, FX(V ) = FX()/V volná algebra třídy V generovaná množinou X, : X FX(V ) vnoření generátorů do volné algebry FX(V ). Nechť A je libovolná -algebra z třídy V a : X A libovolné zobrazení. Pak existuje jediný homomorfismus -algeber : FX(V ) A splňující podmínku = . Důkaz. Dokažme nejprve existenci homomorfismu . Nechť : FX() FX(V ) je projekce na faktorovou algebru. Podle věty 8.2 existuje jediný ho- momorfismus -algeber : FX() A splňující podmínku (x) = (x) pro všechny prvky x X. Protože (FX()) je podalgebra -algebry A patřící do V , z uzavřenosti V plyne, že do V patří (FX()). Označme jádro ho- momorfismu . Podle důsledku věty 4.5 je (FX()) izomorfní s FX()/. Proto FX()/ patří do V , a tedy je jedna z těch kongruencí, jejichž průnikem je V . Je proto kongruence V menší nebo rovna kongruenci . Protože je jádro homomorfismu : FX() A, FX(V ) = FX()/V a : FX() FX(V ) je projekce na faktorovou algebru, podle věty 4.5 exis- tuje jediný homomorfismus -algeber ~ : FX(V ) A s vlastností ~ = . Protože pak ~((x)) = ~((x)) = (x) = (x) pro všechny prvky x X, platí ~ = , a tedy je = ~ hledaný homomorfismus. Dokažme nyní, že homomorfismus je podmínkou věty určen jednoznačně. Nechť tedy ho- momorfismus -algeber : FX(V ) A také splňuje podmínku = . Pak ((x)) = (x) pro všechny prvky x X a = splňuje pod- mínku věty 8.2. Protože homomorfismus splňující tuto podmínku je jediný, dostáváme = . Tedy = ~ , z jednoznačnosti z věty 4.5 plyne = ~ = . Věta je dokázána. Poznámka. V následující větě ukážeme, že podmínka z předchozí věty skutečně charakterizuje -algebru FX(V ), určuje ji totiž jednoznačně až na izomorfismus. Věta 8.5. Nechť je typ, X množina. Nechť V je uzavřená třída - algeber, FX(V ) = FX()/V volná algebra třídy V generovaná množinou X, : X FX(V ) vnoření generátorů do volné algebry FX(V ). Nechť algebra U z třídy V a zobrazení : X U splňují následující podmínku: pro libovolnou -algebru A z třídy V a libovolné zobrazení : X A existuje jediný homomorfismus -algeber : U A splňující podmínku = . Pak platí: existuje izomorfismus -algeber : U FX(V ) takový, 40 že = . Důkaz. Protože -algebra U splňuje podmínku věty, pro -algebru FX(V ) a zobrazení : X FX(V ) existuje homomorfismus -algeber : U FX(V ) splňující = . Jen je třeba ukázat, že je izomorfismus. Naopak, podle věty 8.4 pro -algebru U a zobrazení : X U existuje homomorfis- mus -algeber : FX(V ) U splňující podmínku = . Pak homomor- fismus : FX(V ) FX(V ) splňuje = = . Rovněž identita na FX(V ), tj. zobrazení FX (V ) : FX(V ) FX(V ) splňující FX (V )(a) = a pro každé a FX(V ), je homomorfismem, pro který platí FX (V ) = . Protože dle věty 8.4 (pro -algebru FX(V ) a zobrazení : X FX(V )) je takový homomorfismus určen jednoznačně, platí = FX (V ). Zcela analogicky se dokáže, že je identita na U. To ale znamená, že je inverzní zobrazení k , a tedy je bijekce, což jsme chtěli dokázat. Poznámka. Nyní jsme již schopni dokázat Birkhoffovu větu, kterou jsme uvedli již jednou jako větu 6.6, ale nedokončili jsme důkaz jedné implikace. Věta 8.6. (Birkhoff) Nechť je typ. Třída -algeber je varieta, právě když splňuje všechny tři následující podmínky: ˇ je uzavřená na podalgebry algeber; ˇ je uzavřená na obrazy algeber v homomorfismech; ˇ je uzavřená na libovolné součiny algeber. Důkaz. Jedna implikace byla již dokázána v kapitole 6. Nechť V je li- bovolná uzavřená třída -algeber. Ukážeme, že V je varieta. Označme T množinu všech rovností typu , které platí ve všech -algebrách z třídy V . Označme W varietu -algeber určenou teorií T. Je třeba dokázat, že V = W. Z definice T je jasné, že platí inkluze V W. Ukážeme nyní, že také W V . Zvolme libovolně -algebru A W. Věta bude dokázána, ukážeme-li, že A V . Uvažme volnou algebru FX(W) = FX()/W třídy W generovanou mno- žinou X, přičemž za X volíme nosnou množinu -algebry A. Podle věty 8.4, v níž za zobrazení : X A volíme identitu, existuje homomorfismus - algeber : FX(W) A splňující podmínku (x) = (x) = x pro všechny prvky x X. Protože X = A, je zjevně surjektivní. Máme též volnou algebru FX(V ) = FX()/V třídy V generovanou stejnou množinou X. Označme KV (resp. KW ) množinu všech kongruencí na -algebře FX() takových, že FX()/ patří do třídy V (resp. W). Z inkluze V W plyne inkluze KV KW . Protože V je průnikem všech kongruencí z množiny KV a W je průnikem všech kongruencí z množiny KW , plyne odtud, že W V . Budeme hotovi, ukážeme-li také opačnou inkluzi V W . Pak totiž budou obě kongruence W a V stejné, a proto FX(W) = FX()/W = 41 FX()/V = FX(V ) bude patřit do třídy V . Z uzavřenosti třídy V pak do V bude patřit i homomorfní obraz (FX(W)) = A, což právě potřebujeme dokázat. Zaměřme se tedy na důkaz inkluze V W . Nechť t1, t2 FX() jsou libovolné termy takové, že t1 V t2. Pro projekci na faktoralgebru : FX() FX(V ) tedy platí (t1) = (t2). Podle definice termu nad množinou X je při tvorbě každého termu použito jen konečně mnoho prvků množiny X. Označme si x1, . . . , xn ty prvky množiny X, které byly použity při tvorbě termů t1 a t2; jsou tedy t1 a t2 při tomto označení n-árními termy typu , tj. t1, t2 Fn(). Dokažme nejprve, že rovnost t1 = t2 patří do teorie T, tj. že platí ve všech -algebrách z třídy V . Zvolme libovolně -algebru B z třídy V a její prvky b1, . . . , bn B a ukažme, že (t1)B(b1, . . . , bn) = (t2)B(b1, . . . , bn). Uvažme zobrazení : X B takové, že pro každé m = 1, . . . , n platí (xm) = bm a pro všechny ostatní prvky x X různé od x1, . . . , xn dodefinujme (x) = b1 (ve speciálním případě n = 0 všechny prvky množiny X zobrazíme na nějaký libovolně zvolený prvek z -algebry B). Označme : X FX(V ) vnoření generátorů do volné algebry FX(V ) třídy V . Podle definice je tedy (x) = (x) pro všechny prvky x X. Podle věty 8.4 existuje homomorfismus - algeber : FX(V ) B splňující podmínku = . Označme = , je tedy : FX() B homomorfismus, přičemž pro všechny prvky x X platí (x) = ((x)) = ((x)) = (x). Ovšem Fn() je podalgebra -algebry FX(), proto můžeme uvážit homomorfismus : Fn() B, který je zúžením homomorfismu . Pro každé m = 1, . . . , n platí (xm) = (xm) = (xm) = bm. Z věty 7.4 plyne, že homomorfizmus vycházející z volné algebry Fn() je jednoznačně určen svými obrazy na generátorech x1, . . . , xn, podle věty 7.4 tedy pro libovolný term t Fn() je (t) = tB(b1, . . . , bn). Připomeňme, že (t1) = (t2); celkem tedy platí (t1)B(b1, . . . , bn) = (t1) = (t1) = ((t1)) = ((t2)) = = (t2) = (t2) = (t2)B(b1, . . . , bn), a tedy rovnost t1 = t2 patří do teorie T. Nechť : FX() FX(W) je projekce na faktoralgebru a : Fn() FX(W) její zúžení na podalgebru Fn(). Podle věty 7.4 je homomorfismus jednoznačně určen svými obrazy na generátorech a pro každý term t Fn() tedy platí (t) = tFX (W)( (x1), . . . , (xn)). Ovšem FX(W) je -algebra z variety W určené teorií T, rovnost t1 = t2, o které jsme dokázali, že do teorie T patří, tedy platí i v FX(W), odkud plyne (t1) = (t1) = (t1)FX (W)( (x1), . . . , (xn)) = = (t2)FX (W)( (x1), . . . , (xn)) = (t2) = (t2). 42 To znamená, že t1 W t2, což jsme právě potřebovali dokázat. Poznámka. V průběhu důkazu věty 8.6 jsme odvodili další vlastnost volné algebry, která stojí za zmínku. Všimněte si, že 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 . 43