ZÁKLADY UNIVERZÁLNÍ ALGEBRY Radan Kučera 1. Operace a fž-algebry Úvod. V průběhu přednášky z algebry jsme studovali řadu algebraických struktur: grupoidy, pologrupy, grupy, komutativní grupy, okruhy, obory integrity, tělesa, polosvazy, svazy, Booleovy algebry. Při zkoumání těchto struktur 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 platilo, ž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 x G —>• G, avšak budeme potřebovat tuto definici pozměnit. Vždyť kromě těchto operací, který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 nej menším a nej vě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é karté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 G°? Jak si představit množinu všech 0-tic prvků množiny G? Podobně jako nultou 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 AxG->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 G° jako množinu všech uspořádaných 0-tic prvků množiny G, přičemž uspořádaná Cítíce 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 G° 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 G° = {0}. Pak tedy výběr prvku je zobrazení G° —> G. Definice. Nechť G je množina, n nezáporné celé číslo. Pak n-ární operací na množine 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 +, •, V, A 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 íl spolu se zobrazením a : íl —> NU{0} se nazývá typ. Prvky množiny D, se nazývají operační symboly. Pro f G íž 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 íl (neboli stručně íl-algebra) je množina A, na níž je pro každý n-ární operační symbol z f G íž defínována n-ární operace f a '■ An —> A. Pro libovolné ai,..., an G A značíme /a(oi, ■ ■ ■, an) hodnotu operace f a na uspořádané n-tici (ai,..., an). Poznámka. V případě nulárního operačního symbolu / G íž je n = 0, tedy A° = {0} a nulární operací je tedy zobrazení fA : {0} —>• A. Zadat takovéto zobrazení je totéž jako vybrat pevně jeden prvek /a(0) G A. Pro zjednodušení označení budeme v dalším textu tento pevně vybraný prvek značit jednoduše f a místo /a(0)- Poznámka. Obsahuje-li typ íl alespoň jeden nulární operační symbol, pak je každá íž-algebra neprázdná. Příklady. 1. Pro prázdný typ, tj. íž = 0, 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álni algebra typu {+, •, —, 0,1}. 5. Svaz je univerzálni algebra typu {V, A}. 6. Booleova algebra je univerzálni algebra typu {V, A,0,1}. 7. Vektorový prostor nad tělesem T lze chápat jako univerzální algebru typu {+, —, 0}UT (pro každý prvek tělesa č G 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ě bychom 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ť íl 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 / G íž je hodnota operace f a 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 Q, H C A podmnožina. Řekneme, že H je podalgebra Vt-algebry A, jestliže pro každý n-ární operační symbol f G íž a pro každé ai,..., an G H platí /a(oi, ■ ■ ■, o>n) £ H. Poznámka. V případě nulárního operačního symbolu / G íž je n = 0, tedy A° = {0}. Obraz tohoto jediného prvku jsme se dohodli značit stručně f a místo (možná přesnějšího) označení /a(0)- Podmínku z definice je tedy třeba chápat ve smyslu f a G H. Poznámka. Obsahuje-li typ íl 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ředchozí 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 vektorové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 Q,, I neprázdná množina. Pro každé i G I necht je dána podalgebra Hi C A algebry A. Pak jejich průnik (~)ieI Hi je podalgebra Vt-algebry A. Důkaz. Zvolme libovolně n-ární operační symbol / G íž a libovolně prvky ai,..., an G (~)ieI Hi. Pak pro každé i E I platí a\,... ,an G Hi. Protože Hi je podalgebra íž-algebry A, platí /a(oi, ■ ■ ■, o>n) E Hi. To ovšem znamená, že /a(oi, ■ ■ ■, On) ^ Hie/ c°ž se měl° dokázat. Důsledek. Obsahuje-li typ Vt alespoň jeden nulami operační symbol, pak je průnik libovolného neprázdného systému podalgeber dané algebry neprázdný. Důkaz. V tomto případě není prázdná množina podalgebrou. Důsledek. Necht P je množina všech podalgeber dané univerzální algebry A typu Vt. Pak platí: (P, C) je úplný svaz. Důkaz. Protože uspořádaná množina (P, C) 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 C P má v uspořádané množině (P, C) infimum. Tímto infimem je množinový průnik C\HeM 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 generovanou množinou. Definice. Nechť A je univerzální algebra typu Q, M C A podmnožina nosné množiny. Průnik všech podalgeber Vt-algebry A, které obsahují M jako svou podmnožinu, značíme (M) a nazýváme podalgebrou Vt-algebry A generovanou množinou M. Poznámka. Díky tomu, že alespoň jedna podalgebra íž-algebry A obsahují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 fž-algebry A obsahujících množinu M ta nejmenší (vzhledem k množinové inkluzi). Příklady. V jednotlivých případech příkladu univerzálních algeber z předchozí kapitoly dostáváme tyto podalgebry generované množinou: 1. V případě íž-algebry A prázdného typu fž = 0 je každá podmnožina množiny A podalgebrou, proto v tomto případě pro libovolné MCA je podalgebrou íž-algebry A generovanou množinou M sama množina M. 2. Podgrupoid grupoidu generovaný množinou. Tento pojem jsme v přednášce nezaváděli. 3. Podgrupa (M) grupy generovaná množinou M. 4 4. Podokruh (M) okruhu generovaný množinou M. 5. Podsvaz svazu generovaný 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 vektorů, což je jeden z nej důležitějších pojmů lineární algebry. Poznámka. Díky tomu, že podalgebra íž-algebry je podmnožina uzavř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 dostat 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 íl, (p : A —» B zobrazení. Řekneme, že

i), ■ ■ ■, (p(on)) = i, ■ ■ ■, an)). Poznámka. Pro nulární operační symbol předchozí podmínka samozřejmě znamená <£>(/a) = Íb- Poznámka. Jestliže je íž-algebra A prázdná (v tomto případě tedy typ fž 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 fž-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 íž = 0 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á definice 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 V a A. 6. V případě Booleových algeber jsme požadovali, aby homomorfismus zachovával V, A, 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í zobrazení. Poznámka. Následující dvě věty pro jednotlivé speciální případy univerzálních algeber známe z přednášky: složením dvou homomorfismu opět dostaneme 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 Vt, cp : A —>• B a tp : B —>• C homomorfismy Vt-algeber. Pak je též složení tp o

(((p(an))). Dohromady tedy ° vOCMai, ■ ■ ■, an)) = if)((p(fA(ai,an))) = = ý(fB(i), ■ ■ ■ ,(p(on))) = = fc(ý(i)), ý(n))) = = fc((if> o o (p)(on)), což jsme měli dokázat. 6 Věta 2.3. Nechť A, B jsou univerzální algebry téhož typu Q,

• B homomorfismus Vt-algeber. Pak obraz Vt-algebry A v homomorfismu cp (p(A) = {(p(a); a e A} je podalgebra Vt-algebry B. Důkaz. Zvolme libovolně operační symbol / G íž arity n. Pak pro každé prvky bi,...,bn G (f(A) existují ai,...,an G A tak, že A, ir2 ■ A x B —>• B ze součinu A x B předpisem: pro každé a G A, b G B klademe 7Ti((a, b)) = a, 7r2((a,6)) = b. Věta 3.1. Nechť A, B jsou univerzální algebry téhož typu Vt, AxB součin těchto Vt-algeber. Pak obě projekce ni, 7r2 jsou homomorfismy Vt-algeber. Důkaz. Ukažme, že projekce 7Ti je homomorfismus íž-algeber. Za tím účelem zvolme libovolně operační symbol / G íž arity n a prvky cii,..., an G A, bi,... ,bn G B. Platí TTl (/axb((«1, h), ■ ■ ■ , (an, K))) = TTl ((/a(Ol, ■ ■ ■ , On), ■ ■ ■ , &n))) = = /a(oi, ■ ■ ■ , On) = = /A(7Ti((ai,6i)), ... ,7Ti((an, &„))). Zcela analogicky se dokáže, že projekce 7T2 je homomorfismus íž-algeber. Věta 3.2. Nechť A, B, C jsou univerzálni algebry téhož typu Vt, (p : C —> A, tp : C —>• B homomorfismy Vt-algeber. Pak existuje jediný homomorfismus Vt-algeber p : C —>• A x B s vlastností 7Ti o p = (p, ti2 o p = tp, kde 7Ti : A x B —> A, 7r2 '■ A x B —>• B jsou projekce ze součinu A x B. Důkaz. Je zřejmé, že podmínky 7Ti o p = A x B následujícím předpisem: pro každé c G C klademe p(c) = ((ci)), . . . , ((p(cn), 1p(cn))) = = (/a(v(ci), ■ ■ ■ , (p(Cn)), /fl(^(ci), ■ ■ ■ , lf>(Cn))) ■ Nyní využijeme toho, že (p : C —>• A, ip : C —>• B jsou homomorfismy fž-algeber: (/a(v(ci), ■ ■ ■, (p(cn)), /b(^(ci), ■ ■ ■, ^(c„))) = = ((fc(ci, ■ ■ ■ , Cn))) = = P(7c(ci,...,cn)), 8 což se mělo dokázat. Poznámka. Nyní můžeme zobecnit součin fž-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í x z množiny I takových, že x(i) £ Ai pro každé i g /: n^i = {x= I^\jAi;VieI: X(i)6^}. iei iei Pro libovolné j g I defínujeme j-tou projekci ti j z kartézského součinu A = Y\ieI Ai takto: ti j : A —> Aj je určeno předpisem txj{x) = x(j) Pr0 každé 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 A i nemáme, jsme oprávněni mluvit o součinu: dle definice je součinem riie0^ množina všech zobrazení x : 0 —» Uie0^i- Protože Ai je množina všech prvků x, pro které existuje i E I tak, že x g Aj, je zřejmě Uie0 Ai = 0. Ovšem zobrazení x '■ 0 —>• 0 je jediné, totiž prázdné zobrazení. Proto množina Y[ie$ ^ 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 Ai, A2 rozumíme množinu uspořádaných dvojic Ai x A2 = {(a, b); a g Aub g A2}. Ovšem zadat uspořádanou dvojici (a, b) není nic jiného než pevně zvolit fl6Íi,í)g A2, což znamená právě tolik jako definovat zobrazení x '■ {1, 2} —>• AiUA2 s vlastností x(l) g A1: x(2) g A2: položíme x(l) = a, x(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ť Q je typ. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai typu íž. Součinem těchto Vt-algeber rozumíme novou Vt-algebru defínovanou na kartézském součinu A = YIíeiAí takto: pro každý operační symbol f g íž arity n a každé prvky Xi>--->Xn £ A, klademe /a(xi, ■ ■ ■ ,Xn) = Xj kde x g A je určeno podmínkou = ÍAi (Xi(*)> ■■■■> Xn(i)) Pro každé i g I. Poznámka. Ve speciálním případě, kdy indexová množina I je prázdná, je součinem fž-algebra na jednoprvkové množině, jejímž jediným prvkem je 9 prázdne zobrazení. Tato fž-algebra je jediná, neboť na jednoprvkové množině pro libovolné nezáporné celé číslo n existuje jen jedna n-ární operace (viz pozná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á fž. Ale to se dá snadno vysvětlit: součin Y\ je součin fž-algeber, lze jej aplikovat pouze na íž-algebry pro určité fž. Informace o tom, jak toto íž vypadá, je tedy uložena v tom, o jaký součin Y[ se jedná. Pokud bychom chtěli být naprosto přesní, měli bychom toto íl nějak v symbolu Yl 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 Yl Je Pr0 dané ÍX 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 / G íž podmínka v předchozí definici samozřejmě znamená f a = X> kde x G A je určeno podmínkou x(i) = Věta 3.3. Nechť pro libovolný prvek i množiny I je dána univerzální algebra daného typu D,, nechť A = Yli^i M 3e jejich součin. Pak platí • Pro každé j G / je j-tá projekce ti j : A —> Aj homomorfismus Vt-algeber. • Nechť C je univerzální algebra téhož typu D,, a pro každé j G / nechť je dán homomorfismus Vt-algeber (fj : C —> Aj. Pak existuje jediný homomorfismus Vt-algeber (p : C —>• A takový, že Tij o

A následujícím předpisem. Pro každé c G C klademe (p(c) = x, kde x E A je určeno podmínkou: pro libovolné j E I platí XU) = *ÁX) = Kj((p(c)) = (ttj o tp)(c) = ípj(c). 10 Pro (p (c) G A tedy platí: pro každé j G I je ( A je homomorfismus íž-algeber. Zvolme libovolně operační symbol / G íž arity n a prvky ci,..., cn G C. Označme X = /a(¥>(ci), ■ ■ ■ j ^(Cfi))) podle definice součinu íž-algeber pak pro každé i G J platí x(«) = /^((^(ci))^),...,^^))^)) = /Ai(^(ci),...,^(cn)) = = Ai je homomorfismus íž-algeber. Ovšem ^(/c(ci,...,cn)) = 7ri(^(/c(ci,...,cn))) = ((p(fc(ci,...,Cn)))(i). To znamená, že x a • B homomorfismus Vt-algeber. Pak relace ~ na nosné množině A definovaná předpisem: pro každé a, b G A platí je kongruence na 0,-algebře A. Důkaz. Zřejmě je ~ ekvivalencí příslušnou zobrazení (p. Stačí tedy ukázat, že splňuje implikaci v definici kongruence. Zvolme libovolně n-ární operační symbol / G íž a prvky cii,..., an, bi,..., bn G A tak, že ai ~ bi, ..., dn ~ bn. Odtud plyne n) ~ fňipi, ■ ■ ■, bn). Definice. Nechť A, B jsou univerzální algebry téhož typu íl, (p : A —> B homomorfismus Vt-algeber. Kongruence ~ na Vt-algebře A defínovaná předpisem (1) předchozí věty se nazývá jádro homomorfismu (p. 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 íl, nechť ~ je kongruence na Vt-algebře A. Označme R = Aj'~ rozklad příslušný ~. Pro každý n-ární operační symbol f G íž definujme n-ární operaci na R takto: pro každé (1) íp(fA(ai,an)) = fB((p(ai),tp(an)) = fB(^(bi),..., n) ~ fA(bi,---,bn), což znamená, že /a(oi, ■ ■ ■, an) a fA{b\, ■ ■ ■ ,bn) patří do stejné třídy rozkladu, totiž do třídy /r(Xi, ...,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, V, A) je svaz. Kongruence na něm je ekvivalence ~ na množině S splňující: pro každé a,b,c,d G S takové, že a ~ b a c ~ d, platí aVc~ř)V(lasAc~ř)A(í. Je-li ~ kongruence na svazu (S, V, A), pak faktorsvaz je svaz, jehož nosná množina je rozklad 5/~ a operace na ní jsou definovány pomocí reprezentantů: pro T, R G 5/~ zvolíme a G T, b G R a definujeme T V R jako třídu obsahující a V b a T A R jako třídu obsahující a A b. Věta 4.3. Nechť A je univerzálni algebra typu D,, ~ kongruence na íž-algebre A. Pak zobrazení n : A —>• A/~ určené předpisem a G 7r(a) pro libovolné a G A fŕeeí?/ 7r(a) je rfícřa obsahující prvek a) je surjektivní homo-morfismus Vt-algeber. Důkaz. Zobrazení 7r je surjekce, neboť každá třída rozkladu X G A/~ je neprázdná, existuje tedy a G X, pro které samozřejmě platí 7r(a) = X. Ukažme, že 7r je homomorfismus íž-algeber. Zvolme libovolně n-ární operační symbol / G íž a prvky ai,... ,an G A. Označme Xi = 7r(ai), ..., Xn = 7r(a„). Pak tedy a± G Xi,..., an G Xn a /a/~(Xi, ..., X„) je určeno tím, že obsahuje prvek fA(ai,.. .,an), tj. 7t(/a(«i, ■ ■ ■ ,an)) = fA/~(Xi,.. .,Xn) = /a/~(7t(«i), ■ ■. ,7r(a„)), což se mělo dokázat. Definice. Surjektivní homomorfismus Q-algeber ir : A —>• A/~ konstruovaný v předchozí větě se nazývá projekce Vt-algebry A na faktorovou algebru A/~. Důsledek. Nechť A je univerzální algebra typu Vt. Platí, že každá kongruence na Vt-algebře A je jádrem vhodného homomorfismu Vt-algeber vycházejícího z Vt-algebry A. 13 Důkaz. Nechť ~ je libovolná kongruence na fž-algebře A. Nechť 7r : A —>• A/~ je projekce fž-algebry A na faktorovou algebru A/~. Tvrzení bude dokázáno, ověříme-li, že jádrem 7r je ~. Označme ~ jádro 7r. Podle definice jádra homomorfismu pro libovolné a, b G A platí a ~ b právě tehdy, když 7r(a) = 7r(6), což podle definice projekce znamená, že a a b patří do téže třídy rozkladu neboli a ~ b. Definice. Nechť A je množina, ~ a ~ ekvivalence na množině A. Řekneme, že ekvivalence ~ je menší nebo rovna ekvivalenci ~, jestliže pro každé a, 6 G A platí implikace 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 x A, přičemž například a ~ b je stručnější a přehlednější zápis faktu (a, b) G ~, znamená implikace z předchozí definice vlastně množinovou inkluzi « C ~. 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 x A, v níž každé dva prvky množiny A jsou ekvivalentní (tedy jí odpovídající rozklad má - v případě A ^ 0 - jedinou třídu rozkladu, totiž celou množinu A). Uvažme libovolnou neprázdnou množinu E ekvivalencí na množině A. Průnikem všech ekvivalencí ~ G E je tedy relace ~ na množině A, pro kterou platí: pro libovolné a, b G A je a ~ b právě tehdy, když pro každé ~ G 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á inkluzi je úplný svaz. Rovněž množina všech kongruencí na dané íž-algebřě A uspořádaná inkluzi tvoří úplný svaz, jak plyne z následující věty, uvědomíte-li si, že relace A x 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 Vt-algebře A. Nechť relace ~ na množině A je průnikem všech kongruencí z množiny K, tj. pro libovolné a, b G A klademe a ~ b právě tehdy, když pro každé ~ G K je a ~ b. • Pak relace ~ je kongruencí na Vt-algebře A. • Uvažme součin Vt-algeber B = n~efi-^/~- Pro každé ~GÍř označme 7r^ : B —>• A/~ projekci ze součinu a /i^ : A —> A/~ projekci íž-algebry A na faktorovou algebru A/~. Podle věty 3.3 existuje jediný homomorfismus Vt-algeber (p : A —» B takový, že 7r^ o tp = \x^. Pak platí: jádrem homomorfismu cp 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 (&)), což vzhledem k 7r^ o tp = /i^ znamená právě //~(a) = n~(b), neboli a ~ b. Dokázali jsme, že pro libovolné a, b G A platí a ~ b právě tehdy, když pro každé ~ G 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 Vt, (p : A —>• B homomorfismus Vt-algeber s jádrem ~. Nechť ~ je libovolná kongruence na íž-algebře A menší nebo rovna kongruencí ~. Označme n : A —>• Aj m projekcí Vt-algebry A na faktorovou algebru AJth. Pak platí • Existuje jediné zobrazení (p : AJtu —>• B takové, že (p o 7r = (p. • Toto zobrazení (p je homomorfismus Vt-algeber. • Homomorfismus Cp je surjektivní, právě když homomorfismus cp je surjek-tivní. • Homomorfismus Cp je injektivní, právě když jsou obě kongruence ~ a ~ stejné (tj. ~ = m). Důkaz. Konstruujme zobrazení (p : AJtu —>• B tak, aby (p o 7r = cp. Zvolme libovolně X G A/m. Protože X je třída rozkladu, je neprázdná, a tedy existuje a G X. Podle definice 7r pak 7r(a) = X. Pak z podmínky (p o 7T = cp plyne • B splňující (p o 7r = cp existuje, je jediné. Definujme tedy (p : A/m —>• B tímto jediným způsobem: pro libovolné X G Aj7ti tedy zvolíme a G X a klademe ý>(X) = y(a). Je ale třeba ověřit korektnost této definice, neboli nezávislost na volbě a G X. Mějme další b G X, pak oba prvky a, b leží v téže třídě X rozkladu A/th, odkud a tu b. Protože kongruence ~ je menší nebo rovna kongruencí ~, plyne odtud a ~ b. Ovšem ~ je jádrem homomorfismu cp, proto poslední znamená (p(a) = i,...,an)) = = fB(• B homomorfismus Vt-algeber s jádrem ~. Pak obraz Vt-algebry A v homomorfismu (p 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 í typu íž nám v libovolné fž-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 Q. Nechť A je univerzální algebra typu íž. Definujeme n-ární operaci t a určenou termem t na Vt-algebře A následujícím způsobem. Nechť a\,..., an G 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 ía(oi, ■ ■ ■, o>n) = ak. • Je-li termem t nulární operační symbol f G íž, pak operací určenou termem t je operace na Vt-algebře A příslušná symbolu f, tj. pro t = f klademe ía(oi, ■ ■ ■, o>n) = Ía- • Je-li term t složen pomocí k-árního operačního symbolu f G íž, kde k > 1, z termů ti, ..., t k typu D,, pak operaci t a určenou termem t defínujeme takto: její hodnota vn-tici (ai,..., an) je hodnota operace f a na Vt-algebře A příslušné symbolu f v k-tici ■ ■ ■, o>n), ■ ■ ■ > ■ hodnot operací příslušných termům t\, ..., tk v n-tici (a\,..., an), tj. pro t = /(íi,..., tn) klademe tA(ai, ...,an) = /a((íi)a(oi, ..., a„),..., (íjOa(gi, ■ ■ ■, 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 t a označujeme různé operace! Je-li k nejmenší takové, že term í je ft-ární, pak t a 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 íl obsahuje binární operační symbol +. Jestliže například považujeme term xi + x2 za binární, pak podle předchozí definice platí (xi +x2)a(«i, «2) = ai + a2, pokud tento term však považujeme za 3-ární, pak (x± + x2)a(«i, «2, «3) = «1 + «2- Obecně, pro libovolné n > 2, je-li term x\ + x2 považován za n-ární, pak {x\ + x2)a(oi, ■ ■ ■, an) = a± + 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é a\,..., am G A platí ía(oi, ■ ■ ■, an) = ía(oi, ■ ■ ■, am), 18 kde symbolem ía 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 jiný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(ai, ...,an) = ak = (xk)A(ai, ...,am). • Je-li termem t nulární operační symbol / G íž, pak /a(oi, ■ ■ ■ , On) = f A = /a(oi, ■ ■ ■ , «m)- • Předpokládejme, že je term t složen pomocí /c-árního operačního symbolu / G íž, kde k > 1, z termů íi, ..., tk typu íž, pro které již bylo tvrzení dokázáno, tedy pro každé j = 1,..., k platí (íj)a(oi, ..., a„) = (íj)a(oi, ■ ■ ■, am). Pak platí tA(ai, ...,an) = ■■■,an), = /a((íi)a(oi, ■ ■ ■, «m), = ■ ■ ■ , «m)- Věta je dokázána. Příklad. Nechť Q = {•}, kde • je binární operační symbol, nechť A je univerzální algebra typu íž (tedy grupoid). Uvažme term xi ■ x2- Pak dle předchozí definice tento term určuje binární operaci (xi • x2)a(oi, a2) = (xi)a(oi, «2) • (^2)^(01, «2) = «i • «2- Podobně (x2 ■ xi)A{ai, a2) = {x2)A{ai, a2) ■ (xi)a(oi, a2) = a2 ■ ai. 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. ■ ■ ■, (tk)A{a>i, ■ ■ ■, On)) = ■ ■ ■ , (4)a(«1, ■ ■ ■ , «m)) = 19 Příklad. Uvažme typ Q = {V, A,0,1}, kde operační symboly V a A jsou binární, symbol ' je unární a symboly 0, 1 jsou nulární. Nechť A je univerzá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 nej menším a nej větším prvkem, identity pro komplement - viz následující kapitolu). Uvažme term (x± A x'2) V (x[ A x2), pak hodnota operace na A určené tímto termem v uspořádané dvojici prvků ai, a2 G A je ((xi A x'2) V (x[ A x2))a(oi, «2) = (xi A x'2)A(ai, a2) V (x[ A x2)A(ai, a2) = = ((xi)A(ai,a2) A {x'2)A(ai,a2)) V ((xí)A(«i, «2) A (x2)a(«i, «2)) = = (ai A ((x2)A(ai, a2))') V (((xi)a(oi, a2))' A a2) = = (cii A a'2) V (a[ A 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 /, a term f(xi,..., xn). Pak pro libovolnou íž-algebru A a libovolné a\,..., an G A platí (f(xi,xn))A(ai, ...,an) = fA((xi)A(ai, ...,an),..., (xn)A(ai,an)) = = fA(al,---i an), a tedy (f(xu .. .,xn))A = fA. Poznámka. Právě definované operace určené termy umožňují zformulovat následující obecnou větu o tom, jak vypadá podalgebra íž-algebry generovaná podmnožinou. Se speciálními případy této věty jsme se již několikrá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) Vt-algebry A generovaná množinou M je tvaru (M) = {tA(ai,..., an); n G Z, n > 0, t je n-ární term typu íž, a\,..., an G M}. Důkaz. Označme N množinu na pravé straně uvedené rovnosti. Nejprve dokážeme (M) C iV, a to tak, že ukážeme, že N je podalgebra íž-algebry A obsahující množinu M. Pro inkluzi M C N stačí vzít n = 1 a unární term xi, neboť pro libovolné a G M je (xi)A(a) = a. Dokažme tedy, že N je 20 podalgebra fž-algebry A. Zvolme libovolně ft-ární operační symbol / G íž a k libovolných prvků b\,...,bk G AT a ukažme, že fA{b\, ■ ■ ■, £ -/V". Ovšem pro každé j = 1,..., k existuje rij-ární term t j typu íž a n j prvků ajA,..., ajíTlj G M tak, že fy = (tj)A(ajA,..., ajjTlj). Potřebujeme prvky bi,..., 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 = ri\ + • • • + nk a uvažme n-tici (ai;i,..., aijřll,..., a^i,..., dk,nk) vzniklou poskládáním zmíněných rij-tic za sebe. Označme ťj term, který vznikne z termu t j tím, že se indexy všech proměnných v něm použitých zvětší o číslo ri\ + • • • + 7ij_i (tedy speciálně t[ = ti). Platí tedy pro každé j = 1,..., k bj = ■ ■ ■ , aj,nj) = ■ ■ ■ , Ol,íii, ■ ■ ■ ) ak,l, ■ ■ ■ , ak,nk), a proto /a(&1, ■ ■ ■ , h) = (f(t[, ■ ■ ■ , Í^))a(«1,1, ■ ■ ■ , «l,ni, ■ ■ ■ ) ak,l, ■ ■ ■ , ak,nk)- To je ale dle definice množiny N prvek N, což se mělo dokázat. Dokažme nyní inkluzi (M) D 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 ía(«i, ■ ■ ■, o>n), kde t je n-ární term typu íl a cii j ■ ■ ■ j «n G M. Nechť H je libovolná podalgebra íž-algebry A obsahující množinu M a ukažme indukcí podle definice termu, že tA{ai,..., an) G H. • Je-li termem t proměnná Xk, pak ía(«i, ■ ■ ■, an) = ak E M C H. • Je-li termem t nulární operační symbol / G íž, pak podle definice po-dalgebry tA(ai,..., an) = fA£ H. • Předpokládejme, že je term t složen pomocí /c-árního operačního symbolu / G íž, kde A; > 1, z termů íi, ..., tk typu íž, pro které již bylo tvrzení dokázáno, tedy pro každé j = 1,..., k platí fy = (tj)A(ai,..., an) G Pak platí tA(ai, ...,an) = fA((ti)A(ai, ...,an),..., (tk)A(ai,an)) = = fA(h,...,bk) G H dle definice podalgebry. Věta je dokázána. 6. Variety Definice. Nechť ti, t2 jsou termy typu íž. Výraz ti = t2 nazýváme rovností typu íž. 21 Příklad. Nechť Q = {•}, kde • je binární operační symbol, pak rovností typu íž je například rovnost x\ ■ x2 = x2 ■ x\. Tato rovnost psána naprosto formálně je tvaru -(xi,x2) = •(x2,Xi), 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 íl = kde operační symbol • je binární, symbol _1 je unární a symbol 1 je nulární. Příklady rovností jsou (xi -x2)-x3 = x\ • (x2 • X3), x\ • Xi1 = 1, atd. Definice. Nechť ti at2jsou termy typu íl, nechť A je univerzální algebra typu íž. Nechť n a m jsou nejmenší přirozená čísla taková, ze t\ je n-ární a í2 je m-ární term. Označme k = max{n, m}. Řekneme, ze rovnost t\ = č2 platí v Vt-algebře A, jestliže termy t\, í2 určují stejnou k-ární operaci na Vt-algebře A, tj. pro každé prvky cii,..., a*, G A platí ■ ■ ■, o>k) = (í2)a(«i, ■ ■ ■ ,ak). Poznámka. Podle věty 5.1 platí, že pokud termy t\ a í2 z předchozí definice určují stejnou k-ární operaci na A, tak pro libovolné přirozené číslo / > 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ť ti = t2 je libovolná rovnost typu íl Pak v libovolné jednoprvkové univerzální algebře A typu íž platí rovnost íi = í2- 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 íi = í2 také platí. Příklad. Nechť íl = {•}, kde • je binární operační symbol, pak rovnost xi ■ X2 = X2 ■ xi platí v íž-algebře A, právě když je A komutativní grupoid. Definice. Libovolnou množinu rovností typu Q, nazýváme teorií typu íž. Definice. Nechť T je teorie typu íl. Třídu všech íl-algeber, v nichž platí všechny rovnosti teorie T, nazýváme varietou Vt-algeber určenou teorií T. Příklad. Nechť T je libovolná teorie typu íl 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 fž-algeber, nikoli o množině všech fž-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íM^M vedou ke sporu). 22 Poznámka pro ty, kteří znají predikátovou logiku. Uvážíme predikátovou logiku v jazyce s operačními symboly z fž. Pak pro libovolné n-ární termy je rovnost íi = t2 atomickou formulí predikátové logiky, z níž přidáním kvantifikátorů utvoříme uzavřenou formuli (tj. sentenci) (Vxi)... (Vx„)(íi = 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ť íl = {•}, kde • je binární operační symbol. Teorie {xi-x2 = 22 • xi} určuje varietu všech komutativních grupoidů, teorie {(xi ■ x2) • £3 = Xi ■ (x2 ■ 23)} určuje varietu všech pologrup, teorie {Xi ■ X2 = X2 ■ Xi, (Xi ■ X2) • 23 = Xi • (x2 • 23), 2i • 2i = 2i} 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 íl = kde operační symbol • je binární, symbol _1 je unární a symbol 1 je nulární. Teorie {(2i-22)-23 = 2r(22-23), 2i-l = 2i, l-2i = 2i, 2r(2i)_1 = 1, (2i)_1-2i = 1} určuje varietu všech grup, přidáním další rovnosti x± ■ x2 = x2 ■ x± získáme teorii určující varietu všech komutativních grup. Tato varieta je samozřejmě též varietou určenou teorií {(2i • 22) • 23 = 2i • (22 • 23), 2i • 22 = 22 • 2i, 2i • 1 = 2X, 2X • (2i)"1 = 1}. Příklad. Uvažme typ íl = {+,-,—,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 íž: {(2i + 22) + 23 = 2i + (22 + 23), 2i + 22 = 22 + 2i, 2i + 0 = X\, 2i + (-2i) = 0, (21 • 22) • 23 = 2i • (22 • 23), 2i • 1 = 2i, 1 • 2i = 2i, 2i • (22 + 23) = (21 • 22) + (21 • 23), (21 + 22) • 23 = (21 • 23) + (22 • 23)}. 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 Q = {V, A}, kde oba operační symboly jsou binární. Pak varieta všech svazů je určená následující teorií T typu íž: T = {xi V x2 = x2 V Xi, (xi V x2) V x3 = Xi V (x2 V x3), Xi V Xi = Xi, Xi A x2 = x2 A xi, (xi A x2) A x3 = xi A (x2 A x3), xi A xi = Xi, (xi V x2) A xi = Xi, (xi A x2) Vii = Teorie Ti = T U {x! V (x2 A x3) = (x! V x2) A (xx V x3)} určuje varietu všech distributivních svazů, teorie T2 = T U {(xi A x2) V (xi A x3) = xx A (x2 V (xx A x3))} určuje varietu všech modulárních svazů. Příklad. Uvažme typ íl = {V, A,', 0,1}, kde operační symboly V a A jsou binární, symbol ' je unární a symboly 0, 1 jsou nulární. Nechť 7\ je teorie z předchozího příkladu. Pak teorie Ti U {xi A 0 = 0, xi V 1 = 1, xi V (xi)' = 1, xi A (xi)' = 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ě Qu 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 0. Vektorový prostor nad tělesem (R, +, •) je komutativní grupa (V, ©) a zobrazení © : R x V —> V splňující pro každé u,vEVa každé r,s G R r (D (u® v) = (r (D u)® (r (D v) (r + s)(Du= (r (D u)® (s (D 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 íž = {©, ©, 0} U R, kde operační symbol © je binární, symbol © je unární, symbol o je nulární a pro každé r G i? je r unární operační symbol. Uvažme následující teorii T typu íž: T = {(xi©X2)ffiX3 = Xiffi(x2ffiX3), XiffiX2 = X2ffiXi, XiffiO = Xi, Xiffi(©Xi) = o}. Tato teorie (uvažovaná jako teorie typu {©, ©, o}) určuje varietu všech komutativních grup. Přidáme k ní zbylé čtyři axiomy vektorových prostorů. 24 Čtvrtý axiom 1 © u = u je nejsnadnější: 1 G R je unární operační symbol, tedy odpovídající rovností je rovnost l(xi) = x\. Pro druhý a třetí axiom uvážíme libovolné r, s G 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 íž: První axiom pro libovolné r G R dává rovnost r(x\ © x2) = r(xi) © r(x2). Celkem tedy dostáváme teorii 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 Vt-algeber určená teorií T. Pak pro každou Vt-algebru A G V a každou podalgebru B Vt-algebry A platí Důkaz. Uvažme libovolnou rovnost t\ = t2 z teorie T. Protože A G V, platí tato rovnost v íž-algebře A. Ovšem zřejmě pro každý n-ární term t typu íl a libovolné d\, . . . , Oun G B platí Čb(cíi, ..., an) = ■ ■ ■, o>n)- Proto rovnost íi = t2 platí i v íž-algebře B. Dokázali jsme, že každá rovnost teorie T platí v fž-algebře B a tedy B e 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 íl Věta 6.2. Nechť A, B jsou univerzální algebry typu Vt, (p : A —» B homomorfismus Vt-algeber. Pak pro libovolný n-ární term t typu íž a libovolné ai,..., an G A platí Důkaz. Větu dokážeme indukcí vzhledem k termu t. • Je-li termem t proměnná Xk, pak tA i jsou k-té projekce, a tedy (r + s)(xi) = r(xi) © s(xi), (r • s)(xi) = r(s(xi)). B e V. tB(n) = f a, tB( 1, z termů íi, ..., č& typu íž, pro které již bylo tvrzení dokázáno, tedy pro každé j = 1,..., k platí (tj)B((p(ai), ■ ■ ■, (p(on)) = (p((tj)A(ai, ■ ■ ■, an)). Podle definice operace určené termem platí tA(a±, ■ ■ ■, On) = /a((íi)a(oi, ■ ■ ■, On), ■ ■ ■, ■ ■ ■, On)), podobně íB(^(ai),...,^(an)) = = ■ ■ ■, y(an)), ■ ■ ■, (tk)B(i), ■ ■ ■, y(on)))- Podle definice homomorfismu a indukčního předpokladu platí (p(tA(ai,an)) = (p(fA((ti)a(ai, ...,an),..., ■ ■ ■, an))) = = 7b(<^((íi)a(«i, ■ ■ ■, an)),(p((tk)A(ai,an))) = = fB((h)B((p(ai),(p(an)),..., (tk)B(■■->Xn(«))- Důkaz. Větu dokážeme indukcí vzhledem k termu t. • Je-li termem t proměnná Xk, pak t a i íať jsou k-té projekce, a tedy X = tA(xi,-- ■ ,Xn) = Xk a ÍAi(Xl(*)>- ■ ■ >Xn(«)) = Xk(i) = x(i)- • Je-li termem t nulární operační symbol / g íž, pak dle definice součinu íž-algeber platí f a = £, kde £ g A je určeno podmínkou = 7^, což je dokazované tvrzení. • Předpokládejme, že je term t složen pomocí /c-árního operačního symbolu f g íž, kde A; > 1, z termů íi, ..., 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 tpj = (íj)a(xij ■ ■ ■ > Xn)- Předpokládáme tedy, že t = f (h,..., tk) a že pro každé i g I a pro každé j = 1,..., k platí ipj(i) = (íj)aí(xi(Oj ■ ■ ■ jXíi(O)- Podle definice operace určené termem platí *Ai(Xl(*)>--->Xn(í)) = = /ať((íl)ať(Xl(*)>--->Xn(í))> = fAi(lf>l(i),---,lf>n(i)) a také X = *A(Xl,---,Xn) = = fA((h)A(Xl,---,Xn), = fA(lf>l,---,lf>n), ■■-,(tk)ai(Xl(í),---,Xn(í))) = ■■■,(**)A(Xl,---,Xn)) = 27 a tedy podle definice operací na součinu íž-algeber pro každé i G / platí = fAi(tpi(i),... ,tpn(i)). Ovšem výše jsme odvodili, že ÍAi (-01 (i), ■ ■ ■ , lf>n («)) = tAi (Xl (i), ■ ■ ■ , Xn (»)) ■ 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 D,, V varieta Vt-algeber určená teorií T. Nechť pro libovolný prvek i množiny I je dána univerzální algebra typu íž. Označme A součin těchto Vt-algeber, tj. A = ILe/^- platí: jestliže pro každé i G I je Ai G V, pak též A G V. Důkaz. Uvažme libovolnou rovnost íi = í2 z teorie T. Protože pro každé i G I je Ai G V, platí tato rovnost v íž-algebře Aim Nechť n je takové, že oba termy íi, í2 jsou n-ární. Je třeba ověřit, že pro libovolné xi, ■ ■ ■ > Xn £ A platí (*0a(Xi, ■ ■ ■ , Xn) = (t2)A(XU ■ ■ ■ , Xn)- Označme *0i = (íi)a(xi, ■ ■ ■,Xn) a tp2 = (h)A(xi, ■ ■ ■ ,Xn)- Naším cílem je dokázat, že tpi = tp2- Podle definice součinu množin jsou tpi a ip2 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 G / platí ipi(i) = ip2(i)- Z předchozí věty plyne, že pro každé i G I platí ip^i) = (ti)Ai(xi(i), ■ ■ ■,Xn(i)) a ip2(i) = (h)Ai(xi(i): ■ ■ ■ ,Xn(i))- Protože rovnost íi = í2 platí v íž-algebře Ai, je (tl)Ai(Xl(i), Xn(i)) = (Í2)Aí(Xi(*)> •••■> Xn(i)), a tedy též tpi(i) = ip2(i), což jsme chtěli dokázat. Dokázali jsme, že každá rovnost teorie T platí v íž-algebře A a tedy A G 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ální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 {V, A}, neboť součinem 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 univerzálních algeber typu Rozšířením typu jsme totiž dosáhli toho, že zmíněné podgrupoidy už nebyly podalgebrami {•, _1, l}-algeber. Nabízí se tedy otázka, zda i v případě třídy všech těles nebo třídy všech oborů integrity 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é íž D {+,-,—,0,1}. Podobně třída všech řetězců netvoří varietu íž-algeber pro žádné íl D {V, A}. Poznámka. Následující věta završí popis variet íž-algeber. Charakterizuje, které třídy íž-algeber jsou varietami, tj. které třídy je možné charakterizovat 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 Vt-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 kapitole 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 fž-algebrách z třídy V (uvědomte si, že T je vždy nekonečná množina). 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 C W. Celá obtížnost důkazu věty spočívá v důkazu inkluze W C V. Je totiž nutné ukázat, že libovolnou íž-algebru A G W lze vytvořit pomocí tvoření podalgeber, součinů a obrazů v homomorfismech z fž-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ť Q je typ. Označme F(Q) množinu všech termů typu Q. Na této množine defínujeme Vt-algebru následujícím způsobem. Pro libovolný 29 n-ární operační symbol f G íž deňnujeme n-ární operaci /f(o) na Sl-algebře F(Q) příslušnou operačnímu symbolu f takto: pro libovolné termy t\, ..., tn G F(íí) je /F(n)(íi, ■ ■ ■, tn) = f (h, ■..,*„)■ Poznámka. Všimněte si, jak se počítají hodnoty operací v právě popsané fž-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(Q), 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 = {xi,x2, ■ ■ ■ } a uvažme podalgebru (P) generovanou v algebře F(D,) množinou P. Pak platí (p) = F(n). Důkaz. Stačí ukázat inkluzi F(íľ) C (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 / typu íž platí / = /f(o), což je prvek libovolné podalgebry. Konečně pro term f(t\,... ,tn) vzniklý z n-árního symbolu / G íž a termů ti,... ,tn patřících dle indukčního předpokladu do (P) je /(či,..., tn) = fF(n)(ti,..., tn) G (P) dle definice podalgebry. Definice. íl-algebra F(íľ) z předchozí deňnice se nazývá volná algebra typu Vt generovaná množinou {x\, x2,...}. Definice. Nechť Q je typ, r nezáporné celé číslo. Označme Fr(Q) množinu všech r-árních termů typu íž. Příklad. Jestliže typ íž neobsahuje žádný nulární operační symbol, pak platí F0(íí) = 0. Příklad. Uvažme typ íl = {'}, kde ' je unární symbol. Pak fž-algebrami jsou množiny A spolu se zobrazením ' : A —> A. Pak platí Fi(Q) = {xi,x'1,x'1',x'1",...}, F2(fi) = {x±, Xi, Xi, Xi ,..., x2, x2, x2, x2 ,...}. Příklad. Uvažme typ íž = {', 1}, kde ' je unární symbol a 1 nulární symbol. Volná algebra typu íž generovaná prázdnou množinou je pak fž-algebra F0(íž) = {1, ľ, 1", ľ",... }. To jsou vlastně přirozená čísla. Při konstrukci přirozený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 C N, která by pro každé m G M obsahovala též m' a která by také obsahovala nejaký prvek n, který nelze vyjádřit ve tvaru n = r' pro žádné r G 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(Q) pod-algebra Vt-algebry F(Q) generovaná množinou r proměnných {x\,..., xr}, tj. Fr(Ú) = ({xi,.. .,xr}). Důkaz. Inkluzi Fr(Q) C ({x\,... ,xr}) dokážeme stejně jako předchozí větu. Opačná plyne z toho, že Fr(íľ) je podalgebra íž-algebry F(íl) obsahující množinu proměnných {xi,..., 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(Q) je skutečně podalgebra. Definice. íl-algebra Fr(íl) se nazývá volná algebra typu íl generovaná množinou {xi,..., 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 jediný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 Vt-algebra, 01,02,03,... libovolná pevně zvolená posloupnost prvků z A. Pak existuje jediný homomorfismus Vt-algeber cp : F(Q) —>• A splňující podmínku 1, z termů ti,...,tn G F (Q), pro které platí indukční předpoklad, tj. pro každé j = 1,... ,71 je --->ín)) = = /a(• A splňující podmínku • A. Poznámka. Naším dalším cílem je nalézt volné íž-algebry v každé varietě íž-algeber. Volné íž-algebry F(íľ) a Fr(íl) totiž splňují pouze triviální rovnosti, leží proto jen ve varietě všech fž-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 takové 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 Q-algeber. Na množině F(Q) všech termů typu íž defínujeme relaci ~y takto: pro libovolné termy í1; í2 £ F(Q) klademe ti ~y t2 právě tehdy, když libovolná Vt-algebra z variety V splňuje rovnost ti = t2. Poznámka. Nechť íi, t2 jsou n-ární termy typu íl Pak je tedy íi ~y t2 právě tehdy, když na libovolné íž-algebře A z variety V oba termy íi, t2 určují stejnou n-ární operaci, tj. pro libovolné ai,..., an G A platí (íi)a(«i, ■ ■ ■, o>n) = (í2)a(«i, ■ ■ ■ , On)- 32 Věta 7.5. Pro libovolnou varietu Sl-algeber V je relace ~y kongruencí na Vt-algebře F{Q). Důkaz. Z předchozí poznámky se snadno vidí, že ~y je ekvivalence na množině F(Q). Dokažme, že jde o kongruenci. Za tím účelem zvolme libovolně n-ární operační symbol / G íž a termy t\,... ,tn, s\,..., sn G F (Q) takové, že íi ~y Si,... ,tn ~y sn. Dokážeme, že potom také /(či,... ,tn) ~y /(si,..., sn). Zvolme libovolně fž-algebru A z variety V. Platí tedy (íi)a = ■ ■ ■, (*íi)a = (sn)A- Nechť přirozené číslo k je takové, že všechny zde vystupující termy jsou ft-ární. Pak pro libovolné a\,..., ak G A platí (/(či, ■ ■ ■, čn))a(oi, ■ ■ ■, ak) = /a((či)a(oi, ...,ak),..., (tn)A(ai,ak)) = = /a((si)a(«i, ...,ak),..., (sn)A(ai,ak)) = = (f(si, ■ ■ .,sn))A(ai,.. .,ak), což se mělo dokázat. Poznámka. Můžeme tedy hovořit o faktorové algebře íž-algebry F(Q) podle kongruence ~y. Tuto faktorovou íž-algebru budeme značit F (V) = F(íí)/~v. Poznámka. Uvědomte si, že nehrozí nebezpečí záměny F(Q) a F (V) i kdybychom označili typ jiným písmenem než fž 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 Vt-algeber V je Vt-algebra F(V) prvkem variety V. Důkaz. Nechť T je teorie určující varietu V, nechť či = č2 je libovolná rovnost této teorie. Nechť k je přirozené číslo takové, že oba termy či a t2 jsou ft-ární. Je tedy třeba ověřit, že pro libovolné Vi,...,vk G F (V) platí (ti)F(v)(vi,---,vk) = (t2)F(v)(vi,---,vk). Označme 7r : F(Ú) ->• F (V) projekci na faktorovou algebru. Podle věty 4.3 je 7r surjektivní homomorfismus. Pro každé i = 1,..., k zvolme term s, G F (Q) tak, že ir(si) = V{. Podle věty 6.2 pro j = 1, 2 platí (tj)F(v)(vi, ...,vk) = (Íj)f(v)(tt(si), ■ ■ ■ ,tt(s*)) = 7r((íj)f(n)(si, ■ ■ ■,«*))■ Máme tedy dokázat, že 7r((či)F(n)(si,..., sk)) = 7r((č2)f(n)(si, ■ ■ ■, sk)), což je ekvivalentní s tvrzením (íi)f(íí)(si, ■ ■ ■, sk) ~y (t2)F(n)(si, sk). To bude dokázáno, pokud libovolná íž-algebra A z variety V splňuje rovnost (ti)F(n)(si,...,sk) = (t2)F(n)(si,. ■ - ,sk). 33 Nechť m je přirozené číslo takové, že všechny termy si,...,sk jsou m-ární. Máme tedy ukázat, že pro libovolnou íž-algebru A z variety V a pro libovolné její prvky a±,..., am G A platí ((*i)f(n)(si, ■ ■ ■ ...,am) = ((í2)f(o)(si, .. .,sk))A(ai, ■ ■ ■ ,am)- Doplňme nějak do nekonečné posloupnosti prvků z fž-algebry A, například takto: pro každé n > m klademe an = a\. Podle věty 7.3 existuje homomorfismus íž-algeber

A takový, že pro libovolný /-ární term t G F (Q,) je (p (t) = ■ ■ ■ ,ai). Pro j = 1, 2 tedy platí ((Íj)f(íí)(si, ■ ■ -,Sk))A(ai, ...,am) = • F (V) projekce na faktorovou algebru. Nechť A je libovolná Vt-algebra z variety V, ai, a2, a3,... libovolná pevně zvolená posloupnost prvků z A. Pak existuje jediný homomorfismus Vt-algeber tp : F (V) —>• A splňující podmínku tp(7r(xm)) = am pro všechna přirozená čísla m. Přitom pro tento homomorfismus platí: pro libovolný k-ární term t G F (Q) je tp(7r(t)) = ía(oi, ■ ■ ■ ,a>k), kde tA je operace určená termem t v Vt-algebře A. Důkaz. Podle věty 7.3 existuje jediný homomorfismus íž-algeber cp : F (Q) —>• A splňující podmínku k)- Označme ~ jádro homomorfismu (p. Uvažme libovolné n-ární termy íi, í2 takové, že h ~y t2. Podle definice kongruence ~y je rovnost íi = t2 splněna v íž-algebře A, a proto platí = (h)A(ai, ...,an) = (í2)a(«i, ■ ■ ■, an) = ip(t2), a tedy íi ~ t2. Ukázali jsme, že kongruence ~y je menší nebo rovna kongru-enci ~. Proto podle věty 4.5 existuje jediný homomorfismus ip : F (V) —>• A 34 splňující -0O7T = ip. Pro tento homomorfismus tedy pro všechna přirozená čísla m platí am = • A je splněna podmínka r(7r(xm)) = am pro všechna přirozená čísla m. Pak pro homomorfismus tok; F (Q) —>• A platí (r o 7r)(xm) = am, a tedy podle věty 7.3 je t o 7t = • F (V) projekce na faktorovou algebru. Pro libovolné nezáporné celé číslo r označme Fr(V) obraz podalgebry Fr(íľ) v homomorfísmu ir, tj. Fr(V) = 7r(Fr(íž)). Tuto íl-algebru Fr(V) nazýváme volnou algebrou variety V typu D, generovanou množinou {x\,..., 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 7r : F(D) —>• F (V) dostáváme dle definice Fr(V) surjektivní homomorfismus Fr(íľ) —>• Fr(V), který budeme pro jednoduchost označovat opět 7r a nazývat projekcí. Věta 7.8. Nechť V je libovolná varieta Vt-algeber, r nezáporné celé číslo, Fr(V) volná algebra variety V typu íž generovaná množinou {x±,... ,xr}, 7t : Fr(Q) —>• ^(V) projekce. Nechť A je libovolná Vt-algebra z variety V, G A libovolné pevné zvolené prvky. Pak existuje jediný homomorfismus Vt-algeber tp : ^(V) —>• A splňující podmínku ip(7r(xm)) = am pro všechna m = 1,... ,r. Přitom pro tento homomorfismus platí: pro libovolný term t G Fr(Q) je tp(7r(t)) = ía(oi, ■ ■ ■, a>r), kde tA je operace určená termem t v Vt-algebře A. Důkaz. Tuto větu lze dokázat stejně jako větu 7.7 (jen místo kongruence ~y na F{Q) užíváme zúžení kongruence ~y na podalgebru Fr(Q), tj. průnik relací ~y a Fr(Q) x Fr(Q), neboli jádro projekce 7r : Fr(Q) —>• Fr(V)). Příklad. Uvažme opět typ íž = {'}, kde ' je unární symbol. Připomeňme, že Fo(íí) = 0, F1(Sl) = {x1,x,1,x,l,xT,...}, F2(fi) = {x±, Xi, Xi, x1 ,..., x2, x2, x2, x2 ,...}. 35 Nechť V je varieta určená teorií T = {x± = x"}. Pak platí Xi ~y x" ~y x'"' ~y X[ ~y X»' ~y X'»" ~y Je tedy FX{V) = {{xux'[, xT,...}, <, x?", ...}}■ V této fž-algebře se počítá takto: {xi,x1,x1 ,■■■} = {x1,x1,x1 ,■■■}, {x1; x± , x1 , ■ ■ ■ } = {x±, x1; x1 ,...}. Podobně F2(V) = x'/, xT, ■ ■ ■ }, {x[, x?, x'ľ", ..-h {x2, X2,X2 ,...}, {x2, X2 ,X2 ,...}}. Uvažme nyní varietu W určenou teorií {x[ = x'{}. Platí F1(W) = {{x1], {x[,x'l,x'ľ,...}}, přičemž v této íž-algebře se počítá takto: {xi} = {x1; xl, xl ,... } = {x1; xl, xl ,... }. Promyslete si sami, že pro varietu U určenou teorií {x[ = x'"} platí F^U) = {{Xl}, {x[,x'ľ,x7, ■ ■ ■ }, Wl,x'l",...}}, 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ť Q, je typ, X množina. Termem typu Q, nad množinou X nazveme právě takový výraz, který lze zkonstruovat konečně mnoha aplikacemi následujících pravidel: 36 • Pro libovolný prvek x G X je x term typu íž nad množinou X. • Pro libovolný nulární operační symbol f G íž je f term typu íž nad množinou X. • Pro libovolné přirozené číslo n, libovolný n-ární operační symbol f G íž a libovolné termy t\, ..., tn typu íž nad množinou X je výraz /(či,... ,tn) term typu íž nad množinou X. Množinu všech termů typu íž nad množinou X budeme značit Fx(ft). Poznámka. Termy typu íž, které jsme užívali dosud, jsou tedy termy typu íž nad množinou {x±, x2,... }. Definice. Nechť Q je typ, X množina. Na množině Fx(&) definujeme volnou algebru typu Vt generovanou množinou X následujícím způsobem. Pro libovolný n-ární operační symbol / G íž defínujeme n-ární operaci /fx(o) na Vt-algebře Fx(ft) příslušnou operačnímu symbolu f takto: pro libovolné termy tu ..., tn G Fx(íí) je fFx(n)(ti, ...,*„) = f(tu tn). Poznámka. Oprávněnost názvu íž-algebry Fx(ťl) prokáží věty 8.1 a 8.2. Příklady. íž-algebru F(íľ) z kapitoly 7 dostaneme v předchozí definici pro množinu X = {x±, x2, ■ ■ ■ }, pro libovolné nezáporné celé číslo r dostaneme íž-algebru Fr(Q) z kapitoly 7 v předchozí definici pro množinu X = {x±,..., xr}. Věta 8.1. Nechť íž je typ, X množina. Uvažme podalgebru (X) generovanou 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 Vt-algebra, (j> : X —> A libovolné zobrazení. Pak existuje jediný homomorfismus Vt-algeber cp : Fx(&) —> A splňující podmínku (p(x) = (j>{x) pro všechny prvky x G X. Důkaz. Definujme zobrazení

• A indukcí vzhledem k definici termu nad množinou X. • Pro libovolný prvek x G X klademe (p(x) = (j>{x). • Aby zobrazení

• A mohlo být homomorfismus íž-algeber, je třeba pro libovolný nulární operační symbol / G íž položit A mohlo být homomorfismus íž-algeber, je třeba, aby = V(/(*l,---,*n)) = ¥'(/FJf(n)(íl>--->ín)) = = fA({x) pro všechny prvky x G 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 cp skutečně homomorfismem fž-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 ~y na íž-algebře FX(D,) 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 íl-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 homomorfísmech; • 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 fž-algebry izomorfní s A. Definice. Nechť Q, je typ, X množina. Pro libovolnou uzavřenou třídu íl-algeber V defínujeme relaci ~y na íl-algebře Fx(íl) takto: pro libovolné t\, t2 £ Fx(&) klademe t\ ~y t2 právě tehdy, když pro každou kongruenci ~ na íl-algebře Fx(ťl) takovou, že Fx(íí)/~ patří do třídy V, platí t± ~ í2- Poznámka. Ekvivalentně lze říci, že ~y je průnikem všech kongruenci ~ na íž-algebře Fx(ťl) 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 kongruenci na íž-algebře Fx(íl), pro které faktoralgebra Fx(íl)/~ patří do třídy V. Libovolná uzavřená třída íž-algeber musí obsahovat kartézský součin prázdné množiny fž-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(D,) x FX(D,), v níž jsou libovolné dva prvky ekvivalentní, a tedy příslušná faktoralgebra je jednoprvková. Poznámka. Ukážeme, že právě provedená definice relace ~y je v případě X = {xi,x2,...} ekvivalentní (i když to tak možná na první pohled 38 nevypadá) s definicí kongruence ~y na fž-algebře F (D,) uvedenou v kapitole 7. Tam jsme kongruenci ~y definovali podmínkou: pro libovolné termy h,h £ je ti~vt2 právě tehdy, když libovolná íž-algebra z třídy V (v sedmé kapitole jí byla varieta V) splňuje rovnost íi = t2. Tato podmínka dle definice znamená (jestliže termy í1; t2 jsou ft-ární), že pro libovolnou íž-algebru A z variety V a libovolné prvky ai,...,a,k G A platí (íi)a(oi, ■ ■ ■, a>k) = (Í2)a(oi, ■ ■ ■, a>k)- 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 ip : F(íl) —>• A platí • ELe*-^M^)/~> jehož jádrem je průnik všech kongruenci ~ G K, tedy kongruence ~y. Podle důsledku věty 4.5 je Fxiy) = Fx(Q)/~y izomorfní s podalgebrou (p(Fx(íl)) fž-algebry rLeft-^M^)/~- Tento součin fž-algeber z uzavřené třídy V patří do ľ a opět z uzavřenosti V plyne, že také jeho podalgebra (p(Fx(D,)) patří do V, a tedy do V patří i s touto íž-algebrou izomorfní fž-algebra FX(V), což se mělo dokázat. Definice. Nechť íl je typ, X množina, V je uzavřená třída íl-algeber. Faktorová algebra FX(V) = FX(Q)/~V z věty 8.3 se nazývá volná algebra třídy V generovaná množinou X. Nechť \i : X —>• FX(V) je zobrazení určené podmínkou /i(x) = tt(x) pro všechny prvky x G X, kde 7r : FX(D,) —>• Fx (V) je projekce na faktorovou algebru. Pak zobrazení \i se nazývá vnoření generátorů do volné algebry FX(V). 39 Poznámka. Pokud třída V obsahuje nějakou fž-algebru, která není jednoprvková nebo prázdná, lze snadno odvodit z následující věty 8.4, že zobrazení \i je injektivní. Poznámka. Nyní ukážeme, že íž-algebra FX(V) z předchozí definice skuteč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(Q)/~y volná algebra třídy V generovaná množinou X, \i : X —> FX(V) vnoření generátorů do volné algebry FX(V). Nechť A je libovolná Vt-algebra z třídy V a (j> : X —> A libovolné zobrazení. Pak existuje jediný homomorfismus Vt-algeber tp : FX(V) —> A splňující podmínku tp O /I = (f). Důkaz. Dokažme nejprve existenci homomorfismu ip. Nechť 7r : FX(Q,) —>• Fx(V) je projekce na faktorovou algebru. Podle věty 8.2 existuje jediný homomorfismus íž-algeber (p : FX(D,) —>• A splňující podmínku (p(x) = (p(x) pro všechny prvky x G X. Protože (p(Fx(Q)) je podalgebra íž-algebry A patřící do V, z uzavřenosti V plyne, že do V patří (p(Fx(D,)). Označme ~ jádro homomorfismu (p. Podle důsledku věty 4.5 je (p(Fx(íl)) izomorfní s Fx(íľ)/~. Proto Fx(íí)/~ patří do V, a tedy ~ je jedna z těch kongruencí, jejichž průnikem je ~y. Je proto kongruence ~y menší nebo rovna kongruenci ~. Protože ~ je jádro homomorfismu (p : Fx(íl) —> A, FX(V) = FX(Q)/~V a 7t : FX(Q) —> FX(V) je projekce na faktorovou algebru, podle věty 4.5 existuje jediný homomorfismus íž-algeber (p : FX(V) As vlastností (poir = (p. Protože pak (p(/i(x)) = (p(7r(x)) = (p(x) = (j>(x) pro všechny prvky x G X, platí (p o fi = (f), a tedy je tp = (p hledaný homomorfismus. Dokažme nyní, že homomorfismus ip je podmínkou věty určen jednoznačně. Nechť tedy homomorfismus íž-algeber tp' : FX(V) —>• A také splňuje podmínku tp' o \x = cp. Pak tp'(n(x)) = (p(x) pro všechny prvky xEXa(p' = ip'o7r splňuje podmínku věty 8.2. Protože homomorfismus splňující tuto podmínku je jediný, dostáváme cp' = cp. Tedy tp' o 7r = (p o 7r, z jednoznačnosti z věty 4.5 plyne tp' = (p = tp. 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(Q)/~V volná algebra třídy V generovaná množinou X, \i : X —>• FX(V) vnoření generátorů do volné algebry FX(V). Nechť algebra U z třídy V a zobrazení v : X —>• U splňují následující podmínku: pro libovolnou Vt-algebru A z třídy V a libovolné zobrazení (j> : X —> A existuje jediný homomorfismus Vt-algeber tp : U —>• A splňující podmínku tpou = (p. Pak platí: existuje izomorfismus Vt-algeber p : U —> FX(V) takový, 40 že p o v = p. Důkaz. Protože fž-algebra U splňuje podmínku věty, pro íž-algebru FX(V) a zobrazení p : X —> FX(V) existuje homomorfismus íž-algeber p : U —> FX(V) splňující po u = p. Jen je třeba ukázat, že p je izomorfismus. Naopak, podle věty 8.4 pro íž-algebru U a zobrazení v : X —> U existuje homomorfismus íž-algeber ip : FX(V) —>• U splňující podmínku tpop = v. Pak homomorfismus poip : FX(V) —>• FX(V) splňuje poip o p = p o u = p. Rovněž identita na FX(V), tj. zobrazení ífx(v) '■ FX(V) —>• FX(V) splňující iFx(v)(a) = a Pr0 každé a G FX(V), je homomorfismem, pro který platí ífx(v) ° p = p- Protože dle věty 8.4 (pro íž-algebru FX(V) a zobrazení p : X —> FX(V)) je takový homomorfismus určen jednoznačně, platí potp = ífx(v)- Zcela analogicky se dokáže, že i/j o p je identita na U. To ale znamená, že i/j je inverzní zobrazení k p, a tedy p 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 Vt-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 libovolná 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 fž-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 CW. Ukážeme nyní, že také WCV. Zvolme libovolně íž-algebru A G W. Věta bude dokázána, ukážeme-li, že A e V. Uvažme volnou algebru FX(W) = FX{Q)/~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í (f) : X —> A volíme identitu, existuje homomorfismus íž-algeber cp : FX(W) —>• A splňující podmínku {x) = x pro všechny prvky x G X. Protože X = A, je zjevně

• Fy (V) tedy platí 7r(íi) = 7r(č2). 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 xi,..., xn ty prvky množiny X, které byly použity při tvorbě termů íi a í2; jsou tedy íi a t2 při tomto označení n-árními termy typu íž, tj. íi,í2 G Fn(íí). Dokažme nejprve, že rovnost íi = 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 bi,...,bn G B a ukažme, že (íi)b(&i, ■ ■ ■, K) = (^2)5(^1, ■ ■ ■, bn). Uvažme zobrazení (p : X —>• B takové, že pro každé m = 1,..., n platí (f)(xm) = bm a pro všechny ostatní prvky x E X různé od xi,..., xn dodefinujme (j){x) = b\ (ve speciálním případě n = 0 všechny prvky množiny X zobrazíme na nějaký libovolně zvolený prvek z fž-algebry B). Označme \i : X —> Fy (V-) vnoření generátorů do volné algebry Fx(v) třídy V. Podle definice je tedy /j,(x) = 7r(x) pro všechny prvky x E X. Podle věty 8.4 existuje homomorfismus íž-algeber cp : FX(V) —>• B splňující podmínku (p o \x = (f>. Označme tp = (p o 7r, je tedy tp : Fx(ft) —>• -B homomorfismus, přičemž pro všechny prvky x G AT platí ip(x) = (p(ir(x)) = (p(/ji(x)) = 4>(x). Ovšem Fn(íl) je podalgebra íž-algebry Fx(&), proto můžeme uvážit homomorfismus tp' : Fn(Q) —>• S, který je zúžením homomorfismu tp. Pro každé m = 1,... ,n platí tp'(xm) = ip(xm) = (Pixm) = bm- Z věty 7.4 plyne, že homomorfizmus vycházející z volné algebry Fn(Q) je jednoznačně určen svými obrazy na generátorech xi,..., xn, podle věty 7.4 tedy pro libovolný term t G Fn(íľ) je ip'(ť) = íb(6i, ... ,bn). Připomeňme, že 7r(íi) = 7r(č2); celkem tedy platí (íi)b(6i, ..., bn) = iP'ih) = iP(h) = (p(ir(h)) = (p(n(t2)) = = ^(í2) = ^'(í2) = (í2)b(&i,...A), a tedy rovnost íi = t2 patří do teorie T. Nechť v : Fx(£l) —>• FX(W) je projekce na faktoralgebru a v' : Fn(Q) —>• Fy(W) její zúžení na podalgebru Fn(íl). Podle věty 7.4 je homomorfismus v' jednoznačně určen svými obrazy na generátorech a pro každý term t G Fn(Q) tedy platí u'(ť) = tFx(w)(v'(xi),..., u'(xn)). Ovšem FX(W) je íž-algebra z variety W určené teorií T, rovnost íi = t2, o které jsme dokázali, že do teorie T patří, tedy platí i v FX(W), odkud plyne v(ti) = v'{ti) = (ti)Fx{W)(v'(xi),...,v'(xn)) = = (h)Fx(w)(^(xi), ■ ■ -,^{xn)) = v'{t2) = v{t2). 42 To znamená, že íi ~wfo, 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