4    SVAZY JAKO ALGEBRAICKÉ STRUKTURY
V této kapitole rozvineme základy teorie svazů. Přitom se na svazy budeme dívat jako na algebraické struktury se dvěma operacemi. Zavedeme relaci ..být podsvazem" a budeme věnovat pozornost především podsvazům, které se nazývají ideály a filtry. Ukážeme, jak je možné z daných svazů konstruovat nové svazy pomocí direktního součinu. Zavedeme pojem svazový homomorfismus a dokážeme, že je speciálním případem posetového homomorfismu. V závěru kapitoly ukážeme, že všechny svazové kongruence daného svazu S dávají přehled o všech homomorfních obrazech svazu S. V kapitole je řada poznámek upozorňujících na analogie teorie svazů s teorií grup.
4.1       Svazy jako algebraické struktury
V kapitole 2 jsme definovali svaz jako speciální poset. Protože tato definice vlastně patří do teorie množin, budeme ji v dalším textu často nazývat množinovou definicí. Nyní ukážeme, že svaz je možné zavést též jako určitou algebraickou strukturu se dvěma binárními operacemi. Této druhé definici budeme proto říkat algebraická definice. Zvolíme zde obdobný postup jako v kapitole 2, tzn. nejprve vyslovíme algebraické definice polosvazů a potom pomocí nich vytvoříme algebraickou definici svazu. Z prováděných úvah vyplyne, že obě definice svazů jsou ekvivalentní.
Po vyslovení množinové definice průsekového polosvazů (viz def. 2.1) jsme dokázali, že operace n je idempotentní, komutativní a asociativní. Nyní ukážeme, že tyto tři vlastnosti průsekový polosvaz jednoznačně charakterizují.
Věta 4.1. Nechť (P, n) je algebraická struktura s jednou binární operací, pro kterou platí:
(Vx, y e P) x n y = y n x komutativnost        (4.1)
(Vx, y, z e P) (x n y) n z = x n (y n z) asociativnost (4.2)
(Mx e P) x n x = x idempotence (4.3)
83
Pak množina P tvoří průsekový polosvaz vzhledem k uspořádání definovanému takto:
(Vjc, y e P) x s y «* x n y = x, (4.4) přičemž x n y je infimum množiny {x, y).
Poznámka. Definici relace a v množině P jsme si pripravili ve větě 2.6, která je dokazatelná v libovolném průsekovém polosvazu.
Důkaz (věty 4.1). Důkaz rozdělíme na dvě části. V první části dokážeme, že relace =3 v P je uspořádání, tzn. že dvojice IP. < I je poset. V druhé části ukážeme, že vztah mezi zadanou operací - a definovanou relací ^ je vyjádřen formulí
(V.v.y 6 P) x - y = iní „v. v]. (4.5)
I. Dokážeme, že relace ^ v množině P je a) reflexívní, b) antisymetrická, c) tranzitivní. Nechť x, y, z jsou libovolné prvky z P, pak:
a) z formule (4.3) vyplývá formule (Vjc e P) x ^ x
b) 1. x ^ y a y ^ x Předpoklad
2. xny = XAynx = y Podle (4.4) na ř. 1.
x = y Podle (4.1) na ř. 2.
c) l.isjíAjsz Předpoklad
2. xny = XAynz = y Podle (4.4) na ř. 1.
3. x n z = (x n y) n z = Pomocí ř. 2 a formule (4.2).
= X n (y n z) = X n y = X
x s
Podle (4.4) na ř. 3.
II. Dokážeme, že pro průsek libovolných prvků x, y e P platí a) formule (2.5) a b) formule (2.6).
a) 1. (x n y) n x = {x n x) n y = x n y       Podle (4.1), (4.2), (4.3).
.rnv<i Podle (4.4) na ř. 1.
Obdobně se dokáže x n y ^ y.
b) Nechť z je libovolný prvek z P, pro který platí:
1. z<XAZ<}' Předpoklad
2. znx = ZAZny = z Podle (4.4) na ř. 1.
3. (x n y) n z = x n (y n z) = Pomocí ř. 2 a formulí (4.1), (4.2). = X 1-1 z = z
z ^ x n y Podle (4.4) na ř. 3.
Přistupme k algebraické definici průsekového polosvazu.
Definice 4.1. Algebraická struktura (P, m) se nazývá průsekový polosvaz,právě když je lato struktura komutativní, asociativní a každý prvek z P je vzhledem k operaci n idempotentní. Uspořádání v P lze definovat formulí (4.4).
-ýfg----
■
84
Množinová definice 2.1 průsekového polosvazu je ekvivalentní s algebraickou definicí 4.1. Zopakujme: Zavedeme-li průsekový polosvaz jako speciální poset definicí 2.1, lze v něm dokázat identity (4. 1), (4.2) a (4.3) a platí v něm také formule (4.4). Pokud naopak zavedeme průsekový polosvaz definicí 4.1 jako algebraickou strukturu s jednou operací n, dá se v této struktuře vhodně dodefinovat uspořádání s (viz formule (4.4)) tak, že operace n má k tomuto uspořádání právě takový vztah, jaký požadovala množinová definice (viz formule 4.5).
K větě 4.1 lze vyslovit větu duální a obdobně k definici 4.1 lze vyslovit definici duální. r.
, H: l
Věta 4.1'. Nechf{P, u) je algebraická struktura s jednou binární operací, pro kterou platí:
(Vx, y e P) x u y = y u x komutativnost    (4.1')
(Vx, y, z e P) (x u y) u z = x lj {y i_i z) asociativnost (4.2')
(Vx e P) x u x = x idempotence (4.3')
Pak množina P tvoří spojový polosvaz vzhledem k uspořádání definovanému
(Vx, y e P) x ^ y    x i_i y = y, (4.4')
přičemž x la y je supremum množiny {x, y}.
Definice 4.1'. Algebraická struktura (P, u) se nazývá spojový polosvaz, právě když je tato struktura komutativní, asociativní a každý prvek z P je vzhledem k operaci u idempotentní. Uspořádání v P lze definovat formulí (4.4').
Poznámka. V definicích (4.1) a (4.1) jsme zavedli algebraické struktury s jednou operací. Pokud chceme vytvořit strukturu s alespoň dvéma operacemi, pak se mezi požadavky kladenými izolovaně na tyto operace musí vyskytnout i požadavky, které je „vhodně váží" dohromady. Tím zajišťujeme, že nosič struktury spolu s těmito operacemi tvoří „přijatelný celek". Tuto situaci jsme poznali např. při zavádění okruhů, v nichž „svazujeme" operace + a • pomocí distributivnosti. V našem případě budou hrát roli „spojovacích axiomů" požadavky absorpce, tj. formule
(Vx, y g ,9) x n (x u y) = x, (4.6) (V.v, y e S) x lj (x n y) = x. (4.6')
A nyní již máme připraveno vše k vyslovení algebraické definice svazu.
Definice 4.2. Algebraická struktura (S, n, i_i) se nazývá svaz, právě když v ní platíformule (4.6), (4.6') a dále když struktury (S, u) u (S, n) jsou po řadě spojovým a průsekovým polosvazem. Uspořádání ve svazu S lze definovat kteroukoli z formulí (A A) a {A A').
Množinová a tato algebraická definice svazu jsou ekvivalentní, neboť i požadavky absorpce jsme dokázali na základě množinové definice. Z toho vyplývá, že všechny věty, které jsme doposud o svazech uvedli, zůstanou v platnosti i při tomto
85
algebraickém pojetí. Také je znovu dobře vidět platnost principu duality, protože základní požadavky kladené na obě svazové operace jsou stejné. Poznamenejme, že při bližším zkoumání definice 4.2 se ukáže, že obsahuje nadbytečné požadavky. Idempotence libovolného prvku vzhledem k oběma operacím je již dokazatelná (viz cv. 4.1).
Poznámka. Množinová i algebraická definice tedy zavádějí přesně týž matematický objekt zvaný svaz. Každá z nich však bere za své východisko jeho jinou stránku. Tradičně se v učebnicích algebry zavádí svaz nejprve jako poset a teprve potom jako algebraická struktura*). Tak jsme to také udělali my. Zatímco množinová definice je velmi intuitivní a dovoluje (i díky Hasseovým diagramům) dobře vniknout do problematiky, je druhá definice, jak se později ukáže, vhodnější při vlastním rozvíjení teorie svazů. Pohlížíme-li na svazy jako na algebraické struktury, pak můžeme využít i mnoha zkušeností, které máme s budováním teorií jiných algebraických struktur (především grup a okruhů).
Je zřejmé, že nyní se můžeme na svazy dívat jako na uspořádané algebraické struktury. „Vhodné chování" operací n a u vzhledem k uspořádání :s ukazují např. formule (2.21) a (2.21'). Svaz bychom proto mohli zapisovat i jako čtveřici (S, n, =9). Při tomto algebraickém pojetí svazu 5 budeme někdy dvojici (S, :s) nazývat posetová část svazu 5.
Na závěr článku znovu zdůrazněme, že je jedno, zda se nyní budeme na svaz dívat jako na určitý poset nebo jako na určitou algebraickou strukturu se dvěma operacemi. V dalším textu však bude převládat druhé hledisko.
4.2 Podsvazy
Z praktických důvodů jsme o binární relaci „být podsvazem" hovořili už na konci kapitoly 2 a v souvislosti s tím jsme vyslovili i její definici. Nyní se budeme touto relací zabývat podrobněji a ukážeme některé její důležité vlastnosti. Nejprve vyslovíme ještě jednou definici a to tak, aby odpovídala našemu pojetí svazu jako algebraické struktury. Později ji porovnáme s dřívější definicí 2.4.
Definice 4.3. Svaz (A, n, □) se nazývá podsvazem svazu (5, n, u), právě když A £ 5 a operace n a □ jsou zúžením operací n a u na množinu A. Pokud A <= S, pak se A nazývá vlastní podsvaz svazu S.
Definice 4.3 se někdy vyslovuje také takto: Podmnožina A svazu S tvoří podsvaz svazu 5, právě když je uzavřená vzhledem k operacím n a u. K formulaci definice 4.3 ještě poznamenejme: protože zúžené operace v množině A si ponechávají všechny vlastnosti, které jsme požadovali po svazových operacích v definici 4.2, je podsvazem A svazu S skutečně svaz.
Pouze v definici 4.3 jsme operace v A značili jinak než operace v 5. V dalším textu budeme opět značit operace i jejich zúžení stejně.
*) V něklervch knížkách se to však provádí prakticky současně.
86
Přenecháme čtenáři, aby sám vyslovil definici relace „být podpolosvazem" mezi průsekovými polosvazy, popř. mezi spojovými polosvazy. Protože polosvazy jsou speciální komutativní pologrupy, bude se vlastně jednat o definici relace „být podpologrupou".
Příklad 4.1. Uvažujme v množině N a) množinu Mx všech dělitelů čísla 24, b) množinu M2 všech dělitelů čísla 30. Zavedeme-li v N operace průsek a spojení takto:
x n y =df D{x, y)      x u y =df n(x, y),
pak množiny MÍ,M2 tvoří podsvazy svazu (N, n). Určujeme-li totiž pro libovolné dva prvky z M, největší společný dělitel a nejmenší společný násobek, pak je výsledek stejný vMjivN. Obdobně je tomu i pro M2. Uspořádáním je v těchto svazech relace | (viz příklad 2.5 a 2.4). Posetová část (M,, |) je podposetem posetové části (N, |) a obdobně je tomu i pro M2.
Příklad 4.2. Je-li dána v rovině g kartézská soustava souřadnic, pak každý bod této roviny je jednoznačně popsán pomocí dvojice reálných čísel. Nechť množina S = R x R a operace v S jsou zavedeny takto:
[al, a2] n [bl, b2] =df [min (a,, bx), min (a2, b2)] [al, a2] u [bt, b2] =df [max (a], />,), max (a2, b2)]
Přenecháme čtenáři, aby ověřil, že algebraická struktura (S, u, n) je svaz. Uvažujme dále množinu A bodů znázorněných na obr. 25a. Je zřejmé, že množina A je uzavřená vzhledem k oběma svazovým operacím, a proto tvoří svaz, který je navíc podsvazem svazu S. Pokud bychom ve svazu S potřebovali definovat uspořádání, můžeme to v souladu s formulí (4.4) udělat takto:
Příslušný poset (A, ^) je znázorněn na obr. 25b a je podposetem posetu (S,
Příklady 4.3. Nechť je dána grupa G, pak svaz N(G) všech normálních podgrup grupy G je podsvazem svazu L(G) všech podgrup grupy G.
[a{, a2] =3 [bt, b2] <=>dl a, š b{ a a2 ž b2
0
c
Obr. 25
87
Nechť je dán okruh M, pak svaz všech ideálů okruhu M je podsvazem svazu všech podokruhů okruhu M.
Velmi důležité jsou podsvazy svazu P(M), kde P(M) je potence množiny M. Tyto podsvazy jsou uzavřené vzhledem k množinovým operacím ~ a ~ a nazvali jsme je okruhy množin (viz def. 2.3).
Především závěry příkladů 4.1 a 4.2 nás mohou motivovat k vyslovení následující věty.
Věta 4.2. Jestliže je svaz (A, n, u) podsvazem svazu (S, n, u), pafc ye / posetová část (A, ^) podposetem posetové části (S, ^).
Důkaz. Nechť x, y jsou libovolné prvky z A, pro něž platí:
1. x ss y Předpoklad
2. xuy^y v5 Podle (4.4') na ř. 1.
3. x li v = y v A Podle def. 4.3 na ř. 2. * 23„ y                                           Podle (4.4') na ř. 3.
Obdobně lze dokázat, že z x sA y plyne x ^s y.
Důsledkem věty 4.2 je to, že obě definice podsvazu, tj. definice 2.4 i definice 4.3, jsou skutečně ekvivalentní. Upozorněme ještě, že obrácení věty 4.2 neplatí. Již jsme čtenáři ukázali, že svaz L(G) z příkladu 2.11 je podposetem svazu P(G) z příkladu 2.7, nem však jeho podsvazem (operace u vL(G) není zúžením operace u v P{G)). Ještě názorněji tuto skutečnost ukáže následující jednoduchý příklad.
Příklad 4.4. Na obr. 26a,b jsou znázorněny dva svazy Sj a S2. Je vidět, že posetová část svazu S2 je podposetem posetové části svazu 5:. Svaz S2 však není podsvazem svazu Sl, protože operace u v 52 není zúžením operace u v Sj. V S{ platí b u / = e, zatímco v S2 platí b u / = d.
d d
Na závěr předchozích úvah můžeme říci toto: Jestliže požadujeme, aby operace n a i_i ve svazu A byly zúžením operací ve svazu S, pak je tento požadavek silnější než požadavek, aby uspořádání v A bylo zúžením uspořádání v S.
Některé podsvazy daného svazu S můžeme sestrojit pomocí tohoto lemmatu.
88
Lemma 4.1. Nechť S je svaz, a,b jsou libovolné prvky z S, pak množina A všech prvků x e S takových, že a ^ x ^ b, tvořípodsvaz svazu S.
Lemma 4.1 zahrnuje několik případů:
a) Pokud a X b nebo b o a, pak A = 0.
b) Pokud a = b, pak A = {a}.
c) Pokud a ^ b, pak A je uzavřený interval [a, b\
Důležitými podsvazy daného svazu S jsou také počáteční a koncové intervaly příslušné k jeho libovolnému prvku. Jestliže je tedy a e S, pak a] a [a, jsou podsvazy S. Naproti tomu otevřený interval (a, b) nebo polouzavřené intervaly (a, b], [a, b), kde a, b e S, nemusí tvořit podsvazy svazu S, protože ani samy o sobě nemusí tvořit svazy.
Množinovým průnikem libovolných dvou podsvazů Au A2 svazu 5 je opět podsvaz svazu S. Jestliže totiž x, y e A^ n A2, pak i í n y a x u y leží v A, n A2, neboť tyto prvky patří do dvou podsvazů AUA2 svazu S. Vyslovené tvrzení lze rozšířit na libovolný systém podsvazů svazu S.
Lemma 4.2. Jestliže S je svaz a {^4,}, e, je libovolný neprázdný systém jeho podsvazů, pak průnik (~);, ,A, je také podsvaz svazu S.
Když si dále uvědomíme, že každý svaz S je podsvazem sebe sama, pak dojdeme k závěru, že vlastnost „být podsvazem svazu S" je uzáverovou vlastností v množině S (viz def. 3.4). Proto platí:
Lemma 4.3. Množina všech podsvazů daného svazu S tvoří úplný svaz, jehož nulou je 0 a jednotkou je S.
Nechť S je svaz a množina M s S, pak také průnik systému všech podsvazů svazu S obsahujících množinu M (tento systém je neprázdný, neboť určitě obsahuje svaz S) je podsvaz svazu S obsahující množinu M. Na základě tohoto důsledku lemmatu 4.2, popř. 4.3 můžeme vyslovit následující definici.
Definice 4.4. Nechť M je podmnožina svazu S, pak svaz, který je průnikem všech podsvazů svazu S obsahujících množinu M, se nazývá podsvaz generovaný množinou M a značí se [M\. Množina M se nazývá množina generátorů svazu [M].
Nechť S je svaz, pak na základě lemmatu 4.2, popř. 4.3 můžeme říci, že pro libovolnou množinu MqS svaz [M] existuje a navíc můžeme říci, že je to nejmenší podsvaz svazu S obsahující množinu M. Svaz [M] získáme tak, že na prvky množiny M budeme aplikovat operace n a
Příklad 4.5. Uvažujme svaz A všech dělitelů čísla 24 . 33, jehož Hasseův diagram je znázorněn na obr. 27. Pak podsvaz svazu A generovaný množinou {2, 3] je v uvedeném diagramu znázorněn prázdnými kroužky. Podsvaz svazu
89
A generovaný množinou {a, b, c}, kde a = 23 . 32, b = 22 . 3\ c = 2. je znázorněn plnými kroužky. Množinou generátorů samotného svazu A je napr. množina {2\ 2\ 22 . 3, 2 . 32, 33}.
Obr. 27
V obecném případě lze říci, že dvouprvková množina {a, b] s S generuje ve svazu S maximálně čtyřprvkový podsvaz {a, b, a n b, a i_i b], zatímco tříprvková množina {a, b,c} c S může v nekonečném svazu S generovat i nekonečný podsvaz.
Následující článek budeme věnovat dvěma důležitým navzájem duálním druhům podsvazů.
4.3      Ideály a filtry
Již při probírání podposetů daného posetu v čl. 1.7 jsme se zmínili o dvou důležitých druzích podposetů. Jsou to ideály a filtry. V tomto článku ukážeme nejdůležitější vlastnosti těchto objektů, pokud se omezíme na svazy.
Zopakujme, že ideálem / v posetu P rozumíme každou neprázdnou množinu, která je nahoru usměrněná a je dolní. Protože ve svazech máme k dispozici nejen relaci ^, ale také operaci u, je obvyklé, že se speciálně v nich vyslovuje definice ideálu takto:
Definice 4.5. Nechť S je svaz, pak neprázdná množina I £ S se nazývá svazový ideál v S, právě když platí:
(V*, yeS)(xeI Ayel)^>XLjy€l (4.7)
(Mx,ýeS)(x€l a y^x)^yel (4.8)
Jestliže I <= S, pak se I nazývá vlastní ideál.
Z formule (4.7) nou množinu {x, y} Formule (4.8) říká, posetovým ideálen ideálem, budeme r.
Příklad 4.6. K_r
interval I    a] idea
Definice 4.6 Id
lakový, že I = (—. a
Duálním pojna každou neprázdna ně pro svazy vyslov
Definice 4.5 . ".,
fihr v S, pravé když
(Vx.V€S
Jestliže F c S, pak
Každý svazový f _svazový~ budeme S je koncový interv
Definice 4 o Fi.
takorv.
(fx. je S)
'. --^  -  ; :
(TtT€5)
Důkazy těchto la
Z definic 4.5 a 4
90
Z formule (4.7) vyplývá, že množina / je nahoru usměrněná, neboť pro libovolnou množinu {x, y} c 5 existuje její horní závora v S — tou je např. prvek x lj y. Formule (4.8) říká, že množina / je dolní. Každý svazový ideál ve svazu S je proto posetovým ideálem. Protože také každý posetový ideál ve svazu je svazovým ideálem, budeme přívlastek „svazový" vynechávat.
Příklad 4.6. Každý svaz S je v S ideál. Pro libovolný prvek a svazu 5 je počáteční interval («-, a] ideál. Pokud má svaz S nulu, pak množina {0} je ideál.
Definice 4.6. Ideál / ve svazu S se nazývá hlavní, právě když existuje prvek a e S takový, že I = (<-, a]. Jestliže 0 e S, pak ideál {()} se nazývá nulový.
Duálním pojmem k pojmu ideál je pojem filtr. Filtrem F v posetu P rozumíme každou neprázdnou množinu, která je dolů usměrněná a je horní. Definici speciálně pro svazy vyslovíme duálně k definici 4.5.
Definice 4.5'. Nechť S je svaz, pak neprázdná množina F c S se nazývá svazový filtr v S, právě když platí:
(Vjc, y e S) (x e F a y e F) => x m y e F (4.7') {Vx, y e S) (x e F a x a y)   y e F (4.8')
Jestliže F a S, pak se F nazývá vlastní filtr.
Každý svazový filtr ve svazu S je posetovým filtrem a také obráceně. Přívlastek „svazový" budeme proto v dalším textu vynechávat. Pro libovolný prvek a svazu 5 je koncový interval [a, -*) filtr.
Definice 4.6'. Filtr F ve svazu S se nazývá hlavní, právě když existuje prvek a e S takový, že F = [a, ->). Jestliže 1 e S, pak filtr {l} se nazývá jednotkový.
Následující lemmata budou udávat podmínky ekvivalentní s podmínkami (4.7) a (4.8). Tato lemmata proto umožňují vyslovit ještě dvě jiné definice ideálu, které jsou však s definicí 4.5 ekvivalentní.
Lemma 4.4. Nechť S je svaz, pak neprázdná množina J <=, S je ideál, právě když platí:
(Vx, ye5)(xe/A>'6/)=>JCLjye/ (4.7) {Vx,yeS)xeJ^xnyeI (4.9)
Lemma 4.5. Nechť S je svaz. pak neprázdná množina I Q S je ideál, právě když platí:
{Vx,yeS)(x£l Ayel)** XLjyel (4.10)
Důkazy těchto lemmat zařadíme do cvičení stejně jako formulaci lemmat duálních k lemmatům 4.4 a 4.5.
Z definic 4.5 a 4.5' bezprostředně vyplývá:
91
Lemma 4.6 (a 4.6'). Nechť S je svaz s nulou {jednotkou), pak každý ideál (filtr) ve svazu S tuto nulu [jednotku) obsahuje.
V definici ideálu / svazu S se říká, že I je neprázdná podmnožina svazu S. Věnujme se proto otázce, zda množina / tvoří podsvaz svazu 5, tzn. zda je množina / uzavřená vzhledem k operacím n a u. Uzavřenost množiny / vzhledem k operaci u popisuje formule (4.7). Ve formuli (4.9) se říká, že x n y e / pro libovolný prvek x e I a libovolný pivek y e S. Tím je však zaručeno, že i pro libovolnou dvojici prvků x, y e / je x n y e /. Proto platí:
Lemma 4.7. Jestliže I je ideál ve svazu S, pak I je neprázdný podsvaz svazu S.
Lemma 4.7'. Jestliže F je filtr ve svazu S, pak F je neprázdný podsvaz svazu S.
Množinovým průnikem libovolných ideálů , /: ve svazu S je opět ideál ve svazu S nebo množina 0. Odůvodnění podejme přímo podle def. 4.5. Jestliže x, y jsou libovolné prvky z / , n I2, pak prvek x u y patří do /, i I2, a patří proto i do Ilr\I1. Jestliže prvek x e lí n 72, pak všechna y ^ x, kde y e 5, patří do /] i 12, a proto patří i do II n I2 ■ Uvedené tvrzení lze rozšířit na libovolný neprázdný systém ideálů v S.
Lemma 4.8. Jestliže S je svaz a {/,},,} je libovolný neprázdný systém jeho ideálů, pak průnik pj,Ey/,ye ideál ve svazu S nebo množina 0.
Když si dále uvědomíme, že každý svaz S je ideálem v 5, pak dojdeme k závěru, že vlastnost „být ideál svazu S nebo množina 0" je uzáverová vlastnost v množině S (viz def. 3.4). Proto platí:
Lemma 4.9. Množina všech ideálů daného svazu S doplněna o množinu 0 tvoří vzhledem k e úplný svaz, v němž je nulou množina 0 a jednotkou množina S.
Lemma 4.9'. Množina všech filtrů daného svazu S doplněná o množinu 0 tvoří vzhledem k S úplný svaz, v němž je nulou množina 0 a jednotkou množina S.
Poznamenejme, že pokud má svaz S nulu, pak už samotná množina všech ideálů svazu S tvoří úplný svaz, jehož nulou je nulový ideál {O}. V tomto případě by proto ani nebylo potřeba přidávat k množině ideálů množinu 0. Obdobně je tomu pro filtry.
Nechť S je svaz a neprázdná množina M e S, pak také průnik systému všech ideálů svazu S obsahujících množinu M (tento systém je neprázdný, neboť určitě obsahuje svaz S) je ideál svazu 5 obsahující množinu M. Na základě tohoto důsledku lemmatu 4.9 můžeme vyslovit následující definici.
Definice 4.7. Nechť S je svaz a neprázdná množina M je podmnožinou S, pak průnik všech ideálů v S obsahujících množinu M se nazývá ideál generovaný množinou M a značí se IM.
92
tk každý ideál (filtr)
nožina svazu S. Vě-bzd 5. tzn. zda je ■nožřny I \ zhledem ká, že j n y e / pro ; jaročeno. že i pro
brv podsvaz svazu S.
iný podsvaz svazu S.
■ 5 je opět ideál ve b defc 4.5. Jestliže x, /,, a patří proto i do e 5. patří do /, i I2, Hxjvolný neprázdný
systém jeho ideálů.
tk dojdeme k závěru, rá vlastnost v množi-
ma o množinu 0 tvoří množina S.
. . - ieálú by proto ■: mu pro
Definice 4.7'. Nechť S je svaz a neprázdná množina M je podmnožinou S, pak průnik všech futrů v S obsahujících množinu M se nazývá filtr generovaný množinou M a značí se FM.
Pokud je množina M v definici 4.7 (4.7') jednoprvková, tzn. platí M = {a}, kde a e S, pak obdržíme hlavní ideál (hlavní filtr) svazu 5 generovaný prvkem a. Značíme ho buď /„, nebo (<-, a] (F„, nebo [a, —)).
Nechť S je svaz, pak na základě lemmatu 4.8, popř. 4.9 můžeme říci, že pro libovolnou neprázdnou množinu M e S ideál IM existuje a navíc lze říci, že je to vzhledem k inkluzi nejmenší ideál svazu S obsahující množinu M. Jestliže má svaz 5 nulu, pak nemusíme předpokládat, že množina M # 0. Jestliže M = 0, pak Ie ={0}. Duálně, jestliže má svaz 5 jednotku, pak opět nemusíme předpokládat neprázdnost množiny M. Jestliže M - 0, pak F0 Následující věty budou
popisovat, jak pomocí množiny M získáme IM, popř. FM.
Věta 4.3. Ideál I ve svazu S generovaný neprázdnou množinou M E S je množina všech takových prvků x e 5, pro něž platí x ^ a, u a2 u ... u ak, kde at jsou prvky z množiny M, tzn. IM = {x e S; {iaí, a2,..., ak e M) x ^ a} u a2 u ... i_i a^.
Důkaz. Vyslovíme pouze hlavní myšlenku důkazu. Množina všech takových prvků x splňujících podmínku uvedenou ve větě 4.3 musí být obsažena v každém ideálu obsahujícím množinu M, Tato podmínka však vznikla spojením podmínek (4.7) a (4.8) z definice ideálu rozšířených na k prvků. Proto je tato množina již ideálem v S, který navíc obsahuje množinu M.
Důsledky věty 4.3. Jestliže množina M Q S obsahuje pouze prvek a, pak ideál generovaný množinou M je skutečně hlavní ideál a platí
Ia = {xe S; x ^ «} = (*-, a].
Jestliže množina M s S obsahuje konečný počet prvků ax, a2,...,a„, pak ideál / generovaný množinou M je opět hlavní a lze ho generovat prvkem a = at u i_i a2 u ... i_i a„, tzn. IM = Ia. Z toho vyplývá, že také libovolný ideál konečného svazu je hlavní.
Vyslovení duální věty k větě 4.3 i jejích důsledků přenecháme opět čtenáři.
Příklad 4.7. Uvažujme svaz A všech celočíselných kladných dělitelů čísla 24 . 3?, jehož Hasseův diagram je znázorněn na obr. 28, pak ideál / generovaný množinou (a, b, c}, kde a = 23, b = 22 . 3 a c = 2 . 3, je hlavní ideál generovaný prvkem d — a u b u c = 23 . 3. Tento ideál je znázorněn na obr. 28 plnými kroužky.
S. pak -nno-
93
1
Obr. 28
Příklady 4.8. Uvažujme svaz (R, á) reálných čísel. Tento svaz je sám v sobě ideál, ale nem hlavní, protože nemá žádnou jednoprvkovou množinu generátorů. Obecně zřejmě platí, že každý nekonečný svaz S nemající jednotku je ideál v S, který není hlavní.
Uvažujme opět svaz (R, á), pak intervaly [5, 7) a [5, 9] generují po řadě ideály («-, 7) a (—, 9], z nichž druhý je hlavní.
Uvažujme řetězec {iT3, 5, 7, 6, 4, 2, 0}, pak ideál generovaný množinou {i e N; x > 5 a i je liché} je množina všech lichých čísel. Tento ideál opět není hlavní.
Uvažujme svaz P(M), kde M je nekonečná množina. Množina A všech konečných podmnožin množiny M je ideál ve svazu P(M). Tento ideál není hlavní.
V příkladu 1.28 jsme uvažovali poset f(R), který je dokonce svazem. Množina K všech otevřených intervalů obsahujících určité reálné číslo z generuje filtr všech okolí bodu z ve svazu P(R).
Nyní uvedeme dvě lemmata dávající do souvislosti pojmy hlavní ideál a hlavní filtr s podmínkami rostoucích a klesajících řetězců.
Lemma 4.10 (a 4.10'). Nechť svaz S splňuje podmínku rostoucích (klesajících) řetězců, pak každý ideál I (filtr F) ve svazu S je hlavní.
Důkaz. Nechť / je libovolný ideál ve svazu S splňujícím podmínku rostoucích řetězců. Pak podle věty 1.8 musí v množině / existovat maximální prvek a. Podle formule (4.7) je množina / uzavřená vzhledem k operaci u, a proto je prvek a zároveň nej větším prvkem v /, tzn. I = Ia. Pro filtry je důkaz duální.
Zaveďme ještě určité speciální druhy ideálů a filtrů.
94
■i >am v sobě i generátorů, ideál v S,
po řadě ideály
■aný množinou ideál opět není
A všech konečném' hlavní. - izem. Množi-: generuje filtr
ideál a hlavní
ích {klesajících)
ínku rostoucích rrvek a. Podle proto je prvek i_i'.ní.
Definice 4.8. Vlastní ideál / svazu S se nazývá maximální, právě když ve svazu S neexistuje žádný vlastní ideál obsahující l jako vlastní podmnožinu. Vlastní ideál I svazu S se nazývá prvoideál, právě když pro něj platí
Definice 4.8'. Vlastní filtr F svazu S se nazývá maximální, právě když ve svazu S neexistuje žádný vlastní filtr obsahující F jako vlastní podmnožinu. Vlastní filtr F svazu S se nazývá ultrafiltr, právě když
(Vx, ysS)xLjyeF^(xeF\/yeF).
Jestliže sestrojíme úplný svaz všech ideálů svazu S (viz lemma 4.9), pak maximální ideály v S tvoří koatomy (dolní sousedy jednotky, tj. ideálu S). Analogicky je tomu pro maximální filtry. Dále poznamenejme, že podmínka vyslovená v definici prvoideálu zakazuje situaci znázorněnou na obr. 29. / značí ideál ve svazu S a x, y jsou prvky svazu S.
Příklad 4.9. Na obr. 30a je znázorněn svaz S mající ideály {O}, {0, a], {0. b) a S. Vlastními ideály jsou pouze tři (Oj, {0, a} a {0, b}. Ideály {0, a} a (O, b) jsou maximálními ideály a navíc jsou i prvoideály. Ideál {O} není maximální ani není prvoideálem, neboť a n b e {0} a přitom a, b i {O}. Na obr. 30b je znázorněn diamant M5 a v něm je vyznačen ideál / = {0, cj. Tento ideál je maximální, není však prvoideálem.
Příklad 4.10. Uvažujme svaz reálných čísel ([0, l], á). Pak všechny polouzavře-né intervaly [0, «), kde 0 < a S 1, a všechny uzavřené intervaly [0, a], kde
(Vjc, yeS)xr-iyeI^>(xeIvyel),
95
O á a < 1, jsou prvoideály v [0, l]. Polouzavřený interval [0, 1) je maximální ideál v [0, l]. Žádné další prvoideály nebo maximální ideály ve svazu [0, l] neexistují.
Lemma 4.11. Nechť S je svaz a nechť I a F jsou dvě disjunktní podmnožiny množiny S, pro něž platí I u F — S. Pak I je prvoideál v S, právě když je F ultra-filtr v S.
Důkaz. Nechť / je prvoideál v S, pak dokažme, že F = S - I je ultrafiltr v 5. Nejprve dokážeme, že F je filtr. Postupovat budeme přímo podle definice 4.5'. Nechť x, y jsou libovolné prvky z F, pak x i Iay $ F Protože / je prvoideál, nepatří ani průsek x n y do I, tzn. x n y e F. Nechť x e F a nechť x s y, kde y e S, pak x i I a podle (4.8) ani y í /, tzn. y e F. Množina F je proto filtr. Nyní dokážeme podle definice 4.8', že F je ultrafiltr. Množina F je vlastní podmnožinou 5, protože 7^0. Nechť spojení x u y e F, pak x u y i I a podle obměněné formule k (4.7) alespoň jeden z prvků x, y nepatří do I, tzn. xe F nebo y e F. Proto F je ultrafiltr. Duálně obdržíme důkaz obrácené implikace.
Lemma 4.11 ukazuje, že v libovolném svazu S existuje vzájemně jednoznačné zobrazení množiny jeho prvoideálů na množinu jeho ultrafiltrů. Toto zobrazení přiřazuje každému prvoideálů Iv S ultrafiltr F — S — I.
Je zřejmé, že nulový ideál {0} ve svazu S s nulou je maximální, právě když má svaz S právě dva prvky. Nulový ideál {O} ve svazu 5 s nulou majícím alespoň dva prvky je prvoideál, právě když ve svazu S platí:
(Vx,yeS)xny = 0*(x = 0 vy-0) (4.11)
Každý dvouprvkový svaz S má samozřejmě vlastnost popsanou formulí (4.11). Existují však i víceprvkové svazy mající vlastnost (4.11). Takovým je např. svaz z př. 4.10. Duální tvrzení můžeme vyslovit také pro filtry.
Na základě představy, kterou jsme si vytvořili o provoideálech (viz obr. 29) nebo duálně o ultrafiltrech, není těžké vyslovit následující lemmata.
Lemma 4.12 (a 4.12'). Svaz S je řetězec, právě když všechny jeho vlastní ideály (filtry) jsou prvoideály (ultrafiltry).
Místo důkazu řekněme pouze toto: Pokud je S řetězec, pak je zřejmě každý jeho ideál prvoideálem. Pokud svaz S není řetězec, pak v něm musí existovat alespoň jedna situace znázorněná na obr. 31. Sestrojíme-li hlavní ideál /=(<-, a], pak tento ideál je vlastní a není prvoideálem, neboť a£l,a = xnya přitom x i I a současně y i I.
Obr. 31
4.4 Direkrr
svazů, které ja dňektniho i d svazů. Han
Věta AA. Xedk smxačemA x Ä.>
96
I) je maximální ideál razu [O, l] neexistují.
fjunktní pod množiny wátě když je F ultra-
= 5-7 je ultrafiltr o podle definice 4.5'.
. r" xdeál. nepatří /.kde v e S. pak x i I fíyní dokážeme podle inou 5, protože 7^0.
. . 4.7) alespoň F je ultrafiltr. Duálně
rajemně jednoznačné fOtrú. Toto zobrazení
frimální právě když nlou majícím alespoň
(4.11)
nou formulí (4.11). akovým je např. svaz
(viz obr. 29)
jeho vlastní ideály
je zřejmě každý jeho existovat alespoň § — |__ a\ pak tento i pí»um x 11 a sou-
4.4
Direktní součin svazů
V tomto článku se budeme zabývat konstrukcí nových svazů pomocí svazů, které již máme k dispozici. Tak jako lze v teorii grup vytvářet pomocí direktního součinu z daných grup grupy nové, můžeme analogicky postupovat i u svazů. Platí věta:
Věta 4.4. Nechť (A, n\ u1), (B, n, □) jsou svazy, pak algebraická struktura s nosičem A x B, jejíž operace n a u jsou definovány takto:
[*i. *z] n [yi, >'2] =df k ny,, x2 n y2] (4.12)
[x,, -t2] u [v,, y2] =df [x, u>,, x2 □ y2], (4.12')
/e swz.
Podstata důkazu věty 4.4 spočívá v tom, že při provádění operací s dvojicemi [x,, x2] e A x B se s prvními složkami dělají svazové operace z/la nezávisle na tom se s druhými složkami dělají svazové operace z B. Na základě věty 4.4 lze vyslovit následující definici.
Definice 4.9. Nechť (A, n\ i_/) a (/?, n, □) /som srazy, pa/t sooz A x B, jehož operace n a u definovány formulemi (4.12) a (4.12'), se nazývá direktní součin svazů ^4,5.
Jestliže bude potřeba zavést ve svazu A x B svazové uspořádání, pak to uděláme známým způsobem
což jinak formulováno znamená
[x1,x2]ži\y1,y2]** Xj^y, a x2sBy,. (4.13)
Protože operace direktní součin je asociativní*), lze ji rozšířit na libovolný konečný, popř. i nekonečný soubor svazů. Tuto operaci můžeme samozřejmě zavést i pro polosvazy (v definici použijeme formuli (4.12) nebo (4.12')), popř. pomocí uspořádání už i pro posety (v definici použijeme formuli (4.13)).
Nechť A, B jsou svazy, pak na základě formule (4.13) zavádějící uspořádání ^ v direktním součinu A x B můžeme říci, že zobrazení
F: [x, y] e A x B «• x e A
(4.14)
zachovává uspořádání, tzn. že F je posetový homomorfismus posetu A x B na poset A. V článku 4.5 uvidíme, že toto zobrazení zachovává i operace, a že se
*) Tato asociativnost vyplývá z úmluvy, že uspořádané trojice [[x,, x2], xs] a [xs, [x2, x,]] pokládáme za sobě rovné.
97
proto jedná o svazový homomorfismus svazu A x B na svaz A (viz def. 4,13). Obdobnou vlastnost má zobrazení
Gk[x,y]eAxB**yeB. (4.15)
Na závěr tohoto stručného pojednání o direktních součinech svazů uveďme několik příkladu.
Příklady 4.11. V příkladě 2.5 jsme uvažovali svaz všech dělitelů čísla 24 = 23 . 3 v N. Tento svaz lze zkonstruovat jako direktní součin řetězců {2°, 2\ 22, 23} a {3°, 31}. Obdobně lze např. svaz všech dělitelů čísla 24. 33 v (viz obr. 32a) považovat za direktní součin řetězců {2°, 2', 22, 23, 24} a {3°, 31, 32, 33}. Také např. svaz všech dělitelů čísla 22_^32. 5 v N (viz obr. 32b) lze považovat za direktní součin tří řetězců {2°, 21, 22}, {3°, 31, 32} a {5°, 51}. Obecně:
svaz všech dělitelů čísla p\[ . p1?.....p*" v N, kdept jsou různá prvočísla a /c; jsou
přirozená čísla, lze považovat za direktní součin řetězců všech dělitelů čísel p\\Pz,... ,pť v N (viz poznámka na str. 101).
Také např. svaz P({a, b, c}) (viz obr. 5c) můžeme považovat za direktní součin řetězců {07{fl}}, {07{ď}} a {07{c}}. Obdobně můžeme libovolný svaz P({a, b,..., n}) považovat za direktní součin dvouprvkových svazů {07{a}}, {0t{^}} až {07{«}}.
Obr. 32
4.5      Homomorfismy svazů
V tomto článku budeme studovat především dvě binární relace mezi svazy. Jsou to relace „být izomorfní" a její zobecnění relace „být homomorfní". Tyto relace jsme zavedli již pro posety. Protože se však v této kapitole díváme na svazy jako na algebraické struktury se dvěma operacemi, budou i definice těchto relací obdobné definicím u jiných algebraických struktur, jako jsou např. grupy
98
A (wdef. 4,13).
(4.15) svazů uveďme
tax všech dělitelů čísla ■ učin řetězců ech dětitelú čísla 24. 33 s^rň f2*, 21, 22, 23, 24} F. 5 vN (vizobr. 32b)lze I\ 3:] a {5°, 51}. Obecně: nižná prvočísla a k, jsou izců všech dělitelů čísel
ižovat za direktní součin voinv svaz F\{a, b,..., n})
fif-Sr{6}}až{ér{n}}.
relace mezi Jm homomorfní". kapitole díváme na i definice těchto i např. grupy
nebo okruhy. V článku porovnáme původní posetové definice s novými definicemi pro svazy a ukážeme i nejdůležitější vlastnosti obou těchto relací.
Nejprve se budeme zabývat relací „být izomorfní". Východiskem se stane definice této relace pro polosvazy.
Definice 4.10. Nechť (S, n) a (A, n) jsou průsekové polosvazy, pak říkáme, že polosvaz A je izomorfní s polosvazem S, právě když existuje prosté zobrazení F: S ™ A, které zachovává operaci, tzn. pro něž platí
(V*, y e S) F(x n y) = F{x) n F(y). (4.16)
Zobrazení F se nazývá izomorfní průsekové zobrazení nebo průsekový izomorfis-mus polosvazu S na polosvaz A a polosvazuAse říká izomorfní obraz polosvazu S.
Definice 4.10'. Nechť (S, u) a [A, □) jsou spojové polosvazy, pak říkáme, že polosvaz A je izomorfní s polosvazem S, právě když existuje prosté zobrazení F: S S A, které zachovává operaci, tzn. pro něž platí
(Vx, y e S) F{x u v) = F{x) a F(y). (4.16')
Zobrazení F se nazývá izomorfní spojové zobrazení nebo spojový izomorfismus polosvazu S na polosvaz A a polosvazu A se říká izomorfní obraz polosvazu S.
Víme, že polosvazy jsou z algebraického hlediska určité speciální komutativní pologrupy. Definice 4.10 a 4.10' proto představují definice izomorfismu pologrup.
Definice 4.11. Nechť (S, n, i_i) a (A, n, □) jsou svazy, pak říkáme, že svaz A je izomorfní se svazem S, právě když existuje prosté zobrazeníF: S ™ A, které je průsekovým i spojovým izomorjismem, tzn. pro nějž platí formule (4.16) a (4.16'). Zobrazení F se nazývá izomorfní svazové zobrazení nebo svazový izomorfismus svazu S na svaz A a svazu A se říká izomorfní obraz svazu 5.
Podle definice 4.11 víme, že zobrazení F je svazový izomorfismus svazu S na svaz A, právě když
F je zobrazení S na A, tzn. F: S ™ A,
F je prosté zobrazení,
F zachovává operace n a u.
Úmluvy. Vzhledem k zjednodušení zápisů nebudeme v dalším textu rozlišovat mezi značením operací nauve svazu S a ve svazu A, který je jeho izomorfním obrazem. Je zřejmé, že pokud je svaz A izomorfním obrazem svazu 5 ve svazovém izomorfismu F, pak je také svaz S izomorfním obrazem svazu A ve svazovém izomorfismu F~\ Proto budeme často užívat rčení „svazy S, A jsou navzájem izomorfní".
Příklad 4.12. Uvažujme okruh množin P(M), kde M je množina mající n prvků, v němž jsou, jak je nám známo, svazovými operacemi množinové operace
99
n a u. Dále uvažujme svaz S všech dělitelů čísla 2.3.5.....p„ (součin prvních
n prvočísel v N), v němž svazovými operacemi n a u jsou po řadě: určení největší-ho společného dělitele a určení nejmenšího společného násobku. Ukažme, že svazy P(M) a S jsou navzájem izomorfní. Abychom mohli izomorfismus F těchto
svazů lépe popsat, dohodneme se, že prvky množiny M označíme 1, 2.....n.
Zobrazení F, pro nějž platí F(@) = 1 a dále
F: {/,4} e M <- /?,■ . ph.....pit e 5.
kde í"i, i2,.... ik jsou navzájem různé prvky z množiny {l, 2, n}, je izomorfní zobrazení svazu P(M) na svaz S.
Bezprostředně z definice zobrazení F plyne, že F je prosté zobrazení množiny FIM) na množinu S. Zobrazení F však zachovává i operace. K tomu si stačí uvědomit, jak se pomocí rozkladu v součin prvočísel tvoří nej větší společný dělitel a nejmenší společný násobek pro dvojici přirozených čísel. Největší společný
dělitel D(F(x), F(y)) dvou dělitelů F(x) a F(y) čísla 2.3.5.....p„ určíme tak, že
sestrojíme průnik množin prvočíselných činitelů obou čísel F(x) a F(y) a prvky tohoto průniku vynásobíme. Obdobně: nejmenší společný násobek n(F(x), F(y)) dvou čísel F(x) a F\y) určíme tak, že sjednotíme množiny všech prvočíselných činitelů obou čísel F(x) a F(y) a prvky tohoto sjednocení vynásobíme.
Pokud zvolíme množinu M = {l, 2, 3j, pak svaz S obsahuje právě všechny dělitele čísla 2.3.5. Část izomorfního zobrazení F svazu P(M) na svaz 5 je znázorněna na obr. 33.
2.3.5
Obr. 33
Příklad 4.13. V příkladu 1.38 jsme ukázali dvojici izomorfních posetu. Šlo o posety všech dělitelů čísel 12 a 45 v N. Izomorfismem bylo zobrazení F definované takto:
F: 2k. 3h ~ 3". 5*,     kde k = 0,1,2   a   h = 0,1
Oba tyto posety jsou však svazy a zobrazení F je dokonce jejich svazovým izomor-fismem (viz cv. 4.14). Pozorovanou skutečnost lze zobecnit podobně jako v uvažovaném příkladě 1.38.
Přiklad 4.14. V r
o poset Ei \/i všech e« dů v množině M. ba
F: E e E\M]
Oba ty:c r . -' - '■ izomorfismem (viz cv
Přiklad 4.15 7 : -.
posetovým izomorfis
F:/ieM~
Uvedené poset>" jsoo
Každý řetězec je ! Každý n-prvkový ře*í je totožné s posetovýi lemmaru-
Yen 45. V«*rJ
ffxjcSI.
List
Z. x — i"j
rU)2fll<
100
. p. (součin prvních db po řadě: určení největší-aásobku. Ukažme, že - rf.smus F těchto M označíme 1, 2, n.
{L. 2—, n}, je izomorfní
"razení množiny operace. K tomu si stačí největa společný dělitel : . Nevětší společný — .pn určíme tak, že ■ OHd F[x) a F(y) a prvky Ibčxtý násobek n(F(x), F(y)) nžim visech prvočíselných em vynásobíme. S obsahuje právě všechny r svazu P\M) na svaz 5 je
d rzomorfhích posetu. Šlo n byio zobrazení F defino-
* = 0,1
ce jejich svazovým izomor-ircnit podobně jako v uva-
Příklad 4.14. V příkladu 1.37 jsme ukázali dvojici izomorfních posetu. Šlo o poset LIM) všech evivalencí v neprázdné množině M a poset S(M) všech rozkladů v množině M. Izomorfismem bylo zobrazení F definované takto:
F: E e E{M) - {uEx]XíM e Siní)
Oba tyto posety jsou svazy (viz př. 2.19) a zobrazení F je dokonce jejich svazovým izomorfismem (viz cv. 4.14).
Příklad 4.15. Posety (N, |) a (Z/£, j ) z příkladu 1.36 jsou izomorfní a jejich posetovým izomorfismem je zobrazení
f:«ĚN»r„e Z/E.
Uvedené posety jsou dokonce svazy a zobrazení F je jejich svazovým izomorfismem.
Každý řetězec je svaz, a proto se lemma 1.5 týká izomorfismu svazů. Říká: Každý w-prvkový řetězec je izomorfní s řetězcem n. Svazové izomorfní zobrazení je totožné s posetovým izomorfním zobrazením definovaným v důkazu uvedeného lemmatu.
Poznámka k příkladům 4.11. Když jsme popisovali, jak lze pomoci direktního součinu z určitých řetězců vytvořit svaz všech dělitelů daného čísla, tak jsme vlastně ztotožňovali různé navzájem izomorfní svazy (což je v algebře běžné). Říkali isme např., že svaz všech dělitelů čísla 24 = 23. 3 lze zkonstruovat jako direktní součin řetězců [2", 2\ 2% 23} a [3", 31}. ..Správně" bychom však měli říkat, že tento svaz je izomorfní s direktním součinem příslušných řetězců. V původním vyjádření jsme totiž ztotožnili prvky 2''. 3' s prvky [2*, 3*], které si v daném izomorfismu odpovídají, tzn. zavedli jsme ..izomorfickou" rovnost
2*. 3' =d, [2*, 3*].
Nyní porovnáme nad třídou svazů definici posetového izomorfismu a definici svazového izomorfismu. K následujícím úvahám nás mohou motivovat příklady 4.13, 4.14 a 4.15, v nichž každý posetový izomorfismus byl současně svazovým izomorfismem. Část odpovědi na předloženou otázku nám pomůže nalézt následující věta.
Věta 4.5. Nechť F je svazový izomorfismus svazu S na svaz A, pak F je také posetový izomorfismus posetu S na poset A, tzn.
(Vx, ye5)jc<}'«. F(x) ±> F(y). (4.17)
Důkaz. Dokážeme pouze přímou implikaci. Důkaz obrácené implikace přenecháme do cvičení (viz cv. 4.15). Nechť x, y jsou libovolné prvky svazu S, pro něž platí:
1. x ^ y Předpoklad
2. x = x n y Podle (4.4) na ř. 1.
3. F(x) = F{x n y) = F(x) n F(y) Podle def. zobrazení a (4.16). F{x) ±? F(y)                                         Podle (4.4) na ř. 3.
101
Na základě věty 4.5 tedy víme, že jsou-li dva svazy svazově izomorfní, pak jsou i posetově izomorfní. Pro posetový izomorfismus jsme dokázali některé vlastnosti v čl. 1.8. Všechny tyto vlastnosti proto zůstanou v platnosti i pro svazový izomorfismus. Zbytek odpovědi na výše položenou otázku nám pomůže nalézt následující věta.
Věta 4.6. Necht (S, 21) a (A, ^) jsou posetové části svazů a nechť F je jejich posetovým izomorfismem, pak F je také svazovým izomorfismem svazů S a A.
Důkaz. Nechť F je posetový izomorfismus svazu S na svaz A, tzn. pro F platí formule (4.17). Dále nechť x, y jsou libovolné prvky z 5, pak
1. xny^x Podle (2.13).
2. x n y   y Podle (2.13).
3. F(x ny)< F(x) Podle (4.17) na ř. 1.
4. F(x n^)< F(y) Podle (4.17) na ř. 2.
5. F{x n y) s F(x) m F(y) Podle (2.14) na ř. 3, 4. Protože F je prosté zobrazení na A, existuje z e S takové, že
6. F(z) = F{x) n Fiy) ä F(x)
7. z & x Podle (4.17) na ř. 6.
8. z s. y Obdobně jako ř. 7.
9. z<xny Podle (2.14) na ř. 7, 8. 10. F(x) n F(y) - F{z) «3 F{x n y) Podle (4.17) a ř. 6, 9.
F(x) n F{y) - F(x n y) Podle (2.2) na ř. 5 a 10.
Dokázali jsme, že pro zobrazení F platí formule (4.16). Duálně lze dokázat formuli (4.16').
Na základě vět 4.5 a 4.6 můžeme vyslovit odpověď na předloženou otázku: Nad třídou svazů jsou definice posetového izomorfismu a svazového izomorfismu ekvivalentní — zavádějí tutéž binární relaci.
Zopakujme, že izomorfní zobrazení svazů zachovává relace -«,-<« a X- Dále zachovává nulu a jednotku svazu (pokud existují), suprema a infima (pokud existují) a podmínky klesajících a rostoucích řetězců. Proto také např. platí, že izomorfním obrazem úplného svazu je opět úplný svaz.
Již v kapitole 1 jsme hovořili o tom, že relace „být izomorfní" je ekvivalence v libovolné množině posetu, a protože je tato vlastnost dědičná, je ekvivalencí i v libovolné množině svazů.
Podobně jako se u konečných grup a okruhů používají k definování binárních operací Cayleyho tabulky, mohli bychom je používat i zde u svazů pro operace n a i_i. Protože však tyto operace velmi úzce souvisí s uspořádáním, užíváme často k jejich určení i Hasseovy diagramy. Na obr. 34 jsou znázorněn) všechny Hasseo-vy diagramy svazů po řadě o dvou, třech a čtyřech prvcích. Každý tento diagram
vlastně charakterizuj dva dvouprvkové sv :z ' mořím', v- sz\ :::. mající pět prvků se šestiprvkové svazy. ; svazech počet bloků i 35 pnpiiemu mi.: bloku.
Řekněme si ně:: meneme situaci v m
Poznámka. V teor : cí Gp, která je s grupou < grup můžeme reprezento ;elvch bloků navzájem iz :endence se projevují i p
Z hlediska repn rozkladů množin) c zrup. Anglický mat
Ke každému sua. množině, který je ::
102
~ : rfní. pak jsou některé vlastnosti o svazový izomor-nalézt následují-
a necht F je jejich ^rfismem svazů S a A.
-z
5. pak
1(2-13). 12-13).
|4.17) na ř. 1. (4.17) na ř. 2. (2.14) na ř. 3, 4. takové, že
tzn. pro F platí
vlastně charakterizuje celý blok navzájem izomorfních svazů. Je vidět, že každé dva dvouprvkové svazy a obdobně každé dva triprvkové svazy jsou navzájem izomorfní. Svazy mající čtyři prvky se však již rozpadnou do dvou bloků a svazy mající pět prvků se rozpadnou do pěti bloků (viz obr. 35). Pokud uvažujeme šestiprvkové svazy, pak je těchto bloků již 15. S rostoucím počtem prvků ve svazech počet bloků velmi rychle stoupá. Když k neoznačeným uzlům na obr. 34 a 35 připíšeme názvy prvků, obdržíme konkrétní svazy, patřící do příslušného bloku.
Obr. 34
(4.17) na ř. 6. lne jako ř. 7. (2.14) na ř. 7, 8. [4.17) a ř. 6, 9. (2.2) na ř. 5 a 10. luámě lze dokázat formuli
r na předloženou otázku: a svazového izomorfismu
i :- «=. a X. Dále ■a a infima (pokud existu-tt např. platí, že izomorf-
■omorfní- je ekvivalence t dpriírro je ekvivalencí
k definování binárních n svazů pro operace užívame často pňún všechny Hasseo-ktKaž
Každý tento diagram
d)
Obr. 35
Řekněme si něco o reprezentaci svazů. Nejprve však ve formě poznámky připomeneme situaci v teorii grup.
Poznámka. V teorii grup platí následující Cayleyho věta: Ke každé grupě G existuje grupa permutací Gp, která je s grupou G izomorfní. Uvedená věta vlastně říká, že každý blok navzájem izomorfních grup můžeme reprezentovat nějakou grupou permutací. Metoda abstrakce, která se projevuje studiem celých bloků navzájem izomorfních grup, je tak vyvážena a doplněna metodou konkretizace. Obdobné tendence se projevují i při studiu svazů.
Z hlediska reprezentace hrají svazy ekvivalencí na množinách (popř. svazy rozkladů množin) obdobnou úlohu v teorii svazů jako grupy permutací v teorii grup. Anglický matematik P. Whitman dokázal:
Ke každému svazu S existuje podsvaz A svazu všech ekvivalencí na nekonečné množině, který je izomorfní se svazem S.
103
Československým matematikům J. Tůmovi a P. Pudlákovi se podařilo navíc dokázat, že pokud je svaz S konečný, pak existuje svaz ekvivalencí na konečné množině, který je izomorfní se svazem S. My se budeme podrobněji zabývat problematikou množinové reprezentace u speciálních svazů. Nejprve to budou tzv. distributivní svazy (viz čl. 6.2) a dále budeme tuto otázku řešit u konečných Booleových algeber (viz čl. 10.4).
Podobně jako jsme u posetu pomocí relace „být izomorfní" zavedli relaci „být izomorfně vnořen", můžeme to udělat i zde u svazů.
Definice 4.12. Nechť F je izomorfismus svazu A na svaz A', který je podsvazem svazu S, pak říkáme, že F je izomorfní vnoření svazu A do svazu S,ncbo že svaz A je izomorfně vnořen do svazu S.
Vypustíme-li v definici relace „být izomorfní" mezi polosvazy, popř. mezi svazy, podmínku, aby zobrazení F bylo prosté, pak obdržíme obdobně, jako je tomu u jiných algebraických struktur, definici relace „být homomorfní". Vyslovme tuto definici rovnou pro svazy.
Definice 4.13. Nechť (S, n, u) a (A, n, □) jsou svazy, pak říkáme, že svaz A je homomorfním obrazem svazu S, právě když existuje zobrazení F: S ™ A, které zachovává operace n a tzn. pro nějž platí formule (4.16) a (4.16'). Zobrazení F se nazývá homomorfní svazové zobrazení nebo svazový homomorfismus svazu S na svaz A.
Množina všech prvků z S, které jsou svazovým homomorfismem F zobrazeny na nulu svazu A — tj. množina dFO —, se nazývá dolní jádro svazového homomorfis-mu F. Množina všech prvků z S, které jsou svazovým homomorfismem F zobrazeny na jednotku svazu A— tj.množina nFÍ —, se nazývá horní jádro homomoďismuf
Příklad 4.16. Uvažujme svazy S a A znázorněné na obr. 36. Definujeme-li zobrazení F: A takto: F(0) = F{a) = F(b) = F{c) = 0, F{d) = F{e) = /. F(f) = k, F(g) = F(l) = 1, pak zobrazení F je svazový homomorfismus S na
.4. Prvky dolního jádi že zobrazení F je tak<
Příklad 4.17. V čfc
F:[x.y]eA
zavedli zobrazení svx homomorfisnms .4 x zení.4 x i?na.4.LTa jsou hbovotoé poty.
4.7. \ecMF
Obr. 36
104
Mtíkovi se podařilo navíc : ■ na konečné
•odrobnéji zabývat mazů. Nejprve to budou D otázku řešit u konečných
:
zavedli relaci „být
A', který je podsvazem S,nebo že svaz A je
Kzi pok>> :.z\. popř. mezi :•- : - -   bdobně, jako je lýthomomorfní'. Vyslovme
Tf.pak říkáme, že svaz A je hrazení F: S S A, které za-6) a (4.16). Zobrazení F se n^momorfismus svazu S na
morfismem F zobrazeny na jro s-azo%eho homomorfis-wiomorfismem F zobrazeny >rni jádro homomorfismuF.
na obr. 36. Definujeme-li F*c) = 0. F\d) = F{e) = l, rri homomorfismus S na
A. Prvky dolního jádra a horního jádra jsou vyznačeny plnými kroužky. Je vidět, že zobrazení F je také posetovým homomorfismem S na A.
Příklad 4.17. V článku 4.4 o direktních součinech svazů jsme formulí
F: [x, y] e A x B >-* x e A
zavedli zobrazení svazu A x B na svaz A. Dokažme, že toto zobrazení je svazový homomorfismus A x B na A. Přímo z definice zobrazení F vyplývá, že F je zobrazení A x B na A. Ukažme, že zobrazení F splňuje formuli 4.16. Nechť [x, y] a [u, v] jsou libovolné prvky z A x B, pak
F([x, y] n [u, v]) = F([x n u, y n v]) = x n u = F([x, y]) n F([u, v]).
Duálně lze dokázat formuli 4.16'. Proto je F svazový homomorfismus A x B na A. Zobrazení F také zachovává uspořádání, neboť když [x, y] ^ [u, v], pak x sa u, což znamená F([x, y]) ^ F([u, v]). Zobrazení F je proto i posetovým homomorfismem A x B na A.
Obdobně je i zobrazení G (viz formule (4.15)) jak svazovým, tak i posetovým homomorfismem A x B na B.
Příklad 4.18. Uvažujme řetězec racionálních čísel a dále dvouprvkový řetězec 2 =* {ÔTl}- Nechť r je určité reálné číslo, pak svazový homomorfismus F svazu Q na svaz 2 určíme takto:
(Vjc e Q) (x á r => F(x) = 0) a (x > r => F(x) = l)
Je zřejmé, že zobrazení F splňuje všechny podmínky vyslovené v definici 4.13. Zobrazení F také zachovává uspořádání, tzn. je posetovým homomorfismem Q na 2.
Poznámka. Pro každé reálné číslo můžeme definovat homomorfní zobrazení zavedené v příkladě 4.18. Můžeme však také obráceně pomocí takovýchto homomorfních zobrazení svazu (Q, s) na svaz 2 definovat reálná čísla. Tímto způsobem obdržíme známou konstrukci reálných čísel pomocí Dedekindových řezů. O Dedekindových řezech jsme hovořili už na konci či. 3.4.
Nyní porovnáme nad třídou svazů definici posetového homomorfismu a definici svazového homomorfismu. Motivovat nás mohou příklady 4.16 až 4.18, v nichž jsme ukázali, že každý svazový homomorfismus byl i posetovým homomorfismem. Část odpovědi dává následující věta.
Věta 4.7. Nechť F je svazový homomorfismus svazu S na svaz A, pak F je také posetový homomorfismus S na A, tzn.
(Vx, y e S) x :s y =s- F(x) á F(y).
(4.18)
Důkaz věty 4.7 je zcela stejný jako předložená část důkazu věty 4.5, neboť jsme se při jeho konstrukci nikde neodvolávali na to, že zobrazení F je prosté.
105
Obrácení věty 4.7 však neplatí, jak ukazuje následující příklad.
Příklad 4.19. Uvažujme svaz P(M), kde M = {a, b, c] a svaz 4 (viz obr. 37), pak zobrazení F, které každé množině z P(M) přiřazuje počet jejích prvků, tzn.
F:X eP(M)~cardX e4,
je posetový, nikoli však svazový homomorfismus P(M) na 4. Platí např.:
ve svazu P(M)......{a} u {b} = {a, b}
zobrazení F | |
ve svazu 4........1 u 1 -la nikoli 2
Obr. 37
Věta 4.7 a příklad 4.19 ukazují, že definice svazového homomorfismu obsahuje zesílení podmínek z definice posetového homomorfismu. Vyslovme proto úmluvu, že pod pojmem homomorfismus mezi svazy budeme zásadně rozumět svazový homomorfismus.
Věta 4.7 ukázala, že homomorfní zobrazení F svazu 5 na svaz A zachovává uspořádám. Na základě této věty však víme, že homomorfismus F zachovává i nulu a jednotku. Zopakujme, že tím myslíme toto: Jestliže má svaz 5 nulu (jednotku) a svaz A je jeho homomorfním obrazem v homomorfismu F, pak má nulu (jednotku) i svaz A a platí F(ú) = 0', kde 0 e S a 0' e A (F(\) = ľ, kde 1 e S a ľ e A). Pozor! Pokud má nulu (jednotku) svaz A a je homomorfním obrazem svazu S, pak nemusí mít nulu (jednotku) svaz S — viz př. 4.22. Poznamenejme, že pokud M c 5 a existují sup M a sup F(M), pak nemusí platit F(sup M) = = sup F(M). Příklad: S = [0, l], M = [0, l) a A = 2. Definujme homomorfismus F: S 25 A takto: F(x) = 0 pro x e M a F(í) = 1. Pak sup M = 1 a f(sup M) = 1. zatímco sup F(M) = 0. Důkaz následujících lemmat přenecháme do cvičení.
Lemma 4.13 (a 4.13'). Nechť svaz A je homomorfním obrazem svazu S, pak splňuje-li svaz S podmínku klesajících (rostoucích) řetězců, splňuje tuto podmínku i svaz A.
106
poklad.
i sraz 4 (viz obr. 37), pak t jcýícfa prvků, tzn.
i4. Platí napi.:
Příklady 4.16 až 4.18 ukázaly, že homomorfní zobrazení F svazu 5 na svaz A nezachovává relaci ostrého uspořádání ani relaci pokrývání, ani relaci neporovnatelnosti. Je však možné pro něj dokázat např. následující slabší formuli:
(Vx, y e S) x <i y =* F(x) =a f (y)
Na konci tohoto článku se budeme zabývat vztahem mezi homomorfismy svazu S a ideály, popř. duálně filtry ve svazu S. Uvidíme, že zde neplatí úplná analogie s teorií grup. Nejprve však ve formě poznámky zopakujme situaci v teorii grup.
'homomorfismu obsahuje él Vyslovme proto úmlu-: i^jr.é rozumět svazový
l 5 na svaz A zachovává —. :rf:-:~u> F zachovává ~-   az S nulu (jednot-Kxfismu F, pak má nulu A {F\l)= V, kde 1 e5
- ~ — <nním obrazem
- 22 P?znamenejme, že nosí platit F(sup M) = ' ' '. ho momorfismus ' • 1 a / sup .V/) = 1, : ..   . ••. do cvičení.
m obrazem svazu S, pak ni. splňuje tuto podmín-
Poznámka. Z teorie grup víme, že každému homomorfnímu obrazu grupy G odpovídá právě jedna normální podgrupa H grupy G, která je jádrem tohoto homomorfismu. Platí však i obráceně, že každé normální podgrupč H grupy G odpovídá (až na izomorfismus) právě jeden homomorfní obraz grupy G — tím je např. faktorová grupa grupy G podle podgrupy H značená G/ ff. Uvědomme si, že různým normálním podgrupám grupy G mohou odpovídat homomorfní obrazy grupy G, které jsou navzájem izomorfní. Proto můžeme populárně říci, že grupa G má nejvýše tolik homomorfních obrazů (až na izomorfismus). kolik má normálních podgrup.
Příklad. Uvažujme Kleinovu grupu K všech shodných zobrazení zachovávajících daný obdélník. Jde o čtyřprvkovou grupu obsahující identitu i, osové souměrnosti o,, o, a středovou souměr-
nost s. Normálními podgrupami grupy K jsou {i}, {i, o,}, {í, o grupy K jsou však (až na izomorfismus) pouze tri, neboť grupy {/, oh obrazům.
, {i, s], K. Homomorfní obrazy {i, o2! a {/, s) vedou k izomorfním
Věta 4.8. Nechť svaz A s nulou je homomorfriím obrazem svazu S v homomorfismu F, pak dolním jádrem homomorfismu F je ideál ve svazu S.
Důkaz. Dokážeme, že množina / = aFO splňuje a) formuli (4.7), b) formuli (4.8). Nechť x, y jsou libovolné prvky z S, pak
a) 1. x e I a ye / Předpoklad
2. F(x) = 0 a F(y) = 0 Podle def. I na ř. 1.
3. F{x u y) = F(x) u F(y) = 0 lj 0 = 0        Podle def. 4.13 a (4.3')-x t_i y e /
b) l.xelAy^x
2. F(y) a F[x) - 0
3. F(y) = 0 yel
Podle def. / na ř. 3. Předpoklad
Podle (4.18) a def. /na ř. 1. Podle L 3.2 na ř. 2. Podle def. / na ř. 3.
Věta 4.8'. Nechť svaz A s jednotkou je homomorfním obrazem svazu S v homomorfismu F, pak horním jádrem homomorfismu F je filtr ve svazu S.
Jestliže svaz A nemá nulu, pak dolním jádrem homomorfismu F svazu S na A je množina 0, jestliže svaz A má nulu, pak dolním jádrem je ideál. Každému homomorfismu F s definičním oborem S je proto přiřazen nějaký ideál v S nebo prázdná
107
množina. V příkladě 4.23 ukážeme, že ne každý ideál ve svazu S může být dolním jádrem nějakého homomorfismu. Duálně je tomu pro filtry.
4.6      Svazové kongruence
Svazové kongruence jsou zvláštní ekvivalence, které se chovají vhodně k operacím n a V tomto článku ukážeme jejich velmi blízký vztah k homomor-fismům svazů. Situace je analogická se situací v teorii grup. Připomeňme nejprve obdobnou problematiku v grupách.
Poznámka o grupách
Definice. Ncchf{G, ■) je grupa, pak ekvivalence K v C se nazývá kongruence v G, právě když platí:
(Vjc,y,zí G)xKy^x.zKy.z\z.xKz.y
Kongruenci obvykle značíme symbolem = a místo formule xKy píšeme x = y (mod K) (čteme: x je kongruentní s y modulo K) nebo stručně x = y.
Jestliže je dána grupa G a kongruence K v G, pak lze sestrojit faktorovou grupu G/K. jejímž nosičem je rozklad grupy G indukovaný kongruenci K a v níž je operace násobení definovaná takto (T,, Ty značí bloky rozkladu G/K obsahující prvky x,y): i. ■ 1. -* 1...
Faktorová grupa G/K je homomorfním obrazem grupy G v homomorfismu F:íe G« 7, e G/K.
Tento homomorfismus nazýváme přirozeným homomorfismem G na G/K. Každé kongruenci v G tak odpovídá nějaký homomorfní obraz grupy G.
Lze dokázat, že kromě faktorových grup G/K žádné jiné homomorfní obrazy grupy G (až na izomorfismus) neexistují. To se obvykle vyjadřuje takto (základní věta o homomorfismu grup):
Nechť grupa H je homomorfní obraz grupy G v homomorfismu F, pak existuje taková kongruence K v G, že faktorová grupa G/K je izomorfní s grupou H,
Konstrukci hledané kongruence K popisuje následující formule:
(Vx, y e G) x s y(mod K) » F(x) = Fiy)
Každému homomorfismu F s definičním oborem G tak odpovídá právě jedna kongruence K v grupě G.
Uvědomme si, že různým kongruencím v G mohou odpovídat homomorfní obrazy grupy G, které jsou navzájem izomorfní. Proto lze populárně říci, že grupa G má nejvýše tolik homomorfních obrazů (až na izomorfismus), kolik má kongruenci.
Definice 4.14. Nechť S je svaz, pak ekvivalence K v S se nazývá svazová kongruence v S, právě když
(Vx, y, z s S) xKy => (x n z K y n z a x u z K y u z). (4.19)
Kongruenci obvykle značíme symbolem = a místo formule xKy píšeme x = y (mod K) (čteme: x je kongruentní s y modulo K) nebo pouze stručně x = y.
108
Příklad 4.20. Uvažujme svaz S, jehož Hasseův diagram je znázorněn na obr. 38. Na obr. 38a je vyznačen rozklad množiny S odpovídající kongruenci v S (ověřte formuli (4.19)), zatímco na obr. 38b je vyznačen rozklad odpovídající ekvivalenci E, která není kongruenci v S. Platí např. a E b, ale neplatí a u c E b u c, neboť prvky auc = f, buc = c leží v různých blocích rozkladu S/E.
Obr. 3X
Protože v celém následujícím textu budeme hovořit zásadně o svazových kon-gruencích, budeme přívlastek „svazová" vynechávat.
Věta 4.9. Nechť (S, n, u) je svaz a K je kongruence v S, pak definujeme-li na faktorové množině S/K operace n a u následujícím způsobem (Txa TJsou libovolné bloky z S/K obsahující prvky x a y)
Tx n Ty = Tx n y     a      Tx u Ty = Tx u y,
je trojice {S/K, n, u) 5ťflz.
Důkaz. Dokážeme a) nezávislost definice průseku na volbě reprezentantů, b) formuli (4. l), c) formuli (4.2), d) formuli (4.3), e) formuli (4.6). Důkazy pro operaci u jsou duální. Nechť Tx, Ty, T:, Tn jsou libovolné bloky z S/K, pak:
d)Tx= T. aty=Tu=>x = ZAy=u^xny=zr-\yAynz=unz^>xny =
= Zn U^ Txr,y= T:r,u
b) Tx n Ty = Txny = TynX= Ty n Tx
c) (tx n rv) n tz = r(rn>.)riz = rín^nz) = tx n (rvn T.)
d) T^n T^= rínJ. = Tx
e) r,n (txu rr) = r,...ív,,, = tx
Na základě věty 4.9 můžeme vyslovit následující definici.
Definice 4.15. NechťS je svaz a K je kongruence v S, pak svaz sestrojený podle věty 4.9 se nazývá faktorový svaz svazu S podle kongruence K.
109
Věta 4.10. Nechť (S, n, u) je svaz a K je kongruence v S, pak faktorový svaz {S/K, n, lj) je jeho homomorfním obrazem.
Důkaz. Omezíme se pouze na konstatování, že homomorfismem je zobrazení
F: x e S - Tx e S/K.
Tento homomorfismus se nazývá přirozený homomorfismus svazu S na svaz S/K.
Věta 4.10 říká, že každý faktorový svaz svazu S podle kongruence K je homomorfním obrazem svazu S. Následující věta ukáže, že až na izomorfismus žádné jiné homomorfní obrazy svazu S neexistují. Této větě se ve spojem s větou 4.10 říká základní věta o homomorfismu svazů.
Věta 4.11. Nechť svaz A je homomorfním obrazem svazu S v homomorfismu F, pak existuje takový faktorový svaz S/K, že svaz A je izomorfní se svazem S/K.
Důkaz. Ve větě 4.11 se vlastně tvrdí, že v S existuje kongruence K taková, že svaz S/K je izomorfní s A. Omezíme se zde pouze na uvedení formule popisující kongruenci K:
(Vx, y e S) x = y(mod K) <=> F(x) = F{y)
Izomorfismem svazu S/K na svaz A je následující zobrazení G:
G: Tx e S/K ~ F(x) e A
Uvědomme si, že dvěma různým kongruencím v S mohou odpovídat homo-morfní obrazy svazu S, které jsou navzájem izomorfní. Proto můžeme na základě vět 4.10 a 4.11 říci, že svaz S má nejvýše tolik homomorfních obrazů (až na izomorfismus), kolik má kongruenci. Situace je zde zcela analogická jako v teorii grup.
Příklad 4.21. V příkladě 4.20 jsme uvedli svaz S, jehož jedna kongruence K (přesněji rozklad indukovaný touto kongruenci) je vyznačena na obr. 38a. Faktorový svaz S/K je dvouprvkový. Označíme-li jeho prvky 0, 1, pak přirozený homomorfismus F svazu S na svaz S/K je vyznačen na obr. 39.
S/K
Obr. 39
110
Příklad 4.22. Uvažujme svaz (M, n, u), kde M = [O,4) x [O, 3), který je podsva-zem svazu 5 z příkladu 4.2. Ve svazu M definujme kongruenci K takto ([x, y], [u, v] jsou libovolné uspořádané dvojice z A/):
[x, y] = [h, d] (mod K) <** [x] = [u] a [v] = [»],
kde [x] značí celou část reálného čísla x, tj. největší celé číslo n takové, že n S x. Ověření, že /v je kongruence přenecháme do cvičení. Sestrojíme faktorový svaz M/K. Prvky tohoto svazu jsou polouzavřené čtverce (např. G) na obr. 40a. Označí-me-li tyto čtverce písmeny A, B, C atd., jak je vyznačeno na obrázku, pak Hasseův diagram svazu MjK je znázorněn na obr. 40b. Nulou tohoto svazu je prvek (polou-zavřený čtverec) A a jednotkou je prvek L. Faktorový svaz M/K je homomorfním obrazem svazu M v přirozeném homomorfismu
F:[x,y]eM~T[x!y]eM/K.
V grafickém podání to znamená, že zobrazení F přiřazuje každému bodu polouza-vřeného obdélníku XYZU (kde X = [0, 0], Y = [4, 0], Z - [4, 3] a U - [0, 3]) polouzavřený čtverec, v němž tento bod leží.
Dodejme ještě, že dolním jádrem homomorfismu F je množina dFA, tj. na obr. 40a množina všech bodů polouzavřeného čtverce A. Tato množina tvoří ideál ve svazu M, který není hlavní. Horním jádrem homomorfismu F je množina dFL, tj. množina všech bodů polouzavřeného čtverce L. Tato množina tvoří hlavní filtr ve svazu S.
Obr. 40
Uvažovaný příklad ukazuje ještě tuto zajímavou skutečnost: Svaz M/K je homomorfním obrazem svazu M a přitom svaz M/K má jednotku. Touto jednotkou je polouzavřený čtverec L. Svaz M však jednotku nemá.
V závěru článku 4.5 jsme upozorňovali na to, že mezi homomorfními obrazy svazu S a ideály ve svazu S neexistuje vzájemně jednoznačné zobrazení. Nyní
111
ukážeme příklad ideálu v S, kterému neodpovídá žádný homomorfismus, tzn. který není dolním jádrem žádného homomorfismu s definičním oborem v S.
Příklad 4.23. Uvažujme svaz 5 znázorněný na obr. 41. Množina / = {0, c, d, e) tvoří ideál tohoto svazu. Ukažme, že / nemůže být dolním jádrem žádného homomorfismu. Pokud by tento ideál byl jádrem nějakého homomorfismu, pak by podle věty 4.11 musela ve svazu S existovat kongruence K taková, že prvky 0, c, d, e tvoří právě jeden blok navzájem kongruentmch prvků. Do tohoto bloku by však musely patřit i prvky a, b, 1, neboť:
d = Q/\a = a^ 1 = ái_jfl = 0i_jfl = a (4.20) d = 0Ab = b^l=d^b = 0Ljb = b (4.2l) a=lAĎsô=»fe = Ŕnls6na = 0 (4.22)
Formule (4.22) říká, že b = 0. Na základě tranzitivnosti relace K obdržíme z formulí (4.20) a (4.21), že i 1 = 0 a a = 0. Blok navzájem kongruentních prvků obsahující prvky 0, c, d, e musí proto obsahovat i prvky a, bal. Množina 5 je proto zřejmě minimální ideál tvořící jádro nějakého homomorfismu a obsahující množinu /.
1
0
Obr. 41
Poznámka. Analogiemi mezi teorií grup a teorií svazů, o nichž jsme hovořili v této kapitole, jakož i analogiemi s ostatními algebraickými strukturami se zabývá teorie abstraktních (univerzálních) algeber. Více se o ní čtenář doví např. v knize [22].
CVIČENÍ 4
1 Dokažte, že požadavky idempotence v definici 4.2 jsou nadbytečné.
2 Dokažte, že algebraická struktura (S, n, u) z příkladu 4.2 je svaz.
3 Definujte relaci „být podpolosvazem" a) v průsekových, b) ve spojových polo-svazech. Demonstrujte definice na příkladech.
4 Dokažte, že v př. 4.3 jsou skutečně uváděny podsvazy daných svazů.
112
5 Udejte svaz S a v tomto svazu takové otevřené, popř. polouzavřené intervaly, které a) tvoří, b) netvoří podsvazy svazu S.
6 Dokažte lemma 4.1.
7 Definujte ideál ve spojovém polosvazu a filtr v průsekovém polosvazu. Demonstrujte definice na příkladech.
8 Dokažte lemmata 4.4 a 4.5 a vyslovte k nim lemmata duální.
9 Uvažujte následující svazy: (N, ž),(N, á),(R, á),(N, |) a P({a, b, c}). V každém z těchto svazů určete alespoň tři ideály a uveďte, zda se jedná o hlavní ideály, prvoideály či maximální ideály. Obdobně pro filtry.
10 Nechť a je určitý prvek svazu S a / je ideál v S, pak množina všech prvků x 21 a u c, kde c je libovolný prvek z /, je nejmenší ideál obsahující prvek a a ideál /, tj. ideál generovaný množinou {a} u I. Dokažte. Formulujte duální větu pro filtry.
11 Formulujte příklad 4.10 pro filtry.
12 Definujte direktní součin posetu (A, 21) a (B, 21) tak, aby ve speciálním případě zahrnoval direktní součin polosvazu a svazů. Uveďte příklady pomocí Hasseových diagramů.
13 Načrtněte Hasseovy diagramy všech navzájem neizomorfních svazů pro šesti-prvkovou množinu.
14 Dokažte, že zobrazení F z příkladu 4.13 i z příkladu 4.14 jsou svazové izo-morfismy uvažovaných svazů.
15 Sestrojte kompletní důkaz věty 4.5.
16 Dokažte lemmata 4.13 a 4.13'.
17 Sestrojte jiný svazový homomorfismus svazů S a A znázorněných na obr. 36.
18 Dokažte větu 4.10.
19 Dokažte, že relace K v příkladu 4.22 je kongruence.
20 Určete (až na izomorfismus) všechny homomorfní obrazy svazů P({a}), P({a, b}) a P({a, b, c}). Použijte Hasseovy diagramy.
21 Nechť K je libovolná kongruence ve svazu S, pak platí (V*, yeS)x = y^xny=XLj y(mod K).
Dokažte.
113
5    MODULÁRNÍ SVAZY
Některé důležité svazy splňují vedle identit obsažených v algebraické definici svazu a samozřejmě i všech formulí, které se z nich dají dokázat, ještě některé další. Mezi těmito speciálními druhy svazů jsou nejdůležitější modulární a distributivní svazy. V této kapitole se budeme zabývat modulárními svazy a v následující kapitole distributivními svazy, které jsou jejich zvláštním případem. Modulární svazy dostáváme např. při studiu některých systémů podstruktur dané algebraické struktury a hrají důležitou roli i při studiu projektivních prostorů.
5.1       Definice a vlastnosti
V tomto článku ukážeme různé způsoby definování modulárních svazů. Nejprve podáme nejběžnější definici.
Definice 5.1. Svaz S se nazývá modulární nebo Dedekindův, právě když platí:
Poznamenejme, že formule (5.1) je autoduální. Podle věty 2.9 platí v každém svazu modulární nerovnost. Modulární rovnost (5.1) však platí pouze v některých svazech. Příkladem svazu, v němž neplatí modulární rovnost (5.1), je pentagon N5, o kterém jsme hovořili v příkladu 2.14 a který je znázorněn na obr. 22a. Později ukážeme (viz věta 5.2), že právě výskyt podsvazu typu pentagon je pro nemodulár-nost daného svazu charakteristická. Zdůvodnění důležitosti studia modulárních svazů se opírá především o následující tvrzení.
Lemma 5.1. Množina všech normálních podgrup dané grupy G tvoří modulární svaz.
Důkaz. Nechť Hl, H2 jsou normální podgrupy grupy G, pak zopakujme, že svazové operace průsek a spojení grup H}, H2 definujeme takto:
H y n H2 =df H y n H2 Hi u H2 =df[Hl u H2]
Grupa [Hy u H2] je nejmenšípodgrupa v G obsahující množinu í/, u /í2aobdrží-
(Vx, y, z s S) x ^ z => x i_i (y n z) = (x u y) n z
114
me ji jako množinu součinů každého prvku z H{ s každým prvkem z H2 — proto ji obvykle označujeme H{ . H2, tzn.
H1. H2 - {xe G; (3A, e //,) (3Ä2 eH2)x = hl. h2}.
Protože modulární nerovnost (2.23) platí v libovolném svazu, stačí při dokazování modulární rovnosti (5.1) dokázat formuli
(Vx, y, z e S) x ^ z   (x u y) n z ^ x u (y n z), (5.2)
což v našem případě znamená (Ht, H2, H3 jsou libovolné normální podgrupy v grupě G):
H, c H3 => (//, . H2) n ií3 e //, . (H2 n ff3)
A nyní již k vlastnímu důkazu: Nechť x je libovolný prvek z množiny {Hx . H2) n H3, pak x e H1 . H2, tzn. x = h] . h2, kde hx e Hl & h2 e H2 a současně ieí/j. Na základě pravidel o počítání v grupách víme, že h2 = . x, přičemž hi1 e H1 c, H3ax e H3 — proto také h2 e H3. Protože prvek h2 byl vybrán z množiny H2, musí pro něj platit h2eH2nH3. Protože x = h1.h2, platí x e Hl . (H2 n H3). Tím důkaz končí.
Příklady 5.1. Jednoduchým příkladem demonstrujícím lemma 5.1 je svaz všech normálních podgrup symetrické grupy S3 (viz př. 2.1 1 a obr. 19b).
Modulárním svazem je také svaz všech normálních podgrup Kleinovy grupy K (grupa všech symetrií obdélníku — viz poznámka str. 107). Uvažovaný modulární svaz má pět prvků a je jím diamant M5.
Nekomutativní grupa G všech symetrií čtverce má osm prvků: identitu, čtyři osové souměrnosti, středovou souměrnost a dvě otáčení. Svaz S všech podgrup grupy G má deset prvků a není modulární (viz obr. 42). Podsvazem svazu S je šestiprvkový svaz všech normálních podgrup grupy G, který je modulární (viz černé uzly na obr. 42).
Obr. 42
Je zřejmé, že platí-li formule (5.1) v nějakém svazu, pak musí platit i v jeho libovolném podsvazu — vlastnost „být modulární" je dědičná.
115
Lemma 5.2. Každý podsvaz modulárního svazu je modulární svaz.
Také lze říci, že pokud je daný svaz M modulární, pak i jeho libovolný izomorfní obraz je modulární svaz. Vlastnost „být modulární" se dokonce zachovává i homomorfním zobrazením (viz cv. 5.5). Proto můžeme vyslovit:
Lemma 5.3. Nechť F je svazový homomorfismus modulárního svazu S na svaz A, pak svaz A je také modulární.
Prohloubení představy o modulárních svazech umožní následující věta.
Věta 5.1. Svaz S je modulární, právě když platí:
(Vjc, y, z^S)(x^yAXnz = ynZAXuiz = yuz)^X" y (5.3)
Důkaz. V první části dokážeme, že pokud je svaz S modulární, pak pro něj platí formule (5.3), v druhé části dokážeme opačnou implikaci.*)
I. Nechť S je modulární svaz a nechť x, y, z jsou libovolné tři prvky z S, pro něž platí:
l.ISjíAJtnZ-JnZA JCuZ=yuZ
2. x = x u (x n z) =
3. = x u (y n z) = x u (z n y) =
4. = (x u z) n y = (y u z) n y =
-y
Předpoklady Podle (4.6').
Podle předpokladů a (4.1). Podle (5.1) a předpokladů. Podle (4.1) a (4.6).
II. Nechť neplatí, že svaz S je modulární, tzn. existují alespoň tři prvky x,y, z s 5, pro něž platí:
1. x :2 Z A x i_i (y n z) o (x u y) n Z
í. a = x i
(y n z)
3. Z) = (x u y) n z
4. c = y
5. a < &
6. CuflSCu/)
7. c u a = y u [x u (y n z)] =
8. = (y i_i x) u (y n z) = = x u [y u (y n z)] =
9. = x u y
10. c u Ŕ = y u [(x u y) n z] s
11. ^ [y lj (x u y)] n (y u z) =
12. = (y lj x) n (y lj z)
13. c lj Ŕ :ä x lj y
Předpoklady
Konstrukce prvku a.
Konstrukce prvku
Konstrukce prvku c.
Podle konstrukce a ř. 1.
Podle def. 1.7, (2.21'), (4.1') na ř. 5.
Podle konstrukce c, a.
Podle (4.2'), (4.1').
Podle (4.6').
Podle konstrukce c, b.
Podle (4.1'), (2.22').
Podle (4.1'), (4.2'), (4.3').
Podle (4.1'), (2.13) na ř. 10 a 12.
14. Ctjb:
15. c lj a ■■
16. c n a a «= ŕ
V části II. neplatí ani f o: posledním
Ve větě 5. by bylo mežr.č důsledkem vět s formulí (5.1 & modulámih:
Věta 5.2.
Důkaz. L žádný podsva matu 5.2 je i a proto nem
H. K důkaz pouze toto: N formule (53)
Prvky m.b.c — víz ohr. 4
*) Místo formule qj =» ip však vezmeme její obměnu. IV => -i?>, která je s ní logicky ekvivalentní.
116
sraz.
■»Hwvolny izomorf-f dokonce zachovává
srazu S na svaz A,
■sledu
:ci veta.
= =: (5.3)
ir~   z ■: pro něj platí'
L
prvky z 5, pro něž
Idadů a (4.1). ľ'-Prokladů. [4.6).
m tři prvky x,y, z e 5,
rvku a. rvku rvku c. kce a ř. 1.
,<2_211(4.1')nař.5.
pa<4.3').
J3)nař. 10 a 12.
taí losickv ekvivalentní.
14. C u 6 < ^ u )'
15. Cufl = Cuř)
16. c n a = C n b a o b a a n c
f u fl
Z ř. 13, 9, 7. Podle (2.2) na ř. 6, 14. Duálně jako ŕ. 15. b n c a a u c = ib u c Konjunkce ŕ. 5, 16, 15.
V části II. jsme dokázali, že pokud neplatí formule (5.1) — viz řádek L, pak neplatí ani formule (5.3), neboť existují prvky a, b, c e S takové, že platí formule na posledním řádku důkazu.
Ve větě 5.1 jsme dokázali, že formule (5.3) je ekvivalentní s formulí (5.1). Proto by bylo možné modulární svazy pomocí formule (5.3) definovat. Velmi zajímavým důsledkem věty 5.1 je následující věta, která udává další podmínku ekvivalentní s formulí (5.1). O této podmínce jsme se zmiňovali hned po vyslovení definice 5.1 modulárního svazu.
Věta 5.2. Svaz S je modulární, právě když neobsahuje podsvaz typu pentagon.
Důkaz. I. Dokažme, že pokud je svaz M modulární, pak nemůže obsahovat žádný podsvaz typu pentagon. Jestliže je tedy svaz M modulární, pak podle lemmatu 5.2 je i každý jeho podsvaz modulární. Pentagon však modulární není, a proto nem podsvazem M.
II. K důkazu obrácené implikace (viz poznámka pod čárou na str. 116) řekněme pouze toto: Nechť svaz M není modulární, pak to znamená, že ve svazu M podle formule (5.3) existují prvky a, b, c takové, že
a -a b a a n c
nCAfluC = í)uC.
Prvky a, b, c spolu s prvky a n c a a u c určují pětiprvkový svaz typu pentagon — viz obr. 43.
Na základě věty 5.2 bychom mohli vyslovit už třetí definici modulárního svazu, která by byla s předchozími dvěma ekvivalentní.
Příklady 5.2. Na obr. 44a, b, c jsou znázorněny Hasseovy diagramy tří různých nemodulárních svazů. V každém z nich lze totiž nalézt alespoň jeden podsvaz typu pentagon. Jeden z možných pentagonů je vždy vyznačen plnými kroužky. Svaz
117
znázorněný na obr. 44d je modulární, protože v něm žádný podsvaz typu pentagon neexistuje.
q) b) c) d)
Obr. 44
V příkladě 7.4 je uveden nemodulární svaz 5. Zdůvodnění, že tento svaz obsahuje pentagon, je podáno v poznámce na str. 137.
Na závěr tohoto článku znovu zdůrazněme, že řadu zajímavých modulárních svazů z oblasti algebry obdržíme studiem některých systémů podstruktur dané struktury — např. svazu všech normálních podgrup grupy G (viz lemma 5.1) nebo analogicky svazu všech okruhových ideálů v okruhu M. Také pro libovolný okruh M tvoří všechny M-podmoduly libovolného M-modulu G modulární svaz.
5.2      Další vlastnosti modulárních svazů
Článek je sestaven tak, aby se v jeho závěru ukázala platnost tzv. Jordánovy—Holderovy věty pro modulární svazy. Uvedená věta vlastně zobecňuje zakázanou situaci vyznačenou na obr. 43. Tato část teorie modulárních svazů je zcela analogická určité části teorie grup. Na zmíněnou analogii budeme čtenáře upozorňovat ve formě poznámek. Tyto poznámky však nejsou nutné pro studium předkládané teorie.
Začněme následující zajímavou vlastností modulárních svazů:
Věta 5.3. Nechť a, b jsou libovolné prvky modulárního svazu S, pak intervaly [a, a u b] a [a n b, b] jsou navzájem izomorfní.
Důkaz. Nechť x e [a, a u b], tzn. í)<i<úuŔ, Pak ale platí: anb^xnb^b (viz formule (2.2l), (4.1), (4.6)), a tedy prvek x n b je z intervalu [a n b, b]. Podobně, jestliže y e [a n b, b], pak y u a e [a, a u b]. Určili jsme tak dvě zobrazení mezi uvažovanými intervaly, a to (viz např. obr. 45):
F: x e [a, a u b] >-» x n b € [a n b, b] G: y e [a n b, b] <— y u a e [a, a u b]
Ukažme, že tato zobrazení jsou navzájem inverzní, takže každé z nich představuje
118
prosté zobrazení jednoho intervalu na druhý, které navíc zachovává uspořádání, a tedy i operace.
Nechť x s [a, au b], pak FoG(x) = (x n b) u a = x n (a u ŕ). Protože x :s a u fe, platí podle formule (2.19), že FoG(x) = x, a tedy foG je identické zobrazení intervalu [a, a u b] na sebe. Duálně: GoF(x) = x je identické zobrazení intervalu [a n 6, 6] na sebe. A protože F i G zachovávají uspořádání (viz formule (2.21) a (2.2 ľ)), je každé z nich svazovým izomorfismem uvažovaných intervalů.
Věta 5.3 nás povede k zavedení zvláštní ekvivalence mezi intervaly, přičemž tato ekvivalence bude „silnější" než izomorfismus.
Definice 5.2. Nechť S je modulární svaz, pak intervaly [a, a u b] a [a n b, b] se nazývají transponované nebo podobné. Intervaly [a, b], [c, d] se nazývají projektivní,
právě když existuje konečná posloupnost intervalů
taková, že každé dva za sebou jdoucí intervaly jsou transponované.
Protože každé dva transponované intervaly jsou navzájem izomorfní (viz věta 5.3), a protože relace „být izomorfní" je tranzitivní, jsou i každé dva projektivní intervaly navzájem izomorfní.
Přiklad 5.3. Uvažujme svaz S znázorněný na obr. 45, pak interval vyznačený plnými kroužky je s intervalem vyznačeným prázdnými kroužky navzájem transponovaný.
Uvažujme diamant znázorněný na obr. 46a. Je zřejmé, že intervaly [0, a] a [b, l] jsou transponované, neboť [0, a] = [a n b, a] a [b, l] = [b, a u b]. Obdobně jsou transponované i intervaly [b, l] a [0, cj. Intervaly [0, a] a [0, c] jsou proto projektivní, nejsou však transponované.
anb
Obr. 45
[a, b] = [u,,     [u2,v2],..., [u„,v„] = [c, d]
119
Čtyřprvkové intervaly [a, b], [c, d] ve svazu S znázorněném na obr. 46b jsou izomorfní, nejsou však projektivní.
Již od první kapitoly pracujeme s řetězci. Na dalších stránkách budeme v modulárních svazech uvažovat následující druhy řetězců
a = al ^ a2 23 ... s an + , = b, o nichž říkáme, že jsou neklesající a spojují prvky a, b. Mezi těmito řetězci se stejnými koncovými body zavedeme dvě binární relace.
Definice 5.3. Nechť S je modulární svaz a nechť
a = fl, 33 a2 =9 ... =3 fls+ | = 6 (5.4) a = fej aa £>2 s ... a bl + | = 6 (5.5)
/som í/ľa /e/io neklesající řetězce spojující prvky a, b,pak říkáme, že řetězec (5.5) je zjemněním řetězce (5.4), právě když každý člen řetězce (5.4) je členem řetězce (5.5). Dále říkáme, že řetězec (5.5) je ekvivalentní s řetězcem (5.4), právě když existuje prosté zobrazení množiny intervalů [at, ai+ J na množinu intervalů [bj, bj+ J řafco-ué, že odpovídající si intervaly jsou projektivní.
Poznámka o grupách. V teorii grup hrají roli neklesajících řetězců tzv. normální řady dané grupy, tj. řady typu
[lj - G, s G2s ... s G, + 1 - G,
kde G je daná grupa a G, jsou její podgrupy, přičemž každá grupa G, je normální podgrupou grupy G,+1. Roli intervalů zde přebírají faktorové grupy nebo stručně faktory G,+ ,/G, dané normální řady.
Říkáme, že jedna normální řada je zjemněním druhé normální řady, právě když první řada obsahuje všechny grupy, které se vyskytují v druhé řadě. Dvě normální řady se nazývají ekvivalentní, právě když existuje prosté zobrazení množiny faktorů jedné řady na množinu faktorů druhé řady takové, že odpovídající si faktory jsou izomorfní.
V teorii grup platí následující tzv. Schreierova věta o zjemnění normálních řad: Jakékoli dvě normální řady grupy C mají ekvivalentní zjemnění.
Vraťme se k modulárním svazům a vyslovme Schreierovu větu o zjemnění řetězců.
Věta 5.4. Nechť S je modulární svaz a a, b jsou dva jeho prvky, pro něž platí a :s b, pak jakékoli dva neklesající řetězce spojující a, b mají ekvivalentní zjemnění.
120
Místo kompletního důkazu pouze ukážeme, jak se z řetězců (5.4) a (5.5) spojujících prvky a, b modulárního svazu S získá jejich zjemnění. Sestrojme prvky aík a.bki podle těchto formulí:
aik - (a, u bk) n		i = 1, 2,...	,5, fc-1,2,	...,r + 1	(5.6)
bki = (a, u bk) n	6* + i,	£=1,2,...	,/, /=1,2,	...,s + 1	(5.7)
Pak následující řetězce					
a = au :2 al2 =s	...rsfl!.,	_ , = a21 :s a.	2=3... rg«5,+ l	= 6	(5.8)
a = bu ^ ft12 ^	- - hh		22 «3... <! ŕ, s f	, = 6	(5.9)
jsou zjemněním řetězců (	5.4) a (:	i. 5), přičemž	intervaly [ajVi,	««;*.+d a [&tó	, bk.<+\]
jsou navzájem projektivní. Zobrazení F určující ekvivalenci řetězců (5.8) a (5.9) je proto následující:
F- K k f H k +1] -* K í ,Ki + J (5 •1 °)
Ukažme právě popsanou konstrukci ekvivalentních zjemnění dvou řetězců daného modulárního svazu na konkrétním příkladě.
Příklad 5.4. Uvažujme modulární svaz 5 znázorněný na obr. 47a a dva jeho neklesající řetězce spojující prvky a, b:
a = a, ^ a2   a3 ^ a4 = b a = b] ^ b2 ^ b3 = b,
které jsou na obrázku vyznačeny prázdnými kroužky. Sestrojíme-li řetězec (5.8) prvků aik pomocí formule (5.6), obdržíme (na obr. 47b jsou „hrany" tohoto řetězce vytaženy silně):
a = au Sfl12^ fll3 = íj21 s a22 s a23 = % ^ a32 a a33 = ŕ
Obdobně obdržíme pomocí formule (5.7) řetězec (5.9) prvků bik (na obr. 47b jsou „hrany" tohoto řetězce vyznačené přerušovaně):
b = burs bn s bl3 ^ b14 = b2\ ^ b22 ^ b23 ^ b2i = b
Oba získané řetězce jsou zjemněním původních řetězců a navíc snadno pomocí obrázku 47b ověříme, že jsou ekvivalentní. Vypišme ještě dvojice navzájem projektivních intervalů [aik, aik+1] a [bki,bki+l], které si odpovídají v zobrazení (5.10):
[«n. «12]      [6,1, 612] [a22, a23]      [622, 623]
[«i2, «13]      [621,^22] [«31, «32] [613,614]
[«21, «22]      [6,2,613] [«32, «33]      [623,624]
121
Pro vyslovení hlavní vlastnosti modulárních svazů budeme ještě potřebovat pojem kompoziční řetězec (existence pro konečné posety viz L 1.4).
Definice 5.4. Nechť S je svaz, pak řetězec (5.4) tohoto svazu se nazývá kompoziční řetězec spojující prvky a, b, právě když každé a; + j pokrývá ař (ař + x je horní soused a) pro i = 1, 2,..., s. Číslo s se nazývá délka kompozičního řetězce.
Protože kompoziční řetězec již nelze prodloužit, je následující Jordánova—Hôlderova věta přímým důsledkem Schreierovy věty.
Věta 5.5. Nechť S je modulární svaz a nechť
a = al   a2 -* ... ~» an = b      a      a = b1 •* b2~* ■■■    bm = b
jsou dva kompoziční řetězce spojující prvky a,be M,pak m = na oba řetězce jsou ekvivalentní.
Příklady 5.5. V modulárním svazu znázorněném na obr. 48 lze např. sestrojit tři různé kompoziční řetězce spojující nulu a jednotku tohoto svazu. Všechny tyto řetězce mají délku 3 a jsou navzájem ekvivalentní. Odpovídající si dvojice navzájem projektivních intervalů jsou v obrázku označeny stejným písmenem.
Také v nemodulárním svazu znázorněném na obr. 44b lze libovolné dva body spojit pouze stejně dlouhými kompozičními řetězci. Např. existují dva různé kompoziční řetězce délky 3 spojující nulu a jednotku tohoto svazu.
Poznamenejme, že pro zjišťování nemodulárnosti daného svazu je často užitečná věta 5.5 v její obměněné formě: Jestliže mezi dvěma uzly svazu S existují kompoziční řetězce různé délky, pak svaz S nem modulární. Nejjednodušším příkladem takového svazu je právě pentagon (viz obr. 43).
122
Poznámka o grupách. V teorii grup zastávají roli kompozičních řetězců tzv. kompoziční řady definované takto:
Kompoziční řadou grupy G rozumíme normální řadu
{!}<= G1cC2C...c:GI+1 -G,
v níž je každá grupa G, maximální v grupě G, +,.
Normální grupa H se nazývá maximální v grupě G, právě když neexistuje žádná normální podgru-pa B grupy G taková, že H c: B <= G.
Jordánova—Hôlderova věta pro grupy pak zní takto: Libovolné dvě kompoziční řady grupy G jsou ekvivalentní.
1
Obr. 48
Zaveďme ještě následující pojmy.
Definice 5.5. Nechť S je modulární svaz s nulou a jednotkou, pak existuje-li kompoziční řetězec spojující tyto dva prvky, říkáme, že svaz 5 má konečnou délku. Délkou svazu S je pak délka této kompoziční řady.
Předpokládejme, že modulární svaz S s nulou a jednotkou má konečnou délku, pak pro každý prvek x e S lze sestrojit jeho počáteční interval (■*-, x\. Je to svaz, který opět splňuje vyjmenované požadavky kladené na svaz S. Označme jeho délku symbolem d(x). Také libovolný interval [x, y], kde x, y e S a x sa y, splňuje tyto požadavky. Délku intervalu [x, y] označíme d([x, y]). Nechť x, y jsou libovolné prvky z S, pro něž platí x s y, pak
d{y) = d(x) + d([x,y}).
Dále pro libovolné x, y e S platí:
d(x u y) = d(x) + d([x, x u y]) (5.11)
d{y) = d(xny) + d([x^y,y\) (5.12)
Protože intervaly [x, x u y] a [x n y, y] jsou izomorfní (viz věta 5.3), mají i stejnou délku. Proto lze z formulí (5.1l) a (5.12) obdržet formuli v následující větě.
123
Věta 5.6. Nechť S je modulární svaz konečné délky, pak pro libovolné dva prvky x,y e S platí:
d(x u y) = d(x) + d{y) -d(xny) (5.13)
Závěrečná poznámka. Dedekind objevil tento druh svazů při studiu modulů či přesněji při studiu struktury podmodulů daného modulu — odkud název modulárních svazů. V důležitých modulárních svazech algebry jsou prvky těchto svazů podstruktury určité algebraické struktury S. Operace n představuje množinový průnik; spojení podstruktur 5,, S2 struktury^ je podstruktura generovaná množinou 5, u S2 ■ Svazovým uspořádáním je relace „být podstrukturou". Teorie svazů a především modulárních svazů tak přispívá ke studiu výstavby složitých algebraických struktur z jejich významných podstruktur.
Na modulární svazy však často klademe další požadavky (např. komplementárnost — viz kap. 7), které splňují nejen některé výše uvedené algebraické svazy, ale např. i některé svazy z geometrie, v nichž se provádí protínání a spojování na bodech, přímkách, rovinách atd. S tím souvisí skutečnost, že v rámci teorie modulárních svazů můžeme např. axiomaticky založit tzv. projektivní geometrii roviny (viz poznámka na str. 139).
CVIČENÍ 5
1 Dokažte, že duální svaz k modulárnímu svazu S je modulární.
2 Dokažte, že direktním součinem modulárních svazů je modulární svaz.
3 Zdůvodněte, že svaz {a n c, a, b, c, a u c} uvedený v druhé části důkazu věty 5.2 je pentagon.
4 Dokažte, že svaz S je modulární, právě když platí: (Vje, y,z e 5 ) x u [y n (x u z)] = (x i_i y) n (x u z)
5 Využijte formuli z cvičení 4 k tomu, abyste dokázali, že homomorfním obrazem modulárního svazu je modulární svaz.
6 Uvažujme cyklickou grupu C řádu 60. Sestrojte Hasseův diagram modulárního svazu M všech podgrup grupy C. (Jestliže je a e C generátorem grupy C, pak generátory jednotlivých podgrup jsou prvky a1, a2, a3, a4, a5, ab, a10, a12, a15, a20, a3l,aa6(l.) '
7 Ve svazu M ze cvičení 6 sestrojte ekvivalentní zjemnění řetězců: 0 = [a™] q [a12] c [a] = 1
0 = [a60] s [a30] e [a3] = [a] = 1
8 Ve svazu M z cvičení 6 sestrojte alespoň tři kompoziční řady. Jakou délku má
svaz M?
9 Dokažte, že množina všech ideálů (filtrů) modulárního svazu S tvoří modulární svaz.
124
6    DISTRIBUTIVNÍ SVAZY
V této kapitole ukážeme, že distributivní svazy jsou speciálním případem modulárních svazů. Proto pro ně platí všechno, o čem jsme hovořili v předchozí kapitole. Z toho důvodu se v prvním článku zaměříme na ty vlastnosti, které jsou specifické právě pro distributivní svazy. V další části se budeme zabývat otázkou reprezentace konečných distributivních svazů. Ukážeme, že operace n a i_i v těchto svazech můžeme vždy „izomorfně nahradit" množinovým průnikem a množinovým sjednocením.
6.1      Definice a vlastnosti
Definice 6.1. Svaz .S se nazývá distributivní, právě když
(Vx, y, z e S) x u (y n z) = (jc u y) n (x u z) a (6.1) a jc n (y i_i z) = (x n y) i_i (x n z). (6.1')
Podle vět 2.8 a 2.8' platí v každém svazu distributivní nerovnosti (2.22) a (2.22'). Distributivní rovnosti (6.1) a (6.ľ) však platí pouze v některých svazech. Příkladem svazu, v němž neplatí distributivní rovnosti, je pentagon N5, o kterém jsme hovořili v příkladu 2.14 a který je znázorněn na obr. 22a. Tento svaz nebyl ani modulární. Dalším příkladem svazu, v němž neplatí distributivní rovnosti, je diamant M5, o kterém jsme hovořili také v příkladu 2.14 a který je znázorněn na obr. 22b. O svazu M5 víme, že je (na rozdíl od svazu N5) modulární. Později ukážeme, že právě výskyt podsvazů typu pentagon nebo diamant je pro nedistribu-tivnost svazů charakteristická.
Příklad 6.1. Uvažujme okruh množin P(M), který jsme zavedli v příkladě 2.7. Svazovými operacemi v P(M) jsou množinový průnik a množinové sjednocení. Víme, že pro libovolné tři množiny A, B, C platí:
A u {B n C) = (.4 u B) n (A u C) (6.2)
A n (B u C) = (A n B) u (A n C) (6.2')
Čtenář může formule (6.2) a (6.2') ověřit např. pomocí Vennových diagramů. Svaz P(M) je proto distributivní.
125
Uvažujme jiný druh okruhu množin než v předchozím příkladě. Nechť prvky tohoto okruhu jsou všechny konečné podmnožiny nekonečné množiny M, pak tento množinový okruh je opět distributivní svaz, neboť formule (6.2) a (6.2') zůstávají v platnosti. Zřejmě platí:
Věta 6.1. Každý okruh množin je distributivní svaz.
Následující věta ukáže, že jsme v definici 6.1 mohli požadovat platnost pouze jedné z formulí (6.1) a (6.1'), neboť druhá je již v takovém svazu dokazatelná.
Věta 6.2. Nechť S je svaz, pak formule (6.1) platí v tomto svazu, právě když v něm platí formule (6.1').
Důkaz. Ukážeme, že pokud ve svazu S předpokládáme platnost formule (6.1'), pak musí v S platit i formule (6.1). Nechť x, y, z jsou libovolné prvky svazu S, pak:
1. (x i_i y) n (x u z) = Pravá strana formule (6.1).
2. = [(x uy)ní]u [{x lj y) n z] = Podle (6.1').
3. = Jtu[zn(^uy)]= Podle (4.1) a (4.6).
4. = XLj[(znx)u(zrny)]= Podle (6.1').
5. = [íu(znx)]u(zn y) = Podle (4.2').
= xu(ynz) Podle (4.1) a (4.6').
Důkaz obrácené implikace je duální.
Mnoho příkladů distributivních svazů dostaneme na základě následující věty.
Věta 6.3. Každý řetězec S je distributivní svaz.
Důkaz. Nechť x, y, z jsou libovolné prvky řetězce 5, pak:
1. xnyzšXAXnyziy Podle (2.13).
2. x2ixuyAy2ixLjy Podle (2.13').
Pro vztah prvku x k prvkům y, z platí buď a) x ^ y v x 21 z, nebo b) (negace) y -a x a z -< x.
3. dL)x^yvxžiz=$xn(yuz) = x = (xny)i-j(xr\z) b))i<JtAZ<r=>rn()'uz)=)'uZ=(ín}')u(fnz)
Příklad 6.2. Podle věty 6.3 jsou distributivní např. svazy (N, š), (Z, á), (Q, á),
(R, á) a svazy k nim duální. Distributivním svazem je také např. řetězec {0^2, 4, 6, 1,3,5,7,...}.
Větu 6.3 využijeme také v následujícím příkladě.
126
Příklad 6.3. Nechť M je množina všech reálných funkcí definovaných na intervalu (0, l) — viz př. 1.14. Spojem a průsek definujeme v množině M takto [F, G jsou libovolné funkce z M, x je libovolný prvek z (0, l)):
(FnG)(r)=,f(x)nG(x) (6.3)
{FLjG)(x)=dfF{x)uG(x) (6.3')
Průseky a spojení funkčních hodnot znamenají v našem případě toto:
F{x) n G{x) = min {F{x), G{x))      a      F(x) u G{x) = max {F{x\ G{x)).
Pak trojice (M, u, n) je svaz. Ukažme, že M je dokonce distributivní svaz, tzn. že v něm platí formule (6.1). Nechť F, G, H jsou libovolné funkce z M. Položme U = Fu(Gnf7)aF = (fuG)n(Fu H). Nechť x je libovolné číslo z intervalu <0, 1>, pak:
1. U{x) = [F u (G n //)] (x) = Podle def. funkce U.
2. = F{x) lj [G(x) n //(*)] = Podle (6.3) a (6.3').
3. = (F(x) u G(x)) n {F(x) lj //(.r)) = Podle (6.1) — (R, á) je distribu-
tivní svaz.
4. = [(F lj G) n (F lj H)] {x) = Podle (6.3) a (6.3'). = V{x) Podle def. funkce V.
Právě uvedený příklad lze zobecnit takto:
Lemma 6.1. Necht M je množina všech zobrazení F: A — D, kde A je libovolná množina a D je distributivní svaz. Pak definujeme-li v M operace nau formulemi (6.3) a (6.3'), obdržíme distributivní svaz.
Důkaz je formálně zcela stejný jako důkaz v příkladu 6.3.
Nechť D je libovolný distributivní svaz, pak formule (6.1) a (6.1') lze rozšířit na libovolný konečný počet prvků. V případě úplných distributivních svazů lze tyto formule v některých případech rozšířit i na nekonečný počet prvků. K tomuto rozšíření se znovu vrátíme v kap. 8. Již na začátku předchozí kapitoly a znovu na začátku této kapitoly jsme čtenáře upozorňovali na následující větu.
Věta 6.4. Každý distributivní svaz je modulární.
Důkaz. Nechť x, y, z jsou libovolné prvky distributivního svazu S a nechť platí:
1. x ^ z Předpoklad
2. x u (y n z) = (x u y) n (x u z) = Podle (6.1).
= (iuy)nz Podle (2.19) a ř. 1.
Poznamenejme, že obrácení věty 6.4 neplatí, neboť existují svazy, které jsou modulární a nejsou distributivní. Nejjednodušší takový případ představuje diamant (viz obr. 35d).
127
Je zřejmé, že platř-li formule (6.1) v nějakém svazu, pak musí platit i v jeho libovolném podsvazu — vlastnost „být distributivní" je dědičná.
Lemma 6.2. Každý podsvaz distributivního svazu je distributivní svaz.
Také lze říci, že pokud je daný svaz S distributivní, pak i jeho libovolný izomorfní obraz je distributivní svaz. Vlastnost „být distributivní" se dokonce zachovává i homomorfním zobrazením. Proto můžeme vyslovit:
Lemma 6.3. Nechť F je svazový homomorfismus distributivního svazu S na svaz A, pak svaz A je také distributivní.
Prohloubení představy o distributivních svazech umožní následující lemma.
Lemma 6.4. Nechť S je distributivní svaz. pak platí:
(V.v. y. z s S) (x - : = y - z ■ x _ z = y _, z) => x = y (6.4)
Podle věty 6.4 je vlastnost ..byt distributivní" silnější než vlastnost „být modulární", a proto předpoklady v implikaci ,6.-1 mohou být slabší než předpoklady ve formuli (5.3i tykající se modulárních svazu.
Důkaz. Nechť .v. v. r jsou libovolné prvky distributivního svazu S, pro které platí:
1. x n z = y n z a x u z = y u z Předpoklady
2. x = x n (x lj z) = x n (v u :) = Podle 14.6) a předp.
3. =(jcnv)u(xnz)= ' Podle (6.1').
4. = (x n y) u (y n z) = Podle předpokladu.
5. = (y n x) u (y n z) = Podle (4.1).
6. = vn(jtuz)= Podle (6.ľ).
= y m (y □:) = y Podle předp. a (4.6).
Vyslovíme-li lemma 6.4 v obměněném tvaru, obdržíme: Jestliže ve svazu S neplatí formule (6.4), pak svaz 5 není distributivní. Vraťme se opět ke svazům typ^u pentagon a diamant, o nichž jsme hovořili už na začátku tohoto článku. Opět je dobře vidět, že ani jeden z nich není distributivní, neboť v pentagonu platí (viz obr. 22a):
ÍInC = í)nCAÍIuC-/)uCAa<í)
V diamantu platí (viz obr. 22b):
flnC = ĎnCAfluC = 6uCAa X b
Také obrácení lemmatu 6.4 je dokazatelné. Důkaz však nebudeme uvádět, neboť je poněkud zdlouhavý.
Lemma 6.5. Jestliže ve svazu S platí formule (6.4), pak S je distributivní svaz.
Na základě lemmat 6.4 a 6.5 můžeme vyslovit následující větu.
128
Věta 6.5. Svaz S je distributivní, právě když platí:
(Vx, y, ZE5)(xr-iz = ynZAXuz = yuz)=>x = y (6.4)
Formule (6.4) je autoduální a podle věty 6.5 je ekvivalentní s každou z formulí (6.1) a (6.1'). Proto bychom ji mohli použít k definici distributivního svazu. Důsledkem věty 6.5 je věta udávající další podmínku ekvivalentní s každou z formulí (6.1), (6.ľ) a (6.4).
Věta 6.6. Svaz S je distributivní, právě když neobsahuje podsvaz typu pentagon nebo diamant.
Vyslovme pouze hlavní myšlenky důkazu: Jestliže je svaz 5 distributivní, pak každý jeho podsvaz je distributivní a nemůže tedy obsahovat podsvaz JV5 ani M5, které nejsou distributivní.
Jestliže svaz S není distributivní, tzn. nesplňuje formuli (6.4), pak by měl obsahovat podsvaz Ns nebo M5. Pokud svaz S není ani modulární, pak podle věty 5.2 obsahuje podsvaz Ns. Pokud je modulární, pak musí obsahovat tři prvky a, b, c, z nichž každé dva jsou neporovnatelné. SestrojímeTi prvek d = [(a n b) u c] n n (a u b), pak lze ukázat, že množina {a n b, a, b, d, a u b} tvoří diamant.
Následující tři věty jsou bezprostřední důsledky vět 5.2 a 6.6. Svaz S je distributivní, právě když neobsahuje žádný podsvaz typu pentagon nebo diamant.
Svaz S je modulární a není distributivní, právě když neobsahuje žádný podsvaz typu pentagon a obsahuje aspoň jeden podsvaz typu diamant.
Svaz S není modulární, právě když obsahuje aspoň jeden podsvaz typu pentagon.
Příklad 6.4. Svaz P(M) znázorněný na obr. 5c nebo svaz A znázorněný na obr. 28 jsou příklady distributivních svazů, neboť neobsahují žádný podsvaz typu pentagon nebo diamant.
Svaz znázorněný na obr. 44d obsahuje podsvaz typu diamant, neobsahuje však podsvaz typu pentagon. Jedná se proto o modulární svaz, který není distributivní.
Svaz na obr. 44a obsahuje jak podsvaz typu diamant, tak i podsvaz typu pentagon. Existence podsvazu typu pentagon zaručuje, že tento svaz není modulární. Také svazy na obr. 44b, c nejsou modulární, a tedy ani distributivní.
V definici 4.8 jsme zavedli pojmy maximální ideál a prvoideál. Definice 4.8' zaváděla duální pojmy. Zajímavý vztah mezi maximálními ideály (filtry) a prvo-ideály (ultrafiltry) v distributivních svazech udávají následující navzájem duální věty.
Věta 6.7. Jestliže S je distributivní svaz, pak každý maximální ideál I v S je prvoideál.
129
Důkaz (nepřímo). Nechť I je maximální ideál v distributivním svazu 5, přičemž I není prvoideál, tzn. že v 5 existují prvky a. b takové, že
anbelAaílAbil.
Poznamenejme (viz cv. 4.10), že množina všech takových prvků x e S, že jtáflu y pro nějaké y e /, je nejmenší ideál obsahující ideál / a současně prvek a. Označme ho /,.
Ideál /, je vlastní, neboť b i Ix. Kdyby totiž platilo, zeb e lx, pak b n a u c pro nějaké cel. Protože anbelacnbel, obdržíme
b = (a u c) n b = (a n b) u (c n b) e /,
což je spor s předpokladem.
Protože / c /, (a i I a a e 1',), není ideál / maximální, což je spor s předpokladem.
Obrácení věty 6.7 neplatí, jak ukazuje následující příklad. Ve čtyřprvkovém řetězci {ÔT«, b, c) je množina {0, a] prvoideálem, ale není maximálním ideálem.
Věta 6.7'. Jestliže S je distributivní svaz, pak každý maximální filtr F v S je ultrafiltrem.
6.2      Množinová reprezentace
V tomto článku se budeme zabývat otázkou reprezentace konečných distributivních svazů. K tomuto problému se znovu vrátíme u speciálních distributivních svazů zvaných Booleovy algebry (viz kap. 10). Nyní je naším cílem ukázat, že k libovolnému konečnému distributivmmu svazu 5 existuje určitý okruh množin, který je se svazem S izomorfní. Při tomto pojednám se nám bude hodit pojem dolní množina (viz def. 1.22) a následující nový pojem.
Definice 6.2. Prvek p svazu S se nazývá zdola ireducibilní, právě když platí:
(Vjc, yeS)p = x\-jy=*(x = pvy = p) (6.5)
Příklad 6.5. Na obr. 49 jsou znázorněny svazy C, D, E. Svazy C, D jsou distributivní, svaz E není distributivní. Na každém z těchto diagramů jsou plnými kroužky
Obr. 49 a) b) c)
130
Vlastnost „být zdola ireducibilním prvkem svazu 5" se na Hasseově diagramu svazu 5 projeví takto: Do uzlu odpovídajícímu zdola ireducibilnímu prvku smí zdola vstupovat nejvýše jedna hrana.
Nyní můžeme přistoupit k vlastnímu pojednání o množinové reprezentaci konečných distributivních svazů. Lze dokázat, že v každém konečném svazu S pro libovolný prvek x € S existuje aspoň jeden zdola ireducibilní prvek p e S, který předchází před x. Značí-li / množinu zdola ireducibilních prvků svazu S, pak uvedené tvrzení můžeme zapsat následující formulí:
(Vjc e S) (3p e l)p s x
Platí dokonce silnější tvrzení, že každý prvek x konečného svazu S lze zapsat jako spojem určitých zdola ireducibilních prvků p, přičemž je zřejmé, že každý z těchto prvků p musí předcházet před prvkem x. Uvedené tvrzení bude pro nás základem, a proto ho dokážeme.
Lemma 6.6. Nechť S je konečný svaz, pak každý jeho prvek lze zapsat jako spojení určitých zdola ireducibilních prvků svazu S.
Důkaz (indukcí). Nechť V(n) představuje výrokovou formu: Pro každé x e S, jestliže počet n(x) prvků y s x v 5 je n, pak prvekx je spojením zdola ireducibilních prvků svazu S.
1. V(n) zřejmě platí pro každý zdola ireducibilní prvek.
2. Jestliže x e S není zdola ireducibilní prvek, pak ho lze zapsat ve tvaru
x = a u b,      kde      a ■< x       a 6<x,
což znamená, že n(a) < n(x) a n(b) < n(x). Na základě indukčního předpokladu však pro prvky a, b platí V(n), tzn. že prvky a, b jsou spojením množin X &Y zdola ireducibilních prvků:
a = |_př      a      b = \_\Y Odtud dostaneme
x = aLjb = \_\Xul]Y.
Prvek x je proto také spojením zdola ireducibilních prvků.
Označíme-li množinu všech zdola ireducibilních prvků p předcházejících před prvkem x ve svazu S znakem I(x), pak lze jako důsledek lemmatu 6.6 vyslovit následující lemma.
Lemma 6.7. Nechť S je konečný svaz, pak každý jeho prvek x lze zapsat ve tvaru x = []l{x).
Nechť S je libovolný konečný distributivní svaz, pak zaveďme zobrazení F, které každému prvku x e S přiřazuje množinu l(x). Každá množina l(x) je dolní
131
podmnožina posetu /. Označíme-li množinu všech neprázdných dolních podmnožin posetu / symbolem D(I) , pak pro zobrazení F platí:
Příklad 6
ireducibiLii,
F: xeS» I(x) e D(l) O zobrazení F lze vyslovit toto:
(6.6)
Lemma 6.8. Nechť S je konečný distributivní svaz a nechť D(l) je množinový okruh všech dolních podmnožin množiny I všech zdola ireducibilních prvků v S, pak zobrazení F definované formulí (6.6) je izomorfismem svazů S a D(l).
Důkaz. Zobrazení F převádí v libovolném konečném svazu operaci m na operaci množinový průnik, tzn.
I(x n y) = I(x) n /(y). (6.7)
Platnost formule (6.7) je důsledkem definice svazové operace n, neboť
(V*, y,Z6S)z<jtn)í<*(zsxAZSy).
Zobrazení F převádí v libovolném konečném distributivním svazu operaci i_i na operaci množinové sjednocení, tzn.
I(x uy) = I(x) u /(y).
(6.8)
Platnost formule (6.8) vyplývá z následující úvahy: Nechť p je zdola ireducibilní prvek, pak p s x u y, právě když
f=Pn(iuy) = (pnl)u(|)n^
Protože p je zdola ireducibilní prvek, platí p = p n x nebo p = p n y, což znamená, že p s x nebo p s y. Shrňme:
(V/7 e /) (VX y e S)p1 a x u y **(p 22 x v psy)
O zobrazení F tak platí, že je homomorfním zobrazením konečného distributivního svazu S na množinový okruh D(l). Na základě lemmatu 6.7 lze dokonce říci, že F je vzájemně jednoznačné zobrazení mezi S a D(l), tzn. že F je jejich izomor-fismus.
Z důkazu lemmatu 6.8 vyplývá, že zobrazení F zachovává operaci n v libovolném konečném svazu, operaci u však zachovává pouze v konečném distributivním svazu. Ukažme proto, že formule (6.8) nemusí platit, pokud uvažovaný svaz není distributivní.
/i
tedv
Vyslovme které se říkí
Věta 6.8,
žin, který je
Uvazujme o reprezent^; bloku navzaj jeden okruh
Poznamen konečnosti Sjtruovat jin
Na zákla okruhu mn
K n>::Aa
0. Nechť
1. Sestrojí poseto
2. V Uspoř
132
Príklad 6.6. Uvažujme diamant znázorněný na obr. 22b, jehož množina zdola ireducibilních prvků / = {O, a, b, c}, pak
l(a ub) = 7(1) = {0, a, b, c}
l{a) u I{b) = {0, a) u {0, b) = {0, a, b},
tedy
I(a Ljb)ŕ I{a) u I(b).
Vyslovme lemma 6.8 ještě jednou ve zjednodušené formě. Obdržíme větu, které se říká věta o množinové reprezentaci konečného distributivního svazu.
Věta 6.8. Ke každému konečnému distributivnímu svazu S existuje okruh množin, který je se svazem S izomorfní.
Uvažujme třídu všech konečných distributivních svazů, pak můžeme větu 6.8 o reprezentaci konečných distributivních svazů vyslovit také takto: V každém bloku navzájem izomorfních konečných distributivních svazů existuje alespoň jeden okruh množin.
Poznamenejme, že věta 6.8 zůstává v platnosti, i když vypustíme požadavek konečnosti uvažovaného svazu. Důkaz bychom však v tomto případě museli konstruovat jinak.
Na základě výše prováděných úvah můžeme nyní vypsat postup pro sestrojení okruhu množin izomorfního se zadaným konečným distributivním svazem S.
Konstrukce:
0. Nechť .S' je konečný distributivní svaz.
1. Sestrojíme množinu / všech zdola ireducibilních prvků svazu S. Uspořádání posetu / obdržíme zúžením uspořádání svazu S.
2. V posetu / sestrojíme množinu D{I) všech neprázdných dolních množin. Uspořádáme-li množinu D(í) relací     obdržíme okruh množin, který je izomorfní s původním distributivním svazem S (izomorfismem je zobrazení F zadané formulí (6.6)).
Příklad 6.7. Konstrukci množinového okruhu D(l) izomorfního s konečným distributivním svazem S popíšeme pomocí obr. 50. Znáčem je zde stejné jako ve výše popsané konstrukci. Na obr. 50a je zadaný svaz S, na obr. 50b je poset /zdola ireducibilních prvků v S a na obr. 50c je množinový okruh D(í) (všech neprázdných dolních množin v /), který je izomorfní se svazem S.
133
{0,a,feh/ \{0,b,d} {0,a}</   \\0,b} D(l)
Obr. 50
CVIČENÍ 6
1 Dokažte, že svaz S je distributivní, právě když (Vx, y, z e S) (x u y) n z ^ x u (y n z).
2 Načrtněte Hasseův diagram distributivního svazu (viz věta 6.6) a ověřte větu: Jestliže je svaz S distributivní, pak pro každé a e S je zobrazení
F: x e S <— a n x
homomorfním zobrazením svazu S na počáteční interval (<-, a] a zobrazení
G: x e S " a u x je homomorŕhí zobrazení svazu S na koncový interval [a, -*).
3 Dokažte, že pokud k distributivnímu svazu S přidáte dva nové prvky 0, 1, pro něž platí 0<i< 1 pro všechna x e S, pak vzniklý svaz je opět distributivní.
4 Dokažte, že svaz {a n b, a, b, d, a la b) uvedený v nástinu důkazu věty 6.6 je diamant.
5 Dokažte, že svaz (N, |) je distributivní a že jeho zdola ireducibilmmi prvky jsou všechna prvočísla, mocniny prvočísel a číslo 1.
6 Sestrojte Hasseovy diagramy neizomorfních distributivních svazů délky 2 a délky 4.
7 Definujte shora ireducibilní prvek svazu S a popište pomocí těchto prvků duální konstrukci okruhu množin izomorfního se zadaným distributivním konečným svazem.
V p
pomocí něhož mentárm svaa Booleových al další druh;. • opět jejich ~-
7.1
Dt
Dcf
x e S se nazýu x -
Svaz S s nule priek má
(Vx
F- . " .• .
svazech >c- r r
Príklad " 1
znázornér.e r. obr. 51 d. i -: ke každe—_ : mantu a r;r.: c pra\"e dva k obr. 51d ne Tuto síra.-.;: obr. 51d. e < prvky 1 a 0. < prvek 1 a ko dúkaz je z:e-
134
7    KOMPLEMENTÁRNÍ SVAZY
V první části kapitoly zavedeme „obyčejný" komplement daného prvku, pomocí něhož vymezíme další důležitý druh svazů, kterým budeme říkat komplementární svazy. Vlastnosti těchto svazů budeme využívat především při studiu Booleových algeber v dalších kapitolách. V druhé části této kapitoly zavedeme tři další druhy komplementů, které se také často studují v teorii svazů, a ukážeme opět jejich nejzákladnější vlastnosti.
7.1       Definice a vlastnosti
Definice 7.1. Nechf S je svaz s nulou a jednotkou. Komplementem prvku
x € S se nazývá každý prvek y e S, pro nějž platí
xny=OAJCi_iy=l. (7-1)
Svaz S s nulou a jednotkou se nazývá komplementární, právě když každý jeho prvek má alespoň jeden komplement, tzn. když
(V* e S) (3y e S) x n y = 0 a x u y = 1. (7.2)
Poznamenejme, že požadováním platnosti formule (7.2) v komplementárních svazech se princip duality neporuší, protože tato formule je autoduální.
Příklad 7.1. Na obr. 51 jsou vyznačeny Hasseovy diagramy pěti svazů. Svazy znázorněné na obr. 51a, b, c jsou komplementární, zatímco svazy znázorněné na obr. 51d, e nejsou komplementární. Svaz na obr. 51a se přitom vyznačuje tím, že ke každému prvku existuje právě jeden komplement. To však není splněno u diamantu a pentagonu na obr. 51b, c. U diamantu existují ke každému z prvků a, b, c právě dva komplementy. Stejná situace je i u prvku c v pentagonu. Řetězec na obr. 5ld není komplementární, protože neexistuje komplement k prvku a. Tuto situaci lze zobecnit — viz lemma 7.1. U nekomplementárních svazů na obr. 51d, e existují komplementy pouze k prvkům 0 a 1 a jsou jimi po řadě prvky 1 a 0. Obdobně i v prvních třech příkladech platilo, že komplementem 0 je prvek 1 a komplementem 1 je prvek 0. Toto zjištění vyslovíme jako větu, jejíž důkaz je zřejmý.
135
a)
b)
Off
Věta 7.1 a 7.1'. Necht S je svaz s nulou a jednotkou, pak komplementem nuly je právě jen jednotka a komplementem jednotky je právě jen nula.
Lemma 7.1. Řetězec mající alespoň tři prvky není komplementární svaz.
Příklad 7.2. Uvažujme okruhy množin P(M), kde M je libovolná množina, které
jsme zavedli v příkladě 2.7. Víme o nich, že jsou to distributivní svazy s nulou
a jednotkou. Nulou je množina 0 a jednotkou je množina M. Tyto svazy jsou
komplementární, neboť ke každé množině A e P(M) existuje dokonce právě jeden
komplement a je jím množinový komplement množiny A vzhledem k množině
M. Označíme-li množinový komplement množiny A vzhledem k M symbolem A',
tzn. ,    r .
A ={xeM;xí A),
pak z této formule bezprostředně vyplývá, že pro libovolnou množinu A e P(M) platí
A n A' = 0 a A u A' = M,
což jsou právě požadavky (7.1).
Zopakujme, že okruhem množin jsme nazvali každou množinu K, jejíž prvky jsou podmnožiny (ne nutně všechny) určité množiny M. Množina K však musí být uzavřená vzhledem k množinovým operacím o a u. Nyní zavedeme další důležitý množinový pojem. Dříve však ještě zdůrazníme, že přiřazování komplementů podmnožinám množiny M (viz př. 7.2) lze chápat jako unární operaci.
Definice 7.2. Nechť P(M) je potence množiny M a nechť K je podmnožinou množiny P(M). Množina K se nazývá množinové těleso neho těleso množin, právě když je uzavřená vzhledem k binárním množinovým operacím průnik a sjednocení a dále vzhledem k unární operaci komplement.
Těleso množin i e tedy takový okruh množin, který je uzavřený vzhledem k tvorem komplementů. Z předchozího víme, že každý okruh množin je distributivní svaz, a proto i každé těleso množin je distributivní svaz. který má samozřejmě nulu
£ jednotku. Tělesa se vrátíme v druhe mimořádně důležit
Příklad 7.3. U
sem T. Ukažme. : dimenzi n a nechť každý vektor x -
x = .. v
Nechť Vl je libovol Pak k vektorům te tak, že vzniklá mn V. Podproster - _ storu Vl, neboť pfc
K, n V-
kde 0 je nulový w takto sestro;:: ;eh podprostorů {0} a
Příklad ".4. U-
2.10. Ten:/' >\ _e: -je komplementáři] nekonečně mnoho va diagramu):
a) komplement
b) kompkmenti rovina q rovnobä
e ?: ~r přímka p rovnotu s q a různá od p.
Poznámka. Svaz J Nechť p je libovolná p q <= q, pak pětiprvko*;
Upozorněme, ž ním svazem. Nar: podsvaz znázorní
Lze říci. že p : obraz je kompler-komplementárn: -
136
;1
a:
mk komplementem nuly je fen nula.
mwqtiementární svaz.
efibovolná rntnožina, které ■ttnbutjvni svazy s nulou mna M. Tyto svazy jsou ttuje dokonce právě jeden f A vzhledem k množině ledem k Af symbolem A',
dnou
vir.u A e P(M)
u množinu K, jejíž prvky Množina K však musí být : . . další důležitý (Bázování komplementů : peraci.
medu K je podmnožinou z" tělevo množin, právě mam průnik a sjednocení
-^-•rřny vzhledem k tvoři množin je distributivní tav má samozřejmě nulu
a jednotku. Tělesa množin jsou proto již velmi speciálmmi příklady svazů, k nimž se vrátíme v druhé části knihy při probírání Booleových algeber, neboť tam mají mimořádně důležité postavem.
Příklad 7.3. Uvažujme svaz 5 podprostorů vektorového prostoru V nad tělesem T. Ukažme, že svaz S je komplementární. Nechť vektorový prostor V má dimenzi n a nechť lineárně nezávislé vektory v1, v2 až v„ tvoří jeho bázi, tzn. že každý vektor x e F lze zapsat právě jedním způsobem ve tvaru
x =.a]V, + a2v2 +
kde
a, e T.
Nechť Vl je libovolný podprostor prostoru V mající dimenzi h a bázi ul Pak k vektorům této báze lze přidat lineárně nezávislé vektory uh + l, i
u2az uh.
tak, že vzniklá množina vektorů uu u2, . V. Podprostor V2 generovaný vektory uh. storu P], neboť platí
uh, uh + u„ tvoří bázi prostoru uh + 2,..., u„ je komplementem pro-
K, rn V2 = Vy n V2
V,ljV2 = [V, u V2] - V,
kde 0 je nulový vektor. Ke každému vektorovému podprostorů prostoru V lze takto sestrojit jeho komplement, který je jediný. Přitom vůně, že komplementy podprostorů {O} a V jsou po řadě podprostory V a {O}.
Příklad 7.4. Uvažujme svaz z oblasti geometrie, který jsme zavedli v příkladě 2.10. Tento svaz s nulou a jednotkou, jimiž jsou po řadě množina 0 a množina E3, je komplementární. Každý prvek tohoto svazu s výjimkou nuly a jednotky má nekonečně mnoho komplementů (znázorněte následující situace pomocí Hasseo-va diagramu):
a) komplementem množiny {x}, kde x e Ei, je libovolná rovina g, kde x i p,
b) komplementem přímky p je libovolná přímka s ní mimoběžná nebo libo volná rovina g rovnoběžná s p, kde p n p — 0,
c) komplementem roviny g je libovolná množina {x}, kde x i g, nebo libovolná přímka p rovnoběžná s p a neležící v p nebo libovolná rovina o rovnoběžná s p a různá od p.
Poznámka. Svaz M uvažovaný v příkladě 7.4 není modulární, což můžeme zdůvodnit takto: Nechť p je libovolná přímka z M a nechť rovina q a přímka q jsou dva její komplementy, pro něž platí ?cp, pak pětiprvková množina {0,p, q, g, E3} tvoří pentagon (viz věta 5.2).
Upozorněme, že podsvaz komplementárního svazu nemusí být komplementárním svazem. Např. svazy na obr. 51a, b, c, které jsou komplementární, obsahují podsvaz znázorněný na obr. 51 d, který komplementární není.
Lze říci, že pokud je svaz S komplementární, pak i jeho libovolný izomorfní obraz je komplementární svaz a dokonce i jeho libovolný homomorfní obraz je komplementární svaz. Proto můžeme vyslovit:
137
Lemma 7.2. NechťF je svazový homomorfismus komplementárního svazu S na svaz A, pak svaz A je také komplementární.
modulární. Lze ^ Modulárním k: -
Důkaz. Nechť x je libovolný prvek svazu S a nechť y je některý z jeho komple-mentů, pak platí:
l.In^OAIu)1 =1
2. f(in y) = F(x) n F{y) - F(0)
3. F(x „ y) = F(x) „ F{y) = F(l)
Předpoklady
F je zobrazení a podle (4.16). F je zobrazení a podle (4.16')
Z definice homomorfního zobrazení vyplývá, že pokud prvek x „proběhne" celou množinu S, pak prvek F(x) „proběhne" celou množinu A a jedním z komplementů k prvku F(x) je vždy prvek F(y). Ke každému prvku z A proto existuje jeho komplement.
V důkazu lemmatu 7.2 jsme zjistili, že pokud jsou prvky x,y e S ve vztahu „být komplementem", pak jsou i jejich homomorfní obrazy F(x), F(y) e A ve vztahu „být komplementem". Lze proto říci, že svazový homomorfismus zachovává relaci „být komplementem".
V článku 6.2 jsme ukázali, že ke každému prvku x konečného svazu S existuje alespoň jeden zdola ireducibilní prvek p e 5, který předchází před x. Protože atomy jsou speciálním případem zdola ireducibilních prvků, je následující tvrzení zesílením předchozího: Pro každý nenulový prvek x e S existuje alespoň jeden atom p e S, který předchází před x. Toto tvrzení použijeme v důkaze věty 7.2, kterou budeme formulovat rovněž pouze pro konečné svazy.
Věta 7.2. V každém konečném alespoň dvouprvkovém komplementárním svazu S je jednotka spojením množiny atomů.
Důkaz. Označme a spojení množiny atomů svazu S a nechť b je jeden z komplementů prvku a. Pak pro prvek b platí jedna z následujících možností:
a) Jestliže b = 0, pak podle věty 7.1 je a = 1 a důkaz končí.
b) Jestliže je b atom, pak b s a, a tedy a n b — b, což je spor s tím, že a n b = 0.
c) Jestliže b i= 0 není atom, pak existuje alespoň jeden atom p takový, že p ~& b. Protože p ^ a, je p ^ a n b, což je opět spor s tím, že a n b = 0.
Obrácení věty 7.2 neplatí, jak ukazuje svaz S znázorněný na obr. 52. Jednotka je spojením atomů a přitom k prvku p2 neexistuje komplement. Svaz S navíc není
Obr. 52
138
Poznámka. V : zahrnují svazy, v nicb v rámci teorie m :c
Projektivní r •
ně P říkáme mr ř_-{P, L, i) musí splň •.
1. Pro každé dva i
2. Ke každým dví
3. Existují čtyři m jestliže dva z nicb int
Sestrojme rr.r na S spolu s uspeři způsobem) tvoří moc a jednotky ale>po-. ; cvičení.
Platí však i obři:, kromě nuly a jedr.: předkládáme po.ľr
Naznačili jsnw zřejmé, že tato >. článku zaměříme
Věta 7.3. Jest i nejvýše jeden kon
Důkaz (nepřít prvku a existují
1. a - b =
2. a n c = 0
3. fc?íf
4. a n b = -
5. b = c
Spor na ř. 3 a
Důsledek věn
dému jeho prvku
Tvoření kom r i hodněme se. že pak ho budeme
(V.ví5
lamou
'ámího svazu S na
t některv z jeho komple-ttadv
■azení a podle (4.16). hrazení a podle (4.16').
raek x „proběhne" celou k jedním z komplementú fA proto existuje jeho
Lx,y e 5 ve vztahu „být \,F{y) e A ve vztahu „být ns zachovává relaci „být
:.." - h svazu S existuje dchází před x. Protože ku. je následující tvrzení F existuje alespoň jeden v důkaze věty 7.2,
pón komplementárním
xht b je jeden z komple-
ch možností:
končí.
-r : s tím. že a n b = 0. ■tom p takový, žep ■< b. kb = 0.
nv na obr. 52. Jednotka ~ -. r.: Svaz S navíc není
modulární. Lze dokázat, že v každém modulárním svazu již obrácení věty 7.2 platí. Modulárním komplementárním svazům budeme věnovat i následující poznámku.
Poznámka. Modulární komplementární svazy jsou důležité především jako ten druh svazů, které zahrnují svazy, v nichž se průsek a spojem provádí na bodech, přímkách atd. Načrtněme, jak je možné v rámci teorie modulárních komplementárních svazů axiomaticky založit projektivní geometrii roviny.
Projektivní rovina je trojice (P, L, /), kde P a L jsou dvě disjunktní množiny a / £ P x Ĺ. Množině P říkáme množina bodů, množině L množina přímek a binární relaci / relace incidence. Trojice (P, L, I) musí splňovat následující axiómy:
1. Pro každé dva různé body a, b e P existuje právě jedna přímka p e L tak, že oba body s ní incidují.
2. Ke každým dvěma přímkám p.q e L existuje bod a e P, který inciduje s oběma přímkami.
3. Existují čtyři navzájem různé body a,, a2, a}, a4 e P takové, že pro libovolnou trojici z nich platí: jestliže dva z nich incidují s přímkou p a L, pak třetí z nich s přímkou p neinciduje.
Sestrojme množinu 5 obsahující nulu, všechny body z P, všechny přímky z L a jednotku. Množina S spolu s uspořádáním „být incidentní" (na nulu a jednotku je uspořádám rozšířeno zřejmým způsobem) tvoří modulární a komplementární svaz délky 3, ve kterém má každý prvek kromě nuly a jednotky alespoň dva komplementy. Důkaz vysloveného tvrzení přenecháme čtenáři jako vhodné cvičení.
Platí však i obráceně: Jestliže svaz S je modulární a komplementární, má délku 3 a každý prvek kromě nuly a jednotky má alespoň dva komplementy, pak se jedná o projektivní rovinu. Toto tvrzení předkládáme pouze pro informaci, protože jeho důkaz by byl obtížný.
Naznačili jsme, jak teorie modulárních svazů souvisí s geometrií roviny. Je zřejmé, že tato souvislost existuje i pro prostory vyšších dimenzí. Ve zbývající části článku zaměříme svoji pozornost výhradně na distributivní svazy.
Věta 7.3. Jestliže je svaz S distributivní, pak ke každému jeho prvku existuje nejvýše jeden komplement.
Důkaz (nepřímý). Nechť existuje distributivní svaz S, v němž k určitému prvku a existují alespoň dva komplementy. Označme dva z nich bac. Pak platí:
1. flr-i6 = 0AflLJ& = l
2. flnC = 0Afli_iC=l
3. b é c
4. anŕJ = a[-iCAfli_i/? = flLjc
5. b = c
Spor na ř. 3 a 5.
Předpoklady
Tranzit, rovnosti na ř. 1, 2. Podle (6.4) na ř. 4.
Důsledek věty 7.3. Jestliže distributivní svaz S je komplementární, pak ke každému jeho prvku existuje právě jeden komplement.
Tvorem komplementú v těchto svazech proto představuje unární operaci. Dohodněme se, že pokud k danému prvku x s S existuje právě jeden komplement, pak ho budeme značit x'. V komplementárních a distributivních svazech platí
(Vjc e5)xnjr' = 0AXux'= 1.
(7.3)
139
Příklady 7.1 až 7.4 (pokračování). Svazy na obr. 51a, c, d jsou distributivní, přičemž pouze svaz na obr. 51a je také komplementární. Je proto „jednoznačně komplementární".
Každé těleso množin je distributivní a komplementární svaz, a je proto „jednoznačně komplementární".
Geometrický svaz z př. 7.4 má ke každému prvku s výjimkou nuly a jednotky nekonečně mnoho komplementů, a není proto distributivní. Podle poznámky na str. 137 není tento svaz ani modulární.
Věta 7.4. Nechť S je distributivní svaz s nulou a jednotkou, pak ty prvky svazu S, které mají komplement, tvoří distributivní podsvaz svazu S-.
Důkaz. Nechť x, v jsou libovolné prvky svazu S, které mají komplement. Dokážeme, že potom i prvky x n y a x u y mají komplement a jsou jimi po řadě prvky
x' u ý a x' n y.
1. (x n y) n (x? i_i y') =
2. = (x n y n x1) u [x n y n ý) = Podle (6.ľ) a (4.2) na ř. 1.
3. = (y n 0) u [x n 0) = 0 u 0 - Podle (4.1), (4.2), (7.3), L 3.2.
4. = 0 Podle L 3.2 na ŕ. 3.
5. (x n y) u (x' u y) =
6. = (x u x' u y') nfj-ui'u y') = Podle (6.1) a (4.2') na ŕ. 5.
7. = (1 u y') n (1 lj x') = 1 m 1 = Podle (4.1'), (4.2'), (7.3), L 3.2.
8. = 1 Podle L 3.2 na ŕ. 7.
Duálně lze dokázat, že komplementem k x u y je prvek x' n y'. Z důkazu věty 7.4 vyplývá platnost tzv. de Morganových pravidel.
Věta 7.5 a 7.5'. Nechť S je distributivní svaz a nechť k prvkům x, y e S existují komplementy x', y', pak platí
(x n y)' = x1 u y' a (x u y)' = x' n y'. (7.4)
Příklad 7.2 (pokračování). V libovolném tělese množin K běžně používáme de Morganova pravidla (7.4) pro libovolnou dvojici množin A, B e K, neboť těleso K je distributivní a k libovolné množině existuje komplement. Vzorce (7.4) pak formulujeme takto:
{A n B)' - A' u B'      [Au B)' = A' n B' (7.5)
Čtenář si může formule (7.5) znázornit pomocí Vennových diagramů.
Poznámka. Především v kapitole o distributivních svazech a v této kapitole jsme poznali, že operace n a u ve svazu S jsou abstraktními analogiemi operací n a u v okruhu množin P(M). Jestliže má svaz S nulu a jednotku, pak jsou to opět abstrakce množiny 0 a množiny M. Také svazový komplement lze brát jako abstraktní analogii množinového komplementů.
140
Pozastavme se u definice komplementu A' množiny A. Bylo by možné definovat ho takto: Komplement A' množiny A v množině M je
a) největší podmnožina množiny M, pro niž platí A n A' = @,
b) nejmenší podmnožina množiny M. pro niž platí A <j A' = M.
Pro obě uvedené definice lze najít v teorii svazů analogie, které však už nejsou ekvivalentní. Lze je vyslovit takto:
a, ) Nechť svaz S má nulu, pak se prvek v e S nazývá n-komplement prvku* vS, právě když y je největší
prvek takový, že x n y = 0.
b, ) Nechť svaz S má jednotku, pak se prvek v e S nazývá _-komplcment prvku x v S, právě když y je
nejmenší prvek takový, že x u y = 1. Z definic a,) a b,) vyplývá, že pokud existuje průsekový nebo spojový komplcment prvku x v S, pak je právě jeden. Tyto komplementy se však nemusí sobě rovnat. Např. v pentagonu na obr. 51c je n-komplementem prvku c prvek b, zatímco ^-komplementem téhož prvku c je prvek a. V distributivních svazech platí:
Nechť S je distributivní svaz a prvek x e S má současně n-komplement, který označíme y,, a u-komplement, který označíme y,, pak y, ^ y;.
Důkaz, y, = Vi n 1 = y, n (x u y2) — (yt n x) u (y, n y2) — 0 u (y, n y2) = y, n y. Definice komplementu se někdy vyslovuje takto:
c, ) Nechť svaz S má nulu a jednotku, pak se prvek y e S nazývá komplement prvku x vS, právě když y je
n-komplement i u-komplement prvku x.
Z definice c,) vyplývá, že pokud komplement prvku x e S existuje, pak je právě jeden. Pozor! Definice 7.1 nem ekvivalentní s definicí c,). Požadavek na komplement v definici c,) je silnější než požadavek v definici 7.1. V distributivních svazech jsou však obě definice ekvivalentní. K definici aj se vrátíme v následujícím článku této kapitoly (viz def. 7.4).
7.2      Jiné druhy komplementárních svazů
V tomto článku budeme definovat tři další druhy komplementu a u každého z nich uvedeme některé jeho základní vlastnosti. První z nich je tzv. relativní komplement vzhledem k určitému intervalu.
Definice 7.3. Nechť [a, b] je interval ve svazu S. Relativním komplementem
prvku x £ [a, b] se nazývá každý prvek y, pro který platí:
xny = aAX\-jy = b (7.6)
Svaz 5 se nazývá relativně komplementární, právě když pro každý interval [a, b] a každý prvek x e [a, b] existuje alespoň jeden relativní komplement y e [a, b].
Příklad 7.5. Prohlédneme-li svazy znázorněné na obr. 51, pak zjistíme, že svazy na obr. 5la,b jsou relativně komplementární, zatímco svazy na obr. 51c, d, e relativně komplementární nejsou. Uvažujeme-li v diamantu na obr. 51b např. interval [0, l], pak relativním komplementem prvku a je kterýkoli z prvků b, c. Uvažujeme-li v pentagonu znázorněném na obr. 51c např. interval [0,&],pak pro prvek a e [0, b] neexistuje relativní komplement. Obdobně neexistuje relativní komplement pro prvek a £ [(), l] ve svazu na obr. 5 ld, e.
141
Podsvaz relativně komplementárního svazu nemusí být relativné komplementární. Tato vlastnost tedy není dědičná, jak ukazuje následující příklad. Podsvazem relativně komplementárního svazu znázorněného na obr. 51a je řetězec znázorněný na obr. 5 ld, který není relativně komplementární.
Libovolný izomorfismus a dokonce i libovolný svazový homomorfismus zachovává vlastnost „být relativně komplementární", což vyslovíme takto:
Lemma 7.3. Nechť F je svazový homomorfismus relativně komplementárního svazu S na svaz A, pak svaz A je také relativně komplementární.
Je zřejmé, že relativně komplementární svaz S nemusí být komplementární. K tomu stačí, aby svazu S chyběla nula nebo jednotka. Platí však následující věta.
Věta 7.6. Nechť S je relativně komplementární svaz s nulou a jednotkou, pak je S komplementární svaz, přičemž komplementem prvku x e S je každý jeho relativníkomplement vzhledem k intervalu [0, l],
V další části budeme uvažovat distributivní svazy. Pro tento druh svazů lze vyslovit zesílenou analogii věty 7.3.
Věta 7.7. Svaz S je distributivní, právě když ke každému jeho intervalu a ke každému prvku tohoto intervalu existuje nejvýše jeden relativní komplement.
Věta 7.7 ukazuje, jak by bylo možné zavést distributivní svaz pomocí pojmu relativní komplement. K větě 7.5 můžeme vyslovit obdobný důsledek jako k větě 7.3: Jestliže distributivní svaz S je relativně komplementární, pak ke každému jeho intervalu a ke každému prvku tohoto intervalu existuje právě jeden relativní komplement.
Vraťme se k větě 7.6. Obrácení této věty neplatí, neboť komplementární svaz nemusí být obecně relativně komplementární. Budeme-li však o uvažovaném svazu předpokládat, např. že je distributivní, pak toto zúžené obrácení platí:
Věta 7.8. Nechť svaz S je komplementární a distributivní, pak je svaz S relativně komplementární a navíc platí: Jestliže [a, b] je libovolný interval svazu S, pak pro relativní komplement y prvku x e [a, b] platí
Důkaz. Nechť x je libovolný prvek intervalu [a, b] s S, pak dokážeme, že prvek y určený formulí (7.7) splňuje formule (7.6). Podle věty 7.7 víme, že takový prvek y může existovat nejvýše jeden.
y = (a lj x1) n b.
(7.7)
x n y = x n [(a i_i x') n b] =
= [(x n (ä u X')] n b =
= [(x n a) u (x n X1)] n b =
= [(x n a) u 0] i-i b =
Podle (7.7). Podle (4.2). Podle (6.ľ). Podle (7.3).
142
= X n a n b = = a
Jtuy = Iu[(iiuX')ní)] = = Xu[(flníl)u (x' n Ŕ)] = = (a n ô) u [x u (x' n Ŕ)] = = (a n 6) u [(x i_i x') n (x i_i b)]
= (a n b) u [l i-i (x u ŕ]) = = (a n b) u (x u 6) = a i_i ŕ = = b
Podle (6.1). Podle (7.3).
Podle L 3.2, (4.4), (4.4'). Podle (4.4').
Podle L 3.2.
Podle předpokladu. Podle (7.7). Podle (4.1), (6.1'). Podle (4.2') a (4.1').
Příklad 7.2 (pokračování). Víme, že libovolné těleso množin K je komplementární a distributivní svaz. Podle věty 7.8 je proto těleso množin K také relativně komplementární svaz.
Přistupme k zavedení dalšího druhu komplementů.
Definice 7.4. Nechť svaz S má nulu, pak pseudokomplementem prvku x e S se
nazývá největší z prvků y, pro něž platí x n y = 0, tzn.
Svaz S se nazývá pseudokomplementární, právě když každý jeho prvek má pseudo-komplement.
Zaveďme binární relaci „být disjunktní". Nechť S je svaz s nulou, pak se prvky x, y e S nazývají disjunktní, právě když platí x m y = 0.
Pomocí pojmu „být disjunktní" můžeme uvést jinou formulaci definice 7.4. Nechť S je svaz s nulou, pak pseudokomplement prvku x e S je největším prvkem množiny všech prvků disjunktních s x. Protože uvažovaná množina má nejvýše jeden největší prvek, má i každý prvek x e S nejvýše jeden pseudokomplement. Dohodněme se, že pseudokomplement prvku x (pokud existuje) označíme x*.
Poznamenejme, že pseudokomplement zavedený v definici 7.4 je jenom jiný název pro n-komplement zavedený v definici a, v poznámce na str. 141.
Příklad 7.6. Prohlédneme-li si svazy na obr. 51, pak zjistíme, že svazy na obr. 51a, c, d, e jsou pseudokomplementární, zatímco svaz na obr. 51b pseudokomplementární není (neexistuje např. největší prvek v množině prvků disjunktních s prvkem a).
Každý řetězec s nulou a jednotkou je pseudokomplementární svaz. Pseudokomplementem libovolného jeho nenulového prvku je nula. Pseudokomplementem nuly je jednotka.
Sestrojíme-li např. v pentagonu prvek a* (viz obr. 51c), pak obdržíme c. Pokud sestrojíme prvek c* = a**, pak obdržíme b a nikoli výchozí prvek a (viz formule a) v lemmatu 7.4). Relace „být pseudokomplementem" nem proto symetrická. Základní vlastnosti této relace jsou shrnuty v následujícím lemmatu.
(Va e S) x n a = 0 =* a á y.
143
Lemma 7.4. Nechť x* a y* jsou pseudokomplementy prvků xayve svazu S, pak platí:
a) (Vjc e S) x s x** {pokud existuje jc**)
b) (Vjc e S) x* = x*** {pokud existuje jc**)
c) (Vjc e S) x rs y => y* =3 x*
Důkaz. Podejme na ukázku pouze důkaz formule a) a ostatní necháme do cvičení. Nechť jc je libovolný prvek z S, pro který existuje jc*, pak x n x* = 0. Prvek jc** je největší prvek z S, pro který platí x** n x* = 0, a proto x s x**.
Poznamenejme, že v pseudokomplementárních svazech je porušen princip duality. Požaduje se zde existence pseudokomplementu ke každému prvku a nikoli u-komplementu (viz def. b, v poznámce na str. 141), který je duálním pojmem k pseudokomplementu. Dodejme ještě pro zajímavost, že v libovolném distributivním pseudokomplementárním svazu 5 platí následující formule (x, y jsou libovolné prvky svazu S)
(x u y)* = Jc* n y* a x* u y* rs (jc n y)*, (7.8)
které nápadně připomínají de Morganova pravidla (7.4). Důkazy obou formulí (7.8) necháme do cvičení. Zde pouze uvedeme příklad demonstrující, že v distributivním svazu skutečně může být ve druhé z formulí (7.8) ostrá nerovnost. Bude-me-li uvažovat svaz znázorněný na obr. 51e a položíme-li x = a& y = b, pak
a* u b* = b u a = c a (a n b)* - 0* = 1 a c -< 1.
Dodejme, že speciálním druhem pseudokomplementárních svazů jsou tzv. Sto-neovy svazy. Jsou to pseudokomplementární distributivní svazy 5, pro které platí
(Vjc e S) x* u jc** - 1. (7.9)
Příkladem Stoneova svazu je svaz všech dělitelů čísla 23. 3 v N znázorněný na obr. 18a. Tento svaz je distributivní a platí: pseudokomplementem čísel 2, 22, 23 je číslo 3, pseudokomplementem čísla 3 je číslo 2\ pseudokomplementem čísel 2 . 3, 22 . 3, 23 . 3 je číslo 1, pseudokomplementem čísla 1 je 23 . 3. Ověřte, že i formule (7.9) platí. Jiným příkladem Stoneova svazu je svaz duální ke svazu znázorněnému na obr. 51e. Samotný svaz na obr. 51e Stoneův není, protože a = a**, b = a* a přitom a* u a** = c # 1. Studium Stoneových svazů úzce souvisí s problematikou reprezentace Booleových algeber*).
Posledním druhem komplementu, který zde zavedeme, je tzv. relativní pseudo-komplement.
Definice komplemen: : - •
prvek lakoty, ie m
Svaz S se nazýrm r prvků a, b e S exb
Z definice 7.5 dem k b existuje, chází před prvken proto, že relativní je) označíme a * b je stejně jako u ps
Příklad -.7. Ve
platí: 22 * 2: = 2* 2 . 3 * 2' . 3 = ľ" klady těchto svazu
Lemma ".5. A'.:
svaz.
Důkaz. Nechť x,
a) necht x    ■.
b) nech: .     ■.
Poznamenejme, chozího je videc ž x * x = 1. Nyní vy
Lemma ".6. '•:.
pak y s x * y.
■ :
! O této problematice se může čtenář dozvědět víc např. v [13] nebo v [3].
144
ta y re svazu S. pak
racháme do x n r* = 0. Prvek
porušen princip prvku a niko-;_ilr.ím pojmem yvomém distributiv-
í(jr, _>• jsou libovolné
(7.8)
ikazv obou formulí istrující. že v distri-rá nerovnost. Bude-• a a y = b, pak
-. aru i?ou tzv. Sto-^ 5. pro které platí
(7.9)
■ N znázorněný na ntem čísel 2, 22, 23 omplementem čísel e I .3. Ověřte, že az duální ke svazu r.í-' není. protože h svazů úzce souvisí
relativní pseudo-
Definice 7.5. Nechť a, b jsou dva prvky svazu S, pak se prvek p nazývá pseudo-kompiement prvku a vzhledem k prvku b (nebo modulu b), právě když je p největší prvek takový, že a n p a b, tzn.
(Vx EÍ)«nJf</)«I<|),
(7.10)
Svaz S se nazývá relativně pseudokomplementární, právě když pro každou dvojici prvků a, b e S existuje pseudokomplement prvku a vzhledem k prvku b.
Z definice 7.5 vyplývá, že pokud relativní pseudokomplement prvku a vzhledem k b existuje, pak je jediný. Množina všech prvků x e S jejichž průnik s a předchází před prvkem b může mít totiž nejvýše jeden největší prvek. Dohodněme se proto, že relativní pseudokomplement prvku a vzhledem k prvku b (pokud existuje) označíme a * b. Poznamenejme, že u relativně pseudokomplementárních svazů je stejně jako u pseudokomplementárních svazů porušen princip duality.
Příklad 7.7. Ve svazu všech dělitelů čísla 2d . 33, který je znázorněn na obr. 28, platí: 22 * 22 = 24. 3\ 23 * 2 . 32 = 2 . 33, 23. 3 * 2 . 3 = 2 .33, 22 . 32 * 1 - 1, 2 . 3 * 23 . 3 = 24. 33. Tento svaz je relativně pseudokomplementární. Další příklady těchto svazů poskytuje následující lemma.
Lemma 7.5. Každý řetězec s jednotkou je relativně pseudokomplementární svaz.
Důkaz. Nechť x, y jsou libovolné dva prvky řetězce S, pak:
a) nechť x ^ y, pak x * y = 1,
b) nechť y -a x, pak x * y = y.
Poznamenejme, že prvek x * y nemusí vždy ve svazu S existovat, např. z předchozího je vidět, že x * x existuje, právě když má svaz 5 jednotku, a pak platí x * x = 1. Nyní vyslovíme několik jednoduchých důsledků definice 7.5.
Lemma 7.6. Nechť S je svaz ax,y dva jeho libovolné prvky, pro něž existuje x * y, pak y ^ x * y.
Důkaz.
l.xny^y Podle (2.5).
y=3x*y Podle (7.10) na ř. 1.
Lemma 7.7. Nechť S je svaz s jednotkou, pak platí:
(Vx, y e S) x a y <=> x * y = 1 (Vx e S) 1 * x = x
Lemma 7.8. Nechť S je svaz s nulou, pak platí:
(VxeS)x* = x*0 (7.11)
145
Např. lemmatu 7.8 je třeba rozumět takto: Jestliže existuje prvek na jedné straně rovnosti (7.11), pak existuje i prvek na druhé straně této rovnosti a oba prvky jsou si rovny. Formule (7.11) navíc ukazuje, že relativní pseudokomplement lze považovat za zobecnění pojmu pseudokomplement.
Následující lemma ukáže, že z existence relativního pseudokomplementu vyplývají důsledky distributivního charakteru.
Lemma 7.9. Nechť S je svaz ax,y,z jsou tři jeho libovolné prvky, pro něž existuje prvek x * [(x n y) u (x n z)], pak platí:
x n (y u z) = (x n y) i_i (x n z) (7-12)
Důkaz. Nechť x, y, z jsou libovolné prvky z S, splňující předpoklady věty. Označme u = (x n y) u (x n z). Protože injsuaxnzsu, obdržíme podle (7.10) y 23 x * u a z s x* u. Z toho vyplývá (podle (2.14')), že y u z ^ x * a a z toho opět podle (7.10)
x n (y i_i z) ^ u. (7.13)
Obráceně: Podle (2.13'), (2.21) a (2.15) obdržíme x n y ^ x n (y u z) axr-iz^xn(yuz)a odtud podle (2.14') a konstrukce m získáme:
u =3 x n (y u z) (7.14)
Z formulí (7.13) a (7.14) vyplývá podle (1.6) formule (7.12).
Poznámka. Parciální operace *, která dvojicím prvků x, y nějakého svazu S přiřazuje prvek x * y, velmi úzce souvisí s logickou operací implikace, a proto bývá někdy dokonce značena =*. Platí pro ni např. tato věta:
Jestliže S je distributivní svaz a a: je libovolný prvek, pro nějž existuje komplcment x', pak pro libovolné y e S existuje prvek x * y a platí:
x*y = x1 lj y (7-15)
Ve svazech zvaných Booleovy algebry jsou předpoklady právě uvedené věty splněny (viz kap. 8), a proto v nich formule (7.15) platí pro libovolnou dvojici prvků x,y. Jestliže ve formuli (7.15) nahradíme symboly *, =,', i_i po řadě symboly =>,<=>, ~l a v , pak obdržíme známou tautologii výrokové logiky:
[x => y) <* (~\x v y)
CVIČENÍ 7
1 Dokažte větu 7.1.
2 Dokažte, že v libovolném tělese množin platí de Morganova pravidla (7.5).
3 Dokažte, že pro distributivní svazy S je definice 7.1 ekvivalentní s definicí ct v poznámce na str. 141.
146
tuje prvek na jedné této rovnosti a oba - . _ -complement
: mplementu vy-
.pro něž existuje
4 Dokažte, že pro každý nenulový prvek x z konečného svazu S existuje alespoň jeden atom. který předchází' před x.
5 Dokažte formule b) a c) z lemmatu 7.4.
6 Dokažte lemmata 7.7 a 7.8.
7 Určete, zda svaz z příkladu 7.7 je a) komplementární, b) relativně komplementární, c) pseudokomplementární, d) relativně pseudokomplementární. Určete totéž pro svazy P{M), kde M je libovolná množina, a (N, j).
(7.12)
Klady věty.
* u. obdržíme podle 4")t že y ^ z ^ x * u
(7.13)
In)'íín(yuZ)
získáme:
(7.14)
— : . ■;• prvek .v * y. BK značena =». Platí pro ni
i   -' . pak pro
(7.15)
y splněny (viz kap. 8), i(7.15)nahradí-výrokové logiky:
■on pravidla (7.5). malenmí s definicí Cj
147