Svazy
Buď (A, <) uspořádaná množina a B C A podmnožina. Prvek a E A se nazývá dolní závora množiny B, jestliže pro každý prvek b E B platí a < b. Podmnožina B C A se nazývá zdola ohraničená, má-li alespoň jednu dolní závoru v (A, <). Duálními pojmy k těmto pojmům jsou horní závora podmnožiny B a shora ohraničená podmnožina B. To opět znamená, že prvek a E A je horní závorou množiny B v (A, <) právě tehdy, když tento prvek je dolní závorou množiny B v duálně uspořádané množině (A, >), a podmnožina B je shora ohraničená v (A <) právě tehdy, když je zdola ohraničená v (A, >).
Buď opět (A, <) uspořádaná množina & B C A podmnožina. Prvek a G A se nazývá infimum množiny B, jestliže
a je dolní závora množiny B a přitom
pro každou dolní závoru c E A množiny B platí c < a.
To znamená, že takový prvek a je největší dolní závorou množiny B. Je tedy infimum množiny B, pokud existuje, určeno jednoznačně a značí se symbolem inf B. Duálním pojmem k tomuto pojmu je supremum množiny B a značí se symbolem sup B.
Příklad. V uspořádané množině (N, |) má každá neprázdná konečná podmnožina M C N supremum sup M - je jím nejmenší společný násobek čísel obsažených v M. Pro prázdnou množinu 0 jakožto podmnožinu v N pak platí sup 0 = 1. Žádná nekonečná podmnožina M C N zde ovšem nemá horní závoru a tedy ani supremum, neboť každé číslo m G N má jen konečný počet přirozených dělitelů.
Příklad. Buď A nekonečná množina. Označme J~{A) množinu všech těch podmnožin X C A, pro něž jedna z množin X, A — X je konečná. Je-li nyní Y C A taková podmnožina,
1
že obě množiny Y, A — Y jsou nekonečné, pak množina jednoprvkových množin {{y} \ y G Y} je podmnožinou v J~{A), která v uspořádané množině (J-(A), C) nemá supremum. Má zde totiž nekonečně mnoho horních závor, z nichž ale žádná není nej menší.
Poznámky. Buď (A, <) uspořádaná množina. Pak inf A a sup0 existují právě tehdy, když v A existuje nejmenší prvek x, a v tom případě platí inf A = sup0 = x. Duální tvrzení platí pro sup A a inf 0. To znamená, že tyto prvky existují právě tehdy, když v A existuje největší prvek y,av tom případě platí sup A = inf 0 = y.
Buď dále B C A podmnožina. Existují-li prvky inf B, resp. sup B, pak každý z těchto prvků může, ale obecně nemusí ležet v samotné množině B. První případ nastává právě tehdy, když množina B má nejmenší, resp. největší prvek. V takovém případě právě tyto prvky představují prvky inf B, resp. sup B.
Uspořádaná množina (A, <), v níž pro libovolné prvky a, b G A existují sup{a, b} a inf{a, b}, se nazývá svaz.
Uspořádaná množina (A, <), v níž pro libovolnou podmnožinu B C A existují sup B a inf B, se nazývá úplný svaz.
Všimněme si, že v uspořádané množině (A, <) pro libovolné prvky a, b G A platí
a < b <^=^> inf{a, b} = a <^=^> sup{a, b} = b.
Odtud ihned plyne, že každý řetězec je svaz. Jsou ale řetězce, které nejsou úplnými svazy - například řetězec (Q, <).
Příklad. Buď A množina a buď V(A) její potenční množina. Pak v uspořádané množině (V(A), C) libovolná podmnožina Q C V (A) má supremum i infimum a platí pro ně
supQ = |jQ,  infQ = f|Q.
2
(Přitom pro podmnožinu 0 C V (A) zde chápeme Q 0 jako A.) Je tedy (V (A), C) úplný svaz.
Příklad. Buď A nekonečná množina. Není těžké ověřit, že pak uspořádaná množina (J-(A), C) z předminulého příkladu je svaz, ale viděli jsme tam, že to není úplný svaz.
Příklad. Uspořádaná množina (N, |) je svaz, neboť pro každá m,n G N je sup{ra, n} nejmenší společný násobek čísel m, n a inf{ra, n} je největší společný dělitel čísel m, n. Není zde ale největší prvek, takže nejde o úplný svaz. Podobně uspořádaná množina (o;, |) je svaz a lze se přesvědčit, že se jedná dokonce o úplný svaz.
Tvrzení. Buď (A, <) svaz. Pak pro libovolnou neprázdnou konečnou podmnožinu B C A existují sup B a inf B.
Důkaz. Postupujeme indukcí vzhledem k počtu prvků v B. Obsahuje-li B jeden nebo dva prvky, není co dokazovat. V indukčním kroku máme ukázat, že pro libovolnou neprázdnou konečnou podmnožinu B C A, B ^ A, pro niž sup B a inf B existují, a pro libovolný prvek a E A —B existují také sup(5U{a}) a iní(B\j{a}). Ověříme například existenci sup(5U{a}). Uvažme prvek c = sup{sup B, a}. Poněvadž c > sup B a c > a, je jasné, že c je horní závora množiny B U {a}. Nechť nyní d je libovolná horní závora množiny B U {a}. Pak d > a a d je rovněž horní závora množiny B, odkud plyne d > sup B. Celkem tedy d > sup{sup B, a}, čili d > c. To ukazuje, že c = sup(5 U {a}).
Důsledek. Každý konečný neprázdný svaz je úplný.
Často užíváme následujícího jednoduššího označení. Je-li (A, <) svaz, pak pro libovolné prvky a, b G A prvek sup{a, b} značíme krátce jako a V b a prvek inf{a, b} značíme krátce jako a A b. Pak je možno formulovat následující fakt.
3
Tvrzení. Buď (A, <) svaz. Potom pro libovolné prvky a,b,c G A platí následující rovnosti:
a V a = a                     a A a = a (idempotence)
a V b = b V a                 a A b = b A a (komutativita)
(a V 6) V c = a V (6 V c) (a Ab) A c = a A (b A c) (asociativita)
a V (a A b) = a a A (a V 6) = a (absorbce)
Důkaz. Idempotence a komutativita jsou zřejmé. Pokud jde o asociativitu, podobný obrat jako v předchozím důkazu ukáže, že prvky na obou stranách první rovnosti jsou rovny sup{a, b, c} a prvky na obou stranách druhé rovnosti jsou rovny inf{a, b, c}. Rovněž ověření zákonů absorbce je snadné.
Význam uvedených rovností spočívá také v tom, že tyto rovnosti netoliko vyplývají z definice pojmu svazu, ale bylo by možno ukázat, že těmito rovnostmi je pojem svazu již kompletně charakterizován zhruba v tom smyslu, že by je bylo možno použít jako východisko pro jinou, ekvivalentní definici tohoto pojmu.
Tvrzení. Buď (A, <) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní:
(*) (Va, b, c G A)(a A (b V c) = (a A b) V (a A c)), (**)  (Ve, /,íGA)(eV(/Aff) = (eV/)A(eV g)).
Důkaz. Nechť platí podmínka (*) a nechť e, /, g G A. Pak
(e V /) A (e V g) = ((e V /) A e) V ((e V /) A g) (podle (*))
= e V (g A (e V /)) (absorbce)
= eV((sAe)V(jA/)) (podle (*))
= (e V (g A e)) V (g A f) (asociativita)
= eV(/A<7), (absorbce)
4
takže platí také podmínka (**). Analogicky se ukáže, že z (**) plyne (*).
Svaz (A, <) splňující kteroukoliv z podmínek (*), (**) uvedených v předchozím tvrzení se nazývá distributivní. Zmíněné tvrzení vlastně říká, že svaz (A, >) duální k distributivnímu svazu (A, <) je rovněž distributivní.
Všechny svazy uvedené v předchozích příkladech této kapitoly jsou distributivní. Uvidíme ale, že existují svazy, které nejsou distributivní.
Věta. Buď (A, <) uspořádaná množina, v níž pro každou podmnožinu B C A existuje inf B. Pak pro libovolnou podmnožinu CCA existuje také sup C.
Poznámka. Uvedený předpoklad v sobě zahrnuje požadavek existence prvku inf 0, tedy existenci největšího prvku v (A, <).
Důkaz. Buď C C A libovolná podmnožina. Nechť D je množina všech horních závor množiny C v (A, <). Uvažme prvek / = inf D. Ukážeme, že pak / = sup C Nejprve si všimněme, že pro každý prvek c E C platí, že c < d pro všechna d E D, což znamená, že c je dolní závorou množiny D v (A, <). Ovšem / je největší dolní závora této množiny. Nutně tedy platí c < f pro všechna c G C To znamená, že / je horní závorou množiny C v (A, <). Nechť dále g E A je libovolná horní závora této množiny. Pak g E D, odkud plyne, že / < g. To potvrzuje, že / = sup C.
Dokázaná věta vlastně říká, že uspořádaná množina (A, <) je úplným svazem, jakmile pro libovolnou podmnožinu B C A existuje inf B.
Poznamenejme také, že platí rovněž věta duální k uvedené větě, tedy věta, v níž jsou prohozená suprema a infima.
5
Příklad. Buď A množina. Připomeňme, že symbolem S (A) jsme značili množinu všech ekvivalencí na A. Tyto ekvivalence jakožto relace na A, tedy jakožto podmnožiny v A x A lze porovnávat množinovou inkluzí C . Vzniká tak uspořádaná množina (S(A),C). Ukážeme, že se jedná o úplný svaz. K tomu podle předchozí věty stačí ukázat, že pro libovolnou podmnožinu Q C S(A) existuje iníQ. Snadno se ovšem vidí, že je-li Q ^ 0, pak průnik f] Q všech ekvivalencí z Q je zase ekvivalence na A. Odtud ihned plyne, že v tom případě máme
Konečně je jasné, že pro Q = 0 je inf 0 = A x A. Je tedy opravdu (S(A), C) úplný svaz. Poznamenejme, že má-li množina A alespoň tři prvky, jedná se současně o příklad svazu, který není distributivní.
Závěrem dokážeme následující fakt týkající se řetězce (R, <) všech reálných čísel uspořádaných obvyklým způsobem podle velikosti.
Tvrzení. Každá neprázdná zdola ohraničená podmnožina M C R má inŕimum v (R, <). Každá neprázdná shora ohraničená podmnožina JVCK má supremum v (R, <).
Důkaz. Poněvadž se jedná o dvě vzájemně duální tvrzení a zobrazení přiřazující každému číslu r G R číslo —r je izo-morfismus řetězce (R, <) na duální řetězec (R, >), stačí dokázat například první z uvedených tvrzení. Použijeme k tomu reprezentaci reálných čísel pomocí řezů v (Q, <) z konce minulé kapitoly, tedy fakt, že řetězec (R, <) je izomorfní s tam popsaným řetězcem (7£, ^).
Buď tedy M C R libovolná neprázdná zdola ohraničená podmnožina. Nechť s G R je takové číslo, že s < r pro všechna r G M. Nechť ^ C TZ je množina všech řezů odpovídajících číslům z M při zmíněném izomorfismu a nechť (G, H) je řez v 1Z
6
odpovídající číslu s. Pak z toho, že s < r pro všechna r G M, plyne, že L C H pro všechny řezy (K, L) v $\ Uvažme množinu
vzniklou sjednocením množin L všech řezů (K, L) obsažených v \P'. Pak ovšem také V C H. Je tedy množina V neprázdná a zdola ohraničená. Přitom tato množina nemá nejmenší prvek, neboť kdyby existoval prvek t E V, který by zde byl nej menším prvkem, bylo by t E L pro některý řez (K, Ľ) v & a t by pak byl nejmenší prvek v L, což není možné, neboť takové řezy nejsou v 1Z obsaženy. Navíc je vidět, že pro každé v G V a pro každé g G Q splňující v < q platí také q G V. Skutečně pak totiž zase v E L pro některý řez (K, Ľ) v 1^, odkud plyne q E L. Položíme-li tedy U = Q— F, víme podle předchozí kapitoly, že (f/, V) je řez v (Q, <), a je to buď dedekindovský řez 1. druhu nebo mezera. To znamená, že (f/, V) je řez v TZ. Nechť w E M je číslo odpovídající tomuto řezu ve shora zmiňovaném izomorfismu. Poněvadž pro každý řez (K, Ľ) v & máme L C V, plyne odtud, že w < r pro všechna r E M. Nechť konečně z E M je jakékoliv takové číslo, že z < r pro všechna r E M. Nechť (X, Y) je řez v TZ odpovídající číslu z. Pak odtud plyne, že L C Y pro všechny řezy (K, L) v \P'. To ale celkem znamená, že V C Y, takže z < w. Tím je prokázáno, že w = inf M.
Uvedené tvrzení je možno ještě přeformulovat následujícím způsobem. Připojme k množině R dva nové prvky —oo a oo a rozšiřme uspořádání < z R na R U { — oo, 00} tak, aby pro každé r G R platilo — 00 < r < 00. Tímto způsobem vzniká řetězec (RU{—00, 00}, <). Není těžké si rozmyslet, že pak předchozí tvrzení lze převést do následují podoby.
Důsledek. Řetězec (R U {—00, 00}, <) je úplný svaz.
L
(K,L)£<P
7