Co je to univerzální algebra? Při studiu řadu algebraických struktur (grupoidy, pologrupy, grupy, komutativní grupy, okruhy, obory integrity, tělesa, polosvazy, svazy, Booleovy algebry) se často některé pojmy a úvahy opakovaly: homomorfismy: vždy platilo, že složením homomorfismů opět dostaneme homomorfismus; podobjekty (podgrupy, podokruhy, podtělesa, podsvazy, Booleovy podalgebry atd.): vždy platilo, že průnikem libovolného neprázdného systému podobjektů je opět podobjekt, což umožnilo definovat podobjekt generovaný podmnožinou ve všech případech stejnou konstrukcí; součiny algebraických struktur (grup, okruhů, svazů): na kartézském součinu jsme definovali stejnou strukturu. Jedním z cílů univerzální algebry je tyto společné rysy postihnout a jednotně popsat. Zobecnění pojmu operace na množině Operací na množině G pro nás dosud bylo zobrazení G × G → G. Nyní tento pojem zobecníme, vždyť jsme užívali zobrazení G → G (přiřazení inverzního prvku v grupě nebo komplementu v Booleově algebře). Pracovali jsme s význačnými prvky množiny G (neutrální prvek grupy, 0 a 1 okruhu, nejmenší a největší prvek Booleovy algebry). Výběr význačného prvku lze chápat jako volbu zobrazení z jednoprvkové množiny do 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. Přitom pro n ∈ N definujeme Gn = G × G × · · · × G n , pro n = 0 je G0 = {∅}. Poznámka. Místo 2-ární operace budeme říkat binární operace, místo 1-ární budeme říkat unární, místo 0-ární nulární. Číslu n z definice říkáme arita dotyčné operace. Univerzální algebra daného typu Poznámka. 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). Pro n = 0 je A0 = {∅}, nulární operací je zobrazení fA : {∅} → A zadané jediným prvkem fA(∅) ∈ A, pro zjednodušení jej budeme zapisovat fA místo fA(∅). Příklady Ω-algeber 1. Pro prázdný typ, tj. Ω = ∅, je univerzální algebrou typu Ω libovolná množina. 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). Jednoprvková Ω-algebra Příklad. Nechť Ω je libovolný typ, A = {a} libovolná 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. 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 a s operacemi fA pro každé f ∈ Ω. Například 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. Podalgebra Ω-algebry 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á. Poznámka. Každá podalgebra H libovolné Ω-algebry A je sama Ω-algebrou, stačí pro každý n-ární operační symbol f ∈ Ω definovat fH jako restrikci zobrazení fA na Hn a zmenšit obor hodnot na H, pak totiž fH : Hn → H. Příklady podalgeber V jednotlivých případech z předchozího příkladu univerzálních algeber dostáváme tyto podalgebry: 1. Podmnožina množiny (Ω = ∅). 2. Podgrupoid grupoidu (Ω = {·}). 3. Podgrupa grupy (Ω = {·, −1, 1}). 4. Podokruh okruhu (Ω = {+, ·, −, 0, 1}). 5. Podsvaz svazu (Ω = {∨, ∧}). 6. Booleova podalgebra Booleovy algebry (Ω = {∨, ∧, , 0, 1}). 7. Vektorový podprostor vektorového prostoru (Ω = {+, −, 0} ∪ T, kde T je těleso). Svaz všech podalgeber dané Ω-algebry Věta. 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. Nechť f ∈ Ω je n-ární, a1, . . . , an ∈ i∈I Hi libovolné. Pro každé i ∈ I platí a1, . . . , an ∈ Hi . Protože Hi je podalgebra, je fA(a1, . . . , an) ∈ Hi . Pak fA(a1, . . . , an) ∈ i∈I Hi . 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 neprá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. (P, ⊆) má největší prvek A i infimum libovolné neprázdné podmnožiny (průnik všech podalgeber této podmnožiny). Podalgebra generovaná podmnož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 předchozí věty 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 podalgeber generovaných podmnožinou 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. 2. Podgrupoid grupoidu generovaný množinou (tento pojem jsme v přednášce neměli). 3. Podgrupa M grupy generovaná množinou M. 4. Podokruh M okruhu generovaný množinou M. 5. Podsvaz svazu generovaný množinou (neměli jsme). 6. Booleova podalgebra Booleovy algebry generovaná množinou (neměli jsme). 7. Vektorový podprostor vektorového prostoru generovaný množinou vektorů (jeden z nejdůležitějších pojmů lineární algebry). Homomorfismy Ω-algeber 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)). Je-li navíc ϕ bijektivní, hovoříme o izomorfismu Ω-algeber. Řekneme, že Ω-algebry A a B jsou izomorfní, jestliže existuje nějaký izomorfismus Ω-algeber A → B. 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 homomorfismů Ω-algeber 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í homomorfismem. 2. Pro grupoidy je tato definice totožná s obvyklou definicí homomorfismu grupoidů. 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. Příklady homomorfismů Ω-algeber 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ů jsou homomorfismy právě lineární zobrazení. Složení homomorfismů Ω-algeber Věta. 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)), což jsme měli dokázat. Obraz v homomorfismu Ω-algeber Věta. 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). Věty o izomorfismech Ω-algeber Věta. Nechť A, B jsou univerzální algebry téhož typu Ω, ϕ : A → B izomorfismus Ω-algeber. Pak inverzní zobrazení ϕ−1 : B → A je také izomorfismus Ω-algeber. Důkaz. Zvolme libovolně operační symbol f ∈ Ω arity n. Pak pro každé prvky b1, . . . , bn ∈ B existují a1, . . . , an ∈ A tak, že ϕ(a1) = b1, . . . , ϕ(an) = bn. Z definice homomorfismu fB(b1, . . . , bn) = ϕ(fA(a1, . . . , an)), a tedy ϕ−1(fB(b1, . . . , bn)) = fA(ϕ−1(b1), . . . , ϕ−1(bn)). Věta. Nechť A, B, C jsou univerzální algebry téhož typu Ω. 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 zřejmé. Součin dvou Ω-algeber 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 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 znamená fA×B = (fA, fB). 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. Poznámka. Protože Ω-algebry mohou být i prázdné, nemusí být obecně projekce ze součinu surjektivní. Projekce ze součinu dvou Ω-algeber Věta. 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. 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))). Analogicky se dokáže, že projekce π2 je homomorfismus Ω-algeber. Věta o součinu dvou Ω-algeber Věta. Nechť A, B, C jsou univerzální algebry téhož typu Ω, ϕ : C → A, ψ : C → B homomorfismy Ω-algeber, π1 : A × B → A, π2 : A × B → B projekce ze součinu A × B. Pak existuje jediný homomorfismus Ω-algeber ρ : C → A × B s vlastností π1 ◦ ρ = ϕ, π2 ◦ ρ = ψ. A × B π1 || π2 "" A B C ϕ bb ψ ;;ρ OO Důkaz. Podmínky π1 ◦ ρ = ϕ, π2 ◦ ρ = ψ platí, právě když ρ(c) = (ϕ(c), ψ(c)) pro každé c ∈ C. Zvolme libovolně operační symbol f ∈ Ω arity n a prvky c1, . . . , cn ∈ C. Platí fA×B(ρ(c1), . . . , ρ(cn)) = fA×B((ϕ(c1), ψ(c1)), . . . , (ϕ(cn), ψ(cn))) = = fA(ϕ(c1), . . . , ϕ(cn)), fB(ψ(c1), . . . , ψ(cn)) = = ϕ(fC (c1, . . . , cn)), ψ(fC (c1, . . . , cn)) = = ρ(fC (c1, . . . , cn)), což se mělo dokázat. Součin libovolného počtu 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. Ve speciálním případě I = ∅ vlastně žádnou množinu Ai nemáme. Přesto 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í. Součin libovolného počtu Ω-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 (pro n = 0 tedy fA = χ, kde χ(i) = fAi ). Poznámka. Ve speciálním případě I = ∅ je součinem Ω-algebra na jednoprvkové množině, jejímž jediným prvkem je prázdné zobrazení. Tato Ω-algebra je jediná (na jednoprvkové množině pro libovolné n ∈ N0 existuje jen jedna n-ární operace). Ačkoli nemáme dánu žádnou Ω-algebru, jako součin dostáváme jednoprvkovou Ω-algebru, a tedy máme informaci o tom, jak vypadá Ω. Není to paradox: 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á. Projekce ze součinu Ω-algeber Věta. 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 pro každé j ∈ I je j-tá projekce πj : A → Aj homomorfismus Ω-algeber. Důkaz. Připomeňme, že projekce πj : A → Aj je definována předpisem πj (χ) = χ(j) pro každé χ ∈ A. 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. Věta o součinu Ω-algeber Věta. 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 a πj : A → Aj je j-tá projekce pro každé j ∈ I. 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. A πj && πj ++ . . . Aj . . . Aj · · · (j, j , . . . ∈ I) C ϕj 88 ϕj 33ϕ OO Důkaz věty o součinu Ω-algeber Důkaz. Rovnost πj ◦ ϕ = ϕj pro každé j ∈ I platí, právě když pro každé c ∈ C je ϕ(c) ∈ A určené podmínkou: pro libovolné j ∈ I (ϕ(c))(j) = πj (ϕ(c)) = (πj ◦ ϕ)(c) = ϕ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)), pak pro každé i ∈ I platí χ(i) = fAi ((ϕ(c1))(i), . . . , (ϕ(cn))(i)) = fAi (ϕi (c1), . . . , ϕi (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.