1 Uspořádané struktury
1.1 Úvod
Slovo “uspořádání"se v přirozeném jazyce používá pro několik různých věcí.
Teorie uspořádých množin je matematická oblast spadající do algebry, která
zavádí matematický pojem “uspořádání na množině". Tento pojem, neformálně
řečeno, není v podstatě nic jiného, než že se pro každé dva prvky
a, b ∈ M dané množiny M rozhodneme, že buď a je v nějákem smyslu menší
než b, nebo b je menší než a, a nebo jsou prvky a a b neporovnatelné.
Jako příklad si představme třeba množinu lidí, které uspořádáme podle jejich
velikosti. V tomto případě bude pro káždé dva prvky (lidi) platit, že buď
člověk a je menší než člověk b, a nebo člověk b je menší než člověk a. To je
příkladem situace, které se říká lineární uspořádaní. Nezajímá nás při tom o
kolik je kdo větší, zajímá nás pouze kdo je větší než kdo.
Jako druhý příklad, vezměme množinu M jejiž prvky budou členové vybrané
rodiny. Tuto množinu můžeme uspořádat pomocí vztahu “je rodič".
U tohoto uspořádání se nám může vyskytnout i třetí situace, ve které jsou
dva prvky neporovnatelné, např. u dvou sourozenců. U tohoto příkladu lze
navíc uspořádání i názorně namalovat pomocí známého rodinného (genealogického)
stromu. Podobné znázornění lze obecně provést u každé uspořádané
množiny, v matematice se toto znázornění nazývá tzv. Hasseův diagram. Někteří
z čtenářů se s daným příkladem možná již setkali v jiném kontextu a to
jako příklad matematického pojmu “stromu"(s vyloučením situace, kdy jsou
předkové příbuzní). Tento pojem spádá do tzv. teorie grafů. Na uspořádané
množiny se lze dívat i jako na grafy, tento pohled však není příliš přínosný.
Grafy obecně nesou více informace, jmenovitě informaci vzdálenosti dvou
prvků. To určitým způsobem omezuje možnosti pro jejich zkoumání, resp.
používají se k řešení jiného typu úloh, u kterých tato informace hraje roli.
Tam kde ne, teorie uspořádání poskytuje výrazně výhodnější algebraické ná-
stroje.
1.2 Základní pojmy
Otázkou je, jakým způsobem lze intuitivní představu pojmu “menší nebo
rovno"takového, který umožňuje i neporovnatelné prvky co nejjednodušeji
matematicky zachytit. Mějme množinu M. Můžeme vytvořit novou množinu
R, která bude obsahovat vybrané dvojce [a, b] prvků a, b ∈ M. Přičemž
1
[a, b] ∈ R bude intuitivně znamenat, že a je menší nebo rovno než b. Množina
všech dvojic prvků z M u kterých záleží na pořadí se označuje M × M
(tzv. Kartézský součin). Takže, množinu R můžeme formálně zadat jako
podmnožinu M × M, tedy jako R ⊆ M × M. Taková množina R se nazývá
relace na množině M.
Příklad 1.1. Zvolme množinu M jako tříprvkovou množinu M = {a, b, c}.
Potom
M × M = {[a, a], [b, b], [c, c], [a, b], [b, a], [a, c], [c, b], [b, c], [c, b]}.
Relace na M je libovolná podmnožina v M × M, například
R1 = {[a, a], [b, b], [c, c], [a, b]}.
Zdůrazněme, že R1 je pouze příkladem jedné z relací na M. Relací na M
existuje tolik kolik existuje různých podmnožin M × M.
Pro zachycení intuitivního pojmu “menší nebo rovno"je však pojem relace
příliš obecný. Respektive, má smyl brát v úvahu jen některé relace. Prvně,
budeme požadovat, aby pro každé a ∈ M platilo, že a je větší nebo rovno
než a, tj. [a, a] ∈ R pro všechna a ∈ M. Tato vlastnost se nazývá reflexivita.
Tedy, relace R se nazývá reflexivní relace pokud pro všechna a ∈ M platí
[a, a] ∈ R.
Druhá vlastnost, kterou budeme po relaci R požadovat je, aby platilo, že
pokud a je menší nebo rovno než b a zároveň b je menší nebo rovno než a,
potom a = b. Taková vlastnost se nazývá symetrie. Tedy, relace R ⊆ M ×M
na množině M se nazývá symetrická relace, pokud pro všechna a, b ∈ M
taková, že [a, b] ∈ R a zároveň [b, a] ∈ R platí, že a = b.
Třetí vlastnost, které se říká tranzitivita nám zachycuje představu, že pokud
a je menší nebo rovno než b a b je menší nebo rovno než c, potom a je
menší nebo rovno než c. Tedy, relace R ⊆ M × M na množině M se nazývá
tranzitivní relace, pokud pro všechna a, b, c ∈ M taková, že [a, b] ∈ R a
[b, c] ∈ R platí, že [a, c] ∈ R.
Libovolná relace R ⊆ M × M na množině M taková, která je reflexivní,
symetrická a tranzitivní se nazáývá relace uspořádání.
Příklad 1.2. Mějme pětiprvkovou množinu M = {a, b, c, d, e}. Rozhodněte,
zda jsou nasledující relace uspořádání.
• R1 = {[a, a], [b, b], [c, c], [e, e], [a, b]},
2
• R2 = {[a, a], [b, b], [c, c], [d, d], [e, e], [c, d], [d, c]},
• R3 = {[a, a], [b, b], [c, c], [d, d], [e, e], [c, d], [d, e]},
• R4 = {[a, a], [b, b], [c, c], [d, d], [e, e]},
• R5 = {[a, a], [b, b], [c, c], [d, d], [e, e], [b, c], [c, d], [b, d]},
• R6 = M × M.
Řešení 1. Relace R1 není uspořádání, jelikož není reflexivní (chybí v ní
prvek [d, d]). Relace R2 je reflexivní i tranzitivní, ale není symetrická (obsahuje
prvky [c, d] a [d, c], přičemž c = d), tedy není uspořádáním. Relace
R3 je reflexivní, symetrická, ale není tranzitivní (obsahuje [c, d] a [d, e], ale
neobsahuje [c, e]), takže není uspořádání. Relace R4 je reflexivní, symetrická
i tranzitivní, tudíž to je relace uspořádání. Stejně tak R5 i R6.
V teorii uspořádání je běžné, že se relace uspořádání značí symbolem ≤ namísto
R, tj. ≤⊆ M × M. Pro prvky a, b ∈ M namísto [a, b] ∈≤ pak píšeme
a ≤ b. Množina M spolu s relací uspořádání ≤ na množině M se nazývá uspořádáná
množina a značí se (M, ≤) (místo slov “relace uspořádání"budeme
říkat krátce “uspořádání", resp. “uspořádání na množině M").
Pro grafické znázornění uspořádané množiny (M, ≤) se používá takzvaný
Hasseův diagram uspořádané množiny (M, ≤). Jde o obrázek obsahující všechny
prvky množiny M namalovaný tak, že pokud a ≤ b, potom b je nakresleno
výše než a a jsou spojeny čarou.
Příklad 1.3. Nechť M je tříprvková množina M = {a, b, c} a uspořádání ≤
je zadáno pomocí a ≤ b, a ≤ c (jinak řečeno ≤= {[a, a], [b, b], [c, c], [a, b], [a, c]}).
Potom Hasseův diagram uspořádané množiny (M, ≤) je
a
cb
V případě, že a ≤ b a b ≤ c, potom z vlastnosti tranzitivity víme, že i a ≤ c.
Obrázek pak namalujeme následovně, prvek a s prvkem c již nespojujeme,
jelikož a je spojen s b a b je již spojeno s c, takže z tranzitivity víme, že i
a ≤ c.
a
b
c
3
Tento příklad taktéž ilustruje, jak budeme uspořádané množiny zadávat.
Vzali jsme v něm nejmenší uspořádání na množině M = {a, b, c} ve kterém
a ≤ b a b ≤ c. Není potřeba vypisovat, že a ≤ c, jelikož to plyne z tranzitivity
a není potřeba vypisovat a ≤ a, b ≤ b, c ≤ c, jelikož to plyne z reflexivity.
Tímto způsobem budem uspořádané množiny zadávat i nadále, bude to vždy
nejmenší uspořádání, které splňuje zadné podmínky.
Příklad 1.4. Popište celou relaci a namalujte Hasseovy diagramy naslédujících
uspořádání (M, ≤1), (M, ≤2), (M, ≤3) a (M, ≤4) na množině M =
{a, b, c, d}.
1. a ≤1 b, b ≤1 c, c ≤1 d.
2. b ≤2 c.
3. a ≤3 c, a ≤3 d, b ≤3 c, b ≤3 d.
4. a ≤4 b, b ≤4 c, a ≤4 d, d ≤4 c.
Řešení 2. První relaci uspořádání ≤1 lze explicitně rozepsat jako
≤1= {[a, a], [b, b], [c, c], [d, d], [a, b], [a, c], [a, d][b, c], [b, d], [c, d]}.
Její Hasseúv diagram je:
Obrázek 1: (M, ≤1)
a
b
c
d
Druhou relaci uspořádání ≤2 lze explicitně rozepsat jako
≤2= {[a, a], [b, b], [c, c], [d, d], [b, c]}.
Její Hasseův diagram je:
Třetí relaci uspořádání ≤3 lze rozepsat jako
≤3= {[a, a], [b, b], [c, c], [d, d], [a, c], [a, d], [b, c], [b, d]}.
4
Obrázek 2: (M, ≤2)
b
c
a d
Obrázek 3: (M, ≤3)
a b
c d
Její Hasseův diagram je:
Čtvrtou relaci uspořádání ≤4 lze rozepsat jako
≤4= {[a, a], [b, b], [c, c], [d, d], [a, b], [a, c], [b, c], [a, d], [d, c]}.
Její Hasseův diagram je:
Obrázek 4: (M, ≤4)
a
b
c
d
Uspořádaná množina (M, ≤) se nazývá lineárně uspořádaná množina pokud
pro každé dva prvky a, b ∈ M platí a ≤ b, nebo b ≤ a. Tedy, libovolné
dva prvky jsou porovnatelné. Hasseův diagram lineárně uspořádané množiny
je vždy svislá čára. Příkladem jsou třeba přirozené (N, ≤), celé (Z, ≤),
racionální (Q, ≤), či reálné čísla (R, ≤) uspořádané podle velikosti.
Poznámka 1.5. Jelikož je podstatně jednodušší dohledávat informace v
angličtině, zmiňme se o anglické terminologii (pokud ji čtenář momentálně
nepotřebuje, může poznámku přeskočit). Překlad termínu “relace na množině"je
bezproblémový, tj. “a relation on a set". Komplikace nastává u pojmu
“uspořádáná množina". Přímý překlad “an ordered set"znamená v různých
anglických textech různé věci. Někdy se používá pro “uspořádáná množina",
5
někdy pro “lineárně uspořádaná množina". V angličtině se proto pojmu “an
ordered set"vyhýbají a pro uspořádánou množinu standardně používájí “a
partially ordered set"(doslovně přeloženo “částečně uspořádaná množina") a
pro lineárně uspořádánou “a lineary ordered set".
1.3 Význačné prvky
Mějme zadanou uspořádanou množinu (M, ≤). Zvolme podmožinu N ⊆ M
množiny M. Řekneme, že a ∈ N je nejmenší prvek podmnožiny N pokud
pro všechna x ∈ N platí, že a ≤ x. Podobně, řekneme, že b ∈ N je největší
prvek podmnožiny N pokud pro všechna x ∈ N platí, že x ≤ b. Pro zadanou
podmnožinu N obecně největší (resp. nejmenší) prvek nemusí existovat
(vezměmě třeba relaci R4 a N = M v příkladu 1.2). Pokud ale existuje, je
vždy jedinný.
Podobný, nicméně odlišný je pojem minimálního, resp. maximálního prvku
podmnožiny N. Zatím co nejmenší prvek a ∈ N podmnožiny N popisoval
vlastnost “a z podmnožiny N je menší než všichni ostatní z N", pojem minimálního
prvku m ∈ N popisuje situaci, kdy “v N není žádný menší prvek
než m ∈ N". Pokud je uspořádání na M lineární, tj. všechny prvky jsou
porovnatelné, pak pojem nejmenšího a minimálního prvku splývají. Pokud
jsou v M i vzájemně neporovnatelné prvky, pak se tyto pojmy mohou lišit,
viz příklad 1.4, relace (M, ≤3), kde a, b ∈ M jsou minimální prvky množiny
M, ale ani jeden z nich není nejmenší. Podobný, nicméně odlišný je pojem
minimálního, resp. maximálního prvku podmnožiny N. Zatím co nejmenší
prvek a ∈ N podmnožiny N popisoval vlastnost “a z podmnožiny N je menší
než všichni ostatní z N", pojem minimálního prvku m ∈ N popisuje situaci,
kdy “v N není žádný menší prvek než m ∈ N". Pokud je uspořádání na M
lineární, tj. všechny prvky jsou porovnatelné, pak pojem nejmenšího a minimálního
prvku splývají. Pokud jsou v M i vzájemně neporovnatelné prvky,
pak se tyto pojmy mohou lišit, viz příklad 1.4, relace (M, ≤3), kde a, b ∈ M
jsou minimální prvky množiny M, ale ani jeden z nich není nejmenší. Formálně
řečeno, prvek m ∈ N se nazývá minimální v podmožině N pokud pro
libovolné x ∈ N takové, že x ≤ m platí, že x = m. Podobně, prvek n ∈ N se
nazývá maximální v podmnožině N pokud pro libovolné x ∈ N takové, že
n ≤ x platí, že x = n.
Do třetice, řekneme, že k ∈ M se nazývá dolní závora podmnožiny N pokud
pro všechna x ∈ N platí, že k ≤ x. Pojem dolní závory se od pojmu nejmenšího
prvku liší v tom, že k nemusí ležet v podmnožině N, ale v množině M.
Dolní závory pro zadanou podmnožinu N nemusí existovat, ale narozdíl od
6
nejmenších prvků jich pro N může existovat více. Podobně, l ∈ M se nazývá
horní závora podmnožiny N pokud pro všechna x ∈ N platí, že x ≤ l.
1.4 Svazy
V následující podkapitole probereme klíčový matematický pojem, a to pojem
svazu.
Uvažujme uspořádanou množinu (M, ≤) a nějakou její podmnožinu N ⊆ M.
Prvek a ∈ M se nazývá infimum množiny N pokud je a největším prvkem
v množině dolních závor podmnožiny N. Infimum množiny N značíme jej
N. Analogicky, prvek b ∈ M se nazývá supremum množiny N, pokud je
b nejmenší dolní závora množiny N, značíme N. Pojem infima i suprema
podmnožiny N je velmi intuitivní, jedná se o největší prvek, který je pod
všemi prvky z N, resp. nejmenší prvek, který je nad všemi prvky podmnožiny
N.
Příklad 1.6. Nechť (M, ≤) je svaz na sedmiprvkové množině M = {a, b, c, d, e, f, g}
s uspořádáním a ≤ b, b ≤ c, b ≤ d, c ≤ e, d ≤ e, e ≤ f, f ≤ h,tj. s Hasseovým
diagramem
Obrázek 5: (M, ≤)
b
c
e
d
a
f
g
Vezměme podmnožinu N1 = {a, b}. Její horní závory jsou prvky b, c, d, e, f, g.
Nejmenší z těchto prvků je b, tedy supremum podmnožiny N1 je b, značíme
N1 = b. Dolní závory N1 jsou pouze a, tedy infimum N1 = a.
Vezměme podmnožinu N2 = {c, d}. Horní závory N2 jsou e, f, g, nejmenší z
nich je e, tedy N2 = e. Dolní závory N2 jsou a, b přičemž největší z nich
je b, tedy N2 = b.
Infimum podmnožiny N v obecném případě nemusí existovat. Důvody mnohou
být dva. Pro zvolenou podmnožinu N se může stát, že množina dol-
7
ních závor je prázdná, viz podmnožina N1 = {a, b} v uspořádané množině
(M1, ≤1) zadané diagramem
Obrázek 6: (M1, ≤1)
b
c
a d
Druhý případ, kdy infimum neexistuje je, pokud množina dolních závor je sice
neprázdná, nicméně nemá největší prvek, vezměme podmnožinu N2 = {c, d}
v (M2, ≤2) zadané diagramem
Obrázek 7: (M2, ≤2)
a b
c d
Uspořádaná množina (M, ≤) se nazývá svaz, pokud pro libovolnou konečnou
podmnožinu N existuje suprémum i infimum. Svazy jsou klíčové matematické
objekty a vyskytují se ve všech oblastech matematiky. Teorie svazů
je jednou ze základních částí moderní algebry.
Příklad 1.7. Příklady svazů:
(i) (M, ≤1) a (M, ≤4) z příkladu 1.2,
(ii) (M, ≤) z příkladu 1.4,
(iii) přirozená čísla N spolu s obvyklým uspořádáním podle velikosti ≤, tj.
(N, ≤),
(iv) podobně celá, racionální, reálná čísla s obvyklým uspořádáním, tj.
(Z, ≤), (Q, ≤) a (R, ≤).
Příklad 1.8.
Věta 1.9. Nechť (M, ≤) je uspořádaná množina ve které pro libovolné a, b ∈
M existuje {a, b} i {a, b} (tj. pro libovolou dvouprvkovou podmnožinu
existuje infimum a supremum). Potom (M, ≤) je svaz.
8
Důkaz. Pro ověření definice svazu je potřeba ukázat, že z existence suprema
a infima dvouprvkových podmnožin množiny M už nutně plyne i existence
suprema a infima všech konečných podmnožin množiny M.
Předpokládejme tedy, že existují infima a suprema všech dvouprkových podmnožin.
Vezměme libovolnou konečnou podmnožinu N ⊆ M množiny M
a zkusíme ukázat, že existuje její suprémum. Jelikož je N konečná, můžeme
si její prvky označit pomocí a1, a2, dots, an pro nějaké n ∈ N tj. N =
{a1, dots, an}. Jelikož předpokládáme, že existují suprema dvouprvkových
podmnožin, víme, že existuje prvek {a1, a2}. Stejně tak existuje prvek
{ {a1, a2}, a3}. Takto můžeme postupně přidat všechny prvky N, tj. existuje
prvek a = { {· · · { {a1, a2}, a3} . . . , an−1}, an}.
Jelikož je a supremum a tedy horní závora prvků an a {· · · { {a1, a2}, a3} . . . , an−1},
víme, že an ≤ a a {· · · { {a1, a2}, a3} . . . , an−1} ≤ a. Podobně, z definice
an−1 ≤ {· · · { {a1, a2}, a3} . . . , an−1}. Složením s předchozí nerovností
a použitím tranzitivity získáme an−1 ≤ a. Opakováním úvahy dostaneme, že
ai ≤ a pro libovolný index i ∈ 1, . . . , n. Tedy a je horní závorou podmnožiny
N.
Abysme ukázali, že a supremum, tj. nejmenší horní závora, je potřeba ukázat,
že pro libovolnou jinou horní závoru b ∈ M podmnožiny N platí a ≤ b.
Předpokládejme tedy, že b je horní závora podmnožiny N. Potom z definice
b je i horní závorou podmnožiny a1, a2 ⊆ N, tj. (a1 ∨ a2) ≤ b. Jelikož a3 ≤ b,
potom i (a1 ∨ a2) ∨ a3 ≤ b. Tímto způsobem můžeme postupovat dále a
dostaneme, že (. . . ((a1 ∨ a2) ∨ a3) ∨ a4) · · · ∨ an−1) ∨ an) ≤ b. To ale není nic
jiného, než že a ≤ b.
Existence infim se ukáže analogicky.
Předcházející věta nám říká, že pro ověření zda-li je uspořádaná množina
(M, ≤) svaz stačí ověřit, že existují suprema a infima dvouprvkových pod-
množin.
Pro označení infima (suprema) dvouprvkové podmnožiny {a, b} ⊆ M, a, b ∈
M budeme namísto symbolu {a, b} ( {a, b}) používat symbol a∧b (a∨b),
tedy a ∧ b = {a, b} (a ∨ b = {a, b}).
V tento okamžik čtenáři doporučuje připomenutí si základních definic z algebry
resp. definici grupy, se kterou bude následující úzce souviset. Připomeňme,
že operace ∗ na množině M je definována jako zobrazení ∗ :
M × M → M. Tedy, jedná se o předpis, který dvoum prvkům přiřadí třetí.
Jako příklad můžeme za množinu M vzít přirozená čísla, tj. M = N, s operací
9
sčítání, tedy ∗ = +.
Vezměme nyní libovolný svaz (M, ≤). Pro libovolné dva prvky a, b ∈ M jsme
schopni z definice svazu najít a ∨ b, tj. dvěma prvkům a, b přiřadíme třetí
a ∨ b. Tedy, ∨ nám zadává operaci na množině M. Stejně tak nám ∧ zadává
operaci na množině.
Příklad 1.10. Mějme svaz (M, ≤), zadaný pomocí M = {a, b, c, d} jako
a ≤ b, b ≤ c, a ≤ d, d ≤ c.
Obrázek 8: (M, ≤4)
a
b
c
d
Sestrojme nyní, stejně jako se to dělalo u grup, tabulky operací ∨ a ∧. Výsledek
operace lze vyčíst z tabulky na příslušné pozici, např. b ∨ d = c.
∨ a b c d
a a b c d
b b b c c
c c c c c
d d c c d
∧ a b c d
a a a a a
b a b b a
c a b c d
d a a d d
K tabulkám operací z předchozího příkladu se vrátíme později, nyní mějme
jen na paměti, že na ∨ a ∧ lze pohlížet jako na operace. Stejně jaku grup se
lze bavit o vlastnostech těchto operací ∨ a ∧. Ideálně, zkusíme najít takové,
které budou pro ∨ a ∧ platit v libovolném svazu (M, ≤). První taková důležitá
vlastnost je komutativita. Symbolem ∗ nyní budeme značit libovolnou
operaci na množině M. Operace ∗ : M × M → M na množině M se nazývá
komutativní pokud pro všechna a, b ∈ M platí
10
a ∗ b = b ∗ a.
Druhá důležitá vlastnost operace je, zda-li, pokud operaci provedeme s více
prvky po sobě, záleží na pořadí. Jinak řečeno zda nám záleží na uzávorkování.
Formálně zapsáno, zda pro libovolné a, b, c ∈ M platí
(a ∗ b) ∗ c = a ∗ (b ∗ c).
Pokud je to splněno, říkáme, že operace ∗ je asociativitivní. Pro jednoduchou
představu operace, která je komutativní a asociativní si lze představit přirozené
čísla N s operací sčítání, tj. (N, +). Případně přirozená čísla s násobením
(N, ·).
Další vlastnosti se říká idempotence. Operace ∗ na množině M se nazývá
idempotentní pokud pro všechna a ∈ M platí
a ∗ a = a.
Přirozená čísla se sčítáním (N, +) ani s násobením (N, ·) již idempotetní
nejsou. (N, ·) má jedný idempotetní prvek a to 1, jelikož 1 · 1 = 1.
Věta 1.11. Nechť (M, ≤) je svaz. Potom pro libovolné a, b ∈ M platí
a ∨ b = b ∨ a,
a ∧ b = b ∧ a.
Tedy, operace ∨ a ∧ jsou komutativní.
Důkaz.
Věta 1.12. Nechť (M, ≤) je svaz. Potom pro libovolné a, b, c ∈ M platí
(a ∨ b) ∨ c = a ∨ (b ∨ c),
(a ∧ b) ∧ c = a ∧ (b ∧ c).
Tedy, operace ∨ a ∧ jsou asociativní.
Důkaz.
11
Tedy, pro libovolný svaz (M, ≤), (M, ∨) a (M, ∧) jsou komutativní polo-
grupy.
Věta 1.13. Nechť (M, ≤) je svaz. Potom pro libovolné a ∈ M platí
a ∨ a = a,
a ∧ a = a.
Tedy, operace ∨ a ∧ jsou idempotetní.
Důkaz.
Poslední vlastnost se váže k takové množině M, na ktere jsou definované
dvě operace, označme si je ∗ a ◦. Řekneme, že na M platí absorbční zákony
pokud pro libovolné a, b ∈ M platí
a ∗ (a ◦ b) = a,
a ◦ (a ∗ b) = a.
Absorbční zákony již nejsou jednoduše představitelné tak, jako vlastnosti
předchozí, což momentálně nevadí. Důležité je si uvědomit, že nám říkájí,
že zmíněné dvě operace ∗ a ◦ jsou nějakým způsobem provázány, jsou na
sobě závislé. Pokud zvolíme jednu ∗, potom ◦ nelze zvolit libovolně, ale musí
nějak s ∗ “spolupracovat".
Věta 1.14. Nechť (M, ≤) je svaz. Potom pro libovolné a, b ∈ M platí
a ∨ (a ∧ b) = a,
a ∧ (a ∨ b) = a.
Tedy, pro operace ∨ a ∧ platí absorbční zákony.
Důkaz.
Tedy, shrneme-li předcházející sérii tvrzení, v kazdém svazu (M, ≤) platí pro
operaci ∨ a ∧ komutativita, asociativita, idempotence a absorbční zákony.
Vraťme se nyní k příkladu 1.10. Tam jsme ze znalostí uspořádání ≤ na svazu
(M, ≤) odvodili výsledky operací ∨ a ∧, a byli schopni napsat jejich tabulky.
Nabízí se otázka, pokud by nám někdo zadal pouze množinu M a dvě uvedené
12
tabulky operací ∨ a ∧, ovšem neřekl nám nic o tom, jak vypadá uspořádání
≤, jestli ze zmíněných tabulek operací můžeme jednoznačně uspořádání ≤
odvodit. Odpověď zní - ano. K tomu, jak to provést nám pomůže následující
věta.
Věta 1.15. Nechť (M, ≤) je svaz. Pro libovolné a, b ∈ M platí
a ≤ b právě tehdy když a ∨ b = b
a
a ≤ b právě tehdy když a ∧ b = a.
Důkaz.
Příklad 1.16. Mějme tříprvkovou množinu M = {a, b, c}. Mějme zadné
tabulky operací ∨ a ∧ jako
∨ a b c
a a b c
b b b c
c c c c
∧ a b c
a a a a
b a b b
c a b c
Odvoďte uspořádání ≤ na M a namalujte Hasseův diagram.
Řešení 3. Pomocí věty 1.15 zjistíme z a ∨ b = b, že a ≤ b. Podobně, z
b ∨ c = c, že b ≤ c. Což nám stačí, jelikož uspořádání již nemůže vypadat
jinak než:
a
b
c
13
Přejděme nyní k další úvaze. V předchozím příkladě se nám pomocí věty
1.15 podařilo zjistit uspořádání ≤ na množině M z tabulky operací ∨ a ∧.
Tedy, známe-li operace ∨ a ∧ na konkrétním svazu (M, ≤), jednoznačně z
nich odvodíme uspořádání ≤. Nicméně, u tabulek v předchozím příkladě nám
bylo dopředu řečeno, že jde o tabulky svazových operací ∨ a ∧. Otázka zní,
jestli je možné svazové uspořádání tímto způsobem odvodit z jakýchkoliv
dvou zadaných tabulek, tj. z libovolných dvou zadaných operací na množině
M. Není těžké ukázat, že to nelze. Stačí si vzít dvouprvkovou množinu M =
{a, b} s tabulkou operace
∨ a b
a a a
b a a
Problém zde je, že b∨b = a, což není možné, protože podle věty 1.13 operace
suprema ∨ ve svazu M musí být idempotentní, tedy musí platit b∨b = b. Svaz
s výše zmíněnou tabulkou operace suprema tedy neexistuje. Naši otázku tedy
modifikujeme a zeptáme se, jestli pro zadanou množinu M a dvojci operací
∗ a ◦ na M neexistují nějaké vlastnosti těchto operací které nám zajistí, že
bude existovat svaz (M, ≤) takový, že ∗ = ∨ a ◦ = ∧. Na tuto otázku odpoví
následující věta.
Věta 1.17. Nechť M je množina a ∗ a ◦ operace na M. Pokud jsou obě tyto
operace komutativní, asociativní, idempotentní a splňují absorbční zákony,
potom existuje jednoznačně určený svaz (M, ≤) takový, že ∗ = ∨ a ◦ = ∧.
Důkaz.
Spolu s poznámkou za větou 1.14 dostáváme, že dvě operace ∗ a ◦ na množině
M jednoznačně zadávají svaz pomocí ∗ = ∨ a ◦ = ∧ právě tehdy když jsou
komutativní, asociativní, idempotetní a splňují absorbční zákony.
Tento poznatek je důležitý, protože nám umožňuje svaz zadefinovat jiným
způsobem. Konkrétně, svaz lze definovat jako množinu M se dvěma operacemi
∨ a ∧, které jsou komutativní, asociativní, idempotentní a splňují
absorbční zákony. Tento fakt zdůrazňujeme tím, že svaz zapisujeme jako
(M, ∨, ∧). Pomocí věty 1.17 a věty 1.15 pak z (M, ∨, ∧) můžeme odvodit
svaz jako uspořádanou množinu (M, ≤).
Důvodů proč nás tohle zajímá je vícero. Obě vyjádření svazu (M, ∨, ∧) a
(M, ≤) mají svou užitečnost. Výhodou (M, ≤) je, že skutečne vidíme, jak
uspořádání vypadá, např. můžeme nakreslit jeho Hasseuv diagram. Naproti
14
tomu vyjádření (M, ∨, ∧) je vhodnější z algebraického hlediska. Moderní algebra
se zabývá množinami s operacemi. Pokud čtenář prošel základním kurzem
algebry, setkal s grupami - což jsou množiny s operací se specifickými
vlastnostmi, jejich homomorfismy, jejich faktorizacemi a podobně. Stejně tak
v předmětu pracujícím s lineární algebrou narazil na vektorové prostory - což
jsou opět množiny s operacemi, jejich lineární zobrazení (což je jen jiný název
pro homomorfismy), báze, dimenze a podobně. Vyjádření svazu jako množiny
s operacemi (M, ∨, ∧) nám umožňuje tyto pojmy fomulovat i pro svazy,
tj. bavit se o homomorfismech svazů, faktorizaci svazů, bazích atd.
2 Podsvazy, homomorfismy
V této krátké kapitole zavedeme dva základní algebraické pojmy týkající se
svazů. Prvním bude pojem podsvazu.
Definice 2.1. Podmnožina N ⊆ M svazu (M, ≤) se nazývá podsvaz svazu
(M, ≤) pokud pro všechna a, b ∈ N platí (a ∧ b) ∈ N, (a ∨ b) ∈ N.
Jinak řečeno, podsvaz N svazu (M, ≤) je podmnožina uzavřená na operace.
Čtenáři doporučujeme tuto definici srovnat s definicí podgrupy H
grupy (G, ∗), či podprostoru vektorového prostoru, jelikož jde o úplně stejnou
úvahu.
Nechť (M, ≤). Uvažujme libovolné a, b ∈ M. Symbolem [a, b] označíme podmnožinu
[a, b] ⊆ M, [a, b] = {x ∈ M | a ≤ x ≤ b}. Symbol [a, b] tedy
označuje množinu všech prvků ležících mezi prvky a, b ∈ M. Všiměme si,
že [a, b] je podsvaz. To není těžké ukázat, zřejmě pro libovolné x, y ∈ [a, b]
dostaneme (x∨y) ∈ [a, b] i (x∧y) ∈ [a, b]. Takovému podsvazu budeme říkat
intervalový podsvaz [a, b] svazu (M, ≤).
Druhým důležitým pojmem je izomorfismus dvou svazů.
Definice 2.2. Zobrazení f : M → L se nazývá izomorfismus ze svazu
(M, ∨M , ∧M ) do svazu (L, ∨L, ∧L) pokud je f bijekce a zároveň platí
f(a ∨M b) = f(a) ∨L f(b),
f(a ∧M b) = f(a) ∧L f(b).
Opět, odkazujeme čtenáře na pojem izomorfismu grup, případně vektorových
prostorů, kde jde o analogický pojem bijektivního zobrazení, které zachovává
15
operace. Pokud bychom vynechali podmínku bijekce, dostaneme homomorfismus
svazů, nicméně ten v tomto textu nebudeme potřebovat.
Pokud mezi dvěma svazy existuje (M, ∨M , ∧M ) a (L, ∨L, ∧L) existuje izomorfismus
f : M → L, znamená to (podobně jako u grup), že jsou tyto svazy
“stejné"(z algebraického hlediska), mají stejnou strukturu. Pokud bysme namalovali
jejich Hasseovy diagramy, půjde o stejné obrázky.
3 Modulární svazy
Jeden z pohledů na algebraické struktury, tj. množiny s operacemi, je, že
vznikly z konkrétních matematických objektů tím, že “zapomeneme"všechny
ostaní vlastnosti které nesouvisí s operací na daném objektu. Například, u
celých čísel Z se můžeme bavit o grupě (Z, +). Samořejmě, konkrétní grupa
(Z, +) má víc vlastností než úplně libolná obecná grupa (G, ∗). V té máme
zajištěnou platnost pouze axiomů grupy. Pointa je, že bysme chtěli nikoliv
nejprve zadefinovat Z a pak z něj abstrahovat grupu (Z, +), ale naopak vzít
si obecnou grupu (G, ∗) a najít nějakou (algebraickou) vlastnost, která nám
zajistí, že (G, ∗) bude izomorfní (stejná jako) (Z, +). V tomto konkrétním
případě (Z, +) to lze udělat. Libovolná gurupa (G, ∗) je izomorfní se (Z, +)
právě tehdy když (G, ∗) je generovaná jedním prvkem a je nekonečná.
Pro zadanou grupu (G, ∗) můžeme uvažovat množinu S(G), která obsahuje
všechny její normální podgrupy. Tuto množinu můžeme uspořádat množinovou
inkluzí ⊆. Není těžké dokázat (viz třeba ...), že (S(G), ⊆) je svaz.
Modulární svazy, o kterých se budeme bavit v této kapitole, vznikly abstrakcí
svazu všech normálových podgrup (S(G), ⊆), resp. obecněji faktoralgeber.
Tedy, i poprostory vektorového prostoru, či ideály okruhu uspořádané
množinovou inkluzí ⊆ tvoří modulární svaz (pokud čtenář pojmy z tohoto
odstavce nezná, tak to ničemu nevadí).
Přejděme nyní k definici modularity. Svaz (L, ≤) se nazývá modulární svaz
pokud pro libovolné a, b, c ∈ L takové, že a ≤ b platí
a ∨ (c ∧ b) = (a ∨ c) ∧ b.
Z této definice samozřejmě není hned viditelné, co by tahle podmínka měla
znamenat a proč by svazy, které ji splňují měli někoho zajímat. Než ovšem
uvádět příklady svazů které podmínku splňují, pro pochopení jejího vznamu
je lepší pokusit se najít nějaký svaz, který ji nesplňuje. Půjdeme postupně
od nejmenších svazů, které známe.
16
0.) Svaz na prázdné množině (∅, ≤) triviálně splňuje vše.
1.) Pro jednoprvkový svaz (L1, ≤), L = {x} není těžké ověřit, že podmínka
je splňena, jelikož jedinný případ, co může nastat je
x ∨ (x ∧ x) = x = (x ∨ x) ∧ x.
2.) Dvouprvkový svaz existuje (až na izomorfismus) pouze jeden, a to (L2, ≤),
kde L2 = {x, y} a x ≤ y. Dosazováním prvků do definice modularity:
x ∨ (x ∧ x) = x = (x ∨ x) ∧ x,
x ∨ (y ∧ x) = x = (x ∨ y) ∧ x,
x ∨ (x ∧ y) = x = (x ∨ x) ∧ y,
x ∨ (y ∧ y) = y = (x ∨ y) ∧ y,
y ∨ (x ∧ y) = y = (y ∨ x) ∧ y,
y ∨ (y ∧ y) = y = (y ∨ y) ∧ y.
Tedy (L2, ≤) je modulární.
3.) Tříprvkový svaz existuje (až na izomorfismus) také pouze jeden, a to
(L3, ≤), kde L3 = {x, y, z} a x ≤ y ≤ z. Zde je pořeba ověřit více kombinací,
nicméně prozradíme čtenáři, že i (L3, ≤) je modulární svaz.
4.) Čtyřprovkové svazy existují dva neizomorfní, jmenovitě (L4, ≤L) a (S4, ≤S
).
Obrázek 9: (L4, ≤L), (S4, ≤S)
w
v
x
y
w
v
x y
Opět, postupným dosazováním prvků od rovnosti z definice modularity lze
dojít k závěru, že oba tyto svazy jsou modulární.
17
5.) Až pětiprvkové svazy přinesou změnu. Existuje pět neizomorfních pětiprvkových
svazů. Jejich nalezení je pro čtenáře jednoduché, ale důležité
cvičení. Čtyři z nich opět budou modulární. Zaměřme se nyní na svaz který
označíme jako (M5, ≤). Tento svaz bude definován pomocí M5 = {x, y, z, v, w}
a vyztahů w ≤ x ≤ y ≤ v a w ≤ z ≤ vviz obrázek.
Obrázek 10: (M5, ≤)
z
w
v
x
y
Postupným dosazováním do rovnosti z definice modularity se dostaneme k
případu
x ∨ (z ∧ y) = x = y = (x ∨ z) ∧ y,
tedy (M5, ≤) není modulární. Tento svaz je klíčovým příkladem díky následující
větě.
Věta 3.1. Nechť (L, ≤) je svaz. Potom (L, ≤) je modulární právě tehdy když
neobsahuje podsvaz izomorfní svazu (M5, ≤).
Důkaz.
Předešlá věta nám dává způsob, jak (z obrázku) rozhodnout, zda zadaný
svaz (L, ≤) je či není modulární. Pokud se nám v (L, ≤) podaří najít podsvaz
který vypadá jako (M5, ≤), potom víme, že (L, ≤) není modulární. Pokud
se nám to naopak nepodaří, potom (L, ≤) modulární je.
Pro pochopení smyslu modulárních svazů nám poslouží nasledující věta.
Věta 3.2. Nechť (L, ≤) je svaz. Potom (L, ≤) je modulární právě tehdy když
pro každé dva prvky a, b ∈ L platí, že intervalové podsvazy [a∧b, a] a [b, a∨b]
jsou izomorfní.
Pro dané prvky a, b ∈ L je zmíněný izomorfismus f : [a ∧ b, a] → [b, a ∨ b]
určen předpisem f(x) = x ∨ b.
...obrazek (viz https: // en. wikipedia. org/ wiki/ Modular_ lattice# Diamond_
isomorphism_ theorem )
18
Důkaz.
Pro ilustraci významu předchozí věty uvažujme modulární svaz (L, ≤) zadáný
následujícím obrázkem
Obrázek 11: (L, ≤)
a ∧ b
a b
a ∨ b
Zvolme si dva prvky, např. a, b ∈ L vyznačené na obrázku. Z něj pak dobře
vydíme, že prvky které se nachází mezi a ∧ b a a (tj. z intervalu [a ∧ b, a] )
mají stejnou strukturu (zadávají stejný obrázek) jako prvky, které leží mezi
b a a ∨ b.
Čtenář si múže vybrat libovolné dva jiné prvky a vyzkoušet si, že tato vlastnost
opět bude platit.
Zdůrazněme, že díky slovům “právě tehdy"ve větě 3.2 platí i obrácený směr.
Tj. pokud libovolný svaz (L, ≤) splňuje výše popsanou vlastnost pro každé
dva své prvky, potom je modulární. Modulární svazy si tedy můžeme představovat
jako přesně ty svazy, které mají výše popsanou vlastnost.
19
4 Distributivní svazy
Další důležitou skupinou svazů jsou takzvané distributivní svazy. Distributivita
je vlastnost, se kterou se každý čtenář již setkal již na základní škole a to
v pojmu “vytýkání před závorku"při počítání s reálnými čísly. Jinak řečeno,
víme, že (5 · 3) + (5 · 4) je to samé jako 5(3 + 4). Obecně zapsáno, pro libovolné
x, y, z ∈ R platí x(y + z) = (x · y) + (x · z). Této vlastnosti se v algebře
říka distributivita. Obecně, nemusíme se omezovat na reálná čísla s operací
sčítání a součinu (R, +, ·), ale tuto vlastnost můžeme uvažovat u libovolné
množiny se dvěma operacemi (M, ∗, ◦). Tedy, dává smysl ji uvažovat také u
svazu (L, ∨, ∧).
Svaz (L, ≤) se nazývá distributivní svaz pokud pro libovolné a, b, c ∈ L platí
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ b).
Nyní ukážeme, jak budou distributivní svazy vypadat. Analogicky jako v
předchozí kapitole zkusíme najít co nejmenší svaz, který naopak distributivní
není. Pro stručnost ovšem prozradíme čtenáři, že všechny svazy které mají
4 či méně prvků distributivní jsou (což lze opět ověřit dosazováním jejich
prvků do definice distributivity).
Nyní se vraťme k nejmenšímu svazu, který nesplnil podmínku modularity,
tj. k pětiprvkovému svazu (M5, ≤) zadaného pomocí M5 = {x, y, z, v, w} a
vyztahů w ≤ x ≤ y ≤ v a w ≤ z ≤ v. Postupným dosazováním prvů se
dostaneme k případu
y ∨ (x ∧ z) = y = x = (y ∨ x) ∧ (y ∨ z).
tedy, (M5, ≤) není distributivní svaz.
Podívejme se nyní na další příklad pětiprvkového svazu, a to svazu (N5, ≤)
zadaného pomocí N5 = {x, y, z, v, w} a vyztahů w ≤ x ≤ v, w ≤ y ≤ v a
w ≤ z ≤ v (viz obrázek).
20
Obrázek 12: (N5, ≤)
z
w
v
x y
Opět, ověřujeme-li postupně podmínku distributivity pro jednotlivé prvky,
dostaneme se k případu
x ∨ (y ∧ z) = x = v = (x ∨ y) ∧ (x ∨ z).
Tedy ani (N5, ≤) není distributivní. Není těžké (nicméně zdlouhavé) ukázat,
že pětiprvkové svazy jiné než (M5, ≤) a (N5, ≤) distributivní jsou. Svazy
(M5, ≤) a (N5, ≤) jsou duležitými příklady, jak ukazuje následující věta.
Věta 4.1. Nechť (L, ≤) je svaz. Potom (L, ≤) je distributivní právě tehdy
když neobsahuje podsvaz izomorfní svazu (M5, ≤), nebo (N5, ≤).
Důkaz.
S trochou zamyšlení nad předchozí větou a větou 3.1 vidíme, že každý distributivní
svaz je modulární. Z nich dále plyne následující důsledek
Corollary 4.2. Svaz (M, ≤) je distributivní právě tehdy, pokud je modulární
a neobsahuje podsvaz izomorfní s (N5, ≤).
Tedy, množina distributivních svazů je podmnožinou modulárních svazů přesně
takových, které neobsahují (N5, ≤) jako podsvaz. Proč nás tento fakt zajímá
a k čemu se hodí, když modulární svaz neobsahuje podsvaz (N5, ≤) si nenechte
ujít v následující kapitole.
5 Komplementární svazy
Nyní představíme ještě jeden důležitý pojem a to je pojem komplementu.
Nechť (L, ≤) je svaz obsahující největší prvek 1 ∈ L a nejmenší prvek 0 ∈ L.
Nechť a ∈ L. Prvek a ∈ L se nazývá komplement prvku a ∈ L pokud platí
a ∨ a = 1 a zároveň a ∧ a = 0.
21
Příklad 5.1. Najděte komplementy jednotlivých prvků u svazů zadaných
následujícími diagramy:
Obrázek 13: (C, ≤C), (D, ≤D), (B, ≤B), (U, ≤)
w
v
x
y
a
b
c
d
0
x y z
k
l
m
1
0
p q r s
1
Řešení 4. První svaz (C, ≤C) je řetězec. Vidíme, že pro prvky x, y ∈
Ckomplementy neexistují. Je jasné, že třeba pro x zde není žádný prvek
t takový, pro který by platilo x ∨ t = v a x ∧ t = w. Stejně tak pro y. Komplement
v prvku v je w, tedy w = v . Komplement w prvku w je prvek
v = w .
V druhém svazu (D, ≤D) mají všechny prvky komplementy. Komplement
a prvku a je c, komplement b prvku b je d, komplement c prvku c je a a
komplement d prvku d je b.
Ve třetím svazu (B, ≤B) mají opět všechny prvky komplement. Jsou to:
0 = 1,
x = m,
y = l,
z = k,
k = z,
l = y,
m = x,
1 = 0.
Ve čtvrtém svazu (U, ≤) mají opět všechny prvky komplement, nicméně komplementy
nejsou jednoznačné. Komplementy prvku p jsou prvky q, r, s, protože
vidíme, že platí p ∨ q = 1, p ∧ q = 0, ale taky p ∨ r = 1, p ∧ r = 0 a
zároveň p ∨ s = 1, p ∧ s = 0. Komplementy prvku q jsou prvky p, r, s atd.
Jak je vidno z předchozích příkladů, svaz může obsahovat prvky, pro které
22
komplement neexistuje (viz svaz (C, ≤C)) a stejně tak prvky, které mají
komplementů více (viz svaz (U, ≤)).
Svaz (L, ≤), ve kterém pro každý prvek a ∈ L existuje alespoň jeden komplement
a ∈ L se nazývá komplementární. Zamysleme se nyní, jakou podmínkou
v komplementárním svaze zajistit, aby pro každý prvek a ∈ L existoval
přesně jeden komplement a ∈ L. Pokud požadujeme, aby v komplementárním
svazu existoval pro každý prvek a ∈ L právě jeden komplement a ∈ L,
tak vlastně požadujeme, aby v L neexistovali tři prvky x, y, z ∈ L takové, že
x ∨ y = 1, x ∨ z = 1, y ∨ z = 1,
x ∧ y = 0, x ∧ z = 0, y ∧ z = 0.
Jinak řečeno, aby byly komplementy jednoznačné, komplementární svaz L
nesmí obsahovat podsvaz
Obrázek 14: (N, ≤)
z
0
1
x y
Věta 4.1 nám říká, že pokud je svaz distributivní, neobsahuje podsvaz (N5, ≤
), tedy neobsahuje ani podsvaz výše uvedený podsvaz. Dostáváme tedy:
Věta 5.2. Nechť (L, ≤) je komplementární svaz. Pokud je (L, ≤) distributivní,
potom pro každé a ∈ L existuje právě jedno a ∈ L, takové, že a∨a = 1
a a ∧ a = 0. Jinak řečeno, pro každé a ∈ L existuje právě jeden komplement
a ∈ L. .
Důkaz.
Distribitvita nám tedy v komplementárním svazu zajišťuje jednoznačnost
komplementů. Nabízí se i obrácená otázka, tedy jestli svaz, ve kterém má
každý prvek jednoznačný komplement musí být distributivní. To obecně neplatí,
nicméně ve spoustě důležitých skupin svazů jako jsou třeba modulární
ano. Na distributivitu se tedy můžeme dívat jako na vlastnost, která nám
23
v komplementárních svazech zajišťuje jednoznačnost komplementů. Zdůrazněmě,
že pouze v komplementárních svazech, existují distributivní svazy,
které nejsou komplementární, tj. existují v nich prvky, které nemají žádný
komplement, viz příklad ...
6 Booleovy algebry
Komplementární distributivní svaz (L, ≤) se nazývá Booleův svaz, nebo též
Booleova algebra. Dvě názvy téže věci souvisí s pohledem na svazy jako
na množiny s uspořádáním (L, ≤) a jako na množiny s dvěma operacem
(L, ∨, ∧), tedy jako na algebry.
Většina studentů pravděpodobně již slova Booleova algebra, případně Booleova
logika zaslechla, a to v logice na středí škole, případně v aplikovaných
předmětech. To úzce souvisí s významem a použitím Booleových algeber. K
tomu se dostaneme v druhé části kapitoly, nyní ještě chvíli zůstanem v matemtice
a zaměříme se na jednu z důležitých vlastností Booleových algeber.
Příklad 6.1. Vraťme se k příkladu tříprvkové množiny X = {a, b, c} a množiny
všech jejích podmnožin P(X). Tedy P(X) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Jako uspořádání na P(X) množinovou inkluzi ⊆ , tj. například {a} ⊆ {a, b}.
Potom (P(X), ⊆) je svaz.
Obrázek 15: (P(X), ⊆)
∅
{a} {b} {c}
{a, b}
{a, c}
{b, c}
{a, b, c}
Porozkoumáním obrázku a použítím věty ... zjistíme, že jde o distributivní
svaz. Dále, pro každý prvek lze nalézt jeho komplement, konkrétně ∅ =
{a, b, c}, {a} = {b, c}, {b} = {a, c}, {c} = {a, b}, {a, b} = {c}, {a, c} =
{b}, {b, c} = {a}, {a, b, c} = ∅. Jde tedy o distributivní komplementární
svaz, (P(X), ⊆) je tedy Booleova algebra.
24
Vidíme taky, že pro libovolné podmnožiny A, B ∈ P(X), suprémum A∨B je
rovno sjednocení množin A∪B, tj. A∨B = A∪B. Podobně A∧B = A∩B.
Výše uvedený příklad jde zobecnit. Nemusíme brát X pouze tříprvkouvou,
ale můžeme vzít libovolnou množinu. Tedy, pro libovolnou množinu X, množina
všech podmnožin P(X) uspořádaná množinovou inkluzí ⊆ je Booleova
algebra (P(X), ⊆). Pro konkrétní podmnožinu A ∈ P(X), komplement A
bude její množinový doplňek, tedy A = X − A. Množiny všech podmnožin
jsou důležitým příkladem Booleových algeber.
Zkusme si nyní vyřešit trochu jiný úkol, a to, pokusme se najít všechny
možné Booleovy algebry, které mají 8 prvků. Tedy, čtenář se může pokusit
malovat si různé osmiprvkové svazy tak, aby byly zároveň distributivní a
komplementární. Po krátké snaze mu ale stejně prozradíme, že jedinný takový
obrázek, který se mu podaří najít bude stejný jako obrázek v příkladu
6.1. Jinak řečeno, každá osmiprvková Booleova algebra je izomorfní svazu
podmnožin P(X) tříprvkové množiny X.
Naše otázka zní, platí-li něco podobného i obecněji. Odpověď je možná překvapivě,
že ano.
Věta 6.2. Každá konečná Booleova algbera B je izomorfní svazu všech
podmnožin P(X) nějaké množiny X.
Důkaz výše uvedené věty není náročný a zvídavý čtenář mu se základními
znalostmi může porozumět (lze nalézt třeba v ...), nicméné přesahuje potřeby
tohoto textu jehož smysl je v předání základních úvah teorie svazů. Dodojeme,
že důležitým předpokladem diskutované věty je konečný počet prvků
Booleovy algebry B. Pro nekonečné Booleovy algebry platí obecnější věta,
která říká, že libovolná Booleova algebra B je izomorfní podsvazu svazu
všech podmnožin P(X) nějaké množiny X.
Ačkoliv to čtenáři možná tak nepříjde, věta 6.2 je důležitá na několika úrovních.
První z důsledků je, že pro zadaný počet prvků existuje pouze jedinná
Booleova algebra. Za druhé nám říka, že každá konečná Booleova algebra
má 2n prvků, pro nějaké n ∈ N (jelikož každá množina podmnožin má 2n
prvků). Věta nám dává dobrou představu o tom, jak Booleovy algebry vypadají.
Hlavním důvodem, kvůli kterému se o ni ale bavíme je, že je příkladem
situace, které v matematice říká konkrétní reprezentace.
Booleovu algebru (L, ≤) jsme definovali jako libovolnou množinu L s relací
uspořádání ≤, která je svaz, je distributivní a komplementární. To je v jistém
smyslu abstraktní způsob, je to jakákoliv množina L s relací ≤, která
25
má určité vlastnosti. Na druhé straně máme jendotlivé příklady Booleových
algeber, tj. množiny všech podmnožin P(X) pro zadané množiny X. O těch
víme jak konkrétně vypadají, když nám někdo zadá množinu X, není težké
si představit, jak bude P(X) vypadat. Zmíněná věta nám říká, že ve skupině
abstraktně definovaných (konečných) Booleových algeber žádné jiné Booleovy
algebry, než zmíněné příklady P(X) nejsou.
Čtenáře pravděpodobně napadne, proč se tedy vůbec abstraktní popis Booleových
algeber zavádí, když jsou vlastně všechny mají stejnou strukturu
jako P(X) pro nějaké X. Důvodem je povaha matematické práce, kdy při
dokazování je často výhodnější pracovat s abstraktním popisem, než s konkrétním
P(X). Například, pokud dostaneme zadaný svaz (L, ≤) a máme
ověřit, že jde o Booleovu algebru. Díky abstraktnímu popisu víme, že stačí
ověřit distributivitu a komplementaritu. V případě, že bysme jej neznali, museli
bysme ukázat, že L je izomorfní nějakému P(X), což je mnohem více
práce.
Analogii zmíněné situace lze nalézt v algebře i na jiných místech. Např.
pro studenty se znalostí pojmu vektorového prostoru (V, +) nad tělesem
T. Vektorový prostor (V, +) nad tělesem T je definován taktéž abstraktně
jako libovolná množina V s operací + a pronásobováním prvky z tělsa T,
splňující určité vlastnosti (uzavřenost, komutativitu, asociativitu, existenci
inverzních prvků, axiomy pronásobování z tělesa T). Později se však ukáže,
že libovolný (konečněrozměrný) vektorový prostor na tělesem T je izomorfní
kartézkému součinu Tn, tedy, že není níc jiného, než n-tice prvků z T. Taktéž
by šlo namítnout, proč se trápíme s axiomy vektorového prostoru když by
jej šlo definovat jako n-tice prvků. Nicméně abstraktní popis je nepoměrně
výhodnější při dokazování.
Podobná situce je u grup, v případě konečných komutativních grup. Opět,
konečná komutativní grupa (G, +) je definována “abstraktně"jako množina
G s operací +, která je uzavřená, komutativní, asociativní, pro každý prvek
existuje inverze a má konečný počet prvků. Později se ukáže, že každá taková
grupa G je izomorfní kartézkému součinu Zn1 × Zn2 × · · · × Znk
, kde
Zn1 , . . . , Znk
jsou grupy zbytkových tříd po dělení n1, . . . , nk.
6.1 Booleovy algebry v logice
Pravděpodobně každý čtenář tohoto textu se se symboly ∨ a ∧ setkal již
dříve a to v logice. Konkrétně symbol ∨ zastupuje spojku “a", případně “a
zároveň"(konjunkci) a symbol ∧ zastupuje spojku “nebo"(disjunkci). Připo-
26
meňmě ještě, že v logice se mluvilo o negaci výroků, která se značila ¬. Nyní
budeme chvíli používat symboly ∨ a ∧ v jejich výše zmíněném logickém
smyslu.
Vezměme si nyní dva výroky, jeden bude “prší"a druhý “mluvím". Úkol následujích
stránek bude z těchto dvou výroků utvořit všechny možné nové
výroky které vzniknou použitím výše zmíněných spojek “a", “nebo"či negace.
Pusťme se do toho. První dostaneme výrok “Prší a mluvím". Podobně
výrok “Prší, nebo mluvím". Mohli bychom výrok “prší"přidat dvakrát a dostali
bysme “Prší a prší a mluvím", což je zjevně to samé (platí to právě tehdy
když) jako “Prší a mluvím", takže tyto výroky vyloučíme. Mluvili jsme také
o negaci, takže je potřeba přidat výroky “neprší"a “nemluvím". Výroky typu
“Prší a neprší"jsou vždy nepravdivé, tak ty též nebudeme zmiňovat a označíme
je jako “Nepravda". Naopak výrok “Prší, nebo neprší"je vždy pravdivý,
tak ten označíme jako “Pravda". Určité výroky si budou odpovídat z hlediska
pravdivosti, výrok “(Prší, nebo neprší) a mluvím"platí právě tehdy když platí
“mluvím", takže ten taky nebudeme uvádět. Závorky, které v přirozeném jazyce
samozřejmě neexistují, jsou tu potřeba, protože nám říkájí, v jakém
pořadí logické spojky aplikujeme. Se značnou dávkou přemýšlení bysme se
dostali k tomu, že lze vytvořit přesně 16 různých výroků, a to:
“prší"
“mluvím"
“neprší"
“nemluvím"
“prší a mluvím"
“prší a nemluvím"
“neprší a mluvím"
“neprší a nemluvím"
“prší, nebo mluvím"
“prší, nebo nemluvím"
“neprší, nebo mluvím"
“neprší, nebo nemluvím"
“(prší a mluvím), nebo (neprší a nemluvím)"
“(neprší a mluvím), nebo (prší a nemluvím)"
“Pravda"
“Nepravda"
Ověření toho, že jsou výroky všechny zahrnuje práci s pravdivostníma tabulkama,
což je momentálně zbytečná technikalita, a tedy poprosíme čtenáře
27
o důvěru. Je dále zjevné, že mezi výroky platí nějaké vztahy. Pokud platí
výrok “prší", potom platí i výrok “prší, nebo mluvím". Říkáme, že výrok
“prší"implikuje výrok “prší, nebo mluvím". Namalujme si nyní výroky jako
obrázek a to tak, že pokud nějaký výrok implikuje jiný, bude níže a budou
spojeny čarou. V obrázku nahradíme spojku “a", “nebo"jejich logickými
symboly ∨ a ∧.
Obrázek 16: (M, →)
Nepravda
prsi a mluvim prsi a nemluvim
neprsi a mluvim
neprsi a nemluvm
prsi mluvim
(p. a m.), nebo (np. a nm)
(p. a nm.), nebo (np. a m)
nemluvim
neprsi
prsi, nebo mluvim
neprsi, nebo mluvim
prsi, nebo nemluvim
neprsi, nebo nemluvim
Pravda
Srovnejme výše uvedený obrázek s obrázkem Booleovy algebry množiny
všech podmnožin P(X) na čtyřprvkové množině X = {a, b, c, d}.
28
Obrázek 17: (P(X), ⊆)
∅
{a} {b} {c} {d}
{a, b}
{a, c} {a, d} {b, c} {b, d} {c, d}
{a, b, c} {a, b, d} {a, c, d} {b, c, d}
{a, b, c, d}
Tedy pokud se na logické spojky “a"a “nebo", resp. ∨ a ∧, díváme jako na
operace na množině všech výše uvedených výroků, dostaneme Booleovu algebru.
Konjunkce dvou výroků p a q (spojka “a") odpovídá jejich infimu p ∧ q,
disjunkce dvou výroků p a q (spojka “nebo") odpovídá jejich suprému p ∨ q.
Všiměme si dále, že negace výroku p odpovídá jeho svazovému komplementu
p (např. pokud výrok “prší"odpovídá podmnožině {a, b}, potom výrok “neprší"odpovídá
podmnožině {c, d} v našem příkladě P(X) na čtyřprvkové
množině X, tj. komplementu {a, b}). Uspořádání ≤ pak odpovídá implikaci,
tj. p ≤ q právě tehdy když p implikuje q.
Tohle platí i obecně, pokud vezmeme množinu výroků, která bude uzavřená
na logické operace “a"a “nebo"a negaci, dostaneme Booleovu algebru. Booleovy
algebry tedy z matematického hlediska popisují strukturu množiny
výroků z pohledu výrokové logiky. Tento fakt se označuje tvrzením, že Booleovy
algebry jsou modely výrokových logik. Booleových algebry nám umožňují
používat matematický aparát na zkoumání výrokové logiky.
Nyní zmiňme příklad Booleovy algebry, která je základem mnoha technických
disciplín, mj. logických obvodů, či programování, a to dvouprvková
Booleova algebra B = {0, 1}, kde 0 ≤ 1.
29
...
Pravdivostní tabulky vypadají následovně:
Prvek 0 je standardně interpretován jako logická nepravda, přičemž 1 jako
pravda.
Klíčovým pojmem výrokové logiky je pravdivostní ohodnocení výroku p. V
praxi jde o to, že každému výroku z dané množiny přiřadíme buďto 0, což
znamená, že výrok je nepravdivý, či 1, znamenající, že výrok je pravda. Tohle
přiřazení není úplně libovolné, např. pokud je výrok p pravda, tj. 1, a výrok
q také pravda, tj. přiřadíme mu taktéž 1, potom pravdivostní ohodnocení
vyžaduje, aby ohodnocení výroku “p a zároveň q", tj. p ∧ q, bylo taktéž
pravda. Z hlediska matematiky je prvadivostní ohodnocení množiny výroků
L homomorfismem z Booleovy lagebry L do dvouprvkové Booleovy algebry
B = {0, 1}.
30