Variety Ω-algeber zpravidla obsahují nekonečné Ω-algebry Poznámka. Je jasné, že pro libovolný typ Ω platí, že pokud varieta Ω-algeber obsahuje alespoň jednu alespoň dvojprvkovou Ω-algebru, musí obsahovat také nekonečné Ω-algebry (například součin nekonečně mnoha kopií této Ω-algebry). Proto s výjimkou variety všech nejvýše jednoprvkových Ω-algeber, tedy variety dané teorií {x1 = x2}, každá varieta obsahuje také nekonečné Ω-algebry. Připomeňme si Birkhoffovu větu charakterizující variety: Věta (Birkhoff). Nechť Ω je typ. Třída Ω-algeber V 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. 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ě V = ∅, V = {∅}. Pojem pseudovariety Poznámka. Vhodnou modifikaci pojmu varieta pro třídy konečných Ω-algeber podává následující definice: Definice. Nechť Ω je typ. Třída Ω-algeber V se nazývá pseudovarieta, jestliže obsahuje pouze konečné Ω-algebry, obsahuje alespoň jednu neprázdnou Ω-algebru a 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; pro libovolné A, B ∈ V platí A × B ∈ V . Příklad. Je-li W libovolná varieta Ω-algeber, pak třída W F všech konečných Ω-algeber patřících do W tvoří pseudovarietu. Definice. Pseudovariety Ω-algeber, které jsou rovny třídě W F všech konečných Ω-algeber vhodné variety Ω-algeber W , se nazývají ekvacionální. Poznámka. Existují pseudovariety, které ekvacionální nejsou. Příklad pseudovariety, která není ekvacionální Příklad. Nechť Ω = {·}, kde · je binární operační symbol, Ω-algebry jsou tedy grupoidy. Označme V třídu všech Ω-algeber, které jsou konečné grupy, spolu s prázdným grupoidem. Protože libovolný prvek a konečné grupy má konečný řád, mezi mocninami prvku a s přirozeným exponentem najdeme a−1 i 1. Proto každý neprázdný podgrupoid konečné grupy je konečná grupa. Zřejmě také každý homomorfní obraz konečné grupy je konečná grupa, součinem dvou konečných grup je konečná grupa. Tedy V je pseudovarieta. Ukažme sporem, že V není třídou W F všech konečných Ω-algeber žádné variety W . Předpokládejme, že varieta Ω-algeber W ⊇ V . Pro libovolné n ∈ N obsahuje V cyklickou grupu řádu n, proto W obsahuje jejich součin přes všechna n ∈ N, což je grupa obsahující prvky nekonečného řádu, například prvek g mající v každé složce generátor příslušné grupy. Pak ale W obsahuje i podgrupoid G tohoto součinu, generovaný prvkem g, totiž G = {gn; n ∈ N}. Rozklad {g}, {g2, g3, . . . } zadává kongruenci ∼ na grupoidu G, proto W obsahuje konečný grupoid G/ ∼ nepatřící do V . Některé vlastnosti variet a pseudovariet Věta. Nechť Ω je typ, I neprázdná množina taková, že pro každé i ∈ I je dána varieta Ω-algeber Vi . Pak i∈I Vi je varieta Ω-algeber. Důkaz. Je-li Ti teorie určující varietu Vi , pak sjednocení i∈I Ti je teorie určující i∈I Vi . Věta. Nechť Ω je typ, I neprázdná množina taková, že pro každé i ∈ I je dána pseudovarieta Ω-algeber Vi . Pak i∈I Vi je pseudovarieta Ω-algeber. Předpokládejme navíc, že náš systém pseudovariet je usměrněný, tj. pro každé i, j ∈ I existuje k ∈ I tak, že Vi ∪ Vj ⊆ Vk. Pak i∈I Vi je pseudovarieta Ω-algeber. Důkaz je zřejmý, stačí užít definici pseudovariety; pro důkaz toho, že i∈I Vi s každými svými dvěma Ω-algebrami obsahuje i jejich součin, je třeba využít usměrněnost systému Vi , i ∈ I. Varieta a pseudovarieta generované množinou Ω-algeber Poznámka. Vzhledem k tomu, že systém všech Ω-algeber tvoří varietu a systém všech konečných Ω-algeber tvoří pseudovarietu, předchozí věty umožňují následující definice. Definice. Je-li M libovolná množina Ω-algeber, varietu Var(M) generovanou množinou M definujeme jako průnik všech variet Ω-algeber obsahujících každou Ω-algebru z množiny M. Je-li M = {A} jednoprvková, píšeme Var(A) místo Var({A}). Definice. Je-li M libovolná množina konečných Ω-algeber, pseudovarietu Psvar(M) generovanou množinou M definujeme jako průnik všech pseudovariet Ω-algeber obsahujících každou Ω-algebru z množiny M. Je-li M = {A} jednoprvková, píšeme Psvar(A) místo Psvar({A}). Poznámka. Za chvíli ukážeme, že pseudovarieta Psvar(A) generovaná jedinou konečnou Ω-algebrou A je vždy ekvacionální. Za tím účelem však budeme nejprve zkoumat varietu Var(A). Varieta Var(A) pro konečnou Ω-algebru A Věta. Nechť Ω je typ, A konečná Ω-algebra, X = {x1, . . . , xn} konečná množina. Pak platí, že volná algebra FX (Var(A)) variety Var(A) generovaná množinou X je izomorfní s vhodnou podalgebrou součinu konečně mnoha kopií Ω-algebry A, a tedy FX (Var(A)) je konečná. Důkaz. Var(A) je nejmenší varieta obsahující A, proto je určena teorií obsahující právě všechny rovnosti platné v Ω-algebře A. Podle věty o rovnostech ve volných Ω-algebrách víme, že FX (Var(A)) = FX (Ω)/ ∼, přičemž pro libovolné termy t1, t2 ∈ FX (Ω) platí t1 ∼ t2, právě když rovnost t1 = t2 platí v každé Ω-algebře ve Var(A), tj. platí v A. Z univerzální vlastnosti FX (Ω) víme, že pro každé zobrazení f : X → A existuje (jediný) homomorfismus f : FX (Ω) → A tak, že f |X = f . Rovnost t1 = t2 platí v A, právě když oba termy určují na A tutéž operaci, což podle věty popisující homomorfismus f pro konečnou X nastane, právě když pro každé f : X → A platí f (t1) = f (t2). Proto ∼ = f ∈I ker f , kde I je množina všech zobrazení f : X → A. Označme B = f ∈I A. Podle věty o součinu Ω-algeber existuje jediný homomorfismus ϕ : FX (Ω) → B tak, že komutuje diagram B πf '' πg ++. . . A . . . A · · · (f , g, . . . ∈ I) FX (Ω) f 77 g 33ϕ OO Pro libovolné t ∈ FX (Ω) platí ϕ(t) = (f (t))f ∈I . Proto ker ϕ = f ∈I ker f = ∼. Podle hlavní věty o faktorových algebrách FX (Var(A)) = FX (Ω)/∼ ∼= ϕ(FX (Ω)), což je podalgebra Ω-algebry B = f ∈I A. Věta plyne z toho, že I je konečná množina. Pro konečnou Ω-algebru A je Psvar(A) ekvacionální Definice. Varieta se nazývá lokálně konečná, jestliže každá její Ω-algebra, která má konečnou množinu generátorů, je konečná. Věta. Nechť Ω je typ, A libovolná konečná Ω-algebra. Pak platí: Psvar(A) = Var(A)F , a tedy Psvar(A) je ekvacionální. Varieta Var(A) je lokálně konečná. Důkaz. Zřejmě je Var(A)F pseudovarieta obsahující A, a tedy Psvar(A) ⊆ Var(A)F . Ukažme opačnou inkluzi: Nechť B je libovolná konečná Ω-algebra z Var(A). Označme X nosnou množinu Ω-algebry B. Pak idX : X → B je surjektivní zobrazení, a proto onen jediný homomorfismus FX (Var(A)) → B, který id určuje, je surjektivní. Podle předchozí věty je FX (Var(A)) izomorfní s vhodnou podalgebrou součinu konečně mnoha kopií Ω-algebry A, a tedy FX (Var(A)) ∈ Psvar(A). Odtud B ∈ Psvar(A). Proto Var(A)F ⊆ Psvar(A). Druhá část věty se dokáže podobně: pro libovolnou Ω-algebru B ∈ Var(A) s konečnou množinou generátorů X vezmeme zobrazení inkluze X → B a postupujeme analogicky. Systém reprezentantů konečných Ω-algeber Poznámka. Zvolme pevně přirozená čísla k, m a přemýšlejme, kolika způsoby můžeme zadat k-ární operaci na množině M = {1, 2, . . . , m}. Všech uspořádaných k-tic prvků množiny M je mk, pro každou z nich máme m možností výsledku naší operace na této k-tici. Počet k-árních operací na množině M je mmk . Odtud plyne: Věta. Nechť Ω je typ, m přirozené číslo. Systém všech Ω-algeber s nosnou množinou M = {1, 2, . . . , m} tvoří množinu (nikoliv vlastní třídu). V případě konečného typu Ω je tato množina konečná. Na této množině relace „být izomorfní je relací ekvivalence. Zvolíme-li systém reprezentantů z odpovídajícího rozkladu, dostaneme množinu Ω-algeber s následující vlastností: každá m-prvková Ω-algebra je izomorfní s právě jednou Ω-algebrou z našeho systému reprezentantů. Důsledek. Existuje množina Ω-algeber (která je spočetná, je-li typ Ω konečný) taková, že každá konečná Ω-algebra je izomorfní s právě jednou Ω-algebrou z této množiny. Charakterizace pseudovariet libovolného typu Ω Věta. Nechť Ω je libovolný typ. Každá pseudovarieta Ω-algeber je sjednocením usměrněného systému ekvacionálních pseudovariet. Důkaz. Nechť V je libovolná pseudovarieta Ω-algeber. Podle předchozího důsledku existuje množina M neprázdných Ω-algeber patřících do V taková, že každá neprázdná Ω-algebra z V je izomorfní s právě jednou Ω-algebrou z M. Pak Psvar(A), A ∈ M, je systém pseudovariet, o kterých už víme, že jsou ekvacionální. Zřejmě platí V = A∈M Psvar(A). Zbývá dokázat, že je tento systém pseudovariet usměrněný, tj. že pro libovolné A1, A2 ∈ M existuje B ∈ M tak, že Psvar(A1) ∪ Psvar(A2) ⊆ Psvar(B). Protože A1 × A2 ∈ V , existuje B ∈ M tak, že B ∼= A1 × A2. Protože projekce ze součinu neprázdných Ω-algeber jsou surjektivní, platí A1, A2 ∈ Psvar(B), odkud plyne potřebná inkluze. Charakterizace pseudovariet konečného typu Ω Věta. Nechť Ω je konečný typ. Každá pseudovarieta Ω-algeber je sjednocením neklesající posloupnosti ekvacionálních pseudovariet. Důkaz. Protože typ Ω je konečný, můžeme v důkaze předchozí věty předpokládat, že M = {A1, A2, . . . } je nejvýše spočetná. Pro každé přirozené číslo n označme Vn = Psvar(A1 × · · · × An), což podle jedné z předchozích vět je ekvacionální pseudovarieta. Protože A1 × · · · × An ∈ V , platí Vn ⊆ V . Z důkazu předchozí věty víme, že n i=1 Psvar(Ai ) ⊆ Vn a že ∞ i=1 Psvar(Ai ) = V , a tedy V = ∞ i=1 Psvar(Ai ) = ∞ n=1 n i=1 Psvar(Ai ) ⊆ ∞ n=1 Vn ⊆ V . Vzhledem k tomu, že A1 × · · · × An je obrazem A1 × · · · × An × An+1 ∼= (A1 × · · · × An) × An+1 v surjektivním homomorfismu (v projekci ze součinu), platí A1 × · · · × An ∈ Vn+1, tedy Vn ⊆ Vn+1, a proto je posloupnost V1, V2, . . . neklesající. Věta Eilenberga a Schützenbergera Věta. Nechť Ω je konečný typ a V libovolná pseudovarieta Ω-algeber. Pak existuje posloupnost rovností (εi )i∈N (kde každá rovnost εi je tvaru yi = zi pro některé termy yi , zi typu Ω) splňující následující podmínku: označíme-li Wn varietu určenou teorií Tn = {εi ; i ≥ n}, pak W1 ⊆ W2 ⊆ . . . a platí V = ∞ i=1 Wn F . Jinými slovy: konečná Ω-algebra patří do V , právě když splní rovnost εi pro skoro všechna i ∈ N (tj. všechna až na konečně mnoho). Důkaz. Podle předchozí věty máme neklesající posloupnost ekvacionální pseudovariet V1 ⊆ V2 ⊆ . . . , jejichž sjednocením je V . Víme, že existuje nejvýše spočetný systém T = {B1, B2, . . . } takových Ω-algeber, že každá konečná Ω-algebra nepatřící do V je izomorfní s právě jednou Ω-algebrou z T . Pro každé i ≥ 1, j ≥ 1 platí Bj /∈ Vi . Protože Vi je ekvacionální, existuje rovnost εij , kterou splňují všechny Ω-algebry z Vi , avšak nikoli Bj . Věta bude dokázána, ukážeme-li, že pro libovolnou konečnou Ω-algebru A platí A ∈ V , právě když A splní rovnost εij pro skoro všechny dvojice (i, j), pro které i ≥ j. Důkaz. Podle předchozí věty máme neklesající posloupnost ekvacionální pseudovariet V1 ⊆ V2 ⊆ . . . , jejichž sjednocením je V . Víme, že existuje nejvýše spočetný systém T = {B1, B2, . . . } takových Ω-algeber, že každá konečná Ω-algebra nepatřící do V je izomorfní s právě jednou Ω-algebrou z T . Pro každé i ≥ 1, j ≥ 1 platí Bj /∈ Vi . Protože Vi je ekvacionální, existuje rovnost εij , kterou splňují všechny Ω-algebry z Vi , avšak nikoli Bj . Věta bude dokázána, ukážeme-li, že pro libovolnou konečnou Ω-algebru A platí A ∈ V , právě když A splní rovnost εij pro skoro všechny dvojice (i, j), pro které i ≥ j. Jestliže A ∈ V , pak existuje n tak, že A ∈ Vn, a tedy A ∈ Vi pro všechna i ≥ n, proto A splňuje rovnost εij pro každé i ≥ n a každé j, tedy z rovností εij , kde i ≥ j, může nesplňovat jen rovnosti εij pro j ≤ i < n. Takových dvojic (i, j) je jen konečně mnoho. Jestliže A je konečná Ω-algebra taková, že A /∈ V , pak existuje j tak, že A ∼= Bj . Pak A nesplňuje rovnost εij pro žádné i, takových dvojic (i, j), i ≥ j, je nekonečně mnoho. Implicitní a explicitní operace na pseudovarietě Definice. Nechť Ω je typ, V pseudovarieta Ω-algeber, n nezáporné celé číslo. Mějme pro každou Ω-algebru A ∈ V dánu n-ární operaci πA : An → A. Řekneme, že systém (πA)A∈V tvoří n-ární implicitní operaci na pseudovarietě V , jestliže pro každé A, B ∈ V a každý homomorfismus ϕ : A → B komutuje diagram An πA // ϕn  A ϕ  kde ϕn : An → Bn je definováno po složkách, tj. Bn πB // B ϕn(a1, . . . , an) = (ϕ(a1), . . . ϕ(an)). Jinými slovy, pro každé a1, . . . , an ∈ A platí ϕ(πA(a1, . . . , an)) = πB(ϕ(a1), . . . ϕ(an)). Příklad. Pro libovolný n-ární term typu Ω je systém (tA)A∈V operací daných tímto termem n-ární implicitní operaci na libovolné pseudovarietě V typu Ω. Definice. Implicitní operace z předchozího příkladu nazýváme explicitní. Struktura pologrup generovaných jedním prvkem Definice. Nechť (G, ·) je konečná pologrupa, g ∈ G je libovolný. Pak podpologrupou generovanou prvkem g je g = {gk; k ∈ N}. Z konečnosti pologrupy plyne existence m, n ∈ N takových, že gn = gn+m. Nejmenší n ∈ N s touto vlastností se nazývá předperioda pologrupy g . Nejmenší m ∈ N, které tuto podmínku splní pro předperiodu n, se nazývá perioda pologrupy g . Věta. Nechť (G, ·) je konečná pologrupa, g ∈ G je libovolný. Nechť n je předperioda pologrupy g a m její perioda. Pak platí: Pro libovolné r, s ∈ N je splněno gr = gs, právě když r = s < n anebo r ≥ n, s ≥ n, r ≡ s (mod m). Pro libovolné k ∈ N splňující m | k ≥ n platí gk je jediný idempotentní prvek pologrupy g . Množina {gn , gn+1 , . . . , gn+m−1 } tvoří podpologrupu; je to cyklická grupa řádu m generovaná prvkem gk+1 , jejímž neutrálním prvkem je gk . Důkaz je zřejmý. Příklad implicitní operace, která není explicitní Příklad. Nechť Ω = {·} je typ, kde · je binární; Ω-algebry jsou tedy grupoidy. Označme S pseudovarietu typu Ω, jejímiž prvky jsou právě všechny konečné pologrupy. Na libovolné konečné pologrupě (G, ·) definujme unární operaci ωG : G → G takto: pro libovolné g ∈ G je ωG (g) onen jediný idempotentní prvek pologrupy g generované prvkem g v pologrupě G. Systém (ωG )G∈S je unární implicitní operace na pseudovarietě S. Skutečně, je-li ϕ : G → H homomorfismus pologrup a je-li gk jediný idempotentní prvek pologrupy g ⊆ G, pak ϕ(gk) · ϕ(gk) = ϕ(gk · gk) = ϕ(gk), ϕ(gk) = ϕ(g)k ∈ ϕ(g) , a tedy ϕ(gk) je jediný idempotentní prvek pologrupy ϕ(g) ⊆ H. To znamená ϕ(ωG (g)) = ωH(ϕ(g)). Pro libovolný unární term typu Ω existuje přirozené číslo t tak, že operace určená tímto termem na libovolné pologrupě je umocňování na toto t. Proto implicitní operace (ωG )G∈S není explicitní. Pseudorovnosti a Reitermanova věta Definice. Nechť Ω je typ, V pseudovarieta Ω-algeber, n nezáporné celé číslo. Mějme na V dány dvě n-ární implicitní operace π = (πA)A∈V a µ = (µA)A∈V . Formální zápis π = µ nazýváme pseudorovností na pseudovarietě V ; říkáme, že Ω-algebra A ∈ V splňuje tuto pseudorovnost, jestliže πA a µA jsou stejné n-ární operace na Ω-algebře A. Následující větu Jana Reitermana si uvedeme bez důkazu: Věta. Nechť Ω je typ, V pseudovarieta Ω-algeber, U podtřída pseudovariety V . Pak následující podmínky jsou ekvivalentní: U je pseudovarieta; existuje množina T pseudorovností na pseudovarietě V s touto vlastností: pro libovolnou A ∈ V platí A ∈ U, právě když A splňuje každou pseudorovnost z T. Poznámka. Reitermanova věta ukazuje, že pseudovariety lze zkoumat pomocí pseudorovností, tedy pomocí implicitních operací. Množina n-árních implicitních operací na pseudovarietě V Každá implicitní operace na pseudovarietě V je dána svým chováním na množině reprezentantů konečných Ω-algeber, máme proto množinu všech n-árních implicitních operací na pseudovarietě V . Na této množině lze definovat strukturu Ω-algebry (v níž podmnožina explicitních operací tvoří podalgebru): máme-li k-ární f ∈ Ω, pak pro n-ární implicitní operace π1 = (π1,A)A∈V , . . . , πk = (πk,A)A∈V je f (π1, . . . , πk)A(a1, . . . , an) = fA(π1,A(a1, . . . , an), . . . , πk,A(a1, . . . , an)) pro každou A ∈ V a každé a1, . . . , an ∈ A. Také zde můžeme definovat strukturu metrického prostoru: je-li π1 = (π1,A)A∈V = π2 = (π2,A)A∈V , pak definujeme vzdálenost ρ(π1, π2) = 2−k, kde k je nejmenší přirozené číslo takové, že existuje k-prvková A ∈ V tak, že π1,A = π2,A. Tento metrický prostor je dokonce ultrametrický a úplný, podmnožina explicitních operací v něm tvoří hustou podmnožinu. V případě konečného typu je také kompaktní.