ZÁKLADY TEORIE SVAZŮ Radan Kučera, říjen 2003 Literatura • Doporučená: - 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). • Hlubší: - R. Faure, E. Heurgonová: Uspořádání a Booleovy algebry, Academia, Praha 1984 (kap. II-V). Při studiu z této knihy se však nedejte zmást ani definicí zobrazení uvedenou v kapitole I ani tiskovými chybami, třeba opačně napsanými nerovnosti v Lemma 2 na str. 88. Ú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ě nej vhodně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á nej elegantnej i. 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í GxG —>• G. Jestliže G = 0, pak G x 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 x B, v níž pro každé a G A existuje právě jedna uspořádaná dvojice s první složkou a. Je-li tedy A = 0, pak pro libovolnou množinu B takové zobrazení je jediné: / je také prázdná množina. Je-li naopak A ^ 0 a současně B = 0, pak takové zobrazení neexistuje. Proto tedy na nosné množině G = 0 máme jediný grupoid, jehož (jedinou možnou) operací na G je prázdné zobrazení, tj. trojice (0, 0, 0). 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 podgrupoidu 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 0 průniku podgrupoidu. 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 x M, pro M = 0 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 G 0 ==>• V je pravdivá pro všechna x a pro každé tvrzení V, neboť je nepravdivý předpoklad implikace x G 0), 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 = 0 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 = 0, neboť pro každý prvek prázdné množiny platí zcela cokoli, například 1 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. 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,D) a (2X,U) 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. 1. Polosvazy 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 = xay-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 G existuje supremum a V b. Pak (G, V) je polosvaz. Navíc pro každé a, b G G platí Důkaz. Komutativita i idempotentnost je zřejmá, ekvivalence obou podmínek též. Pro libovolné a, b, c G G jistě platí (a V b) V c > c, (a V b) V c > a V b > a, podobně (a V b) V c > b. Je tedy (a V b) V c horní závora množiny {b, c}, proto (a V b) V c > b V c. Je tudíž (a V b) V c horní závora množiny {a, b V c}, proto (a V b) V c > a V (b V c). Analogicky opačná nerovnost, z antisymetrie asociativita. Věta 1.3. Nechť (G, •) je polosvaz. Potom relace <, daná vztahem pro každé a, b G 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 G platí a < a, a tedy je < reflexivní a antisymetrická relace. Rovněž platí a • infimum, V •<->• A, < •<->• >, 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, V, A) 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 G platí tzv. distributivní nerovnosti (a V b) A (a V c) > a V (b A c), (a A b) V (a A c) < a A (b V c). Je-li navíc c < a, platí tzv. modulární nerovnost (a Ab) V c < a A (6Vc). 6 Důkaz. Jistě platí aV6 > a, aVc > a, a tedy i (aV6) A(aVc) > a. Podobně aVb > b > bAc, aVc> c> bAc, odkud (a V b) A (a V c) > 6 A 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í aAc = c, proto modulární nerovnost plyne z druhé distributivní nerovnosti. Věta 2.4. Nechť G je svaz, n G N. Pro libovolné prvky ai,... ,an G G platí, že cii V • • • V an je supremum množiny {ai,..., an} a cii A ■ ■ ■ A an je infimum množiny {cii,..., an}. Důkaz. Indukcí vzhledem k n. 3. Po dsvazy, ideály, filtry, homomorfismy Definice. Nechť (G, V, A) je svaz, A podmnožina jeho nosné množiny G. Řekneme, že A je podsvaz svazu (G, V, A), jestliže je A podgrupoidem grupoidu (G, A) a současné podgrupoidem grupoidu (G, V). Poznámka. Je tedy A C G podsvazem svazu G, právě když pro každé a, b G A platí aVbeA&aAbeA. 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 podsvazem. Definice. Nechť G je svaz, A C 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 G A a každé x G G platí x < a =^ x G A. Duálné, řekneme, že A je fíltr svazu G, jestliže je A podsvazem svazu G, který navíc splňuje podmínku: pro každé a G A a každé x G G platí x > a =^ x G 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 svazuje opět podsvaz (resp. ideál, resp. filtr) tohoto svazu. 7 Důkaz. Nechť i" ^ 0 a pro každé i G I je Aj podsvaz svazu G. Označme A = (~)ieI Ai jejich průnik. Pak pro každé a, b G A platí a, b G Ai pro všechna i G i", a tedy a V 6 G Ai a a A b G Aj. Odtud oVř)6Ía(iAř)6Í, a proto je A podsvaz svazu G. Předpokládejme navíc, že pro každé i G I je Ai dokonce ideál svazu G. Mějme a G A, x G G, x < a. Pak pro každé i G I je a G Ai, tedy i x G Aj, tudíž x G 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 Ai,...,A„ neprázdné ideály a zvolíme-li a, G Aj, pak a = ai A • • • A an < ai, a tedy a G Aj. 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 G Z je An = {x G Z; x < n} ideál tohoto svazu. Ale (~)neZ 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 C G podmnožina. Díky předchozí větě můžeme nyní defínovat 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ě, fíltr A\ svazu G generovaný množinou A je průnik všech fíltrů tohoto svazu obsahujících množinu A. Je-li A = {a}, píšeme stručně a\. místo {a}l, resp. a\ místo {a}t, a hovoříme o hlavním ideálu, resp. o hlavním fíltru, generovaném prvkem a. Poznámka. Pro svaz G a podmnožinu A C G je ideál Aj. generovaný množinou A tím nej menší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 nej menší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 C G je ideálem svazu G, právě když AI = A, a je filtrem svazu G, právě když A\ = A. Věta 3.2. Necht G je svaz, A C G podmnožina. Pro ideál A\ generovaný 8 množinou A platí A\ = {x G G; 3n G N3ai,..., an G A : x < a± V • • • V an}. Duálně, pro filtr Á\ generovaný množinou A platí A\ = {x G G; 3n G N3ai,..., an G A : x > ai A • • • A an}. Důkaz. Každý ideál svazu G obsahující množinu A musí pro každé ai,..., an G A obsahovat i oi V ■ • • V o„. Proto obsahuje i množinu B = {x G G; 3n G N3ai,..., an G A : x < ai V • • • V an}. Je tedy A|, 3 B. Stačí ověřit, že S je ideál obsahující A. Inkluze A C B je zřejmá, neboť pro a G A lze volit n = 1 a ai = o. Jistě S 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 G B. Potom existují ai,...,an G A tak, že x < ai V • • • V an, a existují bi,... ,bm G A tak, že y < bi V • • • V bm. Pak x A y < x < ai V • • • V an, a tedy x A y G S. Na druhou stranu x < cti V • • • V an < (cii V • • • V a„) V (6i V • • • V 6m), podobně y < 61 V • • - V bm < (ai V • • • V On) V (61 V • • • V bm), odkud x V j/ < (ai V • • • V an) V (h V • • • V bm), proto x V y G S. Je tedy S 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 G platí implikace af(a)±f(b). Řekneme, že f je izomorfísmus uspořádaných množin, je-li f bijekce a obě zobrazení f i f~l jsou izotonní. Definice. Nechť G a H jsou svazy, f : G —» H zobrazení. Řekneme, že je f svazový homomorfísmus, jestliže pro každé a, b G G platí f (a A b) = f (a) A f (b), f (a V b) = f (a) V f (b). Řekneme, že f je svazový izomorfísmus (neboli izomorfísmus svazů), je-li f bijektivní homomorfísmus. Poznámka. Protože každý svaz je také uspořádaná množina, má smysl se ptát, zda svazový homomorfísmus je též izotonní zobrazení. Věta 3.3. Nechť G a H jsou svazy, f : G —» H zobrazení. 1. Je-li f svazový homomorfísmus, pak f je izotonní zobrazení a homo-morfní obraz f(G) = {/(a); a G 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. Dokážme nejprve první část věty. Je-li / svazový homomorfismus, pak pro každé a, b G G z a < b plyne a = a a b, proto f (a) = f (a a b) = f (a) a f(b), a tedy f (a) < f(b). Je tedy / izotonní. To, že f(G) je podsvaz svazu H, plyne přímo z definic. Dokažme nyní druhou část věty. Nechť je / nejdříve svazový izomorfismus, ukážeme, že pak f~l je svazový homomorfismus. Zvolme libovolně c,d G H a označme a = /_1(c), b = f'1 (d). Pak platí f-1 (c V d) = f-1 (f (a) V f (b)) = f-\f(a V b)) = a V b = f-1 (c) V f-\d), r\c a d) = r\f{o) a f (b)) = r\f{a a &)) =« a b = r\c) a r\d). Odvodili jsme, že f~l je svazový homomorfismus. Aplikací první části věty na zobrazení / i f~l dostaneme, že / je izomorfismus uspořádaných množin. Nechť nyní naopak / je izomorfismus uspořádaných množin, a, b G G. Protože a < aV b, 6• U. Pak je totiž f(G) podsvaz svazu U a zúžením oboru hodnot dostaneme svazový izomorfismus / : 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, C) má největší prvek G, je to dle předchozí věty úplný svaz. Přitom pro libovolné dva prvky A, B G U je jejich infimem A A B = A H B množinový průnik, jejich supremem AV B = (A U B)j. je ideál generovaný množinovým sjednocením. Uvažme zobrazení / : G —>• U, které každý prvek svazu G zobrazí na ideál jím generovaný: pro každé a G G klademe f (a) = a\.. Podle věty 3.2 je tedy f (a) = {x G G; x < a}. Odtud plyne, že / je injekce: jsou-li totiž a, b G G takové, že f (a) = f (b), pak a G b\., odkud a < b, analogicky b < a, dohromady a = b. 12 Budeme hotovi, ukážeme-li, že / je svazový homomorfismus. Nechť a, 6 G G jsou libovolné. Máme ukázat, že f (a A b) = f (a) A f(b), /(a V 6) = /(a) V /(&), což znamená (a A 6)4, = a\. H 64,, (a V 6)4, = (al U H)^- Nejprve ukážeme obě inkluze dokazující první rovnost. Protože a A b < a, a A b < b, platí a A b G c4 n 64-, odkud (a A 6)4- C al n 64-. Naopak, je-li x G a4- H 64-, je x < a, x < 6, tedy x < a A 6, neboli x G (a A 6)4-. Nyní se zaměřme na druhou rovnost. Z nerovností a < a V 6, 6 < a V 6, plynou inkluze aj- C (a V 6)4-, 64- C (a V 6)4-, odkud aj- U 64- C (a V 6)4- a proto i (al U 64-)4- í= a V 6J-. Na druhou stranu platí a, 6 G (aj- U 64-)4-, proto i a V 6 G (al U 6^, odkud (a V 6)4, C (al U &j)^. Věta 4.3 (Tarski). Nechť G je úplný svaz, (p : G —> G izotonní zobrazení. Pak existuje prvek a G G tak, že (p(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 < y, což pomocí svazových operací lze zapsat podmínkou x A y = x nebo x A 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 G N: na kartézském součinu nosných množin daných svazů se nové operace V a 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 G takových, že c < a, platí modulární nerovnost (a Ab) V c < a A (6Vc). Definice. Svaz G se nazývá modulární, jestliže pro každou trojici prvků a, b, c G G takových, že c < a, platí modulární rovnost (oAô)Vc = oA(bVc). Příklad. Příklady modulárních svazů jsou svaz (2X, U, Pl) všech podmnožin nějaké množiny X nebo libovolný řetězec. Příklad. Ukážeme, že svaz AT5) 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 iV5 nakresleny nad sebou vlevo, a b jeho pátý prvek. Pak nerovnost (flAb)Vc = 0Vc=c c, aAb = cAb, a V b = c V b =>• a = c. (1) Důkaz. Předpokládejme, že svaz G je modulární a že pro trojici prvků a, b, c G G platí c < a, a A b = c A b, aV6 = cV6. Pak z absorpčních zákonů a modulární rovnosti plyne c = (c A b) V c = (a A b) V c = a A (b V c) = a A (b V 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 G tak, že c < a, a označme x = (a A b) V c, y = a A (b V c). Z modulární nerovnosti (věta 2.3) víme, že x < y. Ukážeme-li, že též platí x A b = y A b, x V b = y V b, podle implikace (1) dostaneme x = y, což je modulární rovnost pro prvky a, b, c. Z x < y plyne x V b < y V b, neboť zyVb>y>x,yVb>bje jasné, že y V b je horní závora prvků x, b. Analogicky x A b < y A b. Ovšem x V b = ((a A b) V c) V b = ((a A b) V b) V c = b V c, jistě 6Vc> aA(&Vc) = y a6Vc> b. To pak znamená xW b = bW c > yW b, což spolu s dříve odvozenou opačnou nerovností znamená x V b = y y b. Analogicky y A b = (a A (b V c)) A b = a A ((b V c) A b) = a A b < (a A b) V c = x, jistě též y Ab = a Ab < b, proto y A b < x A b, opět s opačnou nerovností dostáváme potřebnou rovnost x Ab = y Ab. 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 G tak, že ačkoliv platí a > c, aAb = cAb, aV6 = cV6, přesto a ^ c. Tedy a > c. Snadno se ověří, že pak nemůže nastat žádný z případů b > c (pak by totiž 6 = 6Vc = 6Va, tedy b > a, odkud bAa = a>c = bAc) ani b < a (pak by b = bAa = bAc, tedy b < c, odkud 6 V c = c < a = 6Va). Je tedy b s každým z prvků a, c nesrovnatelný. Proto jsou prvky a, b, c, aAb, aV6 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 G platí distributivní nerovnosti (a V b) A (a V c) > aV(6Ac), (a A b) V (a A c) < aA(&Vc). Definice. Svaz G se nazývá distributivní, jestliže pro každou trojici prvků a, b, c G G platí distributivní rovnost (a A b) V (a A c) = a A (6Vc). 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 G platí i následující distributivní rovnost (a V b) A (a V c) = a V (bAc). 18 Důkaz. Z distributivity a absorpčního zákona dostáváme (a V b) A (a V c) = ((a V 6) A a) V ((a V 6) A c) = a V ((a A c) V (b A c)) = = (a V (a A c)) V (6 A c) = a V (6 A 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 G jsou takové, že c < a. Pak platí a A (b V c) = (a A b) V (a A c) = (a A 6) V 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 rovností. Věta 7.5. Svaz G je distributivní, právě když pro každou trojici prvků a, b, c G G platí implikace a A b = c A b, a V b = c V b a = c. (2) Důkaz. Předpokládejme, že svaz G je distributivní a že pro trojici prvků a,b,c G G platí a A b = c A b, a V & = cV6. Pak z absorpčních zákonů a distributivity plyne c = (c A b) V c = (a A b) V c = (a V c) A (b V c) = = (a V c) A (a V b) = a V (c A b) = a V (a A 6) = 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 G jsou libovolné. Označme a = ((ž/ v z) A z) V (x A y), b = y, c = ((ž/ V z) A x) V (z A 19 Tyto definice jsou voleny tak, že při záměně x •<->• z se zamění a •<->• c. Protože xAycaif>z c A b = b A c = y A (y V z) A (xV (z Ay)) = y A (xV (z Ay)) = (y Ax) V (z Ay). Je tedy a A b = c A b. Z absorpce a modularity (díky y caif>z c V b = ((y V z) A x) V (z A y) V y = ((y V z) A x) V y = (y V z) A (x V y). Je tedy také a V b = c V b, což spolu s aAb = cAb pomocí implikace (2) dává a = c. Z absorpce a modularity (díky x A y < x) dostáváme x A a = x A (y V x) A (z V (x A y)) = x A (z V (x A y)) = (x A z) V (x A y). Podobně z komutativity a absorpce x A c = x A (y V z) A (x V (z A y)) = x A (x V (z A y)) A (y V z) = x A (y V z) Celkem tedy z toho, že a = c, a z komutativity plyne xA(ž/Vz) = xAc = xAa=(xAž/)V(xAz). Protože x,y,z G 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 pod-svaz 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 G tak, že ačkoliv platí aAb = cAb, aV6 = cV6, 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 Ab = c Ab, s = aV6 = cV6, m = ((a V c) A b) V (a Ac). Je zřejmé, že i < c, a tedy i = iAc=aAbAc. Podobně s = a V b V c. Z absorpce a modularity (díky a < a V c) plyne m V a = ((a V c) A 6) V (a A c) V a = ((a V c) A 6) V a = (a V c) A (6 V a). Ovšem 6Va = s = aV6Vc> aVc, odkud my a = a V c. Analogicky (záměnou a •<->• c) se dokáže, že m V c = a V c. Protože a A c < aV c, plyne z modularity m= (aVc)A(ĎV(flAc)). Z absorpce a modularity (díky a A c < a) plyne mAa = a Am = a A (oVc) A (6 V (oAc)) = a A (b V (a A c)) = (a A 6) V (a A c). Ovšem aAb = i = aAbAc< a A c, odkud mAa = a A c. Analogicky (záměnou a •<->• c) se dokáže, že m Ac = a Ac. Tvoří tedy {a, c,?n,aVc,aAc} podsvaz svazu G. Ukažme, že c a m jsou nesrovnatelné. Z c < m plyne c = mAc = aAc, odkud c < a, spor. Podobně z c> m plyne c = mVc = cVa, 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,aVc,(iAc} 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á V-nedosažitelný jestliže pro každé b, c G G takové, že a = 6 V c, platí a = b nebo a = c. Poznámka. Prvek a svazu G je tedy V-nedosažitelný, jestliže není supre-mem žádných dvou prvků ostře menších než on, tj. neexistují b, c G G splňující b < a, c < a, a = 6 V c. Ekvivalentně lze tuto podmínku vyjádřit také takto: prvek a svazu G je V-nedosažitelný, jestliže pro každé b, c G G takové, že b < a a současně c < a, platí b V 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 V-nedosažitelných prvků svazu G označíme J(G). Věta 7.7. V konečném distributivním svazu G je libovolný prvek a roven supremu množiny všech V-nedosažitelných prvků, které neostře převyšuje, tj. a= \/ 6 = \/(4n J(G)). b£j(G),b 1 a že pro všechny distributivní svazy o méně než m prvcích byla již věta dokázána. Nechť a G G je libovolný. Pokud a G J(G), zřejmě je a nej větším prvkem množiny aj, H J (G) a dokazovaná podmínka je pro něj zřejmě splněna. Nechť tedy a ^ J(G), pak existují b, c G G splňující b < a, c < a, a = 6 V c. Uvažujme ideál 4- Zřejmě jde o podsvaz svazu G neobsahující a, tedy |4| < m. Jako podsvaz distributivního svazu je distributivní a tedy podle indukčního předpokladu platí b = \J(bln J(b\)) = \J(blnJ(G)), protože z definice ideálu plyne, že každý V-nedosažitelný prvek v podsvazu bl je V-nedosažitelný vzhledem k celému G. Podobně platí c = V (4 n J (G)). Tedy a = b V c = V(4 n J (G)) V V (4 n J (G)) = \/D, kde D = (4 U 4) n J (G) C aj, n J (G). Nechť d = V(«4 n J (G)). Protože G je konečná množina, můžeme psát a\. H J (G) = {ai,..., an} pro nějaké přirozené n (tato množina není prázdná, neboť jistě obsahuje nejmenší prvek svazu G). Pak platí d = V(<4 ^ = V7=i a«' tedy pro infimum a A d díky distributivitě platí n n n a A d = a a\J a, = \/(a A a,) = \J a, = d, odkud dostáváme a> d = V(<4 H J (G)) >\/ D = a, tedy a = \/(c4n J(G)), což jsme chtěli dokázat. Definice. Nechť (A, <) je uspořádaná množina. Množina B C A se nazývá (dolů) dědičná, pokud pro každý prvek b G B a každý a G A, a < b, platí oGB. 22 Poznámka. Množina B C 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 V-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)),C) je izomorfní se svazem G (chápaným jako uspořádaná množina). 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í r) : G —> D(J(G)) předpisem r)(a) = a\.C\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\. Pl 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 G jsou libovolné takové, že a < b. Pak a\. C b]., tedy r](a) = al n J(G) C b\. Pl J(G) = r](b). Dále definujeme zobrazení ů : D(J(G)) —>• G předpisem ů(X) = \J X, tj. ů(X) je supremem všech prvků množiny X. I toto zobrazení je izotonní, protože pro libovolné X,Y G D(J(G)) takové, že X C Y, platí ů(X) = \/X < \/Y = Ů(Y). Ukážeme, že zobrazení 77 a d jsou navzájem inverzní. Nechť a G L, pak •& o n(á) = -d(al n J (G)) = V(«4 n J (G)) = a podle věty 7.7. Nechť naopak X G D(J(G)). Pak -q o Ů(X) = (\/X)ln J (G). Chceme, aby se složení zobrazení rovnalo identitě na množině D (J (G)), tedy aby (V*Hn J{G) = x. Označme Y levou stranu požadované rovnosti. Inkluzi X C Y dokážeme snadno: pro každé x G X zřejmě platí x < \/ X, a tedy x G (V X)\., a protože x G X C J (G), inkluze X C Y platí. Nechť nyní y G Y. Ptáme se, zda y G X. Pro y však platí y < V X a X je konečná neprázdná množina. Můžeme tedy psát X = {xi,..., xn} pro nějaké přirozené n, a tedy z distributivity n n v = v ^\/ X = y a\J Xi = \J(yAXi). i=l i=l Ovšem y G J (G), a tedy y je V-nedosažitelný. Proto y nemůže být supremem menších prvků (viz poznámku za definicí V-nedosažitelnosti). Existuje tedy i G {1... n} tak, že y = y Axí, což znamená, že y < Xj. Ovšem Xj G X, která 23 je dědičná, tedy j G I, což jsme potřebovali dokázat. Celkem tedy máme izotonní bijekci r] : G —> D (J (G)) a její izotonní inverzi ů : D (J (G)) —>• G, jedná se tedy o izomorfismus uspořádaných množin. Poznámka. Věta mimo jiné říká, že je-li G konečný distributivní svaz, pak i D (J (G)) je konečný distributivní svaz. Protože sjednocení i průnik dědičných množin je opět dědičná množina, jsou operacemi suprema a infima v 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 {0, {1}, {2}, {3}, {1, 2, 3}} uspořádaným inkluzí. 8. Booleovy algebry Definice. Nechť G je svaz s nejmenším prvkem 0 a nejvétším prvkem 1. Řekneme, ze prvek b G G je komplementem prvku a G G ve svazu G, jestliže platí oA6 = 0, oVfe = l. 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 x H. Protože pro každé g G G, h G H platí (ff,/i)A(0,0) = (ffA0,/iA0) = (0,0), 24 je (0,0) nejmenším prvkem svazu G x H. Podobně se ověří, že (1,1) je nej-větším prvkem svazu G x H. Pak pro libovolný komplement g\ prvku g ve svazu G a pro libovolný komplement h\ prvku h ve svazu H platí (g, h) A ( 2P předpisem h(b) = {a G 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é zřejmě platí {ai,..., an} C /i(ai V- • - Va„). Opačnou inkluzi dokažme sporem: předpokládejme, že existuje x G /i(aiV- • -Va„), x £ {ai,..., an}. Pak xAai = • • • = x A an = 0, neboť infimum různých atomů je 0. Z x G h(ai V • • • V an) plyne x < ai V • • • V an, a tedy x = x A (ai V • • • V an) = (x A aľ) V • • • V (x A an) = 0 V • • • V 0 = 0, což je spor s tím, že x G P. Je tedy h surjekce. Ukažme nyní, že h je též injekce. Zvolme libovolně prvek i e G, i / 0. Dokázali jsme, že existuje aspoň jeden p G P, p < x. Proto h(x) ^ 0. Označme {ai,..., an} = h(x). Ukážeme-li, že x = ai V • • • V an, bude zřejmě h injekce. Označme y = ai V • • • V an; protože ai < 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 A 1 = x A (y V y') = (x A y) V (x A y'). Protože y < x, platí x A y = y ^ x, a tedy x A y' ^ 0 (uvědomte si, že dosazením x A y' = 0 do předchozí rovnosti bychom dostali x = xAy). Proto existuje atom p splňující p < x A y', tj. p < x, p < y'. Ovšem z p < x plyne p G h(x) = {ai,..., an}, tedy p = a, pro vhodné i. Proto p < ai V • • • V an = y, což spolu s dříve odvozenou nerovností p < y' tedy dává p < y' A y = 0, spor s tím, že p je atom. Je tedy h : G —> 2P bijekce. Pro libovolné x, y G G, x < y, jistě platí h(x) C h(y). Naopak, odvodili jsme, že pro libovolné X C P je h'1 (X) 27 supremum všech prvků z X. Odtud snadno plyne, že pro X C Y G 2 platí < Je tedy h izomorfismus uspořádaných množin, a proto izomorfismus svazový. Jistě h(0) = 0, h(l) = 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 G 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 G R platí x + y=(x + y)-(x + y) = x- x + x- y + y- x + y- y = x + x- y + y- x + y, odkud x ■ y = —y ■ x = y ■ x, což jsme měli dokázat. Věta 9.2. Nechť (G, V, A) je Booleova algebra. Definujme na množině G operace + a ■ takto: pro libovolné x,y G G klademe x + V = (x A y') V (x' A y), x ■ y = x A y. Pak (G, +, •) je Booleův okruh. Poznámka. Všimněte si, že v případě Booleovy algebry (2X, U, Pl) 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 G platí x + 0 = x, x + x = 0, x ■ 1 = x. Dokažme asociativitu sčítání. Nechť x, y, z G G jsou libovolné. Z definice a 28 věty 8.4 plyne (x + y) + z = (((x A y') V (x' A y)) A z') v(((iA y') V (x' A y))' Azj = = (((x A y') V (x' A y)) A z') V ((x' Vy)A(xV y') A z) = = (x A y' A z') V(x' AyA z') V v(((i'Ai) V {x1 Ay1) V(i/Ai) V {y Ay')) Azj = = (x Ay' A z') V(x' AyA z') V (((x' A ?/') V (í/A x)) Azj = = (x Ay' A z') V(x' AyA z') V (x' A y' A z) V (x A y A 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 G jsou opět libovolné. Z definic a věty 8.4 plyne x • y + x • z = ((x A y) A (x A z)') V ((x A y)' A (x A z)) = = (x A y A (x' V z')) V ((x' V y') A x A z) = = (x A y A x') V (x A y A z') V (x' A x A z) V (y' A x A z) = = (x A í/ A z') V (x A y' A z) = = x A ((?/ A z') V (y' A z)) = x • (y + z), což jsme chtěli dokázat. Věta 9.3. Nechť (R, +, •) je Booleův okruh. Definujme na množině R operace V a A takto: pro libovolné x, y G iž klademe xVy = x- y + x + y, x A y = x ■ y. Pak (R, V, A) je Booleova algebra, kde pro každé x G Ä platí x' = x + 1. Důkaz. Je zřejmé, že operace A je komutativní, asociativní a idempo-tentní. Jistě je též operace V komutativní. Snadno se ověří, že také idempo-tentní. Nechť x,y,z G 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 = xV(yVz), 29 a tedy je V asociativní operace. Ověřme absorpční zákony. Nechť x,y,z G R jsou opět libovolné. Platí (x\/y)Ax = (x-y + x + y)-x = x- y- x + x- x + y- x = x- y + x- y + x = x, a také (xAy)\/x = (x-y)-x + (x-y) + x = x- y + x- y + x = x, což jsme chtěli dokázat. Je tedy (R, V, A) svaz. Protože pro každé x G R je xA0 = 2- 0 = 0, platí 0 < x, podobně x Al = 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 A (x + 1) = x-(x + l)=x-x + x = x + x = 0, xV (x + 1) = x-(x + l) + x + (x + l) = 0 + x + x + l = l. Je tedy (R, V, A) komplementární svaz, zbývá ukázat, že je to též svaz distributivní. Nechť tedy x,y,z G R jsou opět libovolné. Platí {x A z)y {y A z) = (x ■ z) ■ (y ■ z) + (x ■ z) + (y ■ z) = = x- y- z + x- z + y- z = (x-y + x + y)-z = = (x V y) A 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. 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 A, které jsou totožné. Musíme to ověřit tedy pouze pro operace + a V. Mějme tedy Booleův okruh (R, +, •), uvažme k němu příslušnou Booleovu algebru (Ä, V, A), a k ní příslušný Booleův okruh (R, ©, •). Pro libovolné x,y G R tedy platí x © y = (x A y') V (x' A 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. 30 Naopak, mějme nyní Booleovu algebru (R, V, A), uvažme k ní příslušný Bo-oleův okruh (R, +,•), a k němu příslušnou Booleovu algebru (R, U,A). Pro libovolné x,y G R pak platí x\Jy = x- y + x + y = x + y+(xAy) = = x + [(y A (x A y)') V (y' A (x A y))^j = x + [(y A (x' V y')) vo) = = x + ((y A x') V (y A y')) = x + ((y A x') V O) = x + (y A x') = = (x A (y A x')') V (x' A (y A x')) = (x A (y' V x)) V (x' Ay) = = x V (x' A y) = (x V x') A (x V y) = 1 A (x V y) = x V y což bylo třeba ověřit. Poznámka. Podobné dvojí pohledy najeden 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. 31