Další příklady použití věty charakterizující volné algebry Příklad. Pro dané těleso (R, +, ·) uvažme typ Ω = {⊕, , o} ∪ R a varietu V vektorových prostorů nad R. Pro libovolné přirozené číslo n má vektorový prostor Rn následující vlastnost: pro libovolný vektorový prostor U nad tělesem R a libovolnou n-tici vektorů u1, . . . , un ∈ U existuje lineární zobrazení (tedy homomorfismus vektorových prostorů) ϕ : Rn → U určené předpisem ϕ((r1, . . . , rn)) = r1u1 + · · · + rnun. Nechť vi ∈ Rn je n-tice mající v i-té složce 1, jinde nuly. Zřejmě ϕ je jediný homomorfismus Rn → U splňující vi → ui . Proto F{x1,...,xn}(V ) ∼= Rn, vnoření generátorů je definováno takto: xi → vi . Příklad. Nechť Ω = {·} a V je varieta všech pologrup. Pak F{x1,...,xn}(V ) je izomorfní s pologrupou všech neprázdných slov (tedy konečných posloupností) nad abecedou o n písmenech x1, . . . , xn, kde operací je konkatenace (napsání slov za sebe). Jestliže totiž zvolíme libovolnou pologrupu a v ní libovolně prvky a1, . . . , an, pak existuje jediný homomorfismus zobrazující písmeno xi na prvek ai pro každé i. Volné grupy Příklad. Nechť Ω = {·, −1, 1} a V je varieta všech grup. Pro libovolnou množinu X popišme konstrukci volné grupy FX (V ) generované množinou X. Pro každý prvek x ∈ X zavedeme nový symbol ¯x a označíme Y = X ∪ {¯x; x ∈ X}. Nosnou množinou konstruované grupy je množina všech těch slov (tedy konečných posloupností) nad abecedou Y , v nichž nestojí vedle sebe nikde žádné písmeno a jeho pruhovaná varianta. Operace násobení se počítá tak, že se provede konkatenace daných slov (tj. zapíší se slova za sebe) a pokud na rozhraní slov se objevilo písmeno vedle své pruhované varianty, tak se obě odstraní, což se provádí tak dlouho, dokud dostáváme vedle sebe stojící písmeno a jeho pruhovanou variantu. Neutrálním prvkem této grupy je prázdné slovo. A konečně inverzní prvek k danému slovu se vytvoří tak, že se napíše slovo získané z daného slova vypsáním jeho písmen v opačném pořadí a „výměnou pruhů , tj. písmena bez pruhů pruh dostanou a písmena s pruhem o něj přijdou. Tím jsme sestrojili grupu a je možné ověřit, že splňuje potřebnou podmínku o homomorfismech. Rovnosti platné ve volné Ω-algebře Poznámka. Pro uzavřenou třídu Ω-algeber V a množinu generátorů X jsme konstruovali volnou algebru FX (V ) = FX (Ω)/ ∼V tak, že jsme faktorizovali volnou algebru FX (Ω) typu Ω co možná nejmenší kongruencí ∼V , aby platilo FX (V ) ∈ V . Následující věta pro množinu generátorů X = {x1, . . . , xn} popisuje, které rovnosti tvořené n-árními termy v FX (V ) platí: jsou to právě ty rovnosti, které platí v každé Ω-algebře A ∈ V . Věta. Nechť Ω je typ, n nezáporné celé číslo, X = {x1, . . . , xn} je n-prvková 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 věty „(iii) =⇒ (ii) To plyne z FX (V ) ∈ V . „(ii) =⇒ (i) Operace (t1)FX (V ) a (t2)FX (V ) jsou stejné. Homomorfismus π zachovává operace určené termy, proto platí (ti )FX (V )(π(x1), . . . , π(xn)) = π (ti )FX (Ω)(x1, . . . , xn) pro i = 1, 2. Podle definice operací na Ω-algebře FX (Ω) je (ti )FX (Ω)(x1, . . . , xn) = ti . „(i) =⇒ (iii) Zvolme libovolně A ∈ V a libovolné a1, . . . , an ∈ A. Dokažme (t1)A(a1, . . . , an) = (t2)A(a1, . . . , an). Pro zobrazení α : X → A dané předpisem α(xj ) = aj pro každé j = 1, . . . , n máme komutativní diagram X ⊆ yy α "" µ  FX (Ω) π // ϕ 88FX (V ) ψ // A Pro libovolný t ∈ FX (Ω) platí ϕ(t) = tA(a1, . . . , an), a tedy (t1)A(a1, . . . , an) = ϕ(t1) = = ψ(π(t1)) = ψ(π(t2)) = = ϕ(t2) = (t2)A(a1, . . . , an). Teorie určená třídou Ω-algeber Poznámka. Pro každou teorii typu Ω jsme 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. Je to největší teorie (vzhledem k inkluzi) určující varietu V . 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 (vzhledem k inkluzi) obsahující třídu V . Uzavřené třídy určující tutéž teorii mají stejné volné algebry (případ konečně mnoha generátorů) Důsledek. Nechť Ω je typ. 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. X µ1 yy ⊆  µ2 %% FX (V1) FX (Ω) π1oo π2 // FX (V2) Podle předchozí věty pro libovolné t1, t2 ∈ FX (Ω) platí π1(t1) = π1(t2) právě tehdy, když rovnost t1 = t2 platí v každé Ω-algebře A ∈ V1, tedy právě když rovnost t1 = t2 patří do teorie T, což znamená, že rovnost t1 = t2 platí v každé Ω-algebře A ∈ V2, a to podle této věty platí právě tehdy, když π2(t1) = π2(t2). Obě projekce π1 a π2 mají stejná jádra, tedy FX (V1) = FX (V2). Uzavřené třídy určující tutéž teorii mají stejné volné algebry (obecný případ libovolně mnoha generátorů) Poznámka. Předchozí důsledek o volných algebrách s konečně mnoha generátory zobecníme na případ volných algeber s libovolnou množinou generátorů: Věta. Nechť Ω je typ. 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. Víme, že věta platí, je-li X konečná množina. Předpokládejme, že X je 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, 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 . Zvolme libovolné zobrazení µ : X → Y takové, že pro každé y ∈ Y platí µ(y) = y (prvky y ∈ X, y /∈ Y zobrazíme zcela libovolně). Máme tedy komutativní diagram Y ⊆ // idY (( X µ // 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 ⊆  ⊆ // idY ** X ⊆  µ // Y ⊆  FY (Ω) ϕ // π  FX (Ω) πi  FY (Ω) π  FY (Vi ) ϕi // idFY (Vi ) 33FX (Vi ) ψi // FY (Vi ) Existenci homomorfismu ϕ dává volnost FY (Ω) pro zobrazení Y → FX (Ω), je jasné, že ϕ je zobrazení inkluze. Existenci homomorfismů ϕi a ψi dává volnost FY (Vi ) a FX (Vi ) pro zobrazení Y → FX (Vi ) a X → FY (Vi ). Y ⊆  ⊆ // idY ** X ⊆  µ // Y ⊆  FY (Ω) ϕ // π  FX (Ω) πi  FY (Ω) π  FY (Vi ) ϕi // idFY (Vi ) 33FX (Vi ) ψi // FY (Vi ) Zobrazení Y → FX (Vi ) určí homomorfismus FY (Ω) → FX (Vi ) jednoznačně, komutuje tedy „dolní čtverec, tj. πi ◦ ϕ = ϕi ◦ π. „Diagonální obrazení Y → FY (Vi ) dá homomorfismus FY (Vi ) → FY (Vi ) jednoznačně, komutuje tedy „dolní trojúhelník, tj. ψi ◦ ϕi = idFY (Vi ). Proto jsou obě zobrazení ϕ1 a ϕ2 injektivní. Dolní komutativní čtverce pro i = 1 i i = 2 lze najednou nakreslit do diagramu: FX (V1) FY (V1) = FY (V2) + ϕ1 88 s ϕ2 && FY (Ω) ϕ //πoo FX (Ω) π1 ee π2 yy FX (V2) Platí t1, t2 ∈ FY (Ω), ϕ(t1) = t1, ϕ(t2) = t2, ϕ2(π(t1)) = π2(ϕ(t1)) = = π2(t1) = π2(t2) = π2(ϕ(t2)) = = ϕ2(π(t2)), tedy π(t1) = π(t2). Protože ϕ1 je injektivní, ϕ1(π(t1)) = ϕ1(π(t2)), tedy π1(t1) = = π1(ϕ(t1)) = ϕ1(π(t1)) = ϕ1(π(t2)) = π1(ϕ(t2)) = π1(t2), spor. Svou teorií je uzavřená třída jednoznačně určena Věta. Nechť Ω je typ. 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. Volnost FX (V1) dává homomorfismus ψ : FX (V1) → A splňující ψ ◦ µ = idX , kde µ : X → FX (V1) je vnoření generátorů do volné algebry FX (V1). X µ {{ idX  FX (V1) ψ // A Protože idX je surjektivní, je také ψ surjektivní. Podle předchozí věty FX (V1) = FX (V2), tedy FX (V1) ∈ V2. Protože třída V2 je uzavřená, plyne odtud, že A, jakožto obraz algebry FX (V1) v surjektivním homomorfismu ψ, patří do V2. Dokázali jsme inkluzi V1 ⊆ V2, opačná inkluze plyne ze symetrie. Dokončení důkazu Birkhoffovy věty 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. 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 je teorie, kterou určuje třída V , V je varieta Ω-algeber určená teorií T, zřejmě platí V ⊆ V , T teorie, kterou určuje varieta V , zřejmě platí T ⊆ T . Z V ⊆ V plyne T ⊇ T , dohromady T = T . Podle předchozí věty odtud plyne V = V , je tedy V varieta. Význam volných algeber: prezentace grupy Poznámka. Prezentace grup je metoda, jak (jednoznačně až na izomorfismus) popsat grupu: zadáme generátory a relace mezi nimi. Nechť V je varieta všech grup. Mějme libovolnou pevně zvolenou grupu G a zvolme množinu M generátorů grupy G, tedy M ⊆ G, M = G. Zřejmě taková množina M vždy existuje (například M = G). Zvolme množinu X a bijekci ν : X → M. Máme volnou grupu FX (V ) generovanou množinou X, a tedy i homomorfismus ψ : FX (V ) → G. X µ || ν  FX (V ) ψ // G Obraz ψ(FX (V )) je podgrupa grupy G obsahující M, je tedy ψ surjektivní. Proto G ∼= FX (V )/ ker ψ. Protože jde o grupy, je kongruence ker ψ zadána třídou H obsahující 1G . Víme, že H je normální podgrupa grupy G. Protože množina všech normálních podgrup grupy G tvoří úplný svaz, lze definovat „normální podgrupu generovanou množinou obvyklým způsobem. To umožní zadat H množinou generátorů. Definice a příklad prezentace grupy Definice. Prezentací grupy rozumíme zápis X | R , kde X je množina a R je podmnožina volné grupy FX (V ) generované množinou X; zde V značí varietu všech grup. Prezentovanou grupou je pak faktorgrupa FX (V )/H, kde H je normální podgrupa grupy FX (V ) generovaná množinou R. Prvkům množiny X říkáme generátory grupy, prvkům množiny R generující relace. Jsou-li množiny X a R dány výčtem prvků, píšeme x1, . . . , xn | r1, . . . , rm místo přesnějšího {x1, . . . , xn} | {r1, . . . , rm} . Příklad. Pro libovolné n ∈ N je a | an prezentací n-prvkové cyklické grupy, neboť F{a}(V ) = a je nekonečná cyklická grupa, v níž prvek an generuje podgrupu an . Faktorgrupou tedy je grupa a / an , což je n-prvková cyklická grupa. Poznámka. Někdy se relace v prezentaci grupy píší jako rovnosti, tedy zápisem x1, . . . , xn | r1 = r1, . . . , rm = rm znamenajícím x1, . . . , xn | r−1 1 r1, . . . , r−1 m rm . Naopak x1, . . . , xn | r1, . . . , rm lze psát x1, . . . , xn | r1 = 1, . . . , rm = 1 . Pozor: nejde o rovnosti v námi zavedeném smyslu, nelze v nich za zapsané prvky dosazovat jiné! Další příklad prezentace grupy Příklad. Grupa (Dn, ◦) všech symetrií pravidelného n-úhelníka je generována rotací r o úhel 2π n a libovolně zvolenou osovou souměrností s. Skutečně, r je cyklická podgrupa mající n prvků, tedy r, s ⊆ Dn obsahuje více než polovinu z 2n prvků grupy Dn, tedy z Lagrangeovy věty r, s = Dn. V grupě Dn platí rn = 1, s2 = 1, r ◦ s = s ◦ r−1, a tedy r ◦ s ◦ r ◦ s = 1. Zadejme prezentací grupu G = ρ, σ | ρn, σ2, ρ · σ · ρ · σ . Volná grupa generovaná množinou {ρ, σ} je grupa F všech slov nad abecedou {ρ, σ, ¯ρ, ¯σ}, ve kterých se nikde nevyskytne ani písmeno σ vedle ¯σ ani ρ vedle ¯ρ; operací je konkatenace a následné umazání podslov σ¯σ, ¯σσ, ρ¯ρ, ¯ρρ, pokud se vyskytnou. Proto platí σ−1 = ¯σ, ρ−1 = ¯ρ. Homomorfismus ψ : F → Dn určený předpisem ρ → r, σ → s je surjektivní, protože r, s = Dn. Nechť H je normální podgrupa grupy F generovaná množinou {ρn, σ2, ρ · σ · ρ · σ}, z definice tedy G = F/H. Ukážeme G ∼= Dn. Protože v grupě Dn platí rn = 1, s2 = 1, r ◦ s ◦ r ◦ s = 1, platí {ρn, σ2, ρ · σ · ρ · σ} ⊆ ker ψ (zde užíváme jádro homomorfismu grup v původním významu normální podgrupy), a tedy H ⊆ ker ψ. Hlavní věta o faktorových grupách dává surjektivní homomorfismus ˜ψ : G → Dn. F ψ // // π  Dn G = F/H ˜ψ :: :: Ukážeme, že ˜ψ je injektivní. Zvolme třídu rozkladu F/H a v ní reprezentanta, tedy slovo nad abecedou {ρ, σ, ¯ρ, ¯σ}. V tomto slově nahradíme každý výskyt písmene ¯σ písmenem σ a každý výskyt písmene ¯ρ nahradíme n − 1 písmeny ρ. Protože σ2, ρn ∈ H, je nové slovo nad abecedou {ρ, σ} ve stejné třídě jako slovo původní. Pokud nové slovo obsahuje podslovo ρσ, nahradíme jeho první výskyt slovem σρ · · · ρ, v němž se písmeno ρ opakuje (n − 1)-krát. Přitom kdykoli se objeví podslovo σσ, smažeme jej. Protože (ρσ)H = (σρn−1)H, σ2 ∈ H, jsme pořád v téže třídě. Časem dostaneme slovo mající pouze písmena ρ až na případně jedno písmeno σ na začátku. Je-li písmen ρ alespoň n, odstraníme jich n. V každé třídě rozkladu F/H tedy existuje slovo tvaru: nejvýše jedno σ na začátku a dále nejvýše n − 1 písmen ρ. Takových slov je 2n, tedy ˜ψ je injektivní. Využití prezentace grupy Prezentaci ρ, σ | ρn, σ2, ρ · σ · ρ · σ grupy Dn lze využít ke snadnějšímu provádění výpočtů v této grupě. Obecně však musíme být velmi opatrní při hledání prezentace pro danou grupu. Pro danou prezentaci může být nesnadné (nebo dokonce nemožné) rozhodnout, zda zadává konečnou grupu. Například grupa daná prezentací x, y | x2, y2, (xy)2 je čtyřprvková, kdežto grupa daná prezentací x, y | x3, y3, (xy)3 je nekonečná. Další problém je v tom, že dané relace mohou mít nečekané důsledky. Z předchozího víme, že grupa daná prezentací x, y | x4, y2, xyxy je izomorfní s D4, je tedy osmiprvková. Mírná modifikace x, y | x4, y2, x2yxy však nedá osmiprvkovou grupu, protože je zde skrytá relace: z x2yxy ∼ 1 vynásobením x2 zleva a y zprava plyne yx ∼ x2y, tedy x ∼ y2 x ∼ yx2 y ∼ x2 yxy ∼ x4 y2 ∼ 1, a tedy tato grupa je dvojprvková, generovaná prvkem y. Další využití prezentací Příklad. Připomeňme, že SL2(Z) je množina všech matic 2 × 2 s celočíselnými prvky a determinantem 1. Spolu s obvyklým násobením matic tvoří grupu mající dvojprvkovou normální podgrupu 1 0 0 1 , −1 0 0 −1 . Příslušnou faktorgrupu značíme PSL2(Z). (Grupa PSL2(Z) má významnou roli při studiu tzv. modulárních forem.) Je možné ukázat (ale není to úplně snadné), že grupa daná prezentací x, y | x3, y2 je izomorfní právě s grupou PSL2(Z). Přitom prvek x odpovídá třídě obsahující matici 0 −1 1 1 a prvek y třídě obsahující matici 1 0 0 −1 . Poznámka. Fakt, že každá Ω-algebra dané variety je surjektivním obrazem volné Ω-algebry je naprosto zásadní například v teorii modulů nad daným okruhem, kde umožní pro daný modul vytvářet tzv. volné rezolventy. Ale to už je látka z jiného předmětu. . .