Teorie a variety 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). Pro pokročilejší: souvislost s predikátovou logikou Právě zavedený pojem „teorie typu Ω je speciální případ teorie v predikátové logice v jazyce s operačními symboly z Ω. 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 Ω-algeber určená teorií T je pak právě třída všech modelů takto vzniklé teorie predikátové logiky. Varieta grup, varieta komutativních grup 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}. Varieta okruhů 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. Varieta svazů Příklad. Uvažme typ Ω = {∨, ∧}, kde oba operační symboly jsou binární. 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ů. Varieta vektorových prostorů nad tělesem (R, +, ·) Příklad. 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}. Tato teorie (uvažovaná jako teorie typu {⊕, , o}) určuje varietu všech komutativních grup. 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. K teorii T přidáme 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. Variety jsou uzavřené na podalgebry algeber Poznámka. Viděli jsme, že třída všech grup, třída všech okruhů, třída všech vektorových prostorů nad tělesem R jsou příklady variet. Následující věta proto zobecňuje trvrzení, se kterými jsme se setkávali opakovaně: podgrupa grupy je sama grupou, podokruh okruhu je sám okruhem, podprostor vektorového prostoru nad tělesem R je vektorový prostor nad tělesem R atd. Věta. 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. 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 . Homomorfismy zachovávají operace určené termy Věta. 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 indukcí vzhledem ke složitosti termu t. Je-li termem t proměnná xk nebo nulární operační symbol f ∈ Ω, pak věta platí. Nechť pro n-ární termy t1, . . . , tk typu Ω byla věta dokázána a term t = f (t1, . . . , tk) pro k-ární operační symbol f ∈ Ω, k ∈ N. Pak ϕ(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. Variety jsou uzavřené na obrazy algeber v homomorfismech Věta. Nechť T je teorie typu Ω, V varieta Ω-algeber určená teorií T. Nechť A, B jsou Ω-algebry, ϕ : A → B surjektivní homomorfismus Ω-algeber. Pak platí: je-li A ∈ V , pak též B ∈ V . Důkaz. Nechť t1 = t2 je rovnost z teorie T, přičemž že oba termy t1, t2 jsou n-ární. Protože A ∈ V , platí tato rovnost v Ω-algebře A. 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 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 . Důsledek. Variety jsou uzavřené na faktoralgebry. Operace určené termy se v součinu počítají po složkách Věta. 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 indukcí vzhledem ke složitosti termu t. Je-li termem t proměnná xk nebo nulární operační symbol f ∈ Ω, pak věta platí. Nechť pro n-ární termy t1, . . . , tk typu Ω byla věta dokázána a term t = f (t1, . . . , tk) pro k-ární operační symbol f ∈ Ω, k ∈ N. Pak tA(χ1, . . . , χn) (i) = fA((t1)A(χ1, . . . , χn), . . . , (tk)A(χ1, . . . , χn)) (i) = = fAi (t1)A(χ1, . . . , χn) (i), . . . , (tk)A(χ1, . . . , χn) (i) = = fAi (t1)Ai (χ1(i), . . . , χn(i)), . . . , (tk)Ai (χ1(i), . . . , χn(i)) = = tAi (χ1(i), . . . , χn(i)), což se mělo dokázat. Variety jsou uzavřené na součiny algeber Věta. Nechť T je teorie typu Ω, V varieta Ω-algeber určená teorií T. Nechť pro libovolný prvek i množiny I je dána univerzální algebra Ai typu Ω. Označme A součin těchto Ω-algeber, tj. A = i∈I Ai . Pak platí: jestliže pro každé i ∈ I je Ai ∈ V , pak též A ∈ V . Důkaz. Nechť t1 = t2 je rovnost z teorie T, přičemž že oba termy t1, t2 jsou n-ární. Protože pro každé i ∈ I je Ai ∈ V , platí tato rovnost v Ω-algebře Ai . Pro libovolné χ1, . . . , χn ∈ A dokažme (t1)A(χ1, . . . , χn) = (t2)A(χ1, . . . , χn). Stačí ověřit, že pro každé i ∈ I je (t1)A(χ1, . . . , χn) (i) = (t1)Ai (χ1(i), . . . , χn(i)) = = (t2)Ai (χ1(i), . . . , χn(i)) = (t2)A(χ1, . . . , χn) (i), kde prostřední rovnost plyne z Ai ∈ V , zbylé dvě z předchozí věty. Příklady použití předchozích vět Příklad. Ani třída všech oborů integrity ani třída všech těles není varietou 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. To 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). Příklad. Třída všech svazů, které jsou řetězci, netvoří varietu univerzálních algeber typu {∨, ∧}, neboť součinem dvou dvouprvkových řetězců je čtyřprvkový svaz, který není řetězec. Příklad. Třída všech konečných grupoidů netvoří varietu univerzálních algeber typu {·}. Součinem netriviálních konečných grupoidů přes nekonečnou množinu indexů je totiž nekonečný grupoid. Ještě jeden příklad použití předchozích vět 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, například (N, +) je podgrupoid grupy (Z, +). 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é Ω ⊇ {∨, ∧}. Birkhoffova věta 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ěta (Birkhoff). Nechť Ω je typ. Třída Ω-algeber je varieta, právě když splňuje všechny tř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 surjektivních homomorfismech; obsahuje součin libovolného (i prázdného) systému svých Ω-algeber. Poznámka. Předchozí věty dokazují jeden směr (každá varieta splňuje všechny tři podmínky). Pro kompletní důkaz budeme muset zavést a studovat tzv. volné algebry. Poznámka. Třetí podmínku Birkhoffovy věty je možné ekvivalentně formulovat takto: „obsahuje součin libovolného neprázdného systému svých Ω-algeber a současně obsahuje alespoň jednu jednoprvkovou Ω-algebru. Definice termu typu Ω nad množinou X 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 se nazývá množina všech termů typu Ω nad množinou X, jejím prvkům říkáme termy typu Ω nad množinou X. Poznámka. Výrazem f (t1, . . . , tn) je 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 ∩ Ω = ∅, striktně vzato jsme měli v definici také 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. Množina termů FX (Ω) tvoří Ω-algebru Definice. Nechť Ω je typ, X množina. Na množině FX (Ω) definujeme Ω-algebru 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 každé 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. Dá se říci, že se vlastně nepočítají. Termy 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á. Volná algebra typu Ω generovaná množinou X Definice. Ω-algebra FX (Ω) z předchozí definice se nazývá volná algebra typu Ω generovaná množinou X. Poznámka. Abychom ospravedlnili užitý název, je třeba dokázat následující větu. Připomeňme, že symbolem X značíme podalgebru generovanou množinou X. Věta. Ω-algebra FX (Ω) je generovaná množinou X, tj. platí X = FX (Ω). Důkaz. Stačí ukázat inkluzi FX (Ω) ⊆ X , tedy dokázat, že každý term t typu Ω nad množinou X patří do X . To provedeme indukcí vzhledem ke složitosti termu. Pro nulární symbol f typu Ω platí f = fFX (Ω), což je prvek libovolné podalgebry. Také každá proměnná, tedy prvek množiny X jistě patří do X . 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) = fFX (Ω)(t1, . . . , tn) ∈ X dle definice podalgebry. Dohoda o diagramech Poznámka. Budeme pracovat s diagramy, v nichž budou vystupovat Ω-algebry i množiny. Proto některé šipky v takovém diagramu mohou odpovídat homomorfismům Ω-algeber, kdežto jiné budou odpovídat pouze zobrazením. Stále bude platit, že nepřerušované šipky odpovídají daným zobrazením, kdežto přerušovaná právě tomu zobrazení, jehož jednoznačnou existenci věta tvrdí. Fráze „diagram komutuje znamená, že kdykoli se z jednoho místa diagramu lze dostat do jiného dvěma cestami respektujícími orientaci šipek, pak jsou stejná obě zobrazení vzniklá poskládáním odpovídajících zobrazení podle těchto cest. Pro snadnější pochopení diagramu zavedeme tuto dohodu: obyčejná šipka // znázorňuje homomorfismus Ω-algeber, vlnící se šipka // znázorňuje zobrazení, které homomorfismus není. Například inkluze X ⊆ FX (Ω) dává zobrazení X → FX (Ω), které v diagramu znázorníme takto: X // FX (Ω) . Charakterizace volnosti pomocí homomorfismů Věta. 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 ⊆ || α  FX (Ω) ϕ // A Důkaz. Libovolný prvek množiny FX (Ω) je term nad množinou X. Definujme zobrazení ϕ : FX (Ω) → A indukcí vzhledem k definici termu: Pro libovolný prvek x ∈ X klademe ϕ(x) = α(x). Aby zobrazení ϕ : FX (Ω) → A mohlo být homomorfismus Ω-algeber, je třeba pro libovolný nulární operační symbol f ∈ Ω položit ϕ(f ) = fA. Pro libovolné přirozené číslo n uvažme nyní term t = f (t1, . . . , tn) typu Ω nad množinou X, který vznikl z n-árního operačního symbolu f ∈ Ω a termů t1, . . . , tn typu Ω nad množinou X. Aby zobrazení ϕ : FX (Ω) → A mohlo být homomorfismus Ω-algeber, je třeba, aby ϕ(t) = ϕ(f (t1, . . . , tn)) = ϕ(fFX (Ω)(t1, . . . , tn)) = = fA(ϕ(t1), . . . , ϕ(tn)). Klademe proto ϕ(t) = fA(ϕ(t1), . . . , ϕ(tn)). 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. Je také jasné, že ϕ je skutečně homomorfismem Ω-algeber. Zajistili jsme to právě definicemi ve druhém a třetím bodu indukce.