Polosvazy Definice. Prvek x grupoidu (G, ·) se nazývá idempotentní, jestliže x · x = x. Definice. Komutativní pologrupa, jejíž každý prvek je idempotentní, se nazývá polosvaz. Příklad. Pro libovolnou množinu X budeme (i v dalším textu) symbolem P(X) označovat množinu všech podmnožin množiny X. Pak (P(X), ∩) a (P(X), ∪) 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. Poznámka. Připomeňme, že podgrupoidem grupoidu (G, ·) rozumíme libovolnou podmnožinu H množiny G takovou, že pro každé a, b ∈ H je a · b ∈ H. Největším (vzhledem k inkluzi) podrupoidem grupoidu (G, ·) je G, nejmenším ∅. Zřejmě je možné operaci · zúžit na H, čímž dostaneme grupoid (H, ·). Je jasné, že každý podgrupoid libovolného polosvazu je také polosvaz. Věta 1.1. Nechť (G, ·) je komutativní pologrupa. Pak množina všech jejích idempotentních prvků tvoří podgrupoid pologrupy (G, ·), který je polosvazem. Důkaz. Jsou-li x a y idempotentní, pak x · x = x a y · y = y, odkud plyne (x · y) · (x · y) = x · x · y · y = x · y. Jde tedy skutečně o podgrupoid, zbytek tvrzení je zřejmý. Poznámka. Připomeňme, že v uspořádané množině (G, ≤) nazýváme prvek x ∈ G horní závorou prvků a, b ∈ G, jestliže a ≤ x, b ≤ x. Jestliže existuje nejmenší ze všech horních závor prvků a, b, nazýváme ji jejich supremem, které značíme sup{a, b} nebo a ∨ b. Příklad. V uvedené uspořádané množině je supremem prvků a, b prvek x, zatímco prvky c, d supremum nemají: mezi jejich třemi horními závorami x, a, b neexistuje nejmenší. x • a • • b c • • d • Z uspořádané množiny, jejíž každé dva prvky mají supremum, lze vytvořit polosvaz Věta 1.2. Nechť (G, ≤) je uspořádaná množina, v níž k libovolným dvěma prvkům a, b ∈ G existuje supremum a ∨ b. Pak (G, ∨) je polosvaz. Navíc pro každé a, b ∈ G platí a ≤ b ⇐⇒ a ∨ b = b. Důkaz. Komutativita i idempotentnost je zřejmá, ekvivalence obou podmínek též. Pro libovolné a, b, c ∈ G jistě platí (a ∨ b) ∨ c ≥ c, (a ∨ b) ∨ c ≥ a ∨ b ≥ a, podobně (a ∨ b) ∨ c ≥ b. Je tedy (a ∨ b) ∨ c horní závora prvků b, c, proto (a ∨ b) ∨ c ≥ b ∨ c. Je tudíž (a ∨ b) ∨ c horní závora prvků a, b ∨ c, proto (a ∨ b) ∨ c ≥ a ∨ (b ∨ c). Analogicky opačná nerovnost, z antisymetrie asociativita. Z polosvazu lze vytvořit uspořádanou množinu Věta 1.3. Nechť (G, ·) je polosvaz. Potom relace ≤, daná vztahem a ≤ b ⇐⇒ a · b = b pro každé a, b ∈ G, je uspořádání na G, ve kterém pro každé a, b ∈ G je a · b supremum prvků a, b v (G, ≤). Důkaz. Pro každé a, b, c ∈ G platí a · a = a =⇒ a ≤ a, a ≤ b, b ≤ a =⇒ a = b · a = a · b = b, a tedy je ≤ reflexivní a antisymetrická relace. Rovněž platí a ≤ b, b ≤ c =⇒ a · b = b, b · c = c =⇒ a · c = a · (b · c) = (a · b) · c = b · c = c =⇒ a ≤ c, čímž jsme dokázali tranzitivitu. Je tedy ≤ uspořádání na G. Zbývá ukázat, že pro každé a, b ∈ G je a · b supremum prvků a, b v uspořádané množině (G, ≤). Protože a · (a · b) = (a · a) · b = a · b, b · (a · b) = (a · b) · b = a · (b · b) = a · b, platí a ≤ a · b, b ≤ a · b. Nechť c je libovolná horní závora prvků a, b v (G, ≤), tedy a ≤ c, b ≤ c. Pak platí a · c = c, b · c = c, odkud (a · b) · c = a · (b · c) = a · c = c, tedy a · b ≤ c, je tedy a · b supremum prvků a, b v (G, ≤). Důsledek. Polosvazy jsou totéž co uspořádané množiny, v nichž ke každým dvěma prvkům existuje supremum. Princip duality uspořádaných množin Princip duality: Nechť (G, ≤) je uspořádaná množina. Definujeme-li na G novou relaci takto: pro libovolné prvky a, b ∈ G klademe a b ⇐⇒ b ≤ a, pak je (G, ) opět uspořádaná množina, přičemž supremum (resp. infimum) libovolné množiny A ⊆ G v (G, ≤) se stane infimem (resp. supremem) množiny A v (G, ). Podobně největší (resp. nejmenší) prvek v (G, ≤) se stane nejmenším (resp. největším) prvkem v (G, ), maximální (resp. minimální) prvek v (G, ≤) se stane minimálním (resp. maximálním) prvkem v (G, ). Důsledek. Polosvazy jsou totéž co uspořádané množiny, v nichž ke každým dvěma prvkům existuje infimum. Svazy Definice. Uspořádaná množina, v níž ke každým dvěma prvkům existuje supremum i infimum, se nazývá svaz. Příklad. Každý řetězec (neboli lineárně uspořádaná množina, tj. uspořádaná množina, v níž jsou každé dva prvky srovnatelné) je svaz: supremem daných dvou prvků je ten větší z nich, jejich infimem je ten menší. Příklad. Pro libovolnou množinu X je (P(X), ⊆) svaz: supremem libovolných dvou podmnožin množiny X je jejich sjednocení, jejich infimem je jejich průnik. Příklad. Množina přirozených čísel N je uspořádána relací dělitelnosti, přitom (N, |) je svaz: pro libovolná dvě přirozená čísla je jejich supremem jejich nejmenší společný násobek a jejich infimem je jejich největší společný dělitel. Svaz jako množina se dvěma operacemi Věta 2.1. Nechť (G, ≤) je svaz. Pro libovolné prvky a, b ∈ G označme jejich supremum symbolem a ∨ b a jejich infimum symbolem a ∧ b. Pak (G, ∨) a (G, ∧) jsou polosvazy a obě operace jsou spolu svázány tzv. absorpčními zákony: pro každé prvky a, b ∈ G platí a ∨ (b ∧ a) = a ∧ (b ∨ a) = a. Kromě toho pro každé prvky a, b ∈ G platí a ∧ b = a ⇐⇒ a ≤ b ⇐⇒ a ∨ b = b. Důkaz. To, že (G, ∨) a (G, ∧) jsou polosvazy, plyne z věty 1.2 a principu duality; rovněž tak ekvivalentnost uvedených podmínek. Absorpční zákony jsou zřejmé. Co musí splnit dvě operace na množině, aby vznikl svaz? Věta 2.2. Nechť (G, ∨, ∧) je množina se dvěma idempotentními, asociativními a komutativními operacemi, které jsou spolu svázány absorpčními zákony. Pak platí 1. pro každé prvky a, b ∈ G platí a ∧ b = a ⇐⇒ a ∨ b = b, 2. definujeme-li na G relaci ≤ takto: pro libovolné prvky a, b ∈ G klademe a ≤ b ⇐⇒ a ∨ b = b, pak je ≤ uspořádání na G takové, že (G, ≤) je svaz, v němž pro libovolné prvky a, b ∈ G je prvek a ∨ b jejich supremum a prvek a ∧ b jejich infimum. Důkaz. Nechť pro prvky a, b ∈ G platí a ∧ b = a. Pak a ∨ b = (a ∧ b) ∨ b = b ∨ (a ∧ b) = b dle absorpčního zákona. Opačná implikace analogicky. Ostatní plyne z věty 1.3 a principu duality. Princip duality svazů Poznámka. Z dokázaných vět vyplývá, že svazy jsou totéž co algebraické struktury (G, ∨, ∧) se dvěma idempotentními, asociativními a komutativními operacemi, svázanými spolu absorpčními zákony. Proto i tyto struktury (G, ∨, ∧) budeme také nazývat svazy. Princip duality: Je-li (G, ∨, ∧) svaz, pak i (G, ∧, ∨) je svaz (tzv. svaz duální k původnímu svazu). Obecně, jestliže v nějakém platném tvrzení o svazech systematicky zaměníme supremum ↔ infimum, ∨ ↔ ∧, ≤ ↔ ≥, dostaneme opět platné tvrzení o svazech. Poznámka. Protože není nutné zdůrazňovat, zda máme na mysli svaz jako uspořádanou množinu nebo jako algebraickou strukturu se dvěma operacemi, nebudeme dále, nebude-li to z nějakých důvodů vhodné nebo dokonce nevyhnutelné, uspořádání či operace vyznačovat. Budeme tedy místo o svazu (G, ≤) či svazu (G, ∨, ∧) jednoduše psát o svazu G. Distributivní a modulární nerovnosti Věta 2.3. V libovolném svazu G pro každou trojici prvků a, b, c ∈ G platí tzv. distributivní nerovnosti (a ∨ b) ∧ (a ∨ c) ≥ a ∨ (b ∧ c), (a ∧ b) ∨ (a ∧ c) ≤ a ∧ (b ∨ c). Je-li navíc c ≤ a, platí tzv. modulární nerovnost (a ∧ b) ∨ c ≤ a ∧ (b ∨ c). Důkaz. Jistě platí a ∨ b ≥ a, a ∨ c ≥ a, tedy a je dolní závorou prvků a ∨ b, a ∨ c, proto (a ∨ b) ∧ (a ∨ c) ≥ a. Platí a ∨ b ≥ b ≥ b ∧ c, a ∨ c ≥ c ≥ b ∧ c, odkud podobně (a ∨ b) ∧ (a ∨ c) ≥ b ∧ c. Proto je (a ∨ b) ∧ (a ∨ c) horní závorou prvků a, b ∧ c a dostáváme první distributivní nerovnost. Druhou lze principem duality odvodit z první. Je-li navíc c ≤ a, platí a ∧ c = c, proto modulární nerovnost plyne z druhé distributivní nerovnosti. Suprema a infima konečných podmnožin svazu Poznámka. Protože jsou obě operace ∨ a ∧ ve svazu komutativní a asociativní, nezáleží v zápise a1 ∨ · · · ∨ an, resp. a1 ∧ · · · ∧ an na pořadí ani na uzávorkování. Věta 2.4. Nechť G je svaz, n ∈ N. Pro libovolné prvky a1, . . . , an ∈ G platí, že a1 ∨ · · · ∨ an je supremum množiny {a1, . . . , an} a a1 ∧ · · · ∧ an je infimum množiny {a1, . . . , an}. Důkaz. Dokažme indukcí vzhledem k n tvrzení o supremech; pak tvrzení o infimech dostaneme z duality. Tvrzení je pro n = 1 zřejmé, pro n = 2 jde o definici operace ∨. Nechť n > 2 a pro n − 1 již bylo tvrzení dokázáno. Označme b = a1 ∨ · · · ∨ an−1 a c = b ∨ an. Pak c ≥ b, a tedy c je horní závora množiny {a1, . . . , an−1}. Současně c ≥ an, a tedy c je horní závora množiny {a1, . . . , an}. Nechť d je libovolná horní závora množiny {a1, . . . , an}. Pak je d horní závora množiny {a1, . . . , an−1}, a tedy d ≥ b. Současně d ≥ an, a proto d ≥ b ∨ an = c. Podsvazy, ideály, filtry Definice. Nechť (G, ∨, ∧) je svaz, A podmnožina jeho nosné množiny G. Řekneme, že A je podsvaz svazu (G, ∨, ∧), jestliže pro každé a, b ∈ A platí a ∨ b ∈ A a současně a ∧ b ∈ A. Poznámka. A je podsvaz svazu (G, ∨, ∧), právě když je A podgrupoid obou grupoidů (G, ∨) a (G, ∧). Příklad. 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 ⊆ G podmnožina. Řekneme, že A je ideál svazu G, jestliže je A podsvazem svazu G, který navíc splňuje podmínku: pro každé a ∈ A a každé x ∈ G platí x ≤ a =⇒ x ∈ A. Duálně, řekneme, že A je filtr svazu G, jestliže je A podsvazem svazu G, který navíc splňuje podmínku: pro každé a ∈ A a každé x ∈ G platí x ≥ a =⇒ x ∈ A. Poznámka. Ideál svazu je tedy podsvaz, který s každým svým prvkem a obsahuje i všechny prvky svazu menší než a, filtr svazu je podsvaz, který s každým svým prvkem a obsahuje i všechny prvky svazu větší než a. Příklad. Každý svaz je svým ideálem i filtrem. Prázdná množina je ideálem i filtrem libovolného svazu. Věta 3.1. Průnik libovolného neprázdného systému podsvazů (resp. ideálů, resp. filtrů) daného svazu je opět podsvaz (resp. ideál, resp. filtr) tohoto svazu. Důkaz. Nechť I = ∅ a pro každé i ∈ I je Ai podsvaz svazu G. Označme A = i∈I Ai jejich průnik. Pak pro každé a, b ∈ A platí a, b ∈ Ai pro všechna i ∈ I, a tedy a ∨ b ∈ Ai , a ∧ b ∈ Ai . Odtud a ∨ b ∈ A, a ∧ b ∈ A, a proto je A podsvaz svazu G. Předpokládejme navíc, že pro každé i ∈ I je Ai dokonce ideál svazu G. Mějme a ∈ A, x ∈ G, x ≤ a. Pak pro každé i ∈ I je a ∈ Ai , tedy i x ∈ Ai , tudíž x ∈ A. Tvrzení o filtrech nyní plyne z duality. Podsvazy (ideály, filtry) generované podmnožinou Definice. Nechť G je svaz, A ⊆ G podmnožina. Díky předchozí větě můžeme nyní definovat podsvaz A svazu G generovaný množinou A jako průnik všech podsvazů tohoto svazu obsahujících množinu A, vždyť alespoň jeden podsvaz tohoto svazu obsahující množinu A existuje, totiž celý svaz G. Podobně můžeme definovat ideál A↓ svazu G generovaný množinou A jako průnik všech ideálů tohoto svazu obsahujících množinu A. Duálně, filtr A↑ svazu G generovaný množinou A je průnik všech filtrů tohoto svazu obsahujících množinu A. Je-li A = {a}, píšeme stručně a↓ místo {a}↓, resp. a↑ místo {a}↑, a hovoříme o hlavním ideálu, resp. o hlavním filtru, generovaném prvkem a. Poznámka. Pro svaz G a podmnožinu A ⊆ G je podsvaz A (resp. ideál A↓, resp. filtr A↑) generovaný množinou A tím nejmenším (vzhledem k množinové inkluzi) podsvazem (resp. ideálem, resp. filtrem) svazu G ze všech podsvazů (resp. ideálů, resp. filtrů) obsahujících množinu A. Věta 3.2. Nechť G je svaz, A ⊆ G podmnožina. Pro ideál A↓ generovaný množinou A platí A↓ = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≤ a1 ∨ · · · ∨ an}. Duálně, pro filtr A↑ generovaný množinou A platí A↑ = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≥ a1 ∧ · · · ∧ an}. Důkaz. Každý ideál svazu G obsahující množinu A musí pro každé a1, . . . , an ∈ A obsahovat i a1 ∨ · · · ∨ an. Proto obsahuje i množinu B = {x ∈ G; ∃n ∈ N ∃a1, . . . , an ∈ A : x ≤ a1 ∨ · · · ∨ an}. Je tedy A↓ ⊇ B. Stačí ověřit, že B je ideál obsahující A. Inkluze A ⊆ B je zřejmá, neboť pro a ∈ A lze volit n = 1 a a1 = a. Jistě B obsahuje s každým svým prvkem i všechny prvky svazu ještě menší. Nechť x, y ∈ B. Protože x ∧ y ≤ x, je x ∧ y ∈ B. Potřebujeme ověřit, že také x ∨ y ∈ B. Existují a1, . . . , an, b1, . . . , bm ∈ A tak, že x ≤ a1 ∨ · · · ∨ an, y ≤ b1 ∨ · · · ∨ bm. Pak pro c = (a1 ∨ · · · ∨ an) ∨ (b1 ∨ · · · ∨ bm) je x ≤ c, y ≤ c, odkud x ∨ y ≤ c, proto x ∨ y ∈ B. Tvrzení o filtrech plyne z duality. Izotonní zobrazení, homomorfismy svazů Definice. Nechť (G, ≤), (H, ) jsou uspořádané množiny, f : G → H zobrazení. Řekneme, že je f izotonní zobrazení, jestliže pro každé a, b ∈ G platí implikace a ≤ b =⇒ f (a) f (b). Řekneme, že f je izomorfismus uspořádaných množin, je-li f bijekce a obě zobrazení f i f −1 jsou izotonní. Definice. Nechť G a H jsou svazy, f : G → H zobrazení. Řekneme, že je f svazový homomorfismus, jestliže pro každé a, b ∈ G platí f (a ∧ b) = f (a) ∧ f (b), f (a ∨ b) = f (a) ∨ f (b). Řekneme, že f je svazový izomorfismus (neboli izomorfismus svazů), je-li f bijektivní homomorfismus. Poznámka. Protože každý svaz je také uspořádaná množina, má smysl se ptát, zda svazový homomorfismus je též izotonní zobrazení. Každý homomorfismus svazů je izotonním zobrazením Věta 3.3. Nechť G a H jsou svazy, f : G → H zobrazení. 1. Je-li f svazový homomorfismus, pak f je izotonní zobrazení a homomorfní obraz f (G) = {f (a); a ∈ G} je podsvaz svazu H. 2. Zobrazení f je svazový izomorfismus, právě když f je izomorfismus uspořádaných množin. Poznámka. Jak ukazuje tento příklad, izotonní zobrazení mezi svazy nemusí být svazovým homomorfismem. •  // • •  ++ •  // • •  )) • • Důkaz věty. 1. Předpokládejme, že f je svazový homomorfismus. Pro každé a, b ∈ G z a ≤ b plyne a = a ∧ b, proto f (a) = f (a ∧ b) = f (a) ∧ f (b), a tedy f (a) ≤ f (b). Je tedy f izotonní. To, že f (G) je podsvaz svazu H, plyne přímo z definic. 2. „⇒ Nechť je f svazový izomorfismus. Nejprve ukážeme, že pak f −1 je svazový homomorfismus. Zvolme libovolně c, d ∈ H a označme a = f −1(c), b = f −1(d). Pak platí f −1 (c ∨ d) = f −1 (f (a) ∨ f (b)) = f −1 (f (a ∨ b)) = a ∨ b = = f −1 (c) ∨ f −1 (d), f −1 (c ∧ d) = f −1 (f (a) ∧ f (b)) = f −1 (f (a ∧ b)) = a ∧ b = = f −1 (c) ∧ f −1 (d). Odvodili jsme, že f −1 je svazový homomorfismus. Aplikací první části věty na zobrazení f i f −1 dostaneme, že f je izomorfismus uspořádaných množin. 2. „⇐ Nechť nyní naopak f je izomorfismus uspořádaných množin, a, b ∈ G. Protože a ≤ a ∨ b, b ≤ a ∨ b a f je izotonní zobrazení, dostáváme f (a) ≤ f (a ∨ b), f (b) ≤ f (a ∨ b), je tedy f (a ∨ b) horní závora prvků f (a), f (b). Nechť c ∈ H je libovolný takový, že f (a) ≤ c, f (b) ≤ c. Protože f −1 je izotonní zobrazení, platí a ≤ f −1(c), b ≤ f −1(c), proto i a ∨ b ≤ f −1(c), a protože f je izotonní zobrazení, dostáváme f (a ∨ b) ≤ c. To ale znamená, že f (a ∨ b) je supremum prvků f (a), f (b), tedy f (a) ∨ f (b) = f (a ∨ b). Analogicky (nebo z duality) dostaneme f (a) ∧ f (b) = f (a ∧ b). Je tedy f izomorfismus svazů. Úplné svazy Poznámka. Podle věty 2.4 v libovolném svazu má každá neprázdná konečná podmnožina {a1, . . . , an} supremum a1 ∨ · · · ∨ an a infimum a1 ∧ · · · ∧ an. Nekonečná anebo prázdná podmnožina však supremum či infimum obecně mít nemusí. Definice. Uspořádaná množina, v níž pro každou podmnožinu existuje supremum i infimum, se nazývá úplný svaz. Poznámka. Každý úplný svaz G má nejmenší prvek (infimum množiny G) a největší prvek (supremum množiny G). Poznámka. Promysleme si, co znamená infimum, resp. supremum prázdné podmnožiny svazu G. Je-li A ⊆ G, pak infimum množiny A ve svazu G je největší dolní závora množiny A ve svazu G. Dolní závora množiny A ve svazu G je prvek x ∈ G takový, že pro každé a ∈ A platí x ≤ a. V případě A = ∅ je tato podmínka splněna pro každé x ∈ G, a tedy odtud plyne, že každý prvek svazu G je v G dolní závorou prázdné množiny. Proto infimem prázdné množiny ve svazu G je největší prvek svazu G. Duálně: supremem prázdné množiny ve svazu G je nejmenší prvek svazu G. Příklady Příklad. Zřejmě platí, že každý úplný svaz je svazem. Příklad. Podle věty 2.4 je každý neprázdný konečný svaz úplným svazem. Příklad. Prázdný svaz není úplný, neboť pro jeho (jedinou) prázdnou podmnožinu neexistuje infimum ani supremum. Jinými slovy: prázdný svaz nemá nejmenší prvek ani největší prvek, protože nemá žádný prvek. Příklad. Pro libovolnou množinu X je (P(X), ⊆) úplný svaz. Příklad. Pro libovolnou nekonečnou množinu X tvoří množina všech konečných podmnožin množiny X spolu s inkluzí ⊆ svaz, který není úplným svazem. Příklad. Nekonečný řetězec nemusí být úplný svaz, například (N, ≤) není úplný svaz, neboť neexistuje supremum celé množiny N. Ekvivaletní charakterizace úplněho svazu Věta 4.1. Nechť (G, ≤) je uspořádaná množina. Následující podmínky jsou ekvivalentní: 1. (G, ≤) je úplný svaz. 2. každá podmnožina množiny G má v uspořádané množině (G, ≤) supremum. 3. každá podmnožina množiny G má v uspořádané množině (G, ≤) infimum. 4. (G, ≤) má nejmenší prvek a každá neprázdná podmnožina množiny G má v uspořádané množině (G, ≤) supremum. 5. (G, ≤) má největší prvek a každá neprázdná podmnožina množiny G má v uspořádané množině (G, ≤) infimum. Důkaz. Protože infimum (resp. supremum) prázdné množiny je největší (resp. nejmenší) prvek, je čtvrtá podmínka identická s druhou a pátá s třetí. Druhá a třetí podmínka jsou navzájem duální, zatímco první podmínka je duální sama k sobě. Stačí ukázat, že první je ekvivalentní s druhou, ekvivalenci první s třetí dostaneme z duality. Z definice úplného svazu je vidět, že z první podmínky plyne druhá. Ukažme, že z druhé plyne první. Předpokládejme tedy, že každá podmnožina množiny G má v (G, ≤) supremum, a ukažme, že pak také každá podmnožina množiny G má v (G, ≤) infimum, a tedy že (G, ≤) je úplný svaz. Nechť A je libovolná podmnožina množiny G. Označme B množinu všech dolních závor množiny A, tj. B = {x ∈ S; ∀a ∈ A : x ≤ a}. Podle předpokladů má B supremum, které označíme m. Pro libovolné a ∈ A platí x ≤ a pro všechna x ∈ B, proto a je horní závora množiny B. Ovšem m je její supremum, tedy m ≤ a. To však platí pro všechny a ∈ A, a proto m ∈ B. Je tedy m největší ze všech dolních závor množiny A, tedy její infimum. Příklady Příklad. Svaz všech podgrup dané grupy G je dle předchozí věty úplný svaz, neboť má největší prvek (celou grupu G) a každá neprázdná množina podgrup má v tomto svazu infimum, kterým je průnik těchto podgrup (to, že jejich průnikem je opět podgrupa, jsme dokazovali kvůli definici podgrupy generované podmnožinou grupy). Rovněž svaz všech podsvazů (popřípadě svaz ideálů nebo svaz filtrů) daného svazu je úplný svaz (viz větu 3.1). Díky analogickým větám o průnicích neprázdných systémů nějakých podstruktur lze totéž říci i o svazu všech podokruhů daného okruhu nebo o svazu všech podprostorů daného vektorového prostoru. Příklad. (N ∪ {∞}, ≤) je dle předchozí věty úplný svaz, neboť má největší prvek ∞ a každá neprázdná podmnožina množiny N ∪ {∞} má v (N ∪ {∞}, ≤) infimum (plyne z dobré uspořádanosti). Příklad. Ze svazu (N, |), který není úplný, lze doplněním nuly (která se stane jeho největším prvkem) utvořit svaz (N ∪ {0}, |), který je úplný, neboť každé přirozené číslo má jen konečně mnoho dělitelů, a tedy každá neprázdná podmnožina má v (N, |) infimum. Zúplnění svazu Poznámka. Jak ukazuje následující věta, předchozí dva příklady nebyly nijak výjimečné: vždy existuje způsob, jak doplnit svaz tak, aby se stal úplným. Věta 4.2. Nechť G je svaz. Pak existuje úplný svaz U, který obsahuje podsvaz H, který je izomorfní se svazem G. Důkaz. Je jasné, že stačí najít vhodný úplný svaz U a injektivní svazový homomorfismus f : G → U. Pak je totiž f (G) podsvaz svazu U a zúžením oboru hodnot dostaneme svazový izomorfismus f : G → f (G). Nechť U značí množinu všech ideálů svazu G. Ve větě 3.1 jsme ukázali, že průnik libovolného neprázdného systému prvků z U je opět prvkem U. Protože uspořádaná množina (U, ⊆) má největší prvek G, je to dle předchozí věty úplný svaz. Přitom pro libovolné dva prvky A, B ∈ U je jejich infimem A ∧ B = A ∩ B množinový průnik, jejich supremem A ∨ B = (A ∪ B)↓ je ideál generovaný množinovým sjednocením. Uvažme zobrazení f : G → U, které každý prvek svazu G zobrazí na ideál jím generovaný: pro každé a ∈ G klademe f (a) = a↓. Podle věty 3.2 je tedy f (a) = {x ∈ G; x ≤ a}. Odtud plyne, že f je injekce: jsou-li totiž a, b ∈ G takové, že f (a) = f (b), pak a ∈ b↓, odkud a ≤ b, analogicky b ≤ a, dohromady a = b. Budeme hotovi, ukážeme-li, že f je svazový homomorfismus. Nechť a, b ∈ G jsou libovolné. Máme ukázat, že f (a ∧ b) = f (a) ∧ f (b), f (a ∨ b) = f (a) ∨ f (b), což znamená (a ∧ b)↓ = a↓ ∩ b↓, (a ∨ b)↓ = (a↓ ∪ b↓)↓. Nejprve dokažme první rovnost. Protože a ∧ b ≤ a, a ∧ b ≤ b, platí a ∧ b ∈ a↓ ∩ b↓, odkud (a ∧ b)↓ ⊆ a↓ ∩ b↓. Naopak, je-li x ∈ a↓ ∩ b↓, je x ≤ a, x ≤ b, tedy x ≤ a ∧ b, neboli x ∈ (a ∧ b)↓. Nyní se zaměřme na druhou rovnost. Z nerovností a ≤ a ∨ b, b ≤ a ∨ b, plynou inkluze a↓ ⊆ (a ∨ b)↓, b↓ ⊆ (a ∨ b)↓, odkud a↓ ∪ b↓ ⊆ (a ∨ b)↓ a proto i (a↓ ∪ b↓)↓ ⊆ (a ∨ b)↓. Na druhou stranu platí a, b ∈ (a↓ ∪ b↓)↓, proto i a ∨ b ∈ (a↓ ∪ b↓)↓, odkud (a ∨ b)↓ ⊆ (a↓ ∪ b↓)↓. Tarského věta Věta 4.3 (Tarski). Nechť G je úplný svaz, ϕ : G → G izotonní zobrazení. Pak existuje prvek a ∈ G tak, že ϕ(a) = a (tj. a je pevný bod zobrazení ϕ). Důkaz. Označme A = {x ∈ G; x ≤ ϕ(x)}. Protože G je úplný svaz, existuje supremum a množiny A. Pro každé x ∈ A tedy platí x ≤ a, a proto z izotonie ϕ(x) ≤ ϕ(a), což spolu s x ≤ ϕ(x) (vždyť x ∈ A) dává x ≤ ϕ(a). Je tedy ϕ(a) horní závora množiny A, tedy její supremum a ≤ ϕ(a). Z izotonie ϕ(a) ≤ ϕ(ϕ(a)), ale to znamená ϕ(a) ∈ A. Ovšem a je supremum množiny A, proto ϕ(a) ≤ a. Celkem tedy a = ϕ(a). Součin svazů Poznámka. Tak jako jsme součinem grup (G, ·), (H, ·) získali grupu (G × H, ·) na kartézském součinu nosičů obou grup, můžeme součinem svazů získat nový svaz. Konstrukce je stejná: operace na uspořádaných dvojicích se provedou nezávisle v každé složce. Definice. Nechť (G, ∨, ∧), (H, ∨, ∧) jsou svazy. Na kartézském součinu G × H definujme nové operace ∨ a ∧ takto: pro každé g1, g2 ∈ G, h1, h2 ∈ H klademe (g1, h1) ∨ (g2, h2) = (g1 ∨ g2, h1 ∨ h2). (g1, h1) ∧ (g2, h2) = (g1 ∧ g2, h1 ∧ h2). Věta 5.1. (G × H, ∨, ∧) z předchozí definice je svaz. Důkaz. Je třeba ověřit, že obě operace jsou asociativní, komutativní a idempotentní a že platí absorpční zákony. To je snadné: vždy se přitom využije, že dokazovaná rovnost platí v každém z obou svazů a že operace se v součinu počítají po složkách. Poznámky o součinu svazů Poznámka. Jak jsme si rozmysleli v předchozím důkaze, v součinu svazů platí všechny rovnosti platné v obou svazech. Vlastnosti, které se však nedají vyjádřit jako konjunkce rovností, už součin svazů zdědit nemusí. Například vlastnost být řetězec můžeme zachytit takto: pro každé dva prvky x, y platí x ≤ y nebo x ≥ y, což pomocí svazových operací lze zapsat podmínkou x ∧ y = x nebo x ∧ y = y. To však 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. Poznámka. Podobně jako součin dvou svazů jsme mohli definovat i součin n svazů pro libovolné n ∈ N: na kartézském součinu nosných množin daných svazů se nové operace ∨ a ∧ definují po složkách. Modulární svazy Poznámka. Podle věty 2.3 v libovolném svazu G pro každou trojici prvků a, b, c ∈ G takových, že c ≤ a, platí modulární nerovnost (a ∧ b) ∨ c ≤ a ∧ (b ∨ c). Definice. Svaz G se nazývá modulární, jestliže pro každou trojici prvků a, b, c ∈ G platí implikace c ≤ a =⇒ (a ∧ b) ∨ c = a ∧ (b ∨ c). Příklad. Pro libovolnou množinu X je svaz (P(X), ∪, ∩) všech podmnožin množiny X modulární. Snadno se ověří, že pro libovolné množiny A, B, C ⊆ X platí A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ C. Jestliže totiž x ∈ A ∩ (B ∪ C) a x /∈ C, pak x ∈ A ∩ B. Příklad. Libovolný řetězec je modulární svaz. Stačí ověřit rovnost pro každý ze tří případů b ≤ c ≤ a, c ≤ b ≤ a, c ≤ a ≤ b. Pro každý z nich vždy vyjde na obou stranách rovnosti „prostřední prvek. Dva důležité pětiprvkové svazy: svaz N5 (pětiúhelník) Příklad. Svaz N5, zvaný též pětiúhelník, není modulární. • 1 a • • b c • • 0 Skutečně, přestože c < a, platí (a ∧ b) ∨ c = 0 ∨ c = c, a ∧ (b ∨ c) = a ∧ 1 = a. Dva důležité pětiprvkové svazy: svaz M5 (diamant) Příklad. Svaz M5, zvaný též diamant, je modulární. • • • • • Implikace c ≤ a =⇒ (a ∧ b) ∨ c = a ∧ (b ∨ c) z definice modulárního svazu totiž zřejmě platí, je-li c nejmenší prvek svazu (pak je na obou stranách rovnosti a ∧ b) anebo je-li a největší prvek svazu (pak je na obou stranách rovnosti b ∨ c). Jestliže a = c, platí rovnost také, tentokrát díky absorpčním zákonům. V případě svazu M5 jsou tím vyčerpány všechny možnosti. Svaz všech normálních podgrup dané grupy Věta 6.1. Pro libovolnou grupu (H, ·) platí, že svaz všech normálních podgrup grupy H je modulární. Důkaz. Nechť K, L jsou podgrupy grupy H. Každá podgrupa grupy (H, ·), obsahující obě podgrupy K, L, musí obsahovat i množinu K · L = {k · ; k ∈ K, ∈ L}, což obecně nemusí být podgrupa grupy (H, ·). Ukažme, že pokud je K dokonce normální podgrupa grupy (H, ·), pak je K · L podgrupa grupy (H, ·). Jistě K · L = ∅. Pro libovolné k ∈ K, ∈ L platí (k · )−1 = −1 · k−1 = ( −1 · k−1 · ) · −1 ∈ K · L, neboť −1 · k−1 · ∈ K díky tomu, že K je normální podgrupa grupy (H, ·). Podobně pro libovolné k1, k2 ∈ K, 1, 2 ∈ L platí (k1 · 1) · (k2 · 2) = k1 · ( 1 · k2 · −1 1 ) · ( 1 · 2) ∈ K · L, neboť opět 1 · k2 · −1 1 ∈ K. Dokázali jsme, že K · L je podgrupa grupy (H, ·), a to ta nejmenší obsahující K i L. Přitom platí, že pokud jsou obě K i L normálními podgrupami grupy (H, ·), pak je K · L též normální podgrupou grupy (H, ·). Totiž pro libovolné h ∈ H a libovolné k ∈ K, ∈ L platí h · (k · ) · h−1 = (h · k · h−1 ) · (h · · h−1 ) ∈ K · L, což bylo třeba dokázat. Označme S množinu všech normálních podgrup grupy (H, ·). Protože H je největší svá normální podgrupa a průnikem libovolného neprázdného systému normálních podgrup grupy H je normální podgrupa grupy H, je (S, ⊆) úplný svaz, v němž pro libovolné K, L ∈ S platí K ∧ L = K ∩ L, K ∨ L = K · L. Dokážeme, že je tento svaz modulární. Zvolme libovolně K, L, M ∈ S tak, že M ⊆ K a ukažme, že (K ∧ L) ∨ M = K ∧ (L ∨ M). Platí (K ∧ L) ∨ M = (K ∩ L) · M, K ∧ (L ∨ M) = K ∩ (L · M). Máme tedy ukázat, že platí (K ∩ L) · M ⊇ K ∩ (L · M), neboť opačná inkluze je modulární nerovnost platná v každém svazu (věta 2.3). Nechť je tedy k ∈ K ∩ (L · M) libovolné. Pak existují ∈ L, m ∈ M takové, že platí · m = k. Z M ⊆ K plyne m ∈ K, odkud = k · m−1 ∈ K. Je tedy ∈ (K ∩ L) a platí k = · m ∈ (K ∩ L) · M, což jsme chtěli dokázat. Důsledek. Svaz všech podgrup dané komutativní grupy je modulární. Důkaz. V komutativní grupě je každá podgrupa normální. Podsvaz modulárního svazu je modulární Věta 6.2. Podsvaz modulárního svazu je modulární svaz. Důkaz. Plyne přímo z definice: v podsvazu se suprema i infima počítají jako v původním svazu, proto je tam i stejné uspořádání. Příklad. Svaz všech podprostorů daného vektorového prostoru V nad tělesem T je podle předchozí věty modulární. Je totiž podsvazem modulárního svazu všech podgrup grupy vektorů V , která je komutativní. Skutečně, stačí si uvědomit, že každý podprostor je podgrupou, a ověřit, že infima i suprema se ve svazu všech podprostorů počítají stejně jako ve svazu podgrup: infimem dvou podprostorů je jejich množinový průnik a jejich supremem je jejich součet. Charakterizace modularity svazu rovností Věta 6.3. Svaz G je modulární, právě když pro každou trojici prvků a, b, c ∈ G platí (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ (a ∧ c)). Důkaz. Je-li svaz modulární, plyne předchozí rovnost z modulární rovnosti pro prvky a, b, a ∧ c díky zřejmé nerovnosti a ∧ c ≤ a. Naopak, nechť svaz G splňuje rovnost této věty a nechť a, b, c ∈ G jsou libovolné takové, že c ≤ a. Pak platí a ∧ c = c, a tedy (a ∧ b) ∨ c = (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ (a ∧ c)) = a ∧ (b ∨ c), což jsme měli dokázat. Důsledek. Součin modulárních svazů je modulární svaz. Homomorfní obraz modulárního svazu je modulární svaz. Důkaz. Víme z důkazu věty 5.1, že součin zdědí libovolnou rovnost platnou v obou svazech. Také tvrzení o homomorfních obrazech plyne z toho, že modularita je charakterizována rovností. Ekvivalentní podmínka modularity Poznámka. Následující věta dává užitečné kriterium, jak ukázat, že daný svaz není modulární: stačí nalézt dva různé srovnatelné prvky mající se třetím prvkem stejná infima i suprema. Věta 6.4. Svaz G je modulární, právě když pro každou trojici prvků a, b, c ∈ G platí implikace a ≥ c, a ∧ b = c ∧ b, a ∨ b = c ∨ b =⇒ a = c. (1) Důkaz. „⇒ Předpokládejme, že svaz G je modulární a že pro trojici prvků a, b, c ∈ G platí c ≤ a, a ∧ b = c ∧ b, a ∨ b = c ∨ b. Pak z absorpčních zákonů a modulární rovnosti plyne c = (c ∧ b) ∨ c = (a ∧ b) ∨ c = a ∧ (b ∨ c) = a ∧ (b ∨ a) = a. „⇐ Předpokládejme, že ve svazu G platí implikace (1). Zvolme libovolně trojici prvků a, b, c ∈ G tak, že c ≤ a, a označme x = (a ∧ b) ∨ c, y = a ∧ (b ∨ c). Z modulární nerovnosti (věta 2.3) víme, že x ≤ y. Ukážeme-li, že též platí x ∧ b = y ∧ b, x ∨ b = y ∨ b, podle implikace (1) dostaneme x = y, což je modulární rovnost pro prvky a, b, c. Z x ≤ y plyne x ∨ b ≤ y ∨ b, neboť z y ∨ b ≥ y ≥ x, y ∨ b ≥ b je jasné, že y ∨ b je horní závora prvků x, b. Z absorpčního zákona x ∨ b = ((a ∧ b) ∨ c) ∨ b = ((a ∧ b) ∨ b) ∨ c = b ∨ c, jistě b ∨ c ≥ a ∧ (b ∨ c) = y a b ∨ c ≥ b. To pak znamená x ∨ b = b ∨ c ≥ y ∨ b, což spolu s dříve odvozenou opačnou nerovností dává x ∨ b = y ∨ b. Analogicky z x ≤ y plyne x ∧ b ≤ y ∧ b a z absorpčního zákona y ∧ b = (a ∧ (b ∨ c)) ∧ b = a ∧ ((b ∨ c) ∧ b) = a ∧ b. Jistě a ∧ b ≤ (a ∧ b) ∨ c = x, také a ∧ b ≤ b, proto y ∧ b = a ∧ b ≤ x ∧ b, opět s opačnou nerovností dostáváme potřebnou rovnost x ∧ b = y ∧ b.