Charakterizace volnosti pomocí homomorfismů Poznámka. Pro volnou algebru FX (Ω) typu Ω generovanou množinou X jsme dokázali následující větu: 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 ⊆ || α 11 FX (Ω) ϕ GG A Poznámka. Tvrzení věty znamená, že pro libovolnou Ω-algebru A platí, že když v ní jakkoli předepíšeme obraz každému prvku množiny X (což je množina generátorů Ω-algebry FX (Ω)), pak vždy existuje (jediná) možnost, jak tento předpis doplnit na homomorfismus Ω-algeber ϕ : FX (Ω) → A. Prvky množiny X tedy nejsou svázány žádnou netriviální rovností. Speciální případ X = {x1, . . . , xn} Věta. 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. Předchozí věta zaručuje existenci jediného homomorfismu Ω-algeber ϕ : FX (Ω) → A splňujícího podmínku ϕ(xi ) = ai pro všechny i = 1, . . . , n. X ⊆ || α 11 FX (Ω) ϕ GG A Pak platí: tento homomorfismus ϕ přiřadí libovolnému termu t ∈ FX (Ω) hodnotu operace, kterou tento term určuje, v 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. Cíl: konstrukce volné Ω-algebry v dané varietě Nechť Ω je typ, t1, t2 dva různé n-ární termy typu Ω. Z předchozí věty plyne, že pokud má množina X alespoň n prvků, pak ve volné algebře FX (Ω) typu Ω generované množinou X není splněna rovnost t1 = t2. Proto pokud v teorii T typu Ω je alespoň jedna rovnost dvou různých n-árních termů a množina X má alespoň n prvků, pak ve varietě V určené teorií T volná algebra FX (Ω) neleží. Potřebujeme 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. Výhoda takového postupu je, že jej lze užít i v situaci, kdy neznáme teorii T, ale jen jí určenou varietu. Uzavřená třída Ω-algeber Protože naším cílem je důkaz Birkhoffovy věty, nebudeme konstrukci volné Ω-algebry generované množinou X provádět pouze ve varietě V typu Ω, ale zdánlivě obecněji: v libovolné tzv. uzavřené třídě Ω-algeber dle následující definice. (Podle Birkhoffovy věty ovšem každá uzavřená třída Ω-algeber je varietou.) Definice. Nechť V je třída Ω-algeber. O třídě V řekneme, že je uzavřená, právě když splňuje všechny podmínky Birkhoffovy věty, tj. 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. Už víme, že poslední podmínka znamená, že ve V leží také jednoprvková Ω-algebra {∅}. Odtud druhou podmínkou dostaneme, že ve V leží všechny jednoprvkové Ω-algebry, neboť uzavřená třída Ω-algeber s každou Ω-algebrou A obsahuje i všechny Ω-algebry izomorfní s A. Tedy V není množina, ale vlastní třída. Volnou Ω-algebru generovanou X získáme faktorizací FX (Ω) Nechť V je uzavřená třída Ω-algeber. Protože FX (Ω) je Ω-algebra generovaná množinou X, její libovolná faktorová algebra je generovaná třídami obsahujícími prvky z X. Je tedy nutné najít kongruenci ∼ na FX (Ω) tak, aby FX (Ω)/∼ ∈ V . Takových kongruencí může být hodně, ale vždy je alespoň jedna, totiž největší kongruence dávající jednoprvkovou faktorovou Ω-algebru. 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. 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. Dokazovali jsme, že průnik libovolného neprázdného systému kongruencí na dané Ω-algebře je opět kongruence na ní, tedy ∼V je kongruence na FX (Ω). Není však hned jasné, zda faktorová algebra FX (Ω)/∼V leží v třídě V . Připomeňme větu o průniku množiny kongruencí. Věta o průniku množiny kongruencí Věta. 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. 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 o součinu existuje jediný homomorfismus Ω-algeber ϕ : A → B takový, že π∼ ◦ ϕ = µ∼. Pak platí: jádrem homomorfismu ϕ je kongruence ≈. B π∼ 99 π CC . . . A/∼ . . . A/ · · · (∼, , . . . ∈ K) A µ∼ UU µ QQϕ yy Věta. Nechť Ω je typ, X množina, V je uzavřená třída Ω-algeber. Nechť ∼V je relace z předchozí definice, tj. průnik množiny K všech kongruencí ∼ na Ω-algebře FX (Ω) takových, že FX (Ω)/∼ ∈ V . Pak ∼V je kongruence na Ω-algebře FX (Ω) a příslušná faktorová algebra FX (V ) = FX (Ω)/∼V leží v třídě V . Důkaz. Podle připomenuté věty existuje jediný homomorfismus Ω-algeber ϕ : FX (Ω) → ∼∈K (FX (Ω)/∼), pro který komutuje: ∼∈K (FX (Ω)/ ∼) π 77 π∼= CC · · · FX (Ω)/ . . . FX (Ω)/∼= · · · ( , ∼=, . . . ∈ K) FX (Ω) µ UU µ QQ ϕ yy Přitom jádrem ϕ je kongruence ∼V . Proto FX (V ) = FX (Ω)/∼V je izomorfní s podalgebrou ϕ(FX (Ω)) součinu Ω-algeber z V . Protože V je uzavřená třída, platí FX (V ) ∈ V . Volná algebra třídy V generovaná množinou X Definice. Nechť Ω je typ, X množina, V je uzavřená třída Ω-algeber. Faktorová algebra FX (V ) = FX (Ω)/∼V z předchozí věty 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 ). X ⊆ || µ 44 FX (Ω) π GG 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, že zobrazení µ je injektivní. Není to však homomorfismus Ω-algeber, přestože se nazývá vnoření, vždyť X je jen množina, nikoli Ω-algebra. Charakterizace volnosti pomocí homomorfismů Věta. 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 α 44 µ  FX (Ω) π GG FX (V ) ψ GG A Poznámka. Neformálně řečeno, předchozí věta popisuje to, že prvky množiny X generují Ω-algebru FX (V ) v rámci třídy V co „nejvolněji, tedy že tyto generátory jsou v Ω-algebře FX (V ) svázány jen rovnostmi platnými v každé Ω-algebře z třídy V . Důkaz věty Podle věty o volnosti FX (Ω) existuje jediný homomorfismus Ω-algeber ϕ : FX (Ω) → A splňující podmínku ∀x ∈ X : ϕ(x) = α(x). X ⊆ yy α 44 µ  FX (Ω) π GG ϕ VVFX (V ) A ϕ(FX (Ω)) je podalgebra Ω-algebry A ∈ V , z uzavřenosti V na podalgebry ϕ(FX (Ω)) ∈ V . Z důsledku hlavní věty o faktorových algebrách pro jádro ∼ homomorfismu ϕ je ϕ(FX (Ω)) ∼= FX (Ω)/∼, z uzavřenosti V na obrazy v surjektivních homomorfismech FX (Ω)/∼ ∈ V . Tedy ∼ je jedna z těch kongruencí, jejichž průnikem je ∼V . Proto ∼V ⊆ ∼ a podle hlavní věty o faktorových algebrách existuje jediný homomorfismus Ω-algeber ψ : FX (V ) → A s vlastností ψ ◦ π = ϕ, tedy komutuje diagram X ⊆ yy α 44 µ  FX (Ω) π GG ϕ VVFX (V ) ψ GG A Proto ψ ◦ µ = ψ ◦ π ◦ ⊆ = ϕ ◦ ⊆ = α. Jednoznačnost: ψ ◦ µ = α =⇒ ψ ◦ π = ϕ =⇒ ψ = ψ. Volná algebra je určena předchozí větou až na izomorfismus Poznámka. Následující věta umožňuje konstruovat volné algebry jinak než z definice: odhadnout, jak asi vypadá, a pak ukázat, že je to opravdu ona, protože splňuje tuto charakterizační vlastnost. Věta. Nechť Ω je typ, X množina, 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 ψ ◦ µ = ν. ∀A ∀α X ν  α 11 U ρ GG A =⇒ X µ {{ ν 11 FX (V )   ψ GG GG U Důkaz věty Podle předchozí věty pro Ω-algebru U a zobrazení ν : X → U existuje homomorfismus Ω-algeber ψ : FX (V ) → U splňující podmínku ψ ◦ µ = ν. 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 µ ÐÐ ν 11 ιFX (V ) `` FX (V ) ψ CC U ρ kk ιU ff Homomorfismus ρ ◦ ψ splňuje ρ ◦ ψ ◦ µ = ρ ◦ ν = µ = ιFX (V ) ◦ µ, kde ιFX (V ) je identita na FX (V ). Z jednoznačnosti popsané v předchozí větě ρ ◦ ψ = ιFX (V ). Zcela analogicky se dokáže z jednoznačnosti popsané v předpokladech věty, že ψ ◦ ρ = ιU. To znamená, že ψ je inverzní zobrazení k ρ, a tedy ρ je bijekce, tedy izomorfismus. Příklady použití věty Příklad. Nechť Ω = {·, −1, 1} a V je varieta všech grup. Pak F∅(V ) ∼= {e} je jednoprvková grupa, neboť do libovolné grupy jde z grupy {e} jediný homomorfismus. Podobně F{x}(V ) je nekonečná cyklická grupa x . (Každá nekonečná cyklická grupa je izomorfní s grupou (Z, +).) Pro libovolnou grupu G a libovolný prvek g ∈ G máme jediný homomorfimus x → G, totiž xn → gn. Příklad. Nechť Ω = {·, +, −, 0, 1} a V je varieta všech okruhů. Pak F∅(V ) je okruh celých čísel Z, neboť pro libovolný okruh R existuje jediný homomorfismus okruhů Z → R. Podobně F{x}(V ) je okruh polynomů Z[x], protože pro libovolný okruh R a libovolný prvek r ∈ R máme jediný homomorfimus Z[x] → R, totiž anxn + · · · + a1x + a0 → anrn + · · · + a1r + a01, kde vpravo jsou celočíselné násobky prvků z R. Příklad. Nechť Ω = {+, −, 0} a V je varieta všech komutativních grup. Pak F{x,y}(V ) ∼= Z × Z, kde vnoření generátorů je definováno takto: x → (1, 0), y → (0, 1). Podobně F{x1,...,xn}(V ) ∼= Zn.