ZÁKLADY TEORIE SVAZŮ Radan Kučera, 16.listopadu 2010 Literatura • Doporučená: – L. Bican, J. Rosický: Teorie svazů a univerzální algebra, dočasná vysokoškolská učebnice, MŠMT, Praha 1989. – L. Procházka a kol.: Algebra, Academia, Praha 1990 (kap. IX). • Další: – G. Birkhoff, T. C. Bartee: Aplikovaná algebra, Alfa, Bratislava 1981 (kap. 9). – G. Birkhoff, S. Mac Lane: Prehľad modernej algebry, Alfa, Bratislava 1979 (kap. 11). – A. G. Kuroš: Kapitoly z obecné algebry, Academia, Praha 1977 (kap. IV). – S. Mac Lane, G. Birkhoff: Algebra, Alfa, Bratislava 1974 (kap. XIV). Úvodní zamyšlení o volbě definic. Většina pojmů, se kterými se setkáváte na matematických přednáškách, jsou pojmy, na jejichž definici se matematikové v průběhu doby jednoznačně shodli. Často to bývá ta evidentně nejvhodnější ze všech variant, které se nabízely. V některých případech však volba není tak zřejmá: nabízí se najednou více vhodných variant. Příkladem může být definice množiny přirozených čísel: máme považovat nulu za přirozené číslo nebo ne? Je jasné, že příliš se obě varianty neliší, liší se jen ve znění některých vět, u nichž se v předpokladech nebo v tvrzeních musí ubrat či přidat požadavek nenulovosti, a ve znění některých navazujících definic, kde je třeba udělat totéž. V tomto případě jsme se přidali na stranu těch, kteří množinou přirozených čísel N nazývají množinu kladných celých čísel, tj. nulu za přirozené číslo nepovažujeme. 1 Druhý podobný případ je případ okruhů, kdy někdo (tak jako my na přednášce) v definici vyžaduje, aby každý okruh měl jedničku (a pak tedy také požaduje, aby tuto jedničku obsahoval i každý podokruh okruhu a aby homomorfismus okruhů zobrazil jedničku jednoho okruhu na jedničku druhého okruhu). V jiném přístupu se definují okruhy bez požadavku jedničky a o předchozím speciálním případě se mluví jako o okruhu s jedničkou. Je asi každému jasné, že se nedá říci, která z obou variant je ta správná. Správné jsou obě, jen je nezbytné se zvolené definice držet, tj. ve všech následujících úvahách užívat zvolenou definici. Je na tom dobře vidět i tvořivost v matematice: matematik si volí definice do značné míry svobodně a ze zvolených definic pak odvozuje řadu tvrzení o popisovaných objektech. Přitom definice volí s ohledem na to, aby popisované objekty odpovídaly jeho představám o nich a aby v odvozované teorii vycházela tvrzení co možná nejelegantněji. Zde je asi měřítkem elegance to, zda tvrzení lze snadno formulovat bez nutnosti probírat různé speciální případy zvlášť. Podobnou situací, kdy není zcela jasné, jak definici formulovat, je případ prázdné struktury. Máme připustit, aby například grupoid mohl mít za nosnou množinu množinu prázdnou? Ti, kteří zastávají názor, že grupoid má mít neprázdnou nosnou množinu, zdůvodňují svůj postoj tím, že grupoid na prázdné nosné množině je těžké si představit. A že konec konců tím, že tento případ připustíme, získáme jen velmi nezajímavý objekt, o kterém je ihned všechno známo. Jak si vlastně představit grupoid na prázdné množině? Operace na množině G je zobrazení G×G → G. Jestliže G = ∅, pak G×G, jakožto množina uspořádaných dvojic prvků z G, je též prázdná. Připomeňme, co je zobrazení množiny A do množiny B. Je to uspořádaná trojice (A, B, f), kde f je podmnožina kartézského součinu A × B, v níž pro každé a ∈ A existuje právě jedna uspořádaná dvojice s první složkou a. Je-li tedy A = ∅, pak pro libovolnou množinu B takové zobrazení je jediné: f je také prázdná množina. Je-li naopak A = ∅ a současně B = ∅, pak takové zobrazení neexistuje. Proto tedy na nosné množině G = ∅ máme jediný grupoid, jehož (jedinou možnou) operací na G je prázdné zobrazení, tj. trojice (∅, ∅, ∅). A v čem spočívá výhoda toho považovat prázdnou množinu spolu s prázdným zobrazením za grupoid? Jisté výhody se začnou objevovat až v okamžiku, kdy definujeme podgrupoid grupoidu, tj. podmnožinu nosné množiny grupoidu uzavřenou vůči operaci grupoidu. Protože je rozumné chtít, aby (po zúžení operace) byl podgrupoid sám grupoidem, v případě, kdy grupoid definujeme jen na neprázdné nosné množině, je třeba v definici podgrupoidu přidat požadavek neprázdnosti podmnožiny (tedy podgrupoidem rozumět jen takovou neprázdnou podmnožinu, že součin libovolných dvou jejích prvků do ní patří). Ale pak neplatí, že průnikem dvou podgrupoidů daného grupoidu je opět podgrupoid, neboť tímto průnikem může být i prázdná množina. Při- 2 puštěním prázdného grupoidu tedy zjednodušíme definici podgrupoidu i větu o průniku podgrupoidů. A toto formální zjednodušování celé teorie, které jsme viděli na předchozím příkladě, obzvláště vynikne při studiu univerzálních algeber. Právě pod vlivem univerzální algebry jsem se rozhodl opustit svůj předchozí předpoklad neprázdnosti nosné množiny. Myslím si, že určité nepříjemnosti spojené s představou podivného prázdného grupoidu (později též prázdného svazu či prázdné univerzální algebry) jsou čtenáři vyváženy výhodami snadnějších formulací vět a definic. A když se už zabýváme prázdnou množinou, uvědomme si, jaké relace na prázdné množině máme: relací na množině M je libovolná podmnožina kartézského součinu M ×M, pro M = ∅ máme tedy jedinou relaci: prázdnou množinu. A protože pro všechny prvky prázdné množiny platí naprosto cokoli (uvědomte si, že implikace x ∈ ∅ =⇒ V je pravdivá pro všechna x a pro každé tvrzení V , neboť je nepravdivý předpoklad implikace x ∈ ∅), je tato prázdná relace ekvivalencí, ale i uspořádáním na M, které je dokonce dobré: každá neprázdná podmnožina (taková neexistuje) má nejmenší prvek. Promysleme si, jak vypadá rozklad na prázdné množině. Rozkladem na množině M rozumíme množinu neprázdných podmnožin množiny M (těmto podmnožinám říkáme třídy rozkladu) takovou, že každý prvek množiny M patří do právě jedné třídy rozkladu. Rozklad na prázdné množině M = ∅ tedy nemůže mít žádnou třídu rozkladu, neboť neexistuje žádná neprázdná podmnožina prázdné množiny M. Na druhou stranu prázdná množina je rozkladem na M = ∅, neboť pro každý prvek prázdné množiny platí zcela cokoli, například i to, že pro něj existuje třída rozkladu, do níž patří. Na prázdné množině tedy existuje jediný rozklad: prázdná množina. 1. Polosvazy Definice. Prvek x grupoidu (G, ·) se nazývá idempotentní, jestliže x·x = x. Definice. Komutativní pologrupa, jejíž každý prvek je idempotentní, se nazývá polosvaz. Poznámka. Podle předchozí definice tedy budeme i prázdný grupoid, který je samozřejmě komutativní i asociativní, považovat za polosvaz. Příklad. Pro libovolnou množinu X budeme (i v dalším textu) symbolem 2X označovat množinu všech podmnožin množiny X. Pak (2X , ∩) a (2X , ∪) jsou polosvazy. Příklad. Množina všech přirozených čísel N spolu s operací největší společný dělitel (resp. nejmenší společný násobek) tvoří polosvaz. 3 Poznámka. V následující větě použijeme právě učiněnou změnu definice grupoidu: grupoidem rozumíme i grupoid na prázdné množině, proto prázdná množina je podgrupoidem libovolného grupoidu. Protože existují komutativní pologrupy, v nichž žádný prvek není idempotentní (například (N, +)), museli bychom bez této změny následující větu formulovat takto: ” Nechť (G, ·) je komutativní pologrupa. Pak množina všech idempotentních prvků, je-li neprázdná, tvoří podgrupoid pologrupy (G, ·), který je polosva- zem.“ Věta 1.1. Nechť (G, ·) je komutativní pologrupa. Pak množina všech idempotentních prvků tvoří podgrupoid pologrupy (G, ·), který je polosvazem. Důkaz. Jsou-li x a y idempotentní, pak x·x = x a y ·y = y, odkud plyne (x · y) · (x · y) = x · x · y · y = x · y. Jde tedy skutečně o podgrupoid, zbytek tvrzení je zřejmý. Věta 1.2. Nechť (G, ≤) je uspořádaná množina, v níž k libovolným dvěma prvkům a, b ∈ G existuje supremum a ∨ b. Pak (G, ∨) je polosvaz. Navíc pro každé a, b ∈ G platí a ≤ b ⇐⇒ a ∨ b = b. Důkaz. Komutativita i idempotentnost je zřejmá, ekvivalence obou podmínek též. Pro libovolné a, b, c ∈ G jistě platí (a ∨ b) ∨ c ≥ c, (a ∨ b) ∨ c ≥ a ∨ b ≥ a, podobně (a ∨ b) ∨ c ≥ b. Je tedy (a ∨ b) ∨ c horní závora množiny {b, c}, proto (a ∨ b) ∨ c ≥ b ∨ c. Je tudíž (a ∨ b) ∨ c horní závora množiny {a, b ∨ c}, proto (a ∨ b) ∨ c ≥ a ∨ (b ∨ c). Analogicky opačná nerovnost, z antisymetrie asociativita. Věta 1.3. Nechť (G, ·) je polosvaz. Potom relace ≤, daná vztahem a ≤ b ⇐⇒ a · b = b pro každé a, b ∈ G, je uspořádání na G, ve kterém pro každé a, b ∈ G je a · b supremum množiny {a, b} v (G, ≤). Důkaz. Pro každé a, b, c ∈ G platí a · a = a =⇒ a ≤ a, a ≤ b, b ≤ a =⇒ a = b · a = a · b = b, a tedy je ≤ reflexivní a antisymetrická relace. Rovněž platí a ≤ b, b ≤ c =⇒ a · b = b, b · c = c =⇒ a · c = a · (b · c) = (a · b) · c = b · c = c =⇒ a ≤ c, 4 čímž jsme dokázali tranzitivitu. Je tedy ≤ uspořádání na G. Protože a · (a · b) = (a · a) · b = a · b, b · (a · b) = (b · a) · b = (a · b) · b = a · (b · b) = a · b, platí a ≤ a · b, b ≤ a · b. Nechť c je libovolná horní závora množiny {a, b} v (G, ≤), tedy a ≤ c, b ≤ c. Pak platí a · c = c, b · c = c, odkud (a · b) · c = a · (b · c) = a · c = c, tedy a · b ≤ c, je tedy a · b supremum množiny {a, b} v (G, ≤). Poznámka. Z dokázaných vět vyplývá následující Důsledek. Polosvazy jsou totéž co uspořádané množiny, kde ke každým dvěma prvkům existuje supremum. Poznámka. Princip duality: Nechť (G, ≤) je uspořádaná množina. Definujeme-li na G novou relaci takto: pro libovolné prvky a, b ∈ G klademe a b ⇐⇒ b ≤ a, pak je (G, ) opět uspořádaná množina, přičemž supremum v (G, ≤) se stane infimem v (G, ) a naopak. Důsledek. Polosvazy jsou totéž co uspořádané množiny, kde ke každým dvěma prvkům existuje infimum. 2. Svazy Definice. Uspořádaná množina, v níž ke každým dvěma prvkům existuje supremum i infimum, se nazývá svaz. Příklad. Každý řetězec (neboli lineárně uspořádaná množina, tj. uspořádaná množina, v níž jsou každé dva prvky srovnatelné) je svaz. Příklad. Pro libovolnou množinu X je (2X , ⊆) svaz. Věta 2.1. Nechť (G, ≤) je svaz. Pro libovolné prvky a, b ∈ G označme jejich supremum symbolem a∨b a jejich infimum symbolem a∧b. Pak (G, ∨) a (G, ∧) jsou polosvazy a obě operace jsou spolu svázány tzv. absorpčními zákony: pro každé prvky a, b ∈ G platí a ∨ (b ∧ a) = a ∧ (b ∨ a) = a. Kromě toho pro každé prvky a, b ∈ G platí a ∧ b = a ⇐⇒ a ≤ b ⇐⇒ a ∨ b = b. 5 Důkaz. To, že (G, ∨) a (G, ∧) jsou polosvazy, plyne z věty 1.2 a principu duality; rovněž tak ekvivalentnost uvedených podmínek. Absorpční zákony jsou zřejmé. Věta 2.2. Nechť (G, ∨, ∧) je množina se dvěma idempotentními, asociativními a komutativními operacemi, které jsou spolu svázány absorpčními zákony. Pak platí 1. pro každé prvky a, b ∈ G platí a ∧ b = a ⇐⇒ a ∨ b = b, 2. definujeme-li na G relaci ≤ takto: pro libovolné prvky a, b ∈ G klademe a ≤ b ⇐⇒ a ∨ b = b, pak je ≤ uspořádání na G takové, že (G, ≤) je svaz, v němž pro libovolné prvky a, b ∈ G je prvek a ∨ b jejich supremum a prvek a ∧ b jejich infimum. Důkaz. Nechť pro prvky a, b ∈ G platí a∧b = a. Pak a∨b = (a∧b)∨b = b∨(a∧b) = b dle absorpčního zákona. Opačná implikace analogicky. Ostatní plyne z věty 1.3. Poznámka. Z dokázaných vět vyplývá, že svazy jsou totéž co algebraické struktury (G, ∨, ∧) se dvěma idempotentními, asociativními a komutativními operacemi, svázanými spolu absorpčními zákony. Proto i tyto struktury (G, ∨, ∧) budeme také nazývat svazy. Poznámka. Princip duality: Je-li (G, ∨, ∧) svaz, pak i (G, ∧, ∨) je svaz. Obecně, jestliže v nějakém platném tvrzení o svazech systematicky zaměníme supremum ↔ infimum, ∨ ↔ ∧, ≤ ↔ ≥, dostaneme opět platné tvrzení o svazech. Poznámka. Protože není nutné zdůrazňovat, zda máme na mysli svaz jako uspořádanou množinu nebo jako algebraickou strukturu se dvěma operacemi, nebudeme v dalším textu, nebude-li to z nějakých důvodů vhodné nebo dokonce nevyhnutelné, uspořádání či operace vyznačovat. Budeme tedy místo o svazu (G, ≤) či svazu (G, ∨, ∧) jednoduše psát o svazu G. Věta 2.3. V libovolném svazu G pro každou trojici prvků a, b, c ∈ G platí tzv. distributivní nerovnosti (a ∨ b) ∧ (a ∨ c) ≥ a ∨ (b ∧ c), (a ∧ b) ∨ (a ∧ c) ≤ a ∧ (b ∨ c). Je-li navíc c ≤ a, platí tzv. modulární nerovnost (a ∧ b) ∨ c ≤ a ∧ (b ∨ c). 6 Důkaz. Jistě platí a∨b ≥ a, a∨c ≥ a, a tedy i (a∨b)∧(a∨c) ≥ a. Podobně a∨b ≥ b ≥ b∧c, a∨c ≥ c ≥ b∧c, odkud (a∨b)∧(a∨c) ≥ b∧c. Dohromady dostáváme první distributivní nerovnost. Druhou dokážeme analogicky, nebo lze užít principu duality a odvodit ji z první. Je-li navíc c ≤ a, platí a∧c = c, proto modulární nerovnost plyne z druhé distributivní nerovnosti. Věta 2.4. Nechť G je svaz, n ∈ N. Pro libovolné prvky a1, . . . , an ∈ G platí, že a1 ∨ · · · ∨ an je supremum množiny {a1, . . . , an} a a1 ∧ · · · ∧ an je infimum množiny {a1, . . . , an}. Důkaz. Indukcí vzhledem k n. 3. Podsvazy, ideály, filtry, homomorfismy Definice. Nechť (G, ∨, ∧) je svaz, A podmnožina jeho nosné množiny G. Řekneme, že A je podsvaz svazu (G, ∨, ∧), jestliže je A podgrupoidem grupoidu (G, ∧) a současně podgrupoidem grupoidu (G, ∨). Poznámka. Je tedy A ⊆ G podsvazem svazu G, právě když pro každé a, b ∈ A platí a ∨ b ∈ A a a ∧ b ∈ A. Příklady. Každá jednoprvková podmnožina svazu je jeho podsvazem, prázdná množina je podsvazem libovolného svazu, každý svaz je svým pod- svazem. Definice. Nechť G je svaz, A ⊆ G podmnožina. Řekneme, že A je ideál svazu G, jestliže je A podsvazem svazu G, který navíc splňuje podmínku: pro každé a ∈ A a každé x ∈ G platí x ≤ a =⇒ x ∈ A. Duálně, řekneme, že A je filtr svazu G, jestliže je A podsvazem svazu G, který navíc splňuje podmínku: pro každé a ∈ A a každé x ∈ G platí x ≥ a =⇒ x ∈ A. Poznámka. Ideál svazu je tedy podsvaz, který s každým svým prvkem a obsahuje i všechny prvky svazu menší než a, filtr svazu je podsvaz, který s každým svým prvkem a obsahuje i všechny prvky svazu větší než a. Příklady. Každý svaz je svým ideálem i filtrem. Prázdná množina je ideálem i filtrem libovolného svazu. Věta 3.1. Průnik libovolného neprázdného systému podsvazů (resp. ideálů, resp. filtrů) daného svazu je opět podsvaz (resp. ideál, resp. filtr) tohoto svazu. 7 Důkaz. Nechť I = ∅ a pro každé i ∈ I je Ai podsvaz svazu G. Označme A = i∈I Ai jejich průnik. Pak pro každé a, b ∈ A platí a, b ∈ Ai pro všechna i ∈ I, a tedy a ∨ b ∈ Ai a a ∧ b ∈ Ai. Odtud a ∨ b ∈ A a a ∧ b ∈ A, a proto je A podsvaz svazu G. Předpokládejme navíc, že pro každé i ∈ I je Ai dokonce ideál svazu G. Mějme a ∈ A, x ∈ G, x ≤ a. Pak pro každé i ∈ I je a ∈ Ai, tedy i x ∈ Ai, tudíž x ∈ A. Tvrzení o filtrech nyní plyne z duality. Poznámka. Zde nám opět to, že jsme připustili i prázdný podsvaz, zjednodušilo formulaci. Jinak by věta 3.1 musela být formulována takto: ” Průnik libovolného neprázdného systému podsvazů (resp. ideálů, resp. filtrů) daného svazu je opět podsvaz (resp. ideál, resp. filtr) tohoto svazu nebo prázdná množina.“ Důsledek. Průnik libovolného neprázdného konečného systému neprázdných ideálů (resp. filtrů) daného svazu je opět neprázdný ideál (resp. filtr) tohoto svazu. Důkaz. Jsou-li A1, . . . , An neprázdné ideály a zvolíme-li ai ∈ Ai, pak a = a1 ∧ · · · ∧ an ≤ ai, a tedy a ∈ Ai. Průnik tedy není prázdná množina. Duálně pro filtry. Příklad. Ukažme, že průnikem neprázdných ideálů v předchozí větě může být opravdu prázdná množina. Uvažme svaz celých čísel s obvyklým uspořádáním podle velikosti (Z, ≤). Pro libovolné n ∈ Z je An = {x ∈ Z; x ≤ n} ideál tohoto svazu. Ale n∈Z An je prázdná množina, neboť pro každé celé číslo m najdeme celé číslo n < m, pak ovšem m /∈ An, a tedy m nepatří do průniku všech ideálů An. Definice. Nechť G je svaz, A ⊆ G podmnožina. Díky předchozí větě můžeme nyní definovat ideál A↓ svazu G generovaný množinou A jako průnik všech ideálů tohoto svazu obsahujících množinu A. (Uvědomte si, že alespoň jeden ideál tohoto svazu obsahující množinu A existuje, totiž celý svaz G.) Duálně, filtr A↑ svazu G generovaný množinou A je průnik všech filtrů tohoto svazu obsahujících množinu A. Je-li A = {a}, píšeme stručně a↓ místo {a}↓, resp. a↑ místo {a}↑, a hovoříme o hlavním ideálu, resp. o hlavním filtru, generovaném prvkem a. Poznámka. Pro svaz G a podmnožinu A ⊆ G je ideál A↓ generovaný množinou A tím nejmenším (vzhledem k množinové inkluzi) ideálem svazu G ze všech ideálů obsahujících množinu A. Duálně filtr A↑ generovaný množinou A je tím nejmenším (vzhledem k množinové inkluzi) filtrem svazu G ze všech filtrů obsahujících množinu A. Poznámka. Je zřejmé, že podmnožina A ⊆ G je ideálem svazu G, právě když A↓ = A, a je filtrem svazu G, právě když A↑ = A. Věta 3.2. Nechť G je svaz, A ⊆ G podmnožina. Pro ideál A↓ generovaný 8 množinou A platí A↓ = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≤ a1 ∨ · · · ∨ an}. Duálně, pro filtr A↑ generovaný množinou A platí A↑ = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≥ a1 ∧ · · · ∧ an}. Důkaz. Každý ideál svazu G obsahující množinu A musí pro každé a1, . . . , an ∈ A obsahovat i a1 ∨ · · · ∨ an. Proto obsahuje i množinu B = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≤ a1 ∨ · · · ∨ an}. Je tedy A↓ ⊇ B. Stačí ověřit, že B je ideál obsahující A. Inkluze A ⊆ B je zřejmá, neboť pro a ∈ A lze volit n = 1 a a1 = a. Jistě B obsahuje s každým svým prvkem i všechny prvky svazu ještě menší, stačí tedy ověřit, že je B podsvaz. Nechť x, y ∈ B. Potom existují a1, . . . , an ∈ A tak, že x ≤ a1 ∨ · · · ∨ an, a existují b1, . . . , bm ∈ A tak, že y ≤ b1 ∨ · · · ∨ bm. Pak x ∧ y ≤ x ≤ a1 ∨ · · · ∨ an, a tedy x ∧ y ∈ B. Na druhou stranu x ≤ a1 ∨ · · · ∨ an ≤ (a1 ∨ · · · ∨ an) ∨ (b1 ∨ · · · ∨ bm), podobně y ≤ b1 ∨ · · · ∨ bm ≤ (a1 ∨ · · · ∨ an) ∨ (b1 ∨ · · · ∨ bm), odkud x ∨ y ≤ (a1 ∨ · · · ∨ an) ∨ (b1 ∨ · · · ∨ bm), proto x ∨ y ∈ B. Je tedy B podsvaz, což se právě mělo dokázat. Tvrzení o filtrech plyne z duality. Definice. Nechť (G, ≤), (H, ) jsou uspořádané množiny, f : G → H zobrazení. Řekneme, že je f izotonní zobrazení, jestliže pro každé a, b ∈ G platí implikace a ≤ b =⇒ f(a) f(b). Řekneme, že f je izomorfismus uspořádaných množin, je-li f bijekce a obě zobrazení f i f−1 jsou izotonní. Definice. Nechť G a H jsou svazy, f : G → H zobrazení. Řekneme, že je f svazový homomorfismus, jestliže pro každé a, b ∈ G platí f(a ∧ b) = f(a) ∧ f(b), f(a ∨ b) = f(a) ∨ f(b). Řekneme, že f je svazový izomorfismus (neboli izomorfismus svazů), je-li f bijektivní homomorfismus. Poznámka. Protože každý svaz je také uspořádaná množina, má smysl se ptát, zda svazový homomorfismus je též izotonní zobrazení. Věta 3.3. Nechť G a H jsou svazy, f : G → H zobrazení. 1. Je-li f svazový homomorfismus, pak f je izotonní zobrazení a homomorfní obraz f(G) = {f(a); a ∈ G} je podsvaz svazu H. 9 2. Zobrazení f je svazový izomorfismus, právě když f je izomorfismus uspořádaných množin. Důkaz. Dokažme nejprve první část věty. Je-li f svazový homomorfismus, pak pro každé a, b ∈ G z a ≤ b plyne a = a ∧ b, proto f(a) = f(a ∧ b) = f(a) ∧ f(b), a tedy f(a) ≤ f(b). Je tedy f izotonní. To, že f(G) je podsvaz svazu H, plyne přímo z definic. Dokažme nyní druhou část věty. Nechť je f nejdříve svazový izomorfismus, ukážeme, že pak f−1 je svazový homomorfismus. Zvolme libovolně c, d ∈ H a označme a = f−1 (c), b = f−1 (d). Pak platí f−1 (c ∨ d) = f−1 (f(a) ∨ f(b)) = f−1 (f(a ∨ b)) = a ∨ b = f−1 (c) ∨ f−1 (d), f−1 (c ∧ d) = f−1 (f(a) ∧ f(b)) = f−1 (f(a ∧ b)) = a ∧ b = f−1 (c) ∧ f−1 (d). Odvodili jsme, že f−1 je svazový homomorfismus. Aplikací první části věty na zobrazení f i f−1 dostaneme, že f je izomorfismus uspořádaných množin. Nechť nyní naopak f je izomorfismus uspořádaných množin, a, b ∈ G. Protože a ≤ a ∨ b, b ≤ a ∨ b a f je izotonní zobrazení, dostáváme f(a) ≤ f(a ∨ b), f(b) ≤ f(a ∨ b), je tedy f(a ∨ b) horní závora prvků f(a), f(b). Nechť c ∈ H je libovolný takový, že f(a) ≤ c, f(b) ≤ c. Protože f−1 je izotonní zobrazení, platí a ≤ f−1 (c), b ≤ f−1 (c), proto i a ∨ b ≤ f−1 (c), a protože f je izotonní zobrazení, dostáváme f(a ∨ b) ≤ c. To ale znamená, že f(a ∨ b) je supremum prvků f(a), f(b), tj. f(a) ∨ f(b) = f(a ∨ b). Analogicky (nebo z duality) pro infima. 4. Úplné svazy Poznámka. Podle věty 2.4 v libovolném svazu má každá neprázdná konečná podmnožina {a1, . . . , an} supremum a1 ∨· · ·∨an a infimum a1 ∧· · ·∧an. Nekonečná podmnožina však supremum či infimum obecně mít nemusí. Definice. Uspořádaná množina, v níž pro každou podmnožinu existuje supremum i infimum, se nazývá úplný svaz. Poznámka. Každý úplný svaz G má nejmenší prvek (infimum množiny G ve svazu G) a největší prvek (supremum množiny G ve svazu G). Poznámka. Promysleme si, co znamená infimum, resp. supremum, prázdné podmnožiny svazu G. Je-li A ⊆ G, pak infimum množiny A ve svazu G je největší dolní závora množiny A ve svazu G. Dolní závora množiny A ve svazu G je prvek x ∈ G takový, že pro každé a ∈ A platí x ≤ a. V případě A = ∅ je tato podmínka splněna pro každé x ∈ G, a tedy odtud plyne, že každý prvek svazu G je v G dolní závorou prázdné množiny. Proto infimem 10 prázdné množiny ve svazu G je největší prvek svazu G. Duálně: supremem prázdné množiny ve svazu G je nejmenší prvek svazu G. Příklady. Zřejmě platí, že každý úplný svaz je svazem a podle věty 2.4 je každý neprázdný konečný svaz úplným svazem. Příklad. Prázdný svaz není úplný, neboť pro jeho (jedinou) prázdnou podmnožinu neexistuje infimum ani supremum. Jinými slovy: prázdný svaz nemá nejmenší prvek ani největší prvek, protože nemá žádný prvek. Příklad. Pro libovolnou množinu X je (2X , ⊆) úplný svaz. Příklad. Pro libovolnou nekonečnou množinu X tvoří množina všech konečných podmnožin množiny X spolu s inkluzí ⊆ svaz, který není úplným svazem. Příklad. Nekonečný řetězec nemusí být úplný svaz (například (N, ≤) není úplný svaz, neboť neexistuje supremum celé množiny N). Věta 4.1. Nechť (G, ≤) je uspořádaná množina. Následující podmínky jsou ekvivalentní: 1. (G, ≤) je úplný svaz. 2. (G, ≤) má nejmenší prvek a každá neprázdná podmnožina množiny G má v uspořádané množině (G, ≤) supremum. 3. (G, ≤) má největší prvek a každá neprázdná podmnožina množiny G má v uspořádané množině (G, ≤) infimum. Poznámka. Vzhledem k předchozí poznámce víme, že podmínku 2 lze formulovat stručněji takto: každá podmnožina množiny G má v uspořádané množině (G, ≤) supremum. Analogicky pro podmínku 3: každá podmnožina množiny G má v uspořádané množině (G, ≤) infimum. Důkaz. Snadno se vidí, že druhá a třetí podmínka jsou navzájem duální, zatímco první podmínka je duální sama k sobě. Stačí tedy ukázat, že první je ekvivalentní s druhou, ekvivalenci první s třetí pak dostaneme z duality. Ihned z definice úplného svazu je vidět, že z první podmínky plyne druhá. Předpokládejme tedy, že uspořádaná množina (G, ≤) má nejmenší prvek a každá neprázdná podmnožina množiny G má v (G, ≤) supremum, a ukažme, že (G, ≤) je úplný svaz. Pak tedy i celá množina G má v (G, ≤) supremum, což musí být největší prvek uspořádané množiny (G, ≤). Proto prázdná množina má v (G, ≤) infimum. Nechť A je neprázdná podmnožina množiny G a ukažme, že má v (G, ≤) infimum. Označme B množinu všech dolních závor množiny A, tj. B = {x ∈ S; ∀a ∈ A : x ≤ a}. 11 Množina B je neprázdná, neboť jistě obsahuje nejmenší prvek uspořádané množiny (G, ≤). Proto podle předpokladů má B supremum, které označíme m. Ukážeme-li, že m ∈ B, bude pak m největší ze všech dolních závor množiny A, tedy její infimum, a budeme hotovi. Pro libovolné a ∈ A platí x ≤ a pro všechna x ∈ B, proto a je horní závora množiny B. Ovšem m je její supremum, tedy m ≤ a. To však platí pro všechny a ∈ A, a proto m ∈ B, což jsme chtěli dokázat. Příklad. Svaz všech podgrup dané grupy G je dle předchozí věty úplný svaz, neboť má největší prvek (celou grupu G) a každá neprázdná množina podgrup má v tomto svazu infimum, kterým je průnik těchto podgrup (to, že jejich průnikem je opět podgrupa, jsme dokazovali kvůli definici podgrupy generované podmnožinou grupy). Rovněž svaz všech podsvazů (popřípadě svaz ideálů nebo svaz filtrů) daného svazu je úplný svaz (viz větu 3.1). Díky analogickým větám o průnicích neprázdných systémů nějakých podstruktur lze totéž říci i o svazu všech podokruhů daného okruhu nebo o svazu jeho ideálů, o svazu všech podtěles daného tělesa nebo o svazu všech podprostorů daného vektorového prostoru. Příklad. (N∪{∞}, ≤) je dle předchozí věty úplný svaz, neboť má největší prvek ∞ a každá neprázdná podmnožina množiny N∪{∞} má v (N∪{∞}, ≤) infimum (plyne z dobré uspořádanosti). Příklad. Ze svazu (N, |), který není úplný, lze doplněním nuly (která se stane jeho největším prvkem) utvořit úplný svaz (N ∪ {0}, |). Poznámka. Jak ukazuje následující věta, předchozí případy nebyly nijak výjimečné: vždy existuje způsob, jak doplnit svaz tak, aby se stal úplným. Věta 4.2. Nechť G je svaz. Pak existuje úplný svaz U, který obsahuje podsvaz H, který je izomorfní se svazem G. Důkaz. Je jasné, že stačí najít vhodný úplný svaz U a injektivní svazový homomorfismus f : G → U. Pak je totiž f(G) podsvaz svazu U a zúžením oboru hodnot dostaneme svazový izomorfismus f : G → f(G). Nechť U značí množinu všech ideálů svazu G. Ve větě 3.1 jsme ukázali, že průnik libovolného neprázdného systému prvků z U je opět prvkem U. Protože uspořádaná množina (U, ⊆) má největší prvek G, je to dle předchozí věty úplný svaz. Přitom pro libovolné dva prvky A, B ∈ U je jejich infimem A ∧ B = A ∩ B množinový průnik, jejich supremem A ∨ B = (A ∪ B)↓ je ideál generovaný množinovým sjednocením. Uvažme zobrazení f : G → U, které každý prvek svazu G zobrazí na ideál jím generovaný: pro každé a ∈ G klademe f(a) = a↓. Podle věty 3.2 je tedy f(a) = {x ∈ G; x ≤ a}. Odtud plyne, že f je injekce: jsou-li totiž a, b ∈ G takové, že f(a) = f(b), pak a ∈ b↓, odkud a ≤ b, analogicky b ≤ a, dohromady a = b. 12 Budeme hotovi, ukážeme-li, že f je svazový homomorfismus. Nechť a, b ∈ G jsou libovolné. Máme ukázat, že f(a ∧ b) = f(a) ∧ f(b), f(a ∨ b) = f(a) ∨ f(b), což znamená (a ∧ b)↓ = a↓ ∩ b↓, (a ∨ b)↓ = (a↓ ∪ b↓)↓. Nejprve ukážeme obě inkluze dokazující první rovnost. Protože a ∧ b ≤ a, a ∧ b ≤ b, platí a ∧ b ∈ a↓ ∩ b↓, odkud (a ∧ b)↓ ⊆ a↓ ∩ b↓. Naopak, je-li x ∈ a↓ ∩ b↓, je x ≤ a, x ≤ b, tedy x ≤ a ∧ b, neboli x ∈ (a ∧ b)↓. Nyní se zaměřme na druhou rovnost. Z nerovností a ≤ a ∨ b, b ≤ a ∨ b, plynou inkluze a↓ ⊆ (a ∨ b)↓, b↓ ⊆ (a ∨ b)↓, odkud a↓ ∪ b↓ ⊆ (a ∨ b)↓ a proto i (a↓ ∪ b↓)↓ ⊆ a ∨ b↓. Na druhou stranu platí a, b ∈ (a↓ ∪ b↓)↓, proto i a ∨ b ∈ (a↓ ∪ b↓)↓, odkud (a ∨ b)↓ ⊆ (a↓ ∪ b↓)↓. Věta 4.3 (Tarski). Nechť G je úplný svaz, ϕ : G → G izotonní zobrazení. Pak existuje prvek a ∈ G tak, že ϕ(a) = a (tj. a je pevný bod zobrazení ϕ). Důkaz. V úplném svazu existuje nejmenší prvek (infimum celého svazu); označme jej 0. Pak jistě 0 ≤ ϕ(0), a proto množina A = {x ∈ G; x ≤ ϕ(x)} je neprázdná. Označme a supremum množiny A (to existuje, neboť svaz je úplný). Pro každé x ∈ A tedy platí x ≤ a, a proto z izotonie ϕ(x) ≤ ϕ(a), což spolu s x ≤ ϕ(x) (vždyť x ∈ A) dává x ≤ ϕ(a). Je tedy ϕ(a) horní závora množiny A, tedy její supremum a ≤ ϕ(a). Z izotonie ϕ(a) ≤ ϕ(ϕ(a)), ale to znamená ϕ(a) ∈ A. Ovšem a je supremum množiny A, proto ϕ(a) ≤ a. Celkem tedy a = ϕ(a). 5. Součin svazů Poznámka. Podobně jako jsme součinem grup (G, ·), (H, ·) získali grupu (G × H, ·) na kartézském součinu nosičů obou grup, můžeme součinem svazů získat nový svaz. Konstrukce bude naprosto stejná: operace na uspořádaných dvojicích se provedou nezávisle v každé složce. Definice. Nechť (G, ∨, ∧), (H, ∨, ∧) jsou svazy. Na kartézském součinu G × H definujme nové operace ∨ a ∧ takto: pro každé g1, g2 ∈ G, h1, h2 ∈ H klademe (g1, h1) ∨ (g2, h2) = (g1 ∨ g2, h1 ∨ h2). (g1, h1) ∧ (g2, h2) = (g1 ∧ g2, h1 ∧ h2). 13 Věta 5.1. Za předpokladů učiněných v předchozí definici tvoří (G × H, ∨, ∧) svaz. Důkaz. Důkaz je velmi snadný, ukažme například, že operace ∨ je komutativní: Pro každé g1, g2 ∈ G, h1, h2 ∈ H platí (g1, h1) ∨ (g2, h2) = (g1 ∨ g2, h1 ∨ h2) = (g2 ∨ g1, h2 ∨ h1) = (g2, h2) ∨ (g1, h1). Všechny ostatní potřebné rovnosti se dokáží analogicky, vždy se využije, že dokazovaná rovnost platí v každém z obou svazů. Poznámka. Jak jsme viděli v předchozím důkaze, v součinu svazů platí všechny rovnosti platné v obou svazech. Vlastnosti, které se však nedají vyjádřit jako konjunkce rovností, už součin svazů zdědit nemusí. Například vlastnost být řetězec můžeme zachytit takto: pro každé dva prvky x, y platí x ≤ y nebo x ≥ y, což pomocí svazových operací lze zapsat podmínkou x ∧ y = x nebo x ∧ y = y. To ale není konjunkce rovností, ale disjunkce. A skutečně, tato vlastnost se součinem nedědí: součinem dvou dvouprvkových řetězců je čtyřprvkový svaz, který není řetězec (to, že to tak opravdu dopadne, si promyslete sami). Poznámka. Podobně jako součin dvou svazů jsme mohli definovat i součin n svazů pro libovolné n ∈ N: na kartézském součinu nosných množin daných svazů se nové operace ∨ a ∧ definují po složkách. 6. Modulární svazy Poznámka. Viděli jsme ve větě 2.3, že v libovolném svazu G pro každou trojici prvků a, b, c ∈ G takových, že c ≤ a, platí modulární nerovnost (a ∧ b) ∨ c ≤ a ∧ (b ∨ c). Definice. Svaz G se nazývá modulární, jestliže pro každou trojici prvků a, b, c ∈ G takových, že c ≤ a, platí modulární rovnost (a ∧ b) ∨ c = a ∧ (b ∨ c). Příklad. Příklady modulárních svazů jsou svaz (2X , ∪, ∩) všech podmnožin nějaké množiny X nebo libovolný řetězec. Příklad. Ukážeme, že svaz N5, zvaný též pětiúhelník, není modulární, kdežto svaz M5, zvaný též diamant, modulární je (viz Hasseovy diagramy na následujícím obrázku). Označme 0 < c < a < 1 ony čtyři prvky, které jsou 14 v Hasseově diagramu svazu N5 nakresleny nad sebou vlevo, a b jeho pátý prvek. Pak nerovnost (a ∧ b) ∨ c = 0 ∨ c = c < a = a ∧ 1 = a ∧ (b ∨ c). ukazuje, že svaz N5 není modulární. • ////////////// ~~~~~~~ • •  • @@@@@@@ • • 1111111111111 • 1111111111111 • • • Svaz N5 (pětiúhelník) Svaz M5 (diamant) Nyní probírkou všech možností dokažme, že svaz M5 je modulární. Označme 0 nejmenší a 1 největší prvek tohoto svazu. Nechť tedy a, b, c ∈ M5 jsou libovolné takové, že c ≤ a. Jestliže a = c, plyne modulární rovnost z absorpčních zákonů. Jestliže c < a, pak na Hasseově diagramu svazu M5 vidíme, že buď c = 0 nebo a = 1. V obou případech je modulární rovnost zřejmá. Věta 6.1. Svaz všech normálních podgrup dané grupy je modulární. Důkaz. Nechť (H, ·) je grupa, K, L její podgrupy. Každá podgrupa grupy (H, ·), obsahující obě podgrupy K, L, musí obsahovat i množinu K · L = {k · l; k ∈ K, l ∈ L}. Tato množina obecně nemusí být podgrupou grupy (H, ·). Ukažme, že pokud je K dokonce normální podgrupa grupy (H, ·), pak je K ·L podgrupou grupy (H, ·). Jistě K · L = ∅. Pro libovolné k ∈ K, l ∈ L platí (k · l)−1 = l−1 · k−1 = (l−1 · k−1 · l) · l−1 ∈ K · L, neboť l−1 · k−1 · l ∈ K díky tomu, že K je normální podgrupa grupy (H, ·). Podobně pro libovolné k1, k2 ∈ K, l1, l2 ∈ L platí (k1 · l1) · (k2 · l2) = k1 · (l1 · k2 · l−1 1 ) · (l1 · l2) ∈ K · L, neboť opět l1 ·k2 ·l−1 1 ∈ K. Dokázali jsme, že K ·L je podgrupou grupy (H, ·). Protože K · L obsahuje podgrupy K i L, je tedy K · L nejmenší podgrupou 15 grupy (H, ·) obsahující obě podgrupy K, L. Přitom platí, že pokud jsou obě K i L normálními podgrupami grupy (H, ·), pak je K·L též normální podgrupou grupy (H, ·). Totiž pro libovolné h ∈ H a libovolné k ∈ K, l ∈ L platí h · (k · l) · h−1 = (h · k · h−1 ) · (h · l · h−1 ) ∈ K · L, což bylo třeba dokázat. Označme S množinu všech normálních podgrup grupy (H, ·). Protože průnikem normálních podgrup je normální podgrupa, je (S, ⊆) svaz, v němž pro libovolné K, L ∈ S platí K ∧ L = K ∩ L, K ∨ L = K · L. Dokážeme, že je tento svaz modulární. Zvolme proto libovolně K, L, M ∈ S tak, že M ⊆ K. Pak platí (K ∧ L) ∨ M = (K ∩ L) · M, K ∧ (L ∨ M) = K ∩ (L · M). Máme tedy ukázat, že platí (K ∩ L) · M ⊇ K ∩ (L · M), neboť opačná inkluze je modulární nerovnost platná v každém svazu (věta 2.3). Nechť je tedy k ∈ K ∩ (L · M) libovolné. Pak existují l ∈ L, m ∈ M takové, že platí l · m = k. Z M ⊆ K plyne m ∈ K, odkud l = k · m−1 ∈ K. Je tedy l ∈ (K ∩ L) a platí k = l · m ∈ (K ∩ L) · M, což jsme chtěli dokázat. Důsledek. Svaz všech podgrup dané komutativní grupy je modulární. Důkaz. V komutativní grupě je každá podgrupa normální. Věta 6.2. Podsvaz modulárního svazu je modulární svaz. Důkaz. Plyne přímo z definice: v podsvazu se suprema i infima počítají jako v původním svazu, proto je tam i stejné uspořádání. Příklad. Svaz všech podprostorů daného vektorového prostoru V nad tělesem T je podle předchozí věty modulární. Je totiž podsvazem modulárního svazu všech podgrup grupy vektorů V – k tomu si stačí uvědomit, že každý podprostor je podgrupou, a ověřit, že infima i suprema se ve svazu všech podprostorů počítají stejně jako ve svazu podgrup: infimem je množinový průnik a supremem součet podprostorů. Věta 6.3. Svaz G je modulární, právě když pro každou trojici prvků a, b, c ∈ G platí (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ (a ∧ c)). Důkaz. Je-li svaz modulární, plyne předchozí rovnost z modulární rovnosti pro prvky a, b, a∧c a zřejmé nerovnosti a∧c ≤ a. Naopak, nechť svaz G 16 splňuje rovnost této věty a nechť a, b, c ∈ G jsou libovolné takové, že c ≤ a. Pak platí a ∧ c = c, a tedy (a ∧ b) ∨ c = (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ (a ∧ c)) = a ∧ (b ∨ c), což jsme měli dokázat. Důsledek. Součin modulárních svazů je modulární svaz. Homomorfní obraz modulárního svazu je modulární svaz. Důkaz. Už jsme zmiňovali v důkaze věty 5.1, že součin zdědí libovolnou rovnost platnou v obou svazech. Také tvrzení o homomorfních obrazech plyne z toho, že modularita je charakterizována rovností. Věta 6.4. Svaz G je modulární, právě když pro každou trojici prvků a, b, c ∈ G platí implikace a ≥ c, a ∧ b = c ∧ b, a ∨ b = c ∨ b =⇒ a = c. (1) Důkaz. Předpokládejme, že svaz G je modulární a že pro trojici prvků a, b, c ∈ G platí c ≤ a, a ∧ b = c ∧ b, a ∨ b = c ∨ b. Pak z absorpčních zákonů a modulární rovnosti plyne c = (c ∧ b) ∨ c = (a ∧ b) ∨ c = a ∧ (b ∨ c) = a ∧ (b ∨ a) = a. Naopak, předpokládejme, že ve svazu G platí implikace (1), a dokažme, že svaz je modulární. Zvolme libovolně trojici prvků a, b, c ∈ G tak, že c ≤ a, a označme x = (a ∧ b) ∨ c, y = a ∧ (b ∨ c). Z modulární nerovnosti (věta 2.3) víme, že x ≤ y. Ukážeme-li, že též platí x ∧ b = y ∧ b, x ∨ b = y ∨ b, podle implikace (1) dostaneme x = y, což je modulární rovnost pro prvky a, b, c. Z x ≤ y plyne x ∨ b ≤ y ∨ b, neboť z y ∨ b ≥ y ≥ x, y ∨ b ≥ b je jasné, že y ∨ b je horní závora prvků x, b. Analogicky x ∧ b ≤ y ∧ b. Ovšem x ∨ b = ((a ∧ b) ∨ c) ∨ b = ((a ∧ b) ∨ b) ∨ c = b ∨ c, jistě b ∨ c ≥ a ∧ (b ∨ c) = y a b ∨ c ≥ b. To pak znamená x ∨ b = b ∨ c ≥ y ∨ b, což spolu s dříve odvozenou opačnou nerovností znamená x ∨ b = y ∨ b. Analogicky y ∧ b = (a ∧ (b ∨ c)) ∧ b = a ∧ ((b ∨ c) ∧ b) = a ∧ b ≤ (a ∧ b) ∨ c = x, jistě též y ∧ b = a ∧ b ≤ b, proto y ∧ b ≤ x ∧ b, opět s opačnou nerovností dostáváme potřebnou rovnost x ∧ b = y ∧ b. Poznámka. Následující věta ukazuje, že modularitu je možné charakterizovat pomocí svazu N5 (tj. pětiúhelníku, viz Hasseův diagram na straně 15). 17 Věta 6.5. Svaz G je modulární, právě když neobsahuje podsvaz izomorfní se svazem N5. Důkaz. Je-li svaz G modulární, pak podle věty 6.2 je každý jeho podsvaz modulární, proto svaz G neobsahuje podsvaz izomorfní se svazem N5, neboť ten modulární není. Naopak, předpokládejme, že svaz G není modulární. Podle předchozí věty existují a, b, c ∈ G tak, že ačkoliv platí a ≥ c, a∧b = c∧b, a∨b = c∨b, přesto a = c. Tedy a > c. Snadno se ověří, že pak nemůže nastat žádný z případů b ≥ c (pak by totiž b = b ∨ c = b ∨ a, tedy b ≥ a, odkud b ∧ a = a > c = b ∧ c) ani b ≤ a (pak by b = b∧a = b∧c, tedy b ≤ c, odkud b∨c = c < a = b∨a). Je tedy b s každým z prvků a, c nesrovnatelný. Proto jsou prvky a, b, c, a∧b, a∨b různé. Zřejmě tvoří pětiprvkový podsvaz svazu G izomorfní se svazem N5. Důsledek. Duální svaz k modulárnímu svazu je opět modulární. Důkaz. Plyne z toho, že duální svaz ke svazu N5 je izomorfní s N5, a toho, že dualitou se podsvazy převádějí na podsvazy. Poznámka. Předchozí důsledek je také možné snadno dokázat přímo: podmínka, kterou jsou modulární svazy definovány, je samoduální. 7. Distributivní svazy Poznámka. Podle věty 2.3 v libovolném svazu G pro každou trojici prvků a, b, c ∈ G platí distributivní nerovnosti (a ∨ b) ∧ (a ∨ c) ≥ a ∨ (b ∧ c), (a ∧ b) ∨ (a ∧ c) ≤ a ∧ (b ∨ c). Definice. Svaz G se nazývá distributivní, jestliže pro každou trojici prvků a, b, c ∈ G platí distributivní rovnost (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ c). Příklad. Příklady distributivních svazů jsou svaz všech podmnožin nějaké množiny nebo libovolný řetězec. Příklad. Ověřte sami, že svazy N5 (pětiúhelník) a M5 (diamant) nejsou distributivní (viz Hasseovy diagramy na obrázku na straně 15). V obou svazech při ověřování zvolte tři různé prvky a, b, c tak, aby b bylo nesrovnatelné s a i c (a v N5 navíc a > c). Věta 7.1. Nechť G je distributivní svaz. Pak pro každou trojici prvků a, b, c ∈ G platí i následující distributivní rovnost (a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c). 18 Důkaz. Z distributivity a absorpčního zákona dostáváme (a ∨ b) ∧ (a ∨ c) = ((a ∨ b) ∧ a) ∨ ((a ∨ b) ∧ c) = a ∨ ((a ∧ c) ∨ (b ∧ c)) = = (a ∨ (a ∧ c)) ∨ (b ∧ c) = a ∨ (b ∧ c). Poznámka. Duální tvrzení k předchozí větě znamená, že z podmínky z věty plyne podmínka z definice. Je tedy lhostejné, kterou z obou distributivních rovností užijeme v definici, mohli jsme užít i obě najednou. Důsledek. Duální svaz k distributivnímu svazu je opět distributivní. Věta 7.2. Každý distributivní svaz je modulární. Důkaz. Předpokládejme, že G je distributivní svaz, a, b, c ∈ G jsou takové, že c ≤ a. Pak platí a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) = (a ∧ b) ∨ c, což je modulární rovnost. Věta 7.3. Podsvaz distributivního svazu je distributivní svaz. Důkaz. Plyne přímo z definice: v podsvazu se suprema i infima počítají jako v původním svazu. Věta 7.4. Součin distributivních svazů je distributivní svaz. Homomorfní obraz distributivního svazu je distributivní svaz. Důkaz. Plyne z toho, že vlastnost být distributivní je definována rov- ností. Věta 7.5. Svaz G je distributivní, právě když pro každou trojici prvků a, b, c ∈ G platí implikace a ∧ b = c ∧ b, a ∨ b = c ∨ b =⇒ a = c. (2) Důkaz. Předpokládejme, že svaz G je distributivní a že pro trojici prvků a, b, c ∈ G platí a ∧ b = c ∧ b, a ∨ b = c ∨ b. Pak z absorpčních zákonů a distributivity plyne c = (c ∧ b) ∨ c = (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c) = = (a ∨ c) ∧ (a ∨ b) = a ∨ (c ∧ b) = a ∨ (a ∧ b) = a. Naopak, předpokládejme, že svaz G splňuje implikaci (2). Podle věty 6.4 je G modulární, neboť splňuje implikaci (1). Nechť x, y, z ∈ G jsou libovolné. Označme a = ((y ∨ x) ∧ z) ∨ (x ∧ y), b = y, c = ((y ∨ z) ∧ x) ∨ (z ∧ y). 19 Tyto definice jsou voleny tak, že při záměně x ↔ z se zamění a ↔ c. Protože x ∧ y ≤ y ∨ x, z modularity plyne a = (y ∨ x) ∧ (z ∨ (x ∧ y)), a podobně c = (y ∨ z) ∧ (x ∨ (z ∧ y)). Z komutativity, absorpce a modularity (díky x ∧ y ≤ y) plyne a∧b = b∧a = y ∧(y ∨x)∧(z ∨(x∧y)) = y ∧(z ∨(x∧y)) = (y ∧z)∨(x∧y). Stejnými úpravami při záměně a ↔ c a x ↔ z c ∧ b = b ∧ c = y ∧ (y ∨ z) ∧ (x ∨ (z ∧ y)) = y ∧ (x ∨ (z ∧ y)) = (y ∧ x) ∨ (z ∧ y). Je tedy a ∧ b = c ∧ b. Z absorpce a modularity (díky y ≤ y ∨ x) dále plyne a ∨ b = ((y ∨ x) ∧ z) ∨ (x ∧ y) ∨ y = ((y ∨ x) ∧ z) ∨ y = (y ∨ x) ∧ (z ∨ y). Stejnými úpravami při záměně a ↔ c a x ↔ z c ∨ b = ((y ∨ z) ∧ x) ∨ (z ∧ y) ∨ y = ((y ∨ z) ∧ x) ∨ y = (y ∨ z) ∧ (x ∨ y). Je tedy také a ∨ b = c ∨ b, což spolu s a ∧ b = c ∧ b pomocí implikace (2) dává a = c. Z absorpce a modularity (díky x ∧ y ≤ x) dostáváme x ∧ a = x ∧ (y ∨ x) ∧ (z ∨ (x ∧ y)) = x ∧ (z ∨ (x ∧ y)) = (x ∧ z) ∨ (x ∧ y). Podobně z komutativity a absorpce x ∧ c = x ∧ (y ∨ z) ∧ (x ∨ (z ∧ y)) = x ∧ (x ∨ (z ∧ y)) ∧ (y ∨ z) = x ∧ (y ∨ z) Celkem tedy z toho, že a = c, a z komutativity plyne x ∧ (y ∨ z) = x ∧ c = x ∧ a = (x ∧ y) ∨ (x ∧ z). Protože x, y, z ∈ G byly libovolné, znamená to, že G je distributivní svaz, což jsme měli dokázat. Poznámka. Z následující věty a věty 6.5 plyne analogie věty 6.5 pro distributivní svazy: Svaz G je distributivní, právě když neobsahuje ani podsvaz izomorfní se svazem M5 (tj. diamant) ani podsvaz izomorfní se svazem N5 (tj. pětiúhelník, viz Hasseovy diagramy na straně 15). Věta 7.6. Modulární svaz G je distributivní, právě když neobsahuje podsvaz izomorfní se svazem M5. 20 Důkaz. Je-li svaz G distributivní, pak podle věty 7.3 je každý jeho podsvaz distributivní, proto svaz G neobsahuje podsvaz izomorfní se svazem M5, neboť ten distributivní není. Naopak, předpokládejme, že svaz G není distributivní. Podle předchozí věty existují a, b, c ∈ G tak, že ačkoliv platí a ∧ b = c ∧ b, a ∨ b = c ∨ b, přesto a = c. Kdyby a ≤ c nebo c ≤ a, podle věty 6.4 by z modularity svazu plynulo a = c, což neplatí. Jsou tedy a a c nesrovnatelné. Označme i = a ∧ b = c ∧ b, s = a ∨ b = c ∨ b, m = ((a ∨ c) ∧ b) ∨ (a ∧ c). Je zřejmé, že i ≤ c, a tedy i = i ∧ c = a ∧ b ∧ c. Podobně s = a ∨ b ∨ c. Z absorpce a modularity (díky a ≤ a ∨ c) plyne m ∨ a = ((a ∨ c) ∧ b) ∨ (a ∧ c) ∨ a = ((a ∨ c) ∧ b) ∨ a = (a ∨ c) ∧ (b ∨ a). Ovšem b ∨ a = s = a ∨ b ∨ c ≥ a ∨ c, odkud m ∨ a = a ∨ c. Analogicky (záměnou a ↔ c) se dokáže, že m ∨ c = a ∨ c. Protože a ∧ c ≤ a ∨ c, plyne z modularity m = (a ∨ c) ∧ (b ∨ (a ∧ c)). Z absorpce a modularity (díky a ∧ c ≤ a) plyne m∧a = a∧m = a∧(a∨c)∧(b∨(a∧c)) = a∧(b∨(a∧c)) = (a∧b)∨(a∧c). Ovšem a ∧ b = i = a ∧ b ∧ c ≤ a ∧ c, odkud m ∧ a = a ∧ c. Analogicky (záměnou a ↔ c) se dokáže, že m ∧ c = a ∧ c. Tvoří tedy {a, c, m, a ∨ c, a ∧ c} podsvaz svazu G. Ukažme, že c a m jsou nesrovnatelné. Z c ≤ m plyne c = m∧c = a∧c, odkud c ≤ a, spor. Podobně z c ≥ m plyne c = m∨c = c∨a, odkud a ≤ c, opět spor. Analogicky (záměnou a ↔ c) se dokáže, že a a m jsou nesrovnatelné. Proto podsvaz {a, c, m, a ∨ c, a ∧ c} svazu G je izomorfní se svazem M5, což jsme chtěli dokázat. Poznámka. Na závěr kapitoly o distributivních svazech si uvedeme charakterizaci konečných distributivních svazů. Definice. Prvek a svazu G se nazývá ∨-nedosažitelný, jestliže pro každé b, c ∈ G takové, že a = b ∨ c, platí a = b nebo a = c. Poznámka. Prvek a svazu G je tedy ∨-nedosažitelný, jestliže není supremem žádných dvou prvků ostře menších než on, tj. neexistují b, c ∈ G splňující b < a, c < a, a = b ∨ c. Ekvivalentně lze tuto podmínku vyjádřit také takto: prvek a svazu G je ∨-nedosažitelný, jestliže pro každé b, c ∈ G takové, že b < a a současně c < a, platí b ∨ c < a. Odtud se snadno dokáže indukcí, 21 že takový prvek není supremem ani žádné neprázdné konečné množiny prvků ostře menších než on. Označení. Množinu všech ∨-nedosažitelných prvků svazu G označíme J(G). Věta 7.7. V konečném svazu G je libovolný prvek a roven supremu množiny všech ∨-nedosažitelných prvků, které neostře převyšuje, tj. a = b∈J(G), b≤a b = (a↓ ∩ J(G)). Důkaz. Budeme postupovat indukcí vzhledem k počtu m prvků svazu G, které jsou menší než a. Je-li m = 0, je a nejmenší prvek svazu G, který je ∨-nedosažitelný, proto {a} = a↓ ∩ J(G) a tedy tvrzení pro a platí. Předpokládejme tedy, že m > 0 a že pro všechny prvky, které převyšující v G méně než m prvků, byla již věta dokázána. Nechť a ∈ G je libovolný. Pokud a ∈ J(G), zřejmě je a největším prvkem množiny a↓∩J(G) a dokazovaná podmínka je pro něj zřejmě splněna. Nechť tedy a /∈ J(G), pak existují b, c ∈ G splňující b < a, c < a, a = b ∨ c. Zřejmě oba prvky převyšují méně než m prvků, a tedy pro ně podmínka věty platí. Tedy a = b ∨ c = (b↓ ∩ J(G)) ∨ (c↓ ∩ J(G)) = D, kde D = (b↓∪c↓)∩J(G) ⊆ a↓∩J(G). Odtud D ≤ (a↓∩J(G)). Současně a je horní závora množiny a↓ ∩ J(G), a tedy a ≥ (a↓ ∩ J(G)). Celkem tedy platí rovnost, kterou jsme chtěli dokázat. Definice. Nechť (A, ≤) je uspořádaná množina. Množina B ⊆ A se nazývá (dolů) dědičná, pokud pro každý prvek b ∈ B a každý a ∈ A, a ≤ b, platí a ∈ B. Poznámka. Množina B ⊆ A je tedy dědičná, jestliže s každým svým prvkem obsahuje všechny prvky množiny A, které jsou ještě menší. Pomocí této vlastnosti můžeme charakterizovat ideály svazu: jsou to právě dědičné podsvazy. Připomeňme, že na svazy se můžeme dívat jako na uspořádané množiny a že dva svazy jsou izomorfní, právě když jsou izomorfní jako uspořádané množiny (věta 3.3). Označení. Množinu všech neprázdných dědičných podmnožin uspořádané množiny A značíme D(A). Věta 7.8. Pro konečný distributivní svaz G uvažme množinu J(G) všech ∨-nedosažitelných prvků svazu G spolu s uspořádáním, které na J(G) indukuje uspořádání svazu G. Pak uspořádaná množina (D(J(G)), ⊆) je izomorfní se svazem G (chápaným jako uspořádaná množina). 22 Důkaz. Je-li G prázdný svaz, je i D(J(G)) prázdná množina a tedy věta platí. Dále předpokládejme, že G je neprázdný. Definujeme zobrazení η : G → D(J(G)) předpisem η(a) = a↓∩J(G). Zřejmě a↓ je dědičná množina v G a její průnik s J(G) je dědičnou množinou v J(G). Navíc a↓ ∩ J(G) obsahuje nejmenší prvek svazu G, a tedy je prvkem D(J(G)). Ukážeme, že se jedná o izotonní zobrazení. Nechť a, b ∈ G jsou libovolné takové, že a ≤ b. Pak a↓ ⊆ b↓, tedy η(a) = a↓ ∩ J(G) ⊆ b↓ ∩ J(G) = η(b). Podle věty 7.7 pro každé a ∈ G platí a = η(a), je tedy η injektivní: jestliže pro a, b ∈ G platí η(a) = η(b), pak a = η(a) = η(b) = b. Ukažme, že je také η surjektivní. Zvolme libovolně X ∈ D(J(G)), tedy X je neprázdná dědičná podmnožina J(G). Pišme X = {x1, . . . , xn}. Chceme najít a ∈ G tak, aby η(a) = X. Položme a = X = x1 ∨ · · · ∨ xn, pak pro každé i = 1, . . . , n platí a ≥ xi, tedy xi ∈ a↓. Protože také xi ∈ J(G), je xi ∈ η(a). Dokázali jsme X ⊆ η(a). Dokažme nyní opačnou inkluzi: zvolme libovolně y ∈ η(a). Pak y ∈ J(G) a y ≤ a. Proto z distributivity y = y ∧ a = y ∧ (x1 ∨ · · · ∨ xn) = (y ∧ x1) ∨ · · · ∨ (y ∧ xn). Ovšem y je ∨-nedosažitelný. Proto y nemůže být supremem menších prvků (viz poznámku za definicí ∨-nedosažitelnosti). Existuje tedy i ∈ {1 . . . n} tak, že y = y ∧ xi, což znamená, že y ≤ xi. Ovšem xi ∈ X, která je dědičná, tedy y ∈ X, což jsme potřebovali dokázat. Je tedy η izotonní bijekce. Zbývá ukázat, že i inverzní zobrazení η−1 je izotonní. Nechť a, b ∈ G jsou takové, že η(a) ⊆ η(b). Pak podle věty 7.7 platí a = η(a) ≤ η(b) = b. Poznámka. Věta mimo jiné říká, že je-li G konečný distributivní svaz, pak i D(J(G)) je svaz. Zřejmě sjednocení i průnik neprázdných dědičných podmnožin je opět neprázdná dědičná podmnožina (průnik je neprázdný, protože obsahuje nejmenší prvek svazu), jsou operacemi suprema a infima ve svazu D(J(G)) právě množinový průnik a sjednocení. Je tedy D(J(G)) podsvazem svazu všech podmnožin množiny J(G). Důsledek. Každý konečný distributivní svaz je izomorfní s některým podsvazem svazu všech podmnožin nějaké konečné množiny. Poznámka. Podle předchozího důsledku každý konečný distributivní svaz můžeme chápat jako inkluzí uspořádaný systém množin, který je uzavřený na průniky a sjednocení. Protože naopak každý inkluzí uspořádaný systém množin, který je uzavřený na průniky a sjednocení, je zřejmě distributivním svazem, dostali jsme tak slíbenou charakterizaci konečných distributivních svazů. Uvědomte si, že podmínka uzavřenosti na množinový průnik a sjednocení je zde podstatná, vždyť například i nedistributivní svaz M5 (diamant) je izomorfní se systémem množin {∅, {1}, {2}, {3}, {1, 2, 3}} uspořádaným inkluzí. 23 8. Booleovy algebry Definice. Nechť G je svaz s nejmenším prvkem 0 a největším prvkem 1. Řekneme, že prvek b ∈ G je komplementem prvku a ∈ G ve svazu G, jestliže platí a ∧ b = 0, a ∨ b = 1. Svaz G se nazývá komplementární, jestliže ke každému prvku existuje aspoň jeden komplement. Poznámka. Z komutativity obou operací plyne, že je-li prvek b komplementem prvku a, pak je prvek a komplementem prvku b. Příklad. Svazy M5 a N5 jsou komplementární (viz Hasseův diagram na straně 15), avšak k některým prvkům existuje komplementů více než jeden (nalezněte v každém z těchto svazů aspoň jeden takový prvek). Příklad. Řetězec mající aspoň tři prvky není komplementární. Poznámka. Podsvaz komplementárního svazu nemusí být komplementární: komplementární svaz N5 obsahuje čtyřprvkový řetězec jako podsvaz. Věta 8.1. Součin komplementárních svazů je komplementární svaz. Důkaz. Nechť G a H jsou komplementární svazy, uvažme jejich součin G × H. Protože pro každé g ∈ G, h ∈ H platí (g, h) ∧ (0, 0) = (g ∧ 0, h ∧ 0) = (0, 0), je (0, 0) nejmenším prvkem svazu G × H. Podobně se ověří, že (1, 1) je největším prvkem svazu G × H. Pak pro libovolný komplement g1 prvku g ve svazu G a pro libovolný komplement h1 prvku h ve svazu H platí (g, h) ∧ (g1, h1) = (g ∧ g1, h ∧ h1) = (0, 0), (g, h) ∨ (g1, h1) = (g ∨ g1, h ∨ h1) = (1, 1), a tedy (g1, h1) je komplementem prvku (g, h) ve svazu G × H. Poznámka. Duální svaz ke komplementárnímu svazu je komplementární (komplementy se zachovávají). Věta 8.2. V distributivním svazu je komplement prvku, pokud existuje, určen jednoznačně. Důkaz. Nechť a1, a2 jsou komplementy prvku b. Pak platí a1 ∧ b = 0 = a2 ∧ b, a1 ∨ b = 1 = a2 ∨ b. Podle věty 7.5 odtud plyne a1 = a2. Definice. Distributivní komplementární svaz se nazývá Booleova algebra. Poznámka. Nejmenší prvek Booleovy algebry budeme v dalším textu vždy značit 0 a její největší prvek 1. Komplement prvku a ∈ G je dle předchozí věty určen jednoznačně, značíme jej a . 24 Příklad. Prázdný svaz není Booleova algebra. Příklad. V libovolné Booleově algebře platí 0 = 1, 1 = 0. Příklad. Připomeňme, že pro libovolnou množinu X symbolem 2X označujeme množinu všech podmnožin množiny X. Pro každou množinu X je (2X , ∪, ∩) Booleova algebra (uspořádáním je množinová inkluze): nejmenší prvek je ∅, největší prvek je X a komplementem prvku A ⊆ X je prvek X − A. Poznámka. Promyslete si, že duální svaz k Booleově algebře je Booleova algebra (komplementy se zachovávají, 0 a 1 se v dualitě vymění). Věta 8.3. Součinem Booleových algeber je Booleova algebra. Důkaz. Plyne z vět 7.4 a 8.1. Věta 8.4. V libovolné Booleově algebře pro každé prvky a, b platí 1. a = a, 2. (a ∨ b) = a ∧ b , 3. (a ∧ b) = a ∨ b . Důkaz. Prvky a i a jsou komplementy prvku a , z jednoznačnosti komplementu a = a. Druhou rovnost odvodíme z distributivního zákona: (a ∨ b) ∨ (a ∧ b ) = ((a ∨ b) ∨ a ) ∧ ((a ∨ b) ∨ b ) = = ((a ∨ a ) ∨ b) ∧ ((b ∨ b) ∨ a) = = (1 ∨ b) ∧ (1 ∨ a) = 1 ∧ 1 = 1, podobně (a ∨ b) ∧ (a ∧ b ) = (a ∧ (a ∧ b )) ∨ (b ∧ (a ∧ b )) = = ((a ∧ a ) ∧ b ) ∨ ((b ∧ b ) ∧ a ) = = (0 ∧ b ) ∨ (0 ∧ a ) = 0 ∨ 0 = 0. Je tedy a ∧b komplementem prvku a∨b, což jsme chtěli ukázat. Třetí rovnost dostaneme z druhé užitím duality. Definice. Podsvaz L Booleovy algebry G se nazývá Booleova podalgebra, jestliže 0, 1 ∈ L a pro každé a ∈ L platí a ∈ L. Příklad. V libovolné Booleově algebře tvoří {0, 1} Booleovu podalgebru. Podobně pro každý její prvek a je {0, 1, a, a } Booleova podalgebra. Příklad. Je-li X nekonečná množina, uvažme množinu Y = {A ⊆ X; A je konečná nebo X − A je konečná}. 25 Pak Y je Booleova podalgebra Booleovy algebry (2X , ∪, ∩). Věta 8.5. Libovolná Booleova podalgebra je Booleova algebra. Důkaz. Jakožto podsvaz distributivního svazu je Booleova podalgebra distributivní svaz. Protože nejmenší (resp. největší) prvek Booleovy podalgebry je nejmenším (resp. největším) prvkem celé Booleovy algebry, z toho, že operace ∨ a ∧ se v podsvazu počítají stejně jako v celém svazu, plyne, že komplement daného prvku v Booleově podalgebře je stejný jako komplement tohoto prvku v celé Booleově algebře. Je tedy Booleova podalgebra komplementární svaz, což jsme měli dokázat. Definice. Nechť G a H jsou Booleovy algebry, f : G → H zobrazení. Řekneme, že je f homomorfismus Booleových algeber, je-li f svazový homomorfismus, pro který platí f(0) = 0, f(1) = 1. Řekneme, že f je izomorfismus Booleových algeber, je-li f bijektivní homomorfismus Booleových algeber. Booleovy algebry G a H nazveme izomorfní, jestliže existuje izomorfismus Booleových algeber f : G → H. Věta 8.6. Nechť f : G → H je homomorfismus Booleových algeber, a ∈ G. Pak platí f(a ) = f(a) . Důkaz. Jistě platí f(a ) ∨ f(a) = f(a ∨ a) = f(1) = 1, f(a ) ∧ f(a) = f(a ∧ a) = f(0) = 0, odkud plyne, že f(a) je komplementem prvku f(a ) v Booleově algebře H. Definice. Nechť G je Booleova algebra, a ∈ G, a = 0. Řekneme, že a je atom Booleovy algebry G, jestliže kromě 0 neexistuje žádný jiný prvek Booleovy algebry G menší než a. Věta 8.7. Nechť G je konečná Booleova algebra, P množina všech jejích atomů. Pak G je izomorfní s Booleovou algebrou (2P , ∪, ∩). Důkaz. Je-li Booleova algebra G jednoprvková, je P = ∅ a věta zřejmě platí. Dále budeme předpokládat, že Booleova algebra G má aspoň dva prvky. Pro každý prvek x ∈ G, x = 0, existuje aspoň jeden p ∈ P, p ≤ x (jinak by pro každý nenulový prvek y < x existoval nenulový prvek z < y, což by umožnilo konstruovat nekonečnou klesající posloupnost prvků, což v konečné množině zřejmě nelze). Definujme zobrazení h : G → 2P předpisem h(b) = {a ∈ P; a ≤ b}. Ukážeme nejprve, že h je surjekce. Protože G je konečná, je i P konečná a tedy je konečná i libovolná podmnožina množiny P. Pro libovolné a1, . . . , an ∈ P zřejmě platí {a1, . . . , an} ⊆ h(a1∨· · ·∨an). Opačnou inkluzi dokažme sporem: předpokládejme, že existuje x ∈ h(a1∨· · ·∨an), x /∈ {a1, . . . , an}. Pak x∧a1 = · · · = x ∧ an = 0, neboť infimum různých atomů je 0. Z x ∈ h(a1 ∨ · · · ∨ an) 26 plyne x ≤ a1 ∨ · · · ∨ an, a tedy x = x ∧ (a1 ∨ · · · ∨ an) = (x ∧ a1) ∨ · · · ∨ (x ∧ an) = 0 ∨ · · · ∨ 0 = 0, což je spor s tím, že x ∈ P. Je tedy h surjekce. Ukažme nyní, že h je též injekce. Zvolme libovolně prvek x ∈ G, x = 0. Dokázali jsme, že existuje aspoň jeden p ∈ P, p ≤ x. Proto h(x) = ∅. Označme {a1, . . . , an} = h(x). Ukážeme-li, že x = a1 ∨ · · · ∨ an, bude zřejmě h injekce. Označme y = a1 ∨ · · · ∨ an; protože a1 ≤ x, . . . , an ≤ x, je y ≤ x. Naším cílem je ukázat x = y, předpokládejme tedy, že y < x a dojděme ke sporu. Platí x = x ∧ 1 = x ∧ (y ∨ y ) = (x ∧ y) ∨ (x ∧ y ). Protože y < x, platí x ∧ y = y = x, a tedy x ∧ y = 0 (uvědomte si, že dosazením x ∧ y = 0 do předchozí rovnosti bychom dostali x = x∧y). Proto existuje atom p splňující p ≤ x ∧ y , tj. p ≤ x, p ≤ y . Ovšem z p ≤ x plyne p ∈ h(x) = {a1, . . . , an}, tedy p = ai pro vhodné i. Proto p ≤ a1 ∨ · · · ∨ an = y, což spolu s dříve odvozenou nerovností p ≤ y tedy dává p ≤ y ∧ y = 0, spor s tím, že p je atom. Je tedy h : G → 2P bijekce. Pro libovolné x, y ∈ G, x ≤ y, jistě platí h(x) ⊆ h(y). Naopak, odvodili jsme, že pro libovolné X ⊆ P je h−1 (X) supremum všech prvků z X. Odtud snadno plyne, že pro X ⊆ Y ∈ 2P platí h−1 (X) ≤ h−1 (Y ). Je tedy h izomorfismus uspořádaných množin, a proto izomorfismus svazový. Jistě h(0) = ∅, h(1) = P. Je to tedy izomorfismus Booleových algeber. 9. Booleovy okruhy Poznámka. V této kapitole ukážeme, že dvě algebraické struktury, totiž Booleovy algebry a speciální okruhy, tzv. Booleovy okruhy, jsou v podstatě totéž. S touto situací, kdy dva odlišné matematické objekty popisují stejnou situaci, jsme se setkali již několikrát: typickým příkladem jsou ekvivalence a rozklady na množině, nebo případ svazů jakožto speciálních uspořádaných množin nebo speciálních algebraických struktur se dvěma operacemi. Definice. Okruh (R, +, ·) se nazývá Booleův okruh, je-li idempotentní, tj. pro každé x ∈ R platí x · x = x. Věta 9.1. Netriviální Booleův okruh je komutativní okruh charakteristiky 2. Důkaz. Platí 1+1 = (1+1)·(1+1) = 1·1+1·1+1·1+1·1 = 1+1+1+1. Přičtením −(1 + 1) dostaneme 1 + 1 = 0. Protože okruh není triviální, platí 1 = 0, a tedy má charakteristiku 2. Pro libovolné x, y ∈ R platí x + y = (x + y) · (x + y) = x · x + x · y + y · x + y · y = x + x · y + y · x + y, 27 odkud x · y = −y · x = y · x, což jsme měli dokázat. Věta 9.2. Nechť (G, ∨, ∧) je Booleova algebra. Definujme na množině G operace + a · takto: pro libovolné x, y ∈ G klademe x + y = (x ∧ y ) ∨ (x ∧ y), x · y = x ∧ y. Pak (G, +, ·) je Booleův okruh. Poznámka. Všimněte si, že v případě Booleovy algebry (2X , ∪, ∩) všech podmnožin množiny X je výše definovanou operací + právě symetrický rozdíl množin. Důkaz. Je zřejmé, že obě operace jsou komutativní, násobení je i asociativní a idempotentní a pro každé x ∈ G platí x + 0 = x, x + x = 0, x · 1 = x. Dokažme asociativitu sčítání. Nechť x, y, z ∈ G jsou libovolné. Z definice a věty 8.4 plyne (x + y) + z = (x ∧ y ) ∨ (x ∧ y) ∧ z ∨ (x ∧ y ) ∨ (x ∧ y) ∧ z = = (x ∧ y ) ∨ (x ∧ y) ∧ z ∨ (x ∨ y) ∧ (x ∨ y ) ∧ z = = (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ ∨ (x ∧ x) ∨ (x ∧ y ) ∨ (y ∧ x) ∨ (y ∧ y ) ∧ z = = (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ) ∨ (y ∧ x) ∧ z = = (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z). Poslední výraz se nezmění, provedeme-li s x, y, z jakoukoli permutaci. Proto (x + y) + z = (y + z) + x = x + (y + z), a tedy sčítání je asociativní, tudíž (G, +) je komutativní grupa. Zbývá ověřit distributivní zákon. Nechť x, y, z ∈ G jsou opět libovolné. Z definic a věty 8.4 plyne x · y + x · z = (x ∧ y) ∧ (x ∧ z) ∨ (x ∧ y) ∧ (x ∧ z) = = x ∧ y ∧ (x ∨ z ) ∨ (x ∨ y ) ∧ x ∧ z = = (x ∧ y ∧ x ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ x ∧ z) ∨ (y ∧ x ∧ z) = = (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) = = x ∧ (y ∧ z ) ∨ (y ∧ z) = x · (y + z), což jsme chtěli dokázat. 28 Věta 9.3. Nechť (R, +, ·) je Booleův okruh. Definujme na množině R operace ∨ a ∧ takto: pro libovolné x, y ∈ R klademe x ∨ y = x · y + x + y, x ∧ y = x · y. Pak (R, ∨, ∧) je Booleova algebra, kde pro každé x ∈ R platí x = x + 1. Důkaz. Je zřejmé, že operace ∧ je komutativní, asociativní a idempotentní. Jistě je též operace ∨ komutativní. Snadno se ověří, že také idempotentní. Nechť x, y, z ∈ R jsou libovolné. Platí (x ∨ y) ∨ z = (x · y + x + y) · z + (x · y + x + y) + z = = x · y · z + x · z + y · z + x · y + x + y + z = = x · (y · z + y + z) + x + y · z + y + z = x ∨ (y ∨ z), a tedy je ∨ asociativní operace. Ověřme absorpční zákony. Nechť x, y, z ∈ R jsou opět libovolné. Platí (x ∨ y) ∧ x = (x · y + x + y) · x = x · y · x + x · x + y · x = x · y + x · y + x = x, a také (x ∧ y) ∨ x = (x · y) · x + (x · y) + x = x · y + x · y + x = x, což jsme chtěli dokázat. Je tedy (R, ∨, ∧) svaz. Protože pro každé x ∈ R je x ∧ 0 = x · 0 = 0, platí 0 ≤ x, podobně x ∧ 1 = x · 1 = x, a tedy x ≤ 1. Proto je 0 nejmenší a 1 největší prvek tohoto svazu. Ověřme, že skutečně je x + 1 komplementem prvku x: x ∧ (x + 1) = x · (x + 1) = x · x + x = x + x = 0, x ∨ (x + 1) = x · (x + 1) + x + (x + 1) = 0 + x + x + 1 = 1. Je tedy (R, ∨, ∧) komplementární svaz, zbývá ukázat, že je to též svaz distributivní. Nechť tedy x, y, z ∈ R jsou opět libovolné. Platí (x ∧ z) ∨ (y ∧ z) = (x · z) · (y · z) + (x · z) + (y · z) = = x · y · z + x · z + y · z = (x · y + x + y) · z = = (x ∨ y) ∧ z. Věta je dokázána. Věta 9.4. Předchozí dvě věty nám dávají jednoznačnou korespondenci mezi Booleovými okruhy a Booleovými svazy. 29 Důkaz. Je třeba ověřit, že pokud z Booleova okruhu vyrobíme Booleovu algebru a z ní opět Booleův okruh, dostaneme ten, se kterým jsme začínali, a také, že pokud z nějaké Booleovy algebry vyrobíme Booleův okruh a z něj opět Booleovu algebru, je to ta původní. To je zřejmé pro operace · a ∧, které jsou totožné. Musíme to ověřit tedy pouze pro operace + a ∨. Mějme tedy Booleův okruh (R, +, ·), uvažme k němu příslušnou Booleovu algebru (R, ∨, ∧), a k ní příslušný Booleův okruh (R, ⊕, ·). Pro libovolné x, y ∈ R tedy platí x ⊕ y = (x ∧ y ) ∨ (x ∧ y) = = (x · y ) · (x · y) + (x · y ) + (x · y) = = x · (x + 1) · y · (y + 1) + x · (y + 1) + (x + 1) · y = = 0 + x · y + x + x · y + y = x + y. Naopak, mějme nyní Booleovu algebru (R, ∨, ∧), uvažme k ní příslušný Booleův okruh (R, +, ·), a k němu příslušnou Booleovu algebru (R, , ∧). Pro libovolné x, y ∈ R pak platí x y = x · y + x + y = x + y + (x ∧ y) = = x + y ∧ (x ∧ y) ∨ y ∧ (x ∧ y) = x + y ∧ (x ∨ y ) ∨ 0 = = x + (y ∧ x ) ∨ (y ∧ y ) = x + (y ∧ x ) ∨ 0 = x + (y ∧ x ) = = x ∧ (y ∧ x ) ∨ x ∧ (y ∧ x ) = x ∧ (y ∨ x) ∨ (x ∧ y) = = x ∨ (x ∧ y) = (x ∨ x ) ∧ (x ∨ y) = 1 ∧ (x ∨ y) = x ∨ y což bylo třeba ověřit. Poznámka. Podobné dvojí pohledy na jeden objekt bývají v matematice velmi cenné, neboť mnohdy ukáží nečekané souvislosti. Příkladem může být dualita, která je pro Booleovy algebry naprosto zřejmá. Výše uvedenou korespondencí se převádí též na Booleovy okruhy, kde už však není tak snadné si jí všimnout. 30