Svazy Def Svaz je algebra S = ( M ; ∧, ∨ ) se dvěma binárními operacemi taková, že pro libovolné prvky a, b, c ∈ M platí následující podmínky – axiomy svazu: ( a ∧ b ) ∧ c = a ∧ (b ∧ c ) , ( a ∨ b ) ∨ c = a ∨ (b ∨ c ) ,
a ∧ b = b ∧ a, a ∨ b = b ∨ a , a ∧ ( a ∨ b ) = a, a ∨ ( a ∧ b ) = a. Operace ∧ se nazývá průsek, operace ∨ spojení. Axiomy představují zákony asociativní, komutativní a zákon absorpce. Všimněme si, že se vyskytují ve dvojicích, ve kterých jsou vzájemně zaměněny obě operace – o takových formulím říkáme, že jsou duální. Na rozdíl od okruhu jsou tedy požadavky na obě operace zcela stejné. L Buď S = ( M ; ∧, ∨ ) svaz. Operace ∧ a ∨ jsou idempotentní, tj. pro libovolné a ∈ M platí a ∧ a = a, a ∨ a = a .
Důkaz: Buďte a, b ∈ M . Potom podle zákonů absorpce
a ∧ a = a ∧ ( a ∨ ( a ∧ b )) = a a analogicky se dokáže i druhý vztah.
□
Algebry ( M ; ∧ ) a ( M ; ∨ ) se nazývají průsekový a spojový polosvaz. Jsou to komutativní pologrupy. Proto lze psát průseky a spojení konečného počtu prvků svazu bez závorek a v jakémkoli pořadí prvků. Př 1) Je-li A libovolná množina, pak
( P ( A) ; ∩, ∪ )
je svaz; je to svaz všech podmnožin
množiny A . Je-li A = ∅ , pak jde o svaz jednoprvkový. 2) Buď ( M ; ≤ ) lineárně uspořádaná množina. Definujme na množině M
operace
následovně: jsou-li a, b ∈ M , a ≤ b , klaďme a ∧ b = a, a ∨ b = b . Pak S = ( M ; ∧, ∨ ) je svaz, který můžeme nazvat lineární. Takové svazy jsou ovšem velmi speciální a z hlediska teorie svazů ne příliš zajímavé. V obou příkladech svazů lze na jejich nosičích uvažovat uspořádání, které úzce souvisí se svazovými operacemi. Def Buď ( M ; ≤ ) uspořádaná množina. Je-li množina všech horních závor množiny N ⊆ M neprázdná a má-li první prvek, nazývá se tento prvek supremem množiny N a značí se sup N . Analogicky, tj. „duálně“, se definuje infimum množiny N , které značíme inf N .
Uvědomme si, že sup ∅ existuje právě tehdy, když má množina M první prvek p a je potom sup ∅ = inf M = p a analogicky inf ∅ = sup M = q , kde q je poslední prvek, existuje-li, množiny M . Def Uspořádání ≤ na množině M se nazývá svazové, má-li každá dvouprvková podmnožina množiny M supremum i infimum v množině M. L Buď S = ( M ; ∧, ∨ ) svaz. Potom pro libovolná a, b ∈ M platí a ∧ b = a ⇔ a ∨ b = b .
Důkaz: Je-li a ∧ b = a , je a ∨ b = ( a ∧ b ) ∨ b = b ; opačná implikace se dokáže analogicky. V 1) Buď
□
S = ( M ; ∧, ∨ ) svaz. Definujeme-li na množině M binární relaci ≤ vztahem
a ≤ b ⇔ a ∧ b = a , je ≤ svazové uspořádání na množině M . 2) Buď
( M ; ≤)
svazově uspořádaná množina. Definujeme-li na množině M operace ∧ a
∨ vztahy a ∧ b = inf {a, b} , a ∨ b = sup {a, b} , je S = ( M ; ∧, ∨ ) svaz.
Důkaz: 1) Je ihned vidět, že relace ≤ je na M reflexivní a slabě antisymetrická. Buďte a, b, c ∈ M a nechť a ≤ b, b ≤ c ; pak a ∧ c = ( a ∧ b ) ∧ c = a ∧ ( b ∧ c ) = a ∧ b = a , odkud a ≤ c , takže relace ≤ je tranzitivní. Nyní dokážeme, že inf {a, b} = a ∧ b, sup {a, b} = a ∨ b . Zřejmě a ∧ b ≤ a i a ∧ b ≤ b a dále pro libovolné c takové, že c ≤ a, c ≤ b je a ∧ b ∧ c = a ∧ c = c , takže c ≤ a ∧ b . Obdobně se dokáže vztah pro supremum. Uspořádání ≤ je tedy svazové. 2) Ověříme axiomy svazu. Buďte a, b, c ∈ M libovolné prvky.
Snadno se dokáže, že inf {a, b, c} = inf {inf {a, b} , c} . Zaměníme-li prvky a a c , dostaneme
vztah inf {a, b, c} = inf {inf {c, b} , a} . Odtud již ( a ∧ b ) ∧ c = a ∧ ( b ∧ c ) . Obdobně se dokáže asociativní zákon pro spojení. Komutativní zákony jsou zřejmé. Konečně se jednoduše nahlédne, že a ∧ ( a ∨ b ) = inf {a,sup {a, b}} = a , takže operace splňují i axiomy absorpce. □ Pozor V libovolném svazu má infimum i supremum každá konečná množina; snadno se zjistí, že je inf {a1 ,..., ak } = a1 ∧ ... ∧ ak , sup {a1 ,..., ak } = a1 ∨ ... ∨ ak . Pozn. Vidíme, že ve svazech jsou svazové operace velice těsně svázány s odpovídajícím svazovým uspořádáním. Prostřednictvím uspořádání jedna z operací již určuje druhou. Známe-li např. všechny průseky, známe svazové uspořádání, které určuje operaci spojení. Př
1) Buď
( P ( A) ; ∩, ∪ )
svaz všech podmnožin z příkladu...... Pak pro
a, b ∈ P ( A )
je
a ≤ b ⇔ a ∩ b = a ⇔ a ⊆ b , takže svazovým uspořádáním je inkluze. 2) V příkladu.....je svazovým uspořádáním dané lineární uspořádání ≤ . 3) Na množině N 0 uvažme uspořádání | („dělí beze zbytku“). Uspořádání je svazové, pro libovolná k , l ∈ N 0 je inf {k , l} = δ ( k , l ) , sup {k , l} = ν ( k , l ) , a definujeme-li tedy operace
vztahy k ∧ l = δ ( k , l ) , k ∨ l = ν ( k , l ) , získáme svaz. 4) Buďte G grupa, M množina všech jejích podgrup resp. všech jejích normálních podgrup. Definujeme-li na množině M uspořádání ≤ předpisem H ≤ K ⇔ H ⋅ ⊆ K ⋅ , jedná se o
svazové uspořádání, přičemž inf { H , K } = H ∩ K , sup { H , K } = HK , a můžeme tedy mluvit o svazu všech podgrup a svazu všech normálních podgrup dané grupy. 5) Buďte R okruh, M množina všech jeho podokruhů resp. všech jeho ideálů. Definujme na množině M uspořádání ≤ předpisem I ≤ J ⇔ I ⋅ ⊆ J ⋅ ; pak se jedná o svazové
uspořádání, přičemž inf { I , J } = I ∩ J , sup { I , J } = I + J a můžeme tedy mluvit o svazu všech podokruhů a svazu všech ideálů okruhu R . 6) Podobně lze uvažovat svaz všech podmodulů daného modulu a speciálně svaz všech podprostorů vektorového prostoru s uspořádáním inkluzí a s operacemi průnik a součet. 7) Buď M ≠ ∅ množina. Množina E všech ekvivalencí na množině M je svazově uspořádaná inkluzí, přičemž zřejmě inf {a, b} = a ∩ b, sup {a, b} = ∩ {e ∈ E | a ∪ b ⊆ e} a definujeme-li tedy operace vztahy a ∧ b = a ∩ b, a ∨ b = ∩ {e ∈ E | a ∪ b ⊆ e} , je ( E; ∧, ∨ ) svaz. V bodech 1) a 4) jsou svazovým uspořádáním inkluze a průsekem je v obou případech průnik. Operace spojení se však liší: a ∨ b = sup {a, b} , tj. nejmenší horní závora, kterou je v 1) sjednocení množin, avšak ve 4) je to součin podgrup.
L Buď
S = ( M ; ∧, ∨ )
libovolný svaz a nechť
a, b, c ∈ M , přičemž je
a ≤ b . Potom
a ∧ c ≤ b ∧ c, a ∨ c ≤ b ∨ c . Důkaz: Je a ∧ c ∧ b ∧ c = a ∧ c, a ∨ c ∨ b ∨ c = b ∨ c , takže dokazované nerovnosti platí.
□
L Buď S = ( M ; ∧, ∨ ) svaz. Libovolný minimální resp. maximální prvek svazově uspořádané množiny M je již jejím prvním resp. posledním prvkem a nazývá se nulou resp. jednotkou svazu S . Důkaz: Nechť m je minimální prvek v M a buď x ∈ M libovolný prvek; pak m ∧ x ≤ m , takže m ∧ x = m , odkud m ≤ x . □ Př Nulou a jednotkou jsou ve svazech z příkladu.....po řadě ∅, A v 1), 1 a 0 (v tomto pořadí!) v 3), E a G ve 4) a Dg M a M × M v 7). Lineární svaz z bodu 2) nemusí mít nulu ani jednotku. Def
Buď
S = ( M ; ∧, ∨ )
svaz a nechť
N ⊆ M , N ≠ ∅ je množina uzavřená vůči průseku a
spojení, tj. nechť pro libovolná a, b ∈ N je a ∧ b ∈ N , a ∨ b ∈ N . Potom T = ( N ; ∧, ∨ ) (s operacemi zúženými na množinu N) je svaz, o kterém říkáme, že je podsvazem svazu S a píšeme T ⊂⊂ S . Snadno se nahlédne platnost následujícího tvrzení: V Průnik libovolného systému podsvazů svazu S je buď množina prázdná, nebo je to podsvaz svazu S . Př 1) Nejjednoduššími podsvazy jsou určitě svazy jednoprvkové obdahující libovolný prvek svazu; hned za nimi následují podsvazy tvořené libovolnými dvěma srovnatelnými prvky. Obecněji, libovolný řetězec ve svazu je jeho podsvazem. 2) Množinovým svazem rozumíme libovolný podsvaz svazu všech podmnožin nějaké množiny. 3) Buď S = ( M ; ∧, ∨ ) svaz a nechť a, b ∈ M , a ≤ b . Potom množiny
Sa = { x ∈ M | x ≤ a} , S a = { x ∈ M | x ≥ a} , a, b = { x ∈ M | a ≤ x ≤ b} jsou nosiče podsvazů svazu S ; odpovídající svazy budeme značit stejnými symboly. 4) Svaz normálních podgrup grupy je podsvazem svazu všech jejích podgrup. 5) Svaz podgrup grupy G není podsvazem svazu všech podmnožin množiny G ⋅ (při licenci nerozlišující podgrupy a jejich nosiče), neboť svaz podgrup není uzavřený vůči sjednocení. Def Buďte S = ( M ; ∧, ∨ ) , T = ( N ; ∧, ∨ ) libovolné svazy. Zobrazení h : M → N
se nazývá
(svazový) homomorfismus, platí-li pro libovolná x, y ∈ M vztahy
h ( x ∧ y) = h ( x) ∧ h ( y) , h ( x ∨ y) = h ( x) ∨ h ( y) .
Speciální případy homomorfismu svazů se definují stejně jako u grupoidů a okruhů. Snadno se nahlédne, že homomorfní obraz svazu S je podsvazem svazu T . Jsou-li svazy S a T izomorfní, píšeme S ≅ T . L Buďte S = ( M ; ∧, ∨ ) , T = ( N ; ∧, ∨ ) svazy a nechť h : S → T je homomorfismus. Potom h
je izotonní zobrazení. Má-li svaz S nulu 0 nebo jednotku 1 , pak h ( 0 ) je nulou a h (1) jednotkou svazu h ( S ) .
Důkaz: Nechť a, b ∈ M , a ≤ b . Pak h ( a ) ∧ h ( b ) = h ( a ∧ b ) = h ( a ) , takže h ( a ) ≤ h ( b ) . Zvolíme-li a = 0 , je h ( 0 ) ≤ h ( b ) pro libovolné b ∈ M .
□
V Buďte S = ( M ; ∧, ∨ ) , T = ( N ; ∧, ∨ ) svazy. Zobrazení h : M → N je izomorfismem svazů právě tehdy, je-li izomorfismem svazově uspořádaných množin M a N .
Důkaz: Protože oba izomorfismy jsou bijekcemi, stačí dokázat ekvivalenci zbývajících vlastností. Buďte a, b ∈ M . ⇒)
Implikace a ≤ b ⇒ h ( a ) ≤ h ( b ) plyne z předchozího lemmatu. Dokažme opačnou.
Je-li h ( a ) ≤ h ( b ) , pak h ( a ∧ b ) = h ( a ) ∧ h ( b ) = h ( a ) , takže a ∧ b = a , čili a ≤ b .
⇐)
Dokážeme, že
a ∧ b ≤ a , je
Protože
inf {h ( a ) , h ( b )} = h ( a ∧ b ) ;
h (a ∧ b) ≤ h ( a)
d ∈ N , d ≤ h ( a ) , d ≤ h ( b ) ; je
odtud bude h ( a ) ∧ h ( b ) = h ( a ∧ b ) .
a analogicky je
d = h ( c ) pro nějaké
h ( a ∧ b ) ≤ h ( b ) . Dále buď
c∈M a
c ≤ a, c ≤ b , takže
c ≤ a ∧ b , odkud konečně d ≤ h ( a ∧ b ) . Vztah pro spojení se dokáže obdobně. □ Def Ideálem ve svazu S = ( M ; ∧, ∨ ) rozumíme takový podsvaz I ⊂⊂ S , I = ( N ; ∧, ∨ ) , pro který platí ∀a ∈ N ∀s ∈ M ( a ∧ s ∈ N ) . Duálním pojmem k ideálu je filtr. Ideály jsou tedy uzavřené vůči spojení svých libovolných dvou prvků a vůči průseku s libovolným prvkem celého svazu. Obdobně filtry jsou uzavřené vůči průseku svých libovolných dvou prvků a vůči spojení s libovolným prvkem celého svazu. V Buď S = ( M ; ∧, ∨ ) svaz a nechť ekvivalentní: 1) ∀a ∈ N ∀s ∈ M ( a ∧ s ∈ N ) ,
N ⊆ M , N ≠ ∅ . Potom následující podmínky jsou
2) ∀a ∈ N ∀b ∈ M ( b ≤ a ⇒ b ∈ N ) ,
3) ∀a, b ∈ M ( a ∨ b ∈ N
⇒ a, b ∈ N ) .
Důkaz: 1) ⇒ 2) : b = a ∧ b , 2) ⇒ 3) : a ≤ a ∨ b, b ≤ a ∨ b , 3) ⇒ 1) :
(a ∧ s) ∨ a = a ∈ N
, takže
(a ∧ s) ∈ N
□
.
Věta dává jiné, ekvivalentní formulace pojmu ideál. Obdobná věta platí pro filtry. Př 1) Celý svaz je ideálem i filtrem. Podsvazy Sa
S
a
z bodu 2 příkladu......jsou ideály, podsvazy
jsou filtry. Skutečně, Sa je jistě uzavřený vůči menším prvkům a pro b, c ∈ S a je
b ≤ a, c ≤ a , takže i b ∨ c = sup {b, c} ≤ a . Ideál Sa se nazývá hlavní ideál a značí se I a , zatímco filtr S a se značí Fa a říká se mu hlavní filtr. 2) Má-li svaz nulu nebo jednotku, pak podsvaz s nosičem každý ideál obsahuje nulu a každý filtr jednotku.
{0}
resp. {1} je ideál resp. filtr a
3) Buďte
S = ( M ; ∧, ∨ ) , T = ( N ; ∧, ∨ )
svazy,
h : S → T homomorfismus. Má-li svaz
h ( S ) nulu resp. jednotku, pak můžeme definovat jádro Ker0 h resp. pseudojádro Ker1 h
homomorfismu h rovnostmi Ker0 h = { x ∈ M | h ( x ) = 0} , Ker1 h = { x ∈ M | h ( x ) = 1} . Snadno se nahlédne, že jádro je ideál a pseudojádro je filtr ve svazu S .
Úplné svazy Def Řekneme, že svaz je úplný, má-li v něm libovolná podmnožina infimum i supremum. L Libovolný úplný svaz má nulu i jednotku. Důkaz: Buď S = ( M ; ∧, ∨ ) úplný svaz. Pak inf M je nulou, sup M je jednotkou .
□
Př Úplnými svazy jsou každý konečný svaz, dále svaz všech podmnožin, svaz ekvivalencí, svaz všech podgrup a svaz všech normálních podgrup. Naproti tomu lineární svaz všech racionálních čísel není úplný, ale ani lineární svaz všech reálných čísel není úplný, neboť nemá ani nulu, ani jednotku. Množinový svaz také nemusí být úplný. Skutečně, uvažme množinu otevřených intervalů M = {( 0, n ) | n ∈ ℕ} , která je inkluzí lineárně, a tedy svazově uspořádaná a představuje tudíž množinový svaz, který však není úplný, neboť nemá jednotku. V Buď
( M ; ≤)
uspořádaná množina, ve které má libovolná podmnožina infimum. Potom
libovolná podmnožina má v M supremum a definujeme-li pro a, b ∈ M operace rovnostmi
a ∧ b = inf {a, b} , a ∨ b = sup {a, b} ,
je S = ( M ; ∧, ∨ ) úplný svaz.
Důkaz: Buď A ⊆ M . Pro A = ∅ je sup ∅ = inf M . Bud tedy A ≠ ∅ . Označme Z množinu všech horních závor množiny A . Množina Z je neprázdná, neboť obsahuje poslední prvek inf ∅ množiny M . Libovolné a ∈ A je dolní závorou množiny Z, takže pro libovolné a ∈ A je a ≤ inf Z ; to však znamená, že inf Z ∈ Z , a tudíž sup A = inf Z . □ Přirozeně platí i duální věta se záměnou infim a suprem, takže dostáváme Důsl Svaz je úplný právě tehdy, má-li v něm každá podmnožina infimum nebo každá podmnožina supremum. Př V uspořádané množině
( N 0 ;|)
má každá podmnožina
A ⊆ N 0 infimum - největší dolní
závoru (speciálně inf ∅ = 0 ). Podle předchozí věty je tedy sup A = inf Z , kde Z je množina všech horních závor množiny A . Pro A konečnou je sup A rovno nejmenšímu společnému
násobku čísel z množiny
A , zatímco pro A
nekonečnou je
Z = {0} , takže
sup A = inf {0} = 0 . Definujeme-li operace jako v příkladu....bod3), dostaneme tedy úplný svaz, ve kterém je číslo jedna nulou a číslo nula jednotkou. V o pevném bodě Tarski Buď S = ( M ; ∧, ∨ ) úplný svaz a nechť f : M → M je izotónní zobrazení. Potom existuje
u ∈ M tak, že f ( u ) = u .
Důkaz: Označme U = {a ∈ M | a ≤ f ( a )} , u = sup U . Je U ≠ ∅ , neboť
0 ∈ U . Pro libovolné
a ∈ U je f ( u ) ≥ f ( a ) ≥ a , takže f ( u ) je horní závora množinu U , a tedy f ( u ) ≥ u .
Odtud f ( u ) ≤ f ( f ( u ) ) , čili f ( u ) ∈ U , a tedy f ( u ) ≤ u . Celkem f ( u ) = u .
□
Poznamenejme, že platí také věta obrácená: Má-li libovolné izotónní zobrazení svazu do sebe pevný bod, je tento svaz úplný. Pomocí věty o pevném bodě lze znovu dokázat Cantorovu-Bersteinovu větu....: ( M N et N M ) ⇒ M ≈ N . Nechť M N , N M
a buďte
f : M → N, g : N → M
injekce. Definujme zobrazení
f : P ( M ) → P ( N ) , g : P ( N ) → P ( M ) jako obrazy množin při zobrazeních
f , g , tj.
pro U ⊆ M , V ⊆ N klaďme f (U ) = f (U ) , g (V ) = g (V ) , a zobrazení
h : P ( M ) → P ( M ) předpisem h (U ) = M − g ( N − f (U ) ) .
Zobrazení f , g jsou (vzhledem k uspořádání inkluzí) izotónní, a tedy pro libovolné množiny A ⊆ B ⊆ M platí postupně f ( A) ⊆ f ( B ) ,
g ( N − f ( A) ) ⊇ g ( N − f ( B ) ) ,
h ( A) ⊆ h ( B ) , takže zobrazení h je izotónní na úplném svazu P ⊆ M , pro nějž je odkud
( P ( M ) ; ∩, ∪ ) . Existuje tedy „pevný bod“
P = h ( P) = M − g ( N − f ( P)) , M − P = g ( N − f ( P )) = g ( N − f ( P )) ,
a tedy restrikce zobrazení g −1 na množinu M − P je bijekce na množinu Položíme-li nyní f ( x ) pro x ∈ P h ( x ) = −1 , g ( x ) pro x ∈ M − P je zobrazení h bijekcí množiny M na množinu N . Snadno se nahlédne platnost následujícího tvrzení: V
N − f ( P) .
□
Průnik libovolného systému ideálů svazu S je buď množina prázdná, nebo je to ideál v S . L Průnik konečného systému ideálů ve svazu S je ideál ve svazu S . Důkaz: Buďte { I j | j ∈ J } systém ideálů, J konečná množina. Vyberme po jednom prvku a j ∈ I j a položme a = inf {a j | j ∈ J } .
Pak pro libovolné
j∈J
je a ≤ a j , a tedy a ∈ I j , takže
a∈∩ Ij .
□
j∈J
Průnik nekonečného systému ideálů může být prázdný. Tak např. v lineárním svazu celých čísel uvažme hlavní ideály I n = { z ∈ Z | z ≤ n} ; pak ∩ I n = ∅ . n∈Z
L Průnik libovolného systému ideálů ve svazu S s nulou (speciálně v úplném svazu) je ideál ve svazu S . Důkaz: Všechny ideály obsahují nulu, takže jejich průnik je neprázdný. □ Ozn Označme I S množinu všech ideálů a HS množinu všech hlavních ideálu ve svazu S . Buď S = ( M ; ∧, ∨ )
svaz s nulou. Množina
IS
je uspořádaná inkluzí a pro
libovolnou množinu N ⊆ I S existuje inf N = ∩ N , což je ideál v S . Podle věty.....má tedy libovolná množina N ⊆ I supremum a odpovídající svaz je úplný. Přitom je sup N = inf Z , kde Z je množina všech horních závor množiny N . Jinými slovy,
sup N = ∩ { K ∈ I S | ∀I ∈ N ( I ⊆ K )} . Sestrojili jsme úplný svaz
operacemi danými rovnostmi I ∧ J = I ∩ J , nazývá svaz ideálů svazu S . L Hlavní ideály tvoří podsvaz
( HS ; ∧, ∨ )
T = ( I S ; ∧, ∨ )
s
I ∨ J = ∩ { K ∈ IS | I ∪ J ⊆ K } . Svaz T se
svazu T = ( I S ; ∧, ∨ ) .
Důkaz: Buďte a, b ∈ M . Předně je I a ∧ I b = I a ∩ I b = { x | x ≤ a et
x ≤ b} = { x | x ≤ a ∧ b} = I a ∧b .
Dále, je-li x ∈ I a ∪ I b , pak x ≤ a ∨ b , a tedy x ∈ I a ∨ b ; odtud I a ∪ I b ⊆ I a ∨ b , ale pak také I a ∨ I b ⊆ I a ∨ b . Naopak, a, b ∈ I a ∨ I b , tudíž také a ∨ b ∈ I a ∨ I b , a tedy I a ∨ b ⊆ I a ∨ I b .
Celkem tedy I a ∨ I b = I a ∨ b . Def Řekneme, že svaz S lze izomorfně vnořit do svazu h : S → T . Pak je tedy S ≅ h ( S ) ⊂⊂ T .
□
T , existuje-li monomorfismus
Lze dokázat, že libovolný svaz lze izomorfně vnořit do nějakého svazu ekvivalencí a také do svazu všech podgrup vhodné grupy. V Libovolný svaz lze izomorfně vnořit do úplného svazu. Důkaz: Buď S = ( M ; ∧, ∨ ) libovolný svaz. Budeme předpokládat, že svaz S má nulu. (V opačném případě můžeme definovat svaz
S ′ = ( M ′; ∧, ∨ ) , kde položíme
M ′ = M ∪ {0}
a
dodefinujeme, že pro libovolné a ∈ M je 0 < a , a svaz S lze pak jistě izomorfně vnořit do svazu S ′ , a složení dvou monomorfismů je monomorfismus.) Definujme zobrazení h : M → IS předpisem h ( a ) = I a . Jelikož ze vztahu h ( a ) = h ( b ) snadno plyne rovnost a = b , je zobrazení h injekcí, a je tedy bijekcí na množinu HS všech hlavních ideálů svazu S . Dále, nerovnost a ≤ b platí právě tehdy, když I a ⊆ I b , takže zobrazení h je izomorfismem uspořádané množiny
( M ;≤)
na uspořádanou množinu
( HS ; ⊆ ) . Podle věty....to však je totéž, jako že zobrazení h je izomorfismem svazu svaz ( HS ; ∧, ∨ ) . Svaz S jsme izomorfně vnořili do úplného svazu T = ( I S ; ∧, ∨ ) .
S na □
Distributivní svazy Def Řekneme, že svaz S = ( M ; ∧, ∨ ) je distributivní, pokud pro libovolná a, b, c ∈ M platí
( D1 ) ( D2 )
a ∧ (b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ) ,
a ∨ (b ∧ c) = ( a ∨ b) ∧ ( a ∨ c) .
L Z rovnosti D1 plyne rovnost D2 (a ovšem i naopak). Důkaz: ( a ∨ b ) ∧ ( a ∨ c ) = (( a ∨ b) ∧ a ) ∨ (( a ∨ b ) ∧ c ) = a ∨ ( a ∧ c ) ∨ (b ∧ c ) = a ∨ (b ∧ c )
□
L Buď S = ( M ; ∧, ∨ ) libovolný svaz. Potom pro libovolná a, b, c ∈ M platí vztahy a ∧ (b ∨ c ) ≥ ( a ∧ b) ∨ ( a ∧ c ) , a ∨ (b ∧ c ) ≤ ( a ∨ b) ∧ ( a ∨ c ) ,
a je-li a ≤ c, pak a ∨ ( b ∧ c ) ≤ ( a ∨ b ) ∧ c .
Důkaz: Protože b ≤ b ∨ c, c ≤ b ∨ c , je a ∧ b ≤ a ∧ ( b ∨ c ) , a ∧ c ≤ a ∧ ( b ∨ c ) , z čehož již plyne první nerovnost. Druhá se dokáže analogicky a třetí je důsledkem druhé. □ Zaveďme nerovnosti, které jsou opačné k prvním dvěma nerovnostem z předchozího lemmatu:
( N1 ) a ∧ ( b ∨ c ) ≤ ( a ∧ b ) ∨ ( a ∧ c ) ,
(N2 ) a ∨ (b ∧ c ) ≥ ( a ∨ b ) ∧ ( a ∨ c ) , V Svaz S = ( M ; ∧, ∨ ) je distributivní právě tehdy, platí-li pro libovolná a, b, c ∈ M kterákoli z nerovností N1 nebo N 2 . Důkaz: Přímá implikace je jasná, opačná plyne z předchozích dvou lemmat.
□
Př Distributivními svazy jsou: 1) Libovolný množinový svaz. 2) Libovolný lineární svaz. Skutečně, vzhledem k lemmatu.....stačí dokázat rovnost D1 , která nabude tvar min {a, max {b, c}} = max {min {a, b} , min {a, c}} . Je-li a ≤ b, c , pak na obou stranách rovnosti je a . Je-li naopak
a ≥ b, c , potom na obou
stranách rovnosti je max {b, c} . Je-li prvek a „ostře mezi“ prvky b,c, pak na obou stranách rovnosti je a . 3) Svaz ( ℕ; ∧, ∨ ) z příkladu..... Dokažme rovnost D1 . Buďte p1 ,..., pn ∈ P, ki , li , mi ∈ N 0 taková čísla, že n
n
n
i =1
i =1
i =1
a = ∏ pi ki , b = ∏ pi li , c = ∏ pi mi
.
Pak je n
min k ,max{li , mi }} a ∧ ( b ∨ c ) = δ ( a,ν ( b, c ) ) = ∏ pi { i
,
i =1
n
( a ∧ b ) ∨ ( a ∧ c ) = ν (δ ( a, b ) , δ ( a, c ) ) = ∏ pi max{min{k ,l },min{k ,m }} i i
i
i
,
i =1
a stačí tedy pro libovolná k , l , m ∈ N 0 dokázat rovnost
min {k , max {l , m}} = max {min {k , l} , min {k , m}} , která je však zvláštním případem rovnosti dokázané v předešlém příkladě. Snadno se ověří platnost následujícího tvrzení: V Libovolný podsvaz i libovolný homomorfní obraz distributivního svazu je distributivní svaz.
Množinové svazy jsou distributivní a libovolný distributivní svaz je izomorfní s nějakým množinovým svazem. To je obsahem věty, při jejímž důkazu budeme pracovat se speciálními filtry, tzv. ultrafiltry. Def Filtr F ve svazu S = ( M ; ∧, ∨ ) se nazývá ultrafiltrem, je-li F ≠ M a pro a, b ∈ M platí
a ∨ b∈ F
⇒
(a ∈ F
vel b ∈ F ) .
Př Buďte M ≠ ∅ libovolná množina, m ∈ M . Pak hlavní filtr F{m} = { N ⊆ M | {m} ⊆ N } je ultrafiltrem ve svazu všech podmnožin mnořiny M . Skutečně, je-li zřejmě
{m} ⊆ A
nebo
{m} ⊆ B
{m} ⊆ A ∪ B
, pak
. Je-li však množina C ⊆ M alespoň dvouprvková, pak
hlavní filtr FC již není ultrafiltrem. Označení 1) Označme FS množinu všech filtrů, US množinu všech ultrafiltrů svazu S .
2) Buďte S = ( M ; ∧, ∨ ) svaz, ∅ ≠ N ⊆ M . Označme
N
N = ∩ { F ∈ FS | N ⊆ F } . Pak
je zřejmě filtr – nejmenší filtr obsahující množinu N .
L Buďte F filtr ve svazu S = ( M ; ∧, ∨ ) , a0 ∈ M . Potom
F ∪ {a0 } = {a ∈ M | ∃c ∈ F ⋅ ( a ≥ c ∧ a0 )} . ⋅
Důkaz: Množina na pravé straně je filtr (uzavřenost vůči větším prvkům je zřejmá a dále z nerovností a1 ≥ c1 ∧ a0 , a2 ≥ c2 ∧ a0 plyne nerovnost a1 ∧ a2 ≥ c1 ∧ c2 ∧ a0 ), a přitom je podmnožinou
libovolného filtru obsahujícího množinu F ∪ {a0 } .
□
L Buď S = ( M ; ∧, ∨ ) distributivní svaz. Potom pro libovolné prvky a, b ∈ M takové, že není a ≤ b , existuje takový ultrafiltr F ∈ US , pro který a ∈ F , b ∉ F . Důkaz: Buď F inkluzí uspořádaná množina všech filtrů F ∈ FS , pro které je a ∈ F , b ∉ F . Je F ≠ ∅ , neboť hlavní filtr Fa ∈ F . Obvyklým způsobem se dokáže, že libovolný řetězec R
v množině F má horní závoru
∪R
, která patří do F , neboť také a ∈ ∪ R , b ∉ ∪ R .
Podle Zornova lemmatu existuje v F alespoň jeden maximální prvek, označme jej F 0 . Nyní stačí dokázat, že F 0 je ultrafiltr. Nechť tomu tak není. Potom (protože jistě není F 0 = M ) existují a1 , a2 ∈ M tak, že a1 ∨ a2 ∈ F 0 , ale a1 ∉ F 0 , a2 ∉ F 0 . Pro i = 1, 2 položme F i = F 0 ∪ {ai } . Dokážeme, že b ∉ F 1 nebo b ∉ F 2 - to bude spor s maximálností filtru F 0 . Nechť tomu tak není, tj. nechť b ∈ F 1 ∩ F 2 . Pak dle lemmatu .... existují c1 , c2 ∈ F 0 tak, že
b ≥ c1 ∧ a1 , b ≥ c2 ∧ a2 a položíme-li c = c1 ∧ c2 , je c ∈ F 0 , b ≥ c ∧ a1 , b ≥ c ∧ a2 , odkud
b ≥ ( c ∧ a1 ) ∨ ( c ∧ a2 ) = c ∧ ( c ∨ a2 ) ∧ ( a1 ∨ c ) ∧ ( a1 ∨ a2 ) = c ∧ ( a1 ∨ a2 ) ∈ F 0 ,
a tedy b ∈ F 0 , a to je spor. Je tedy např. b ∉ F 1 , takže F1 ∈ F a přitom F 0 F 1 , což je spor. Dokázali jsme, že F 0 je ultrafiltr požadovaných vlastností. V Stone
□
Libovolný distributivní svaz je izomorfní s nějakým množinovým svazem. Důkaz: Buď S = ( M ; ∧, ∨ ) distributivní svaz a uvažme množinový svaz T = ( P ( US ) ; ∩, ∪ ) .
Definujme zobrazení h : M → P ( US ) předpisem h ( x ) = { F ∈ US | x ∈ F } a dokažme, že je to monomorfismus. Buďte a, b ∈ M . Potom
( non ( a ≤ b ) vel non ( b ≤ a ) ) ⇒ , ∃F ∈ U ( ( a ∈ F et b ∉ F ) vel ( b ∈ F et a ∉ F ) ) ⇒ ∃F ∈ U ( F ∈ h ( a ) − h ( b ) vel F ∈ h ( b ) − h ( a ) ) ⇒ h ( a ) ≠ h ( b )
a≠b ⇒ ⇒ ⇒
S S
takže h je prosté. Dále, pro libovolné F ∈ US je
F ∈ h ( a ∧ b) ⇔ a ∧ b ∈ F ⇔
( F ∈ h (a)
⇔
F ∈ h (b )) ⇔
et
takže h ( a ∧ b ) = h ( a ) ∩ h ( b ) , a konečně
F ∈ h ( a ∨ b) ⇔ a ∨ b ∈ F ⇔
( F ∈ h (a)
a tedy h ( a ∨ b ) = h ( a ) ∪ h ( b ) .
(a ∈ F
vel
⇔
et b ∈ F ) ⇔
F ∈ h ( a ) ∩ h (b )
(a ∈ F
vel b ∈ F ) ⇔
F ∈ h (b )) ⇔ F ∈ h ( a ) ∪ h (b )
,
,
□
Modulární svazy Některé důležité svazy, jako např. svaz všech normálních podgrup dané grupy nejsou obecně distributivní. V této kapitole zobecníme distributivní svazy na svazy modulární, vyšetříme jejich základní vlastnosti a mimo jiné ukážeme, že výše zmíněné svazy jsou modulární. Při definici modulárních svazů vyjdeme od rovností D1 a D2 , nebudeme však žádat jejich splnění pro libovolné prvky a, b, c , ale jen pro ty, které splňují nerovnost a ≤ c . Pak první rovnost je splněna vždy, zatímco druhá dává vztah (M ) a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ c . Def Řekneme, že svaz S = ( M ; ∧, ∨ ) je modulární, pokud pro libovolná a, b, c ∈ M taková, že
a ≤ c platí rovnost (M) . Ihned vidíme, že platí V Libovolný distributivní svaz je modulární. V Svaz všech normálních podgrup libovolné grupy je modulární. Důkaz: Buďte G grupa, A, B, C její normální podgrupy a nechť A⋅ ⊆ C ⋅ . Z lemmatu......víme, že
platí inkluze A ( B ∩ C ) ⊆ ( AB ) ∩ C . Stačí tudíž dokázat opačnou inkluzi, tj. vztah
( AB ) ∩ C ⋅ ⊆ ( A ( B ∩ C ) )
⋅
⋅
a ∈ A⋅ , b ∈ B⋅ ; dále,
. Nechť
x ∈ ( AB ) ∩ C ⋅ ; pak (viz lemma....) ⋅
b = a −1 x ∈ C ⋅ , neboť
A⋅ ⊆ C ⋅ , takže
x ∈ ( A( B ∩ C )) . ⋅
x = ab , kde
b ∈ C ⋅ . Celkem □
Důsl. Svaz všech podgrup libovolné Abelovy grupy je modulární. Uvidíme (příklad......), že svaz všech podgrup libovolné grupy již nemusí být modulární. L Svaz S = ( M ; ∧, ∨ ) je modulární právě tehdy, když pro libovolná a, b, c ∈ M platí rovnost
a ∨ (b ∧ ( a ∨ c )) = ( a ∨ b ) ∧ ( a ∨ c ) .
Důkaz: ⇒ ) Ihned dosazením prvku a ∨ c za c do rovnosti (M). ⇐ ) Z předpokladu a ≤ c plyne ihned rovnost (M) .
□
Snadno se ověří následující V Libovolný podsvaz i libovolný homomorfní obraz modulárního svazu je modulární svaz. V Svaz všech podmodulů libovolného modulu je modulární. Svaz všech ideálů libovolného netriviálního asociativního okruhu s jednotkou je modulární. Důkaz: První ze svazů je podsvazem modulárního svazu všech podgrup „nosné“ Abelovy grupy. Dále, uvážíme-li aditivní grupu okruhu R jako modul nad okruhem R (srv. příklad......), jsou jeho podmoduly právě všechny levé ideály okruhu R a svaz všech ideálu je podsvazem svazu □ všech levých ideálů. Def Buď S svaz s nulou a jednotkou. Konečná posloupnost A = ( a0 , a1 ,..., am ) prvků svazu S se nazývá normální řadou ve svazu S , jestliže a0 = 1, am = 0 a pro libovolné i ∈ mˆ je
ai < ai −1 . Číslo m nazveme délkou řady A . Normální řada B = ( b0 , b1 ,..., bn ) se nazývá
zjemněním řady A , pokud pro každé i ∈ mˆ existuje j ∈ nˆ tak, že ai = b j . Je-li navíc n > m , hovoříme o vlastním zjemnění. S normálními řadami jsme se setkali v kapitole o grupách. Normální řada v modulárním svazu všech normálních podgrup libovolné grupy je zřejmě normální řadou ve smyslu definice.....Pro normální řady v grupách platí Schreierova věta; její obdobou v modulárních svazech je následující V (Schreier) Libovolné dvě normální řady v modulárním svazu S mají zjemnění stejných délek. Důkaz: Buďte A = ( a0 , a1 ,..., am ) , B = ( b0 , b1 ,..., bn ) libovolné normální řady ve svazu S. Definujme
aij = ai ∨ ( ai −1 ∧ b j )
( i ∈ mˆ , b ji = b j ∨ ( b j −1 ∧ ai ) ( j ∈ nˆ,
j = 0,1,..., n ) i = 0,1,..., m )
a vytvořme posloupnosti Aɶ = ( a10 , a11 ,..., a1n , a20 , a21 ,..., a2 n ,..., am 0 , am1 ,..., amn ) . Bɶ = ( b , b ,..., b , b , b ,..., b ,..., b , b ,..., b ) 10
11
1m
20
21
2m
n0
n1
nm
Pro i ∈ mˆ je ai 0 = ai −1 , ain = ai , takže ai −1n = ai 0 ( i = 2,..., m ) , a protože b j < b j −1 , je aij ≤ aij −1 ( i ∈ mˆ , j ∈ nˆ ) . Posloupnost Aɶ je tedy nerostoucí a vynecháním opakujících se členů z ní získáme zjemnění řady A . Totéž platí o vztahu posloupnosti Bɶ k řadě B . ⌢ ⌢ Označme A resp. B posloupnosti vzniknuvší z posloupnosti Aɶ resp. Bɶ vynecháním opakujících se prvků a20 , a30 ,..., am 0 resp. b20 , b30 ,..., bn 0 . Protože
m ( n + 1) − ( m − 1) = mn + 1 = n ( m + 1) − ( n − 1) , ⌢ ⌢ mají posloupnosti A a B stejný počet členů. ⌢ ⌢ Nyní stačí dokázat, že posloupnosti A a B mají stejný počet opakujících se členů. Nechť tedy pro nějaká i ∈ mˆ , j ∈ nˆ je aij −1 = aij (přičemž symbol ai 0 označuje prvek ai −1n ); dokážeme, že pak bude b ji −1 = b ji , odkud již (vzhledem k symetrii) tvrzení plyne. Nejdříve provedeme pomocný výpočet, ve kterém postupně využijeme definice prvku aij −1 a axiomu absorpce, předpokladu
aij −1 = aij , nerovnosti
aij ≤ ai −1 , definice prvku
aij a nakonec
modularity spolu s nerovností ai −1 ∧ b j ≤ b j −1 :
ai −1 ∧ b j −1 = aij −1 ∧ ( ai −1 ∧ b j −1 ) = aij ∧ ai −1 ∧ b j −1 = aij ∧ b j −1 =
(
)
= ( ai −1 ∧ b j ) ∨ ai ∧ b j −1 = ( ai −1 ∧ b j ) ∨ ( ai ∧ b j −1 )
Potom je
.
b ji −1 = b j ∨ ( b j −1 ∧ ai −1 ) = b j ∨ ( ai −1 ∧ b j ) ∨ ( ai ∧ b j −1 ) = b j ∨ ( ai ∧ b j −1 ) = b ji .
□
Def Normální řada, která nemá vlastní zjemnění, se nazývá hlavní. Podobně jako u grup je snadným důsledkem Schreierovy věty V (Jordan, Hölder) Buď S modulární svaz s nulou a jednotkou. Všechny hlavní řady v S mají stejnou délku. Existuje-li v S nějaká hlavní řada, lze libovolnou normální řadu zjemnit na řadu hlavní. Buďte S = ( M ; ∧, ∨ ) svaz, a, b ∈ M , a < b . Víme, že interval a, b je podsvazem svazu S ; v následující větě, která je obdobou první věty o izomorfismu pro grupy, jej pro větší názornost označíme b / a . V Buďte S = ( M ; ∧, ∨ ) modulární svaz, a, b ∈ M . Potom
(a ∨ b) / a ≅ b / (a ∧ b)
Důkaz:
.
Definujme zobrazení
f : ( a ∨ b) / a → b / (a ∧ b) , g : b / (a ∧ b) → (a ∨ b) / a
f ( x ) = x ∧ b, g ( x ) = x ∨ a . Pro libovolné x ∈ a, a ∨ b
předpisy
je (s využitím modularity)
g ( f ( x )) = g ( x ∧ b) = a ∨ (b ∧ x ) = ( a ∨ b) ∧ x = x .
Analogicky se ukáže, že pro x ∈ a ∧ b, b je f ( g ( x ) ) = x . Každé ze zobrazení gf , fg je tak identické, a tedy obě zobrazení f i g jsou bijekcemi. Dále, je-li x ≤ y , pak f ( x ) ≤ f ( y ) , g ( x ) ≤ g ( y ) , a také naopak:
f ( x ) ≤ f ( y ) ⇒ g ( f ( x )) ≤ g ( f ( y )) ⇒ x ≤ y . Celkem je zobrazení f izomorfismem uspořádaných množin, a tedy dle ...... je izomorfismem svazu ( a ∨ b ) / a na svaz b / ( a ∧ b ) . □ Buď S modulární svaz s nulou a jednotkou, ve kterém existuje hlavní řada a buď a ∈ S . Potom v podsvazu a / 0 existuje také hlavní řada, její délku označme a ; skutečně, ⋅
je-li A = ( a0 , a1 ,..., am ) hlavní řada, která je zjemněním normální řady nějaké k ∈ mˆ je ak = a a
( ak ,..., am )
(1, a, 0 )
, pak pro
je hlavní řada ve svazu a / 0 , přičemž a = m − k .
V Buď S modulární svaz s nulou a jednotkou, ve kterém existuje hlavní řada a buďte a, b ∈ S ⋅ . Potom a ∨ b = a + b − a ∧ b .
Důkaz: Délky hlavních řad ve svazech ( a ∨ b ) / a a b / ( a ∧ b ) avšak dle předchozí věty jsou uvedené délky stejné.
jsou
a∨b − a a b − a∧b , □
Př Buď S svaz všech podprostorů vektorového prostoru konečné dimenze. Svaz S je modulární a má nulu i jednotku. Hlavní řady jsou posloupnosti podprostorů ( P0 , P1 ,..., Pn ) takových, že
P0 = V , Pn = {o} a ∀i ∈ nˆ ( dim Pi −1 = dim Pi + 1) . Dále zřejmě Pi = dim Pi
( i = 0,..., n )
.Z
věty..... plyne, že pro libovolné podprostory P, Q platí
dim ( P + Q ) = dim P + dim Q − dim ( P ∩ Q ) , což je věta o dimenzi známá z lineární algebry.
Komplementární svazy Def Buď S svaz s nulou a jednotkou. Prvek a′ ∈ S ⋅ se nazývá komplementem prvku a ∈ S ⋅ , pokud a ∧ a′ = 0, a ∨ a′ = 1 . Svaz, ve kterém má libovolný prvek alespoň jeden komplement, se nazývá komplenentární. Př 1) Komplementem nuly je jednotka, komplementem jednotky je nula. 2) Svaz S všech podmnožin libovolné neprázdné množiny A je komplementární: nulou svazu je prázdná množina, jednotkou množina A , množinový komplement je svazovým
komplementem. Komplementární však již nemusí být jakýkoli množinový svaz, tj. podsvaz svazu S . 3) Žádný lineární svaz, mající alespoň tři prvky, není komplementární. 4) Uvažme svaz N 5 obsahující pět prvků 0,1, a, b, c , přičemž 0 je nulou, 1 je jednotkou, a < c a prvek b je nesrovnatelný s prvky a a c. Pak prvek b má dva různé, a přitom srovnatelné komplementy, totiž a a c. Tento svaz se nazývá pentagon. Vidíme, že to není svaz modulární, neboť má dvě hlavní řady rozdílných délek. 5) Jiným svazem na stejných pěti prvcích je svaz M5 , tzv. diamant, ve kterém jsou prvky a, b, c po dvou nesrovnatelné. Zde má kterýkoli z těchto tří prvků za komplement libovolný ze dvou zbývajících - nesrovnatelných - prvků. V Buď S modulární svaz s nulou a jednotkou a nechť a1 , a2 jsou komplementy prvku a ∈ S ⋅ takové, že a1 ≤ a2 . Potom a1 = a2 .
Důkaz: a1 = a1 ∨ 0 = a1 ∨ ( a ∧ a2 ) = ( a1 ∨ a ) ∧ a2 = 1 ∧ a2 = a2
□
V modulárních svazech nemůže mít tedy žádný prvek dva různé srovnatelné komplementy. Některý prvek může však mít různé nesrovnatelné komplementy, jak tomu je ve svazu M5 , který je modulární, avšak není distributivní. V distributivních svazech není již možný ani tento případ. V Buď S distributivní svaz s nulou a jednotkou. Pak libovolný prvek má nejvýše jeden komplement. Důkaz: Buďte a1 , a2 komplementy prvku a ∈ S ⋅ . Pak
a1 = a1 ∨ 0 = a1 ∨ ( a ∧ a2 ) = ( a1 ∨ a ) ∧ ( a1 ∨ a2 ) = 1 ∧ ( a1 ∨ a2 ) = ( a1 ∨ a2 ) ,
takže a2 ≤ a1 , a tedy dle předchozí věty je a1 = a2 .
□
V Svaz je modulární právě tehdy, neobsahuje-li jako podsvaz pentagon. Důkaz: Místo obou implikací dokážeme jejich transpozice. ⇒ ) Nechť svaz S obsahuje jako podsvaz pentagon N 5 . Potom je sice a < c , ale
( a ∨ b ) ∧ c = c ≠ a = a ∨ (b ∧ c )
,
takže S není modulární. ⇐ ) Buď S svaz, který není modulární. Pak existují prvky a, b, c ∈ S ⋅ takové, že a ≤ c , ale
( a ∨ b ) ∧ c > a ∨ (b ∧ c )
. Zřejmě a < c a prvek b není srovnatelný ani s a , ani s c ;
skutečně, pro žádný z případů b ≤ a, b ≥ a, b ≤ c, b ≥ c není splněna hořejší ostrá nerovnost. Nyní prvky a, c, b ∨ c, b, a ∧ b tvoří pentagon, který je podsvazem svazu S. Skutečně, buďte d , e prvky různé od zmíněných pěti a nechť b ∧ c = d ≠ a ∧ b ; je buď a ∨ b = c ∨ b , a pak c > c , nebo a ∨ b = e ≠ c ∨ b , ale pak a > c ; odtud b ∧ c = a ∧ b . Podobně musí být a ∨ b = c ∨ b . □
Pozn Svaz s nulou a jednotkou, ve kterém existuje hlavní řada a který obsahuje pentagon, není ovšem modulární, neboť má různě dlouhé hlavní řady. Stejná délka hlavních řad však ještě k modularitě nestačí, jak ukazuje příklad hexagon.... OBR Obdobně jako větu ..... lze dokázat následující tvrzení. V Svaz je distributivní právě tehdy, neobsahuje-li diamant ani pentagon. Př Uvažme svaz S všech podgrup alternující grupy A4 . Jednotkou svazu je celá grupa A4 , nulou triviální grupa E a netriviálními podgrupami jsou Kleinova grupa K 4 , její podgrupy
{
}
L12 , L22 , L32 , kde např. L12 = (1) ( (1, 2 )( 3, 4 ) ) a dále čtyři tříprvkové podgrupy A31 , A32 , A33 , A34 ,
kde např. A31 = {(1) , (1, 2,3)(1,3, 2 )} .
OBR Vidíme, že svaz S není modulární, neboť jeho podsvazem je pentagon tvořený prvky E , L12 , K 4 , A4 , A31 . Současně vidíme, že svaz všech normálních (všechny jsou normální!) podgrup grupy K 4 není distributivní.
Booleovy svazy a algebry Def Svaz s nulou a jednotkou se nazývá Booleův, je-li současně komplementární a distributivní. V Booleově svazu má tedy libovolný prvek právě jeden komplement a můžeme tedy přidat ke svazovým operacím další, unární operaci „přiřazení komplementu“; tak dospějeme k pojmu Booleova algebra. Def Booleova algebra je algebra A = ( M ; ∧, ∨,′ ) , kde
( M ; ∧, ∨ )
je Booleův svaz, ´ je unární operace a pro libovolný prvek a ∈ M platí rovnosti a ∧ a′ = 0, a ∨ a′ = 1 .
V Buďte A = ( M ; ∧, ∨,′ ) Booleova algebra, a, b ∈ M . Potom platí 1)
( a′ )′ = a
3)
( a ∧ b )′ = a′ ∨ b′, ( a ∨ b )′ = a′ ∧ b′,
, 0′ = 1, 1′ = 0 , 2) a ∧ b = 0 ⇔ b ≤ a′ , a ∨ b = 1 ⇔ b ≥ a′ , 4) a ≤ b ⇔ a′ ≥ b′ .
První vlastnost v bodě 2 říká, že komplement prvku a je největší ze všech prvků, které mají s prvkem a nulový průsek; obdobně druhá vlastnost. Důkaz: Vlastnosti v bodě 1 jsou zřejmé. Dokažme první ekvivalenci v 2). Je-li a ∧ b = 0 , pak b = b ∧ 1 = b ∧ ( a ∨ a ′ ) = ( b ∧ a ) ∨ ( b ∧ a′ ) = 0 ∨ ( b ∧ a ′ ) = ( b ∧ a ′ ) , takže b ≤ a′ . Je-li naopak b ≤ a′ , pak a ∧ b ≤ a ∧ a′ = 0 , odkud a ∧ b = 0 . Dále je ( a ∧ b ) ∨ ( a′ ∨ b′) = ( a ∨ a′ ∨ b′ ) ∧ ( b ∨ a′ ∨ b′ ) = 1,
( a ∧ b ) ∧ ( a′ ∨ b′) = ( a ∧ b ∧ a′ ) ∨ ( a ∧ b ∧ b′) = 0,
odkud plyne první rovnost v 3). Konečně, s využitím právě dokázaných de Morganových zákonů, dostaneme a ≤ b ⇒ a ∧ b = a ⇒ a ′ ∨ b′ = a ′ ⇒ a ′ ≥ b′ . Def Podalgebrou Booleovy algebry
A = ( M ; ∧, ∨,′ )
B = ( N ; ∧, ∨,′ ) takovou, že N ⊆ M průseku, spojení a komplementu.
□
rozumíme libovolnou Booleovu algebru
je (neprázdná) množina, která je uzavřená vůči
Př 1) Asi nejznámější Booleovou algebrou je algebra všech podmnožin nějaké množiny. Její podalgebry se nazývají množinové Booleovy alghebry. Zdaleka ne každý její podsvaz je však její podalgebrou. 2) Vyloučíme-li příliš triviální případ jednoprvkové algebry, je nejjednodušší dvouprvková algebra tvořená pouze prvky 0 a 1, která hrála roli v Booleově algebraizaci výrokového kalkulu. Def Buďte
A = ( M ; ∧, ∨,′ ) ,
B = ( N ; ∧, ∨,′ )
Booleovy algenry. Řekneme, že zobrazení
h:M → N
je homomorfismus, je-li homomorfismem odpovídajících svazů, a navíc pro libovolný prvek a ∈ M platí rovnost h ( a′ ) = h ( a )′ . V Filtr F v Booleově svazu S = ( M ; ∧, ∨ ) je ultrafiltrem právě tehdy, když
∀x ∈ M ( x ∈ F
⇔
x′ ∉ F ) .
Důkaz: ⇒ ) Buďte F ultrafiltr, x ∈ M . Je x ∨ x′ = 1 ∈ F , takže x ∈ F vel x′ ∈ F . Přitom nemůže být x, x′ ∈ F , neboť pak by bylo 0 = x ∧ x′ ∈ F , odkud F = M , což není možné. ⇐ ) Buďte F filtr, x, y ∈ M a nechť x ∨ y ∈ F ; pak x′ ∧ y′ = ( x ∨ y )′ ∉ F , čili x′ ∉ F , nebo y′ ∉ F , ale potom x ∈ F nebo y ∈ F . V Libovolná Booleova algebra je izomorfní s nějakou množinovou Booleovou algebrou. Důkaz:
Buď A = ( M ; ∧, ∨,′ ) libovolná Booleova algebra. Distributivní svaz S = ( M ; ∧, ∨ ) lze dle věty......izomorfně vnořit do množinového svazu T = ( P ( US ) ; ∩, ∪ ) , přičemž příslušným
monomorfismem je zobrazení dané předpisem h ( x ) = { F ∈ US | x ∈ F } . Obraz h ( S ) je tedy
množinovým svazem izomorfním se svazem S . Dále, pro libovolné x ∈ M platí h ( 0 ) = { F ∈ U S | 0 ∈ F } = ∅,
h (1) = { F ∈ US | 1∈ F } = US ,
.
h ( x′ ) = { F ∈ U S | x′ ∈ F } = { F ∈ U S | x ∉ F } = U S − h ( x ) = ∁ ( h ( x ) ) Odtud plyne, že svaz
h(S )
obsahuje nulu a jednotku a s každým prvkem také jeho
komplement, takže je podalgebrou algebry ( P ( US ) ; ∩, ∪, ∁ ) . Z posledního vztahu též vidíme, že zobrazení h je monomorfismem Booleových algeber. Celkem, množinovou Booleovou algebrou izomorfní s algebrou A .
( h ( M ) ; ∩, ∪, ∁ )
je
□
V Libovolná konečná Booleova algebra je izomorfní s množinovou Booleovou algebrou všech podmnožin vhodné konečné množiny. V Konečná Booleova algebra s r prvky existuje právě tehdy, je-li Libovolné dvě konečné Booleovy algebry téhož řádu jsou izomorfní.
r = 2 n , kde
n∈ℕ .
