ZÁKLADY UNIVERZÁLNÍ ALGEBRY Radan Kučera, 16. prosinec 2011 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 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 podobjekt. 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. Jedním z cílů 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í, 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 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é 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 G0 ? 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. 1 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 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á 0tice 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 2. Grupoid je totéž, co množina s jednou binární operací, je to tedy univerzální algebra typu, který má jeden binární operační symbol ·. 3. Každá grupa je univerzální algebra typu {·, −1 , 1}. Nikoliv naopak, ne každá univerzální algebra typu {·, −1 , 1} je grupou (aby byla grupou, musí splňovat jisté axiomy). 4. Každý okruh je univerzální algebra typu {+, ·, −, 0, 1}. 5. Každý svaz je univerzální algebra typu {∨, ∧}. 6. Každá Booleova algebra je univerzální algebra typu {∨, ∧, , 0, 1}. 7. Pro dané těleso T lze každý vektorový prostor nad tělesem T 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ě 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ť Ω 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ředchozí kapitoly dostáváme tyto podalgebry: 1. Podmnožina množiny. 2. Podgrupoid grupoidu. 3. Podgrupa grupy. 4. Podokruh okruhu. 5. Podsvaz svazu. 3 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. 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 i∈I Hi je podalgebra Ω-algebry A. Důkaz. Zvolme libovolně n-ární operační symbol f ∈ Ω a libovolně prvky a1, . . . , an ∈ i∈I 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) ∈ i∈I 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 H∈M 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 Ω, 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 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 Ω-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 Ω = ∅ 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. 4 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. 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 vektorů, což je jeden z nejdů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 Ω, ϕ : 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 samozř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ů. 5 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éž 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 univerzálních algeber známe z přednášky: složením dvou homomorfismů 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 Ω, ϕ : 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í symbol 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)), 6 což jsme měli dokázat. 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 budeme 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ézském součinu A × B definujeme novou univerzální algebru typu Ω, kterou 7 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)). Poznámka. Předchozí podmínka v případě nulárního operačního symbolu 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. A × B π1 {{wwwwwwwww π2 55GGGGGGGGG A B C ϕ ™™GGGGGGGGG ψ YYwwwwwwwww ρ yy       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 8 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)), 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: i∈I Ai = χ : I → i∈I Ai; ∀i ∈ I : χ(i) ∈ Ai . Pro libovolné j ∈ I definujeme j-tou projekci πj z kartézského součinu A = i∈I 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činem i∈∅ Ai množina všech zobrazení χ : ∅ → i∈∅ Ai. Protože i∈I 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}. 9 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} → A1∪A2 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 = i∈I 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 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 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á Ω. 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 = i∈I 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. 10 A πj 88MMMMMMMMMMMMM πj CCVVVVVVVVVVVVVVVVVVVVVVVVVVV . . . Aj . . . Aj · · · (j, j , . . . ∈ I) C ϕj VVqqqqqqqqqqqqq ϕj QQhhhhhhhhhhhhhhhhhhhhhhhhhhh ϕ yy       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). 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. 11 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 rozkladem 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 komutativní 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 zadat rozklad celý. Rozklad samozřejmě lze zadat pomocí jemu odpovídající ekvivalence. Protože později budeme chtít konstruovat na tomto rozkladu operace pomocí reprezentantů (viz definici na další straně), pro korektnost této konstrukce je nutné, aby odpovídající ekvivalence splňovala následující podmínku: Definice. Nechť A je univerzální algebra typu Ω, nechť ∼ je relace ekvivalence 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 ∈ A, b1, . . . , bn ∈ A platí a1 ∼ b1, . . . , an ∼ bn =⇒ fA(a1, . . . , an) ∼ fA(b1, . . . , bn). 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í operační symbol f ∈ Ω a prvky a1, . . . , an, b1, . . . , bn ∈ A tak, že a1 ∼ b1, . . . , 12 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ředpisem (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é 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 kongruence ∼, 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 13 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í homomorfismus Ω-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/∼ konstruovaný 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á kongruence na Ω-algebře A je jádrem vhodného homomorfismu Ω-algeber vycházejícího z Ω-algebry A. 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. Poznámka. Ukažme si nyní jednu zajímavou souvislost mezi kongruencemi a podalgebrami. Nechť ∼ je ekvivalence na nosné množině Ω-algebry A. Z definice je tedy ∼ ⊆ A×A podmnožinou nosné množiny součinu Ω-algeber A × A. Věta 4.4. Nechť ∼ je ekvivalence na nosné množině Ω-algebry A. Pak platí: ∼ je kongruence na Ω-algebře A, právě když je ∼ podalgebrou Ω-algebry A × A. 14 Důkaz. Předpokládejme, že ∼ je kongruence na Ω-algebře A. Abychom dokázali, že ∼ je podalgebrou Ω-algebry A × A, zvolme libovolný n-ární operační symbol f ∈ Ω a prvky (a1, b1), . . . , (an, bn) ∈ A×A. Jestliže všechny tyto uspořádané dvojice patří do ∼, pak platí a1 ∼ b1, . . . , an ∼ bn, což podle definice kongruence znamená fA(a1, . . . , an) ∼ fA(b1, . . . , bn). To ale není nic jiného, než že dvojice (fA(a1, . . . , an), fA(b1, . . . , bn)) je také prvkem ∼, což jsme měli dokázat. Předpokládejme nyní, že ∼ je podalgebrou Ω-algebry A × A. Zvolme libovolně n-ární operační symbol f ∈ Ω a prvky a1, . . . , an, b1, . . . , bn ∈ A takové, že a1 ∼ b1, . . . , an ∼ bn. Pak dvojice (a1, b1), . . . , (an, bn) jsou prvky podalgebry ∼ a z definice podalgebry plyne, že také fA×A((a1, b1), . . . , (an, bn)) = (fA(a1, . . . , an), fA(b1, . . . , bn)) patří do podalgebry ∼, neboli fA(a1, . . . , an) ∼ fA(b1, . . . , bn). Je tedy ∼ kongruence na Ω-algebře A. 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, 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á implikace 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 neprá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ře A uspořádaná inkluzí tvoří úplný svaz, jak plyne z věty 4.4 a druhého důsledku věty 2.1. Plyne to také z následující věty, uvědomíte-li si, že relace A × A je vždy kongruencí na Ω-algebře A. 15 Věta 4.5. 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 ≈. B π∼ 99NNNNNNNNNNNNN π CCWWWWWWWWWWWWWWWWWWWWWWWWWWWWW . . . A/∼ . . . A/ · · · (∼, , . . . ∈ K) A µ∼ UUppppppppppppp µ QQggggggggggggggggggggggggggggg ϕ yy       Důkaz. První tvrzení plyne z vět 4.4 a 2.1; je také důsledkem druhého tvrzení, 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.6. 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. ∼ = ≈). 16 A ϕ GG π 33CCCCCCCC B A/≈ ˜ϕ aaz z z z 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 π 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 17 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í homomorfismus, 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 homomorfismu ϕ ϕ(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í. 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 algebrá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: 18 • 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 Ω. Množinu všech termů typu Ω budeme značit symbolem F(Ω). Poznámka. Pokud by měl někdo pocit, že přes veškerou snahu o přesnost 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 x∨x 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. Poznámka. Předchozí definici by bylo možné napsat také takto: Nechť Ω je typ, pro každé nezáporné celé číslo n označme Ωn množinu všech operačních symbolů z Ω, které jsou n-ární. Položme M0 = Ω0 ∪ {x1, x2, x3, . . . } a pro každé i ∈ N označme Mi = Mi−1 ∪ {f(t1, . . . , tn); n ∈ N, f ∈ Ωn, t1, . . . , tn ∈ Mi−1}. Pak F(Ω) = ∞ i=0 Mi nazýváme množinou všech termů typu Ω, jejím prvkům říkáme termy typu Ω. Definice. Řekneme, že term t typu Ω je n-ární, jestliže se při jeho konstrukci 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 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 libovolné Ω-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. 19 • 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 n-árních termů t1, . . . , tk typu Ω, pak operaci tA určenou termem t definujeme 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), 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 20 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(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 symbolu 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. 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 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, idempotentnost obou operací, absorpční a distributivní zákony, identity spojené 21 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í 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 Ω-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 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 22 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 njtic 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 podalgebry tA(a1, . . . , an) = fA ∈ H. • Předpokládejme, že je term t složen pomocí k-árního operačního symbolu 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í 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 rovností typu Ω. Poznámka. Zdůrazněme, že v předchozí definici je užito symbolu = jen jako dalšího znaku abecedy, který oba termy spojil do jediného slova. V žádném případě tímto zápisem není myšleno, že jsou termy t1 a t2 stejné. 23 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 (x1·x2)·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í definice 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). 24 Poznámka pro ty, kteří znají predikátovou logiku. Uvažíme prediká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 všeobecných 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 {x1·x2 = 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 {(x1·x2)·x3 = x1·(x2·x3), x1·1 = x1, 1·x1 = 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. 25 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 = {(x1 ⊕ x2) ⊕ x3 = x1 ⊕ (x2 ⊕ x3), x1 ⊕ x2 = x2 ⊕ x1, x1 ⊕ o = x1, x1 ⊕ ( x1) = o}. 26 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ů. Č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} ∪ r∈R {r(x1 ⊕ x2) = r(x1) ⊕ r(x2)} ∪ ∪ r∈R s∈R {(r + s)(x1) = r(x1) ⊕ s(x1), (r · s)(x1) = r(s(x1))} . Tato teorie určuje varietu všech vektorových prostorů nad tělesem R. 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 homomorfismu 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. 27 • Je-li termem t proměnná xk, pak tA i tB jsou k-té projekce, a tedy ϕ(tA(a1, . . . , an)) = ϕ(ak) = tB(ϕ(a1), . . . , ϕ(an)). • 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 symbolu f ∈ Ω, kde k ≥ 1, z n-árních 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.6 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 . 28 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). 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 definová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 = i∈I 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 symbolu f ∈ Ω, kde k ≥ 1, z n-árních 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é termem platí tAi (χ1(i), . . . , χn(i)) = = fAi ((t1)Ai (χ1(i), . . . , χn(i)), . . . , (tk)Ai (χ1(i), . . . , χn(i))) = = fAi (ψ1(i), . . . , ψn(i)) 29 a také χ = tA(χ1, . . . , χn) = = fA((t1)A(χ1, . . . , χn), . . . , (tk)A(χ1, . . . , χn)) = = fA(ψ1, . . . , ψn), 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. Protože víme, že součinem prázdné množiny Ω-algeber je jednoprvková Ω-algebra a že jednoprvkové Ω-algebry patří do každé variety, můžeme se v následující větě omezit na součiny neprázdné množiny Ω-algeber. Věta 6.5. Nechť T je teorie typu Ω, V varieta Ω-algeber určená teorií T. Nechť pro libovolný prvek i neprázdné množiny I je dána univerzální algebra Ai typu Ω. Označme A součin těchto Ω-algeber, tj. A = i∈I 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á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 30 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činem dvou dvouprvkových svazů, které jsou řetězci, je čtyřprvkový svaz, který není řetězec. 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 {·, −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ů 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é Ω ⊇ {+, ·, −, 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. 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 následující kapitole. Věta 6.6. (Birkhoff) Nechť Ω je typ. Třída Ω-algeber je varieta, právě když splňuje všechny čtyři následující podmínky: • obsahuje všechny podalgebry všech svých Ω-algeber; • obsahuje obrazy všech svých Ω-algeber ve všech homomorfismech; • obsahuje součin libovolného neprázdného systému svých Ω-algeber; • obsahuje alespoň jednu jednoprvkovou Ω-algebru. Poznámka. Protože jediné zobrazení mezi jednoprvkovými Ω-algebrami je izomorfismus, z druhé podmínky plyne, že čtvrtou podmínku je možné psát i takto: „obsahuje všechny jednoprvkové Ω-algebry. Je také jasné, že třetí 31 a čtvrtou podmínku je možné nahradit podmínkou jedinou: „je uzavřená na libovolné součiny Ω-algeber. Již jsme dokázali ve větách 6.1, 6.3 a 6.5, že libovolná varieta Ω-algeber všechny 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 následující kapitole. Nechť V je třída Ω-algeber splňující všechny čtyř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 varietu Ω-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 následující kapitoly. 7. Volné algebry Poznámka. Zobecněme nyní pojem termu typu Ω takto: Definice. Nechť Ω je typ, X libovolná množina disjunktní s Ω. Pro každé nezáporné celé číslo n označme Ωn množinu všech operačních symbolů z Ω, které jsou n-ární. Položme M0 = Ω0 ∪ X a pro každé i ∈ N označme Mi = Mi−1 ∪ {f(t1, . . . , tn); n ∈ N, f ∈ Ωn, t1, . . . , tn ∈ Mi−1}. Pak FX(Ω) = ∞ i=0 Mi nazýváme množinou všech termů typu Ω nad množinou X, jejím prvkům říkáme termy typu Ω nad množinou X. Poznámka. Stejně jako dříve je výrazem f(t1, . . . , tn) nutno rozumět slovo nad abecedou, která obsahuje kromě prvků X ∪Ω také závorky a čárku. Termy typu Ω, které jsme užívali dosud, jsou tedy termy typu Ω nad množinou {x1, x2, . . . }, platí tedy F(Ω) = F{x1,x2,... }(Ω). Podobně F{x1,...,xn}(Ω) je množina všech n-árních termů typu Ω. V dalším textu nebudeme stále opakovat předpoklad X ∩ Ω = ∅, stejně striktně vzato jsme měli v předchozí definici navíc předpokládat, že množina X ∪ Ω neobsahuje závorky ani čárku. Kdykoli tedy dále napíšeme FX(Ω), mlčky předpokládáme, že zmíněné předpoklady jsou splněny. 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. 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 32 se do operačního symbolu pouze dosadí, čímž vznikne nový term, a to je výsledek. Znamená to, že každý prvek množiny FX(Ω), který nepatří do X, 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. Ω-algebra FX(Ω) je generovaná množinou X, tj. X = FX(Ω). Důkaz. Stačí ukázat inkluzi F(Ω) ⊆ X , tedy dokázat, že každý term t typu Ω nad množinou X patří do X . To je ale snadné indukcí vzhledem k definici termu: pro nulární symbol f typu Ω platí f = fF(Ω), což je prvek libovolné podalgebry, a 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 X je f(t1, . . . , tn) = fF(Ω)(t1, . . . , tn) ∈ X dle definice podalgebry. Definice. Ω-algebra FX(Ω) z předchozí definice a věty se nazývá volná algebra typu Ω generovaná množinou X. Poznámka. V následujícím textu budeme pracovat s diagramy, v nichž některé šipky budou znázorňovat homomorfismy Ω-algeber, kdežto jiné budou pouze zobrazení. Pro snadnější zorientování v diagramu budeme zobrazení, která nejsou homomorfismy, znázorňovat vlnovkou se šipkou GGGoGoGo , kdežto homomorfismy budeme znázorňovat obyčejnou šipkou GG . Stále platí, že nepřerušované šipky jsou dány, kdežto přerušovaná je právě ta šipka, jejíž jednoznačnou existenci věta tvrdí. Kupříkladu tedy inkluze X ⊆ FX(Ω) nám dává zobrazení X GGGoGoGo FX(Ω) . Věta 7.2. Nechť Ω je typ, X množina. Dále nechť A je libovolná Ωalgebra a φ : X → A libovolné zobrazení. Pak existuje jediný homomorfismus Ω-algeber ϕ : FX(Ω) → A splňující podmínku ϕ(x) = φ(x) pro všechny prvky x ∈ X. X ⊆ {{ {Y {Y {Y {Y {Y φ 111•1•1•1•1• FX(Ω) ϕ GG_______ A 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 ∈ 33 Ω 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)). 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. Důsledek. Nechť Ω je typ, n nezáporné celé číslo, X = {x1, . . . , xn} je n-prvková množina proměnných. Dále nechť A je libovolná Ω-algebra a a1, . . . , an ∈ A libovolné. Nechť φ : X → A je zobrazení určené předpisem φ(xi) = ai pro každé i = 1, . . . , n. Pak dle předchozí věty jediný homomorfismus Ω-algeber ϕ : FX(Ω) → A určený zobrazením φ, tj. splňující podmínku ϕ(xi) = ai pro všechny i = 1, . . . , n, přiřadí libovolnému termu t ∈ FX(Ω) hodnotu operace, kterou tento term určuje, na n-tici (a1, . . . , an), tj. platí ϕ(t) = tA(a1, . . . , an). Důkaz. Stačí porovnat konstrukci z důkazu předchozí věty s definicí nární operace určené termem z kapitoly 5. Poznámka. Naším dalším cílem je nalézt volné Ω-algebry v každé varietě Ω-algeber. Volná Ω-algebra FX(Ω) totiž splňuje pouze triviální rovnosti, leží proto jen ve varietě všech Ω-algeber (s výjimkou některých velmi speciálních případů, kupříkladu pro Ω = X = ∅ je FX(Ω) = ∅). Budeme tedy pro danou teorii T typu Ω konstruovat Ω-algebru generovanou množinou X, 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. 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. 34 Definice. Nechť V je třída Ω-algeber. O třídě V řekneme, že je uzavřená, právě když splňuje následující podmínky z Birkhoffovy věty: • obsahuje všechny podalgebry všech svých Ω-algeber; • obsahuje obrazy všech svých Ω-algeber ve všech homomorfismech; • obsahuje součin libovolného neprázdného systému svých Ω-algeber; • obsahuje alespoň jednu jednoprvkovou Ω-algebru. 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 izomorfní 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: ∼V je průnikem všech kongruencí ∼ na Ω-algebře FX(Ω) takových, že FX(Ω)/∼ patří do třídy V . Poznámka. 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 . Libovolná uzavřená třída Ω-algeber musí obsahovat jednoprvkovou algebru. 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 ekvivalentní, a tedy příslušná faktoralgebra je jednoprvková. Věta 7.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 kongruence ∼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.5. Podle druhého tvrzení věty 4.5 existuje jediný homomorfismus Ω-algeber ϕ : FX(Ω) → ∼∈K FX(Ω)/∼, 35 pro který komutuje následující diagram: ∼∈K (FX(Ω)/ ∼) π 99NNNNNNNNNNN π∼= CCWWWWWWWWWWWWWWWWWWWWWWWWWWWW · · · FX(Ω)/ . . . FX(Ω)/∼= · · · ( , ∼=, . . . ∈ K). FX(Ω) µ TTmmmmmmmmmmmmm µ PPfffffffffffffffffffffffffffffffff ϕ yy       Přitom jádrem ϕ je průnik všech kongruencí ∼ ∈ K, tedy kongruence ∼V . Podle důsledku věty 4.6 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 7.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 ). Poznámka. Pokud třída V obsahuje nějakou Ω-algebru, která není jednoprvková nebo prázdná, lze snadno odvodit z následující věty 7.4, že zobrazení µ je injektivní. Věta 7.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, π : FX(Ω) → FX(V ) je projekce na faktorovou algebru a µ : 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 ψ ◦ µ = φ. X ⊆ yy yW yW yW yW yW yW φ 555™5™5™5™5™5™ µ  y y y FX(Ω) π GG FX(V ) ψ GG___ A Důkaz. Dokažme nejprve existenci homomorfismu ψ. Podle věty 7.2 existuje jediný homomorfismus Ω-algeber ϕ : FX(Ω) → A splňující podmínku 36 ϕ(x) = φ(x) pro všechny prvky x ∈ X: X ⊆ yy yW yW yW yW yW yW φ 555™5™5™5™5™5™ µ  y y y FX(Ω) π GG ϕ VVFX(V ) ψ GG___ A 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 homomorfismu ϕ. Podle důsledku věty 4.6 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.6 existuje 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 homomorfismus Ω-algeber ψ : FX(V ) → A také splňuje podmínku ψ ◦ µ = φ. Pak ψ (π(x)) = φ(x) pro všechny prvky x ∈ X a ϕ = ψ ◦ π splňuje podmínku věty 7.2. Protože homomorfismus splňující tuto podmínku je jediný, dostáváme ϕ = ϕ. Tedy ψ ◦ π = ˜ϕ ◦ π, z jednoznačnosti z věty 4.6 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 charakterizuje Ω-algebru FX(V ), určuje ji totiž jednoznačně až na izomorfismus. To nám umožňuje konstruovat volné algebry jinak než z definice: intuitivně odhadnout, jak asi vypadá, a pak ukázat, že je to opravdu ona, a to tak, že dokážeme, že splňuje tuto charakterizační vlastnost. Věta 7.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 ψ : FX(V ) → U takový, že ψ ◦ µ = ν. X ν ~~ ~b ~b ~b ~b φ 222–2–2–2– U ρ GG_______ A =⇒ X µ {{ {Y {Y {Y {Y {Y ν 111•1•1•1•1• FX(V ) 1  ψ GG GG_______ U 37 Důkaz. Podle věty 7.4 pro Ω-algebru U a zobrazení ν : X → U existuje homomorfismus Ω-algeber ψ : FX(V ) → U splňující podmínku ψ◦µ = ν. Jen je třeba ukázat, že ψ je izomorfismus. Naopak, 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í ρ ◦ ν = µ. X µ ÐÐ Ðd Ðd Ðd Ðd Ðd ν 111•1•1•1•1• ιFX (V ) `` FX(V ) ψ CC U ρ kk ιU gg Pak homomorfismus ρ ◦ ψ : 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 7.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. Věta 7.6. Nechť Ω je typ, n nezáporné celé číslo, X = {x1, . . . , xn} je nprvková množina proměnných. Nechť V je uzavřená třída Ω-algeber a nechť π : FX(Ω) → FX(V ) je projekce na volnou algebru třídy V generovanou množinou X. Pak pro libovolné n-ární termy t1, t2 typu Ω, tj. pro libovolné t1, t2 ∈ FX(Ω), jsou následující podmínky ekvivalentní: (i) π(t1) = π(t2); (ii) rovnost t1 = t2 platí v Ω-algebře FX(V ); (iii) rovnost t1 = t2 platí v každé Ω-algebře A ∈ V . Důkaz. Protože FX(V ) ∈ V , plyne z podmínky (iii) podmínka (ii). Podmínka (ii) říká, že (t1)FX (V ) a (t2)FX (V ) jsou stejné n-ární operace na Ω-algebře FX(V ). Ovšem π je homomorfismus, a tedy pro každé i = 1, 2 platí podle věty 6.2 (ti)FX (V )(π(x1), . . . , π(xn)) = π (ti)FX (Ω)(x1, . . . , xn) = π(ti) podle definice operací na Ω-algebře FX(Ω), odkud plyne podmínka (i). Předpokládejme nyní platnost podmínky (i) a zvolme libovolně A ∈ V a libovolné a1, . . . , an ∈ A. Abychom dokázali podmínku (iii), musíme dokázat, že (t1)A(a1, . . . , an) = (t2)A(a1, . . . , an). Definujme zobrazení φ : X → A 38 předpisem φ(xj) = aj pro každé j = 1, . . . , n. Podle věty 7.4 máme komutativní diagram X ⊆ yy yW yW yW yW yW yW φ 555™5™5™5™5™5™ µ  y y y FX(Ω) π GG ϕ VVFX(V ) ψ GG A Podle důsledku věty 7.2 pro libovolný t ∈ FX(Ω) platí ϕ(t) = tA(a1, . . . , an). Z podmínky (i) tedy plyne (t1)A(a1, . . . , an) = ϕ(t1) = ψ(π(t1)) = ψ(π(t2)) = ϕ(t2) = (t2)A(a1, . . . , an). Poznámka. V kapitole 6 jsme pro každou teorii typu Ω definovali varietu, kterou tato teorie určuje a dokázali, že tato varieta je uzavřenou třídou Ωalgeber. Nyní naopak každé třídě Ω-algeber přiřadíme teorii, kterou tato třída určuje: Definice. Nechť V je třída Ω-algeber. Teorii určenou třídou V definujeme jako množinu všech rovností platících v každé Ω-algebře A ∈ V . Poznámka. Přímo z definic plyne, že je-li T teorie typu Ω, V varieta určená teorií T a T teorie určená varietou V , pak platí T ⊆ T . Teorii T lze pak chápat jako množinu všech důsledků rovností z teorie T. Podobně je-li V libovolná třída Ω-algeber, T teorie určená třídou V a V varieta určená teorií T, pak V ⊆ V . Zřejmě je V nejmenší varietou obsahující třídu V . Důsledek. Nechť V1 a V2 jsou uzavřené třídy Ω-algeber určující stejnou teorii T. Nechť n je libovolné nezáporné celé číslo a X = {x1, . . . , xn}. Pak platí FX(V1) = FX(V2). Důkaz. Nechť π1 : FX(Ω) → FX(V1) a π2 : FX(Ω) → FX(V2) jsou projekce na volné algebry tříd V1 a V2. Podle věty 7.6 pro libovolné t1, t2 ∈ FX(Ω) platí π1(t1) = π1(t2) právě tehdy, když rovnost t1 = t2 patří do teorie T, což podle této věty platí právě tehdy, když π2(t1) = π2(t2). Obě projekce π1 a π2 tedy mají stejná jádra, a proto FX(V1) = FX(V2). Poznámka. Následující věta zobecní předchozí důsledek o volných algebrách s konečně mnoha generátory na případ volných algeber s libovolnou množinou generátorů: Věta 7.7. Nechť V1 a V2 jsou uzavřené třídy Ω-algeber určující stejnou teorii T. Pak pro libovolnou množinu proměnných X platí FX(V1) = FX(V2). Důkaz. Vzhledem k předchozímu důsledku se stačí omezit na případ, kdy je X nekonečná množina. Nechť opět π1 : FX(Ω) → FX(V1) a π2 : FX(Ω) → FX(V2) jsou projekce na volné algebry tříd V1 a V2. Důkaz povedeme sporem, 39 budeme předpokládat, že FX(V1) = FX(V2). Pak tedy π1 a π2 mají různá jádra. Bez újmy na obecnosti můžeme tedy předpokládat, že existují t1, t2 ∈ FX(Ω) splňující π1(t1) = π1(t2) a π2(t1) = π2(t2). V termech t1 a t2 vystupuje jen konečně mnoho generátorů. Zvolme neprázdnou konečnou množinu Y ⊆ X tak, že každá proměnná vystupující v alespoň jednom z termů t1 a t2 patří do Y . Dále zvolme libovolné zobrazení µ : X → Y takové, že pro každé y ∈ Y platí µ(y) = y (prvky X nepatřící do Y zobrazíme zcela libovolně. Máme tedy komutativní diagram Y ⊆ GGGoGoGo idY @@Su Rt Qs Pr Iq Hp Go Fn Em Dl Ck Bj Ai X µ GGGoGoGo Y Podle předchozího důsledku platí FY (V1) = FY (V2), označme π : FY (Ω) → FY (V1) projekci na volnou algebru. Pro každé i = 1, 2 doplníme předchozí diagram takto Y ⊆  y y y ⊆ GGGoGoGoGoGoGo idY BBQs Qs Pr Iq Hp Hp Go Fn Fn Em Dl Ck Ck X ⊆  y y y µ GGGoGoGoGoGoGo Y ⊆  y y y FY (Ω) ϕ GG___ π  FX(Ω) πi  FY (Ω) π  FY (Vi) ϕi GG___ idFY (Vi) QQY \ _ b e FX(Vi) ψi GG___ FY (Vi) Existenci homomorfismu ϕ zaručuje věta 7.2 pro zobrazení Y → FX(Ω), je však zřejmé, že je ϕ zobrazení inkluze. Existenci homomorfismů ϕi a ψi zaručuje věta 7.4 pro zobrazení Y → FX(Vi) a X → FY (Vi). Jednoznačnost z věty 7.2 pro zobrazení Y → FX(Vi) zaručuje, že „dolní čtverec je komutativní, tj. že platí πi ◦ ϕ = ϕi ◦ π. Jednoznačnost z věty 7.4 pro „diagonální zobrazení Y → FY (Vi) zaručuje, že „dolní trojúhelník je komutativní, tj. že platí ψi ◦ ϕi = idFY (Vi). Odtud plyne, že obě zobrazení ϕ1 a ϕ2 jsou injektivní. Dolní komutativní čtverce pro i = 1 i i = 2 lze najednou nakreslit do následujícího diagramu: FX(Vi) FY (V1) = FY (V2) C ϕ1 VVrrrrrrrrrr s ϕ2 88LLLLLLLLLL FY (Ω) ϕ GGπoo FX(Ω) π1 eeKKKKKKKKK π2 yysssssssss FX(Vi) 40 Z předpokladů víme, že t1, t2 ∈ FY (Ω) a že ϕ(t1) = t1 a ϕ(t2) = t2. Dále platí ϕ2(π(t1)) = π2(ϕ(t1)) = π2(t1) = π2(t2) = π2(ϕ(t2)) = ϕ2(π(t2)), odkud π(t1) = π(t2). Protože ϕ1 je injektivní, dostáváme ϕ1(π(t1)) = ϕ1(π(t2)), tedy π1(t1) = π1(ϕ(t1)) = ϕ1(π(t1)) = ϕ1(π(t2)) = π1(ϕ(t2)) = π1(t2), což je spor a věta je dokázána. Věta 7.8. Nechť V1 a V2 jsou uzavřené třídy Ω-algeber určující stejnou teorii T. Pak V1 = V2. Důkaz. Nechť A ∈ V1 je libovolná. Označme X nosnou množinu Ωalgebry A. Máme tedy zobrazení idX : X → A. Věta 7.4 nám dá homomorfismus ψ : FX(V1) → A splňující ψ ◦ µ = idX, kde µ : X → FX(V1) je vnoření generátorů do volné algebry FX(V1). Protože idX je surjektivní, je také ψ surjektivní. Podle vět 7.7 a 7.3 platí FX(V1) = FX(V2) ∈ V2. Protože třída V2 je uzavřená, plyne odtud, že A, jakožto obraz algebry FX(V1) v homomorfismu ψ, patří do V2. Dokázali jsme inkluzi V1 ⊆ V2, opačná inkluze plyne ze symetrie. Poznámka. Nyní již můžeme dokončit důkaz Birkhoffovy věty naznačený na konci kapitoly 6. Věta 6.6. (Birkhoff) Nechť Ω je typ. Třída Ω-algeber je varieta, právě když je uzavřená, neboli splňuje všechny čtyři následující podmínky: • obsahuje všechny podalgebry všech svých Ω-algeber; • obsahuje obrazy všech svých Ω-algeber ve všech homomorfismech; • obsahuje součin libovolného neprázdného systému svých Ω-algeber; • obsahuje alespoň jednu jednoprvkovou Ω-algebru. Důkaz. Víme, že každá varieta je uzavřená třída, a potřebujeme dokázat, že také naopak každá uzavřená třída je varietou. Nechť V je libovolná uzavřená třída Ω-algeber, T teorie, kterou určuje třída V . Nechť dále je V varieta Ω-algeber určená teorií T a T teorie, kterou určuje varieta V . Budeme hotovi, ukážeme-li V = V . Podle věty 7.8 bude stačit, dokážeme-li, že platí T = T . V poznámce za definicí na straně 39 jsme si rozmýšleli, že zřejmě platí T ⊆ T a V ⊆ V . Protože T, resp. T je množina všech rovností platných v každé Ω-algebře patřící do V , resp. V , z inkluze V ⊆ V dostáváme T ⊇ T . Celkem tedy T = T , což bylo třeba dokázat. 41