Modulární svazy - charakterizace „zakázaným podsvazem
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.
Věta 6.5. Svaz G je modulární, právě když neobsahuje podsvaz
izomorfní se svazem N5 (pětiúhelníkem).
Důkaz. „⇒ Každý podsvaz libovolného modulárního svazu je
modulární, což N5 není.
„⇐ Dle věty 6.4. existují a, b, c ∈ G splňující a > c,
a ∧ b = c ∧ b, a ∨ b = c ∨ b. Pak podmnožina
{a, b, c, a ∧ b, a ∨ b} ⊆ G je podsvaz G, který není modulární
podle věty 6.4. Protože každý nejvýše čtyřprvkový svaz modulární
je, jsou tyto prvky po dvou různé, proto je b nesrovnatelné s a i c.
Tento podsvaz je tedy izomorfní s N5.
Důsledek. Duální svaz k modulárnímu svazu je opět modulární.
Distributivní svazy - definice
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).
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).
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).
Distributivní svazy - příklady a základní vastnosti
Důsledek. Duální svaz k distributivnímu svazu je opět distributivní.
Příklad. Svaz P(X) všech podmnožin libovolné množiny X je
distributivní. Libovolný řetězec je distributivní.
Věta 7.2. Každý distributivní svaz je modulární.
Důkaz. Nechť G je distributivní svaz, a, b, c ∈ G takové, že c ≤ a.
Pak platí modulární rovnost
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) = (a ∧ b) ∨ c.
Příklad. Svaz N5 (pětiúhelník) ani svaz M5 (diamant) nejsou
distributivní.
Věta 7.3. Podsvaz distributivního svazu je distributivní svaz.
Důkaz. 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. Vlastnost „být distributivní je definována rovností.
Distributivní svazy - ekvivalentní podmínka
Připomeňme:
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)
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. „⇒ Nechť G je distributivní svaz, a, b, c ∈ G splňují
a ∧ b = c ∧ b, a ∨ b = c ∨ b. Z absorpčních zákonů a distributivity
c = (c ∧ b) ∨ c = (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c) =
= (a ∨ c) ∧ (a ∨ b) = a ∨ (c ∧ b) = a ∨ (a ∧ b) = a.
„⇐ Z (2) plyne (1), tedy podle věty 6.4 je G modulární. Nechť
x, y, z ∈ G jsou libovolné. Označme b = y,
a = (y ∨ x) ∧ z ∨ (x ∧ y) = (y ∨ x) ∧ z ∨ (x ∧ y) ,
c = (y ∨ z) ∧ x ∨ (z ∧ y) = (y ∨ z) ∧ (x ∨ z ∧ y) ,
tedy při záměně x ↔ z se zamění a ↔ c. Protože x ∧ y ≤ y, máme
a∧b = y∧(y∨x)∧ z∨(x∧y) = y∧ z∨(x∧y) = (y∧z)∨(x∧y) = c∧b.
Podobně z y ≤ y ∨ x plyne
a∨b = ((y∨x)∧z)∨(x∧y)∨y = ((y∨x)∧z)∨y = (y∨x)∧(z∨y) = c∨b.
Pomocí implikace (2) dostáváme a = c. Z x ∧ y ≤ x plyne
x ∧ a = x ∧ (y ∨ x) ∧ z ∨ (x ∧ y) = x ∧ z ∨ (x ∧ y) =
= (x ∧ z) ∨ (x ∧ y),
x ∧ c = x ∧ (y ∨ z) ∧ (x ∨ (z ∧ y)) = x ∧ (x ∨ (z ∧ y)) ∧ (y ∨ z) =
= x ∧ (y ∨ z).
Celkem tedy x ∧ (y ∨ z) = x ∧ c = x ∧ a = (x ∧ y) ∨ (x ∧ z).
Protože x, y, z ∈ G byly libovolné, je G distributivní svaz.
Distributivní svazy - charakterizace „zakázanými podsvazy
Připomeňme:
Věta 6.5. Svaz G je modulární, právě když neobsahuje podsvaz
izomorfní se svazem N5 (pětiúhelníkem).
Věta 7.6. Modulární svaz G je distributivní, právě když neobsahuje
podsvaz izomorfní se svazem M5 (diamantem).
Důsledek. Svaz G je distributivní, právě když neobsahuje ani
podsvaz izomorfní se svazem M5 (diamantem) ani podsvaz
izomorfní se svazem N5 (pětiúhelníkem).
Důkaz věty 7.6. „⇒ Každý podsvaz libovolného distributivního
svazu je distributivní, což M5 není.
„⇐ Nechť modulární svaz G není distributivní. Podle předchozí
věty 7.5 existují a, b, c ∈ G tak, že a = c, a ∧ b = c ∧ b,
a ∨ b = c ∨ b. Podle věty 6.4 jsou a, c nesrovnatelné. Označme
m = (a ∨ c) ∧ b ∨ (a ∧ c).
Z modularity (díky a ∧ c ≤ a ≤ a ∨ c) plyne
m = (a ∨ c) ∧ b ∨ (a ∧ c) .
Máme tedy v modulárním svazu G prvky a = c, a ∧ b = c ∧ b,
a ∨ b = c ∨ b, m = (a ∨ c) ∧ b ∨ (a ∧ c) = (a ∨ c) ∧ b ∨ (a ∧ c) .
Prvky a, c zde vystupují symetricky, prvek m se nezmění při
záměně a ↔ c.
Pak z modularity
m∨a = ((a∨c)∧b)∨(a∧c)∨a = ((a∨c)∧b)∨a = (a∨c)∧(b∨a),
neboť a ≤ a ∨ c. Protože b ∨ a je horní závora b, c, je
b ∨ a ≥ a ∨ c, odkud m ∨ a = a ∨ c.
Záměnou a ↔ c dostáváme, že m ∨ c = a ∨ c.
Dualizací předchozího výpočtu m ∧ a = a ∧ c = m ∧ c.
Proto {a, c, m, a ∨ c, a ∧ c} je podsvaz svazu G, který podle věty
7.5 není distributivní.
Snadno se ověří, že všechny nejvýše pětiprvkové modulární svazy
jsou distributivní s výjimkou těch, které jsou izomorfní s M5.
Proto je podsvaz {a, c, m, a ∨ c, a ∧ c} izomorfní s M5.
∨-nedosažitelnost
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
neexistují b, c ∈ G splňující b < a, c < a, a = b ∨ c.
Ekvivalentně: 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 indukcí: ∨-nedosažitelný 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 = sup{b ∈ J(G) | b ≤ a} = sup(a↓ ∩ 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 = sup{b ∈ J(G) | b ≤ a} = sup(a↓ ∩ J(G)).
Důkaz. Indukcí vzhledem k počtu m prvků svazu G menších než a.
I. krok. 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í.
II. krok. 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), tedy i supremem.
Nechť tedy a /∈ J(G), pak existují b, c ∈ G splňující b < a, c < a,
a = b ∨ c. Zřejmě oba prvky splňují indukční předpoklad, tedy
a = b ∨ c = sup(b↓ ∩ J(G)) ∨ sup(c↓ ∩ J(G)) =
= sup (b↓ ∩ J(G)) ∪ (c↓ ∩ J(G)) = sup (b↓ ∪ c↓) ∩ J(G) ≤
≤ sup(a↓ ∩ J(G)),
protože (b↓ ∪ c↓) ∩ J(G) ⊆ a↓ ∩ J(G). Ovšem sup(a↓ ∩ J(G)) ≤ a,
protože a je horní závora množiny a↓ ∩ J(G). Dohromady rovnost.
Konečné distributivní svazy
Definice. Nechť (A, ≤) je uspořádaná množina. Podmnožina B ⊆ A
se nazývá dědičná (někdy pro zdůraznění říkáme 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.
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 uspořádanou
množinu (J(G), ≤), tj. 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).
Důkaz. Je-li G prázdný svaz, je i D(J(G)) prázdná množina a věta
platí. Dále předpokládejme, že G je neprázdný.
Definujme zobrazení η : G → D(J(G)) předpisem
η(a) = a↓ ∩ J(G) pro libovolné a ∈ G.
Zřejmě a↓ je dědičná množina v G, proto 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)).
Ukažme, že η je izotonní zobrazení: nechť a, b ∈ G splňují 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 = sup η(a), je tedy η
injektivní: jestliže pro a, b ∈ G platí η(a) = η(b), pak
a = sup η(a) = sup η(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 = x1 ∨ · · · ∨ xn = sup X, 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ý, a tedy nemůže být supremem menších
prvků. 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, tedy
η(a) ⊆ X. Dohromady η(a) = X.
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 = sup η(a) ≤ sup η(b) = b.
Charakterizace konečných distributivních svazů
Věta 7.8. Pro konečný distributivní svaz G uvažme uspořádanou
množinu (J(G), ≤), tj. 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).
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.
Důkaz. 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).
Proto 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 (P(J(G)), ⊆) všech
podmnožin množiny J(G).
Komplementární svazy
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 (diamant) a N5 (pětiúhelník) jsou
komplementární, avšak k některým prvkům existuje komplementů
více než jeden.
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 (pětiúhelník) 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.
Booleovy algebry
Definice. Distributivní komplementární svaz se nazývá Booleova
algebra.
Příklad. Prázdný svaz není 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 .
Příklad. V libovolné Booleově algebře platí 0 = 1, 1 = 0.
Poznámka. Duální svaz k Booleově algebře je Booleova algebra
(komplementy se zachovávají, 0 a 1 se v dualitě vymění).
Příklad. Pro libovolnou množinu X je (P(X), ∪, ∩) 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.
Věta 8.3. Součinem Booleových algeber je Booleova algebra.
Důkaz. Plyne z vět 7.4 a 8.1.
De Morganovy zákony
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 distributivity:
(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.
Booleovy podalgebry Booleovy algebry
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 B tvoří {0, 1} Booleovu
podalgebru. Pro každý a ∈ B je {0, 1, a, a } Booleova podalgebra.
Příklad. Je-li X nekonečná množina, pak
Y = {A ⊆ X; A je konečná nebo X − A je konečná}
je Booleova podalgebra Booleovy algebry (P(X), ∪, ∩).
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.
Homomorfismy Booleových algeber
Definice. Mějme Booleovy algebry G a H a zobrazení f : G → H.
Ř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.
Odtud plyne, že f (a) je komplementem prvku f (a ) v Booleově
algebře H.
Konečné Booleovy algebry
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, A množina všech
jejích atomů. Pak G je izomorfní s Booleovou algebrou
(P(A), ∪, ∩).
Důkaz. Užijeme větu 7.8. Každý atom je ∨-nedosažitelný, stejně
jako prvek 0. Ukážeme, že jiné ∨-nedosažitelné prvky G nemá.
Jestliže ∨-nedosažitelný prvek x ∈ G není atom ani 0, existuje y ∈ G,
že 0 < y < x. Pak x = x ∧ 1 = x ∧ (y ∨ y ) = (x ∧ y) ∨ (x ∧ y ).
Ze ∨-nedosažitelnosti x plyne x = x ∧ y , tj. x ≤ y , odkud y < y ,
tedy y = y ∧ y = 0, spor.
Ukázali jsme, že J(G) = A ∪ {0}, a protože libovolné dva různé
atomy jsou nesrovnatelné, je D(J(G)) = {M ⊆ A ∪ {0} | 0 ∈ M}.
Zřejmě zobrazení f : P(A) → D(J(G)) určené předpisem
f (M) = M ∪ {0} je izomorfismus uspořádaných množin, tedy i
svazů, a věta plyne z věty 7.8.