Zdrojový kód
%\wikiskriptum{01ALG}
\xxx{Teorie svazů}
\xxxx{Svazy}
\define
\defined[svaz]{Svazem} (angl. \defined{lattice}) rozumíme algebru $S=(M,\SA,\SV)$
se dvěma binárními operacemi takovou, že pro libovolné $a,b,c\in M$ platí:
\begin{enumerate}
\item
$a\SA b=b\SA a$, \; $a\SV b=b\SV a$ (komutativní zákon);
\item
$(a\SA b)\SA c=a\SA (b\SA c)$, \; $(a\SV b)\SV c=a\SV (b\SV c)$ (asociativní zákon);
\item
$a\SA (b\SV a)=a$, \; $a\SV(b\SA a)=a$ (\defined[zákon!absorpce]{zákon absorpce}).
\end{enumerate}
Operaci $\SA$ nazýváme \defined[průsek]{průsek} a operaci $\SV$ \defined[spojení]{spojení}.
\lemma
Ve svazu $S=(M,\SA,\SV)$ platí pro libovolný prvek $a\in M$, že $a\SA a=a$ a $a\SV a=a$
(tzv. \defined[idempotentnost]{idempotentnost})
\proof
$a\SA a=a\SA(a\SV(b\SA a))=a$, druhá rovnost symetricky.
\QED
\theorem(princip duality v teorii svazů)
Máme-li formuli v~teorii svazů, která platí ve všech svazech,
pak duální formule vzniklá prohozením operací průseku a spojení opět platí ve všech svazech.
\xxxx{Svazově uspořádaná množina}
\remark
Připomeneme důležité pojmy pro uspořádané množiny $(M,\leq)$.
\begin{enumerate}
\item
Horní závora množiny $A\sse M$ je každé takové $a\in M$, že $(\AA x\in A)(x\leq a)$.
\item
Má-li množina horních závor první prvek, nazveme jej supremum $A$.
Pro $s=\sup A$ platí:
\begin{enumerate}
\item $(\AA a\in A)(a\leq s)$;
\item $\bigl(\AA t\in M\bigr)\bigl((\AA a\in A)(a\leq t)\Limpl s\leq t\bigr)$.
\end{enumerate}
\item
$\sup \emptyset$ je první prvek množiny $M$ (pokud existuje).
\item
$\sup M$ je poslední prvek množiny $M$ (pokud existuje).
\end{enumerate}
\define
Řekneme, že uspořádaná množina $(M,\leq)$ je \defined[uspořádání!svazové]{svazově uspořádaná},
má-li v~ní libovolná 2prvková množina infimum a supremum.
\lemma
Pro libovolné prvky svazu platí, že
$$a\SA b=a \iff a\SV b=b.$$
\proof
\begin{description}
\ditem{$\Rightarrow$} $a\SV b=(a\SA b)\SV b=b$.
\ditem{$\Leftarrow$} $a\SA b=a\SA(a\SV b)=a$.
\end{description}
\QED
\theorem
\begin{enumerate}
\item
Buď $S=(M,\SA,\SV)$ svaz.
Definujme-li na $M$ binární relaci $\leq$ jako $a\leq b\Lequiv a\SA b=a$,
pak $(M,\leq)$ je svazově uspořádaná.
\item
Buď $(M,\leq)$ svazově uspořádaná množina.
Definujeme-li na $M$ binární operace $\SA, \SV$ jako $a\SA b:=\inf\{a,b\}$ a $a\SV b:=\sup\{a,b\}$,
pak $(M,\SA,\SV)$ je svazem.
\end{enumerate}
\proof
\begin{enumerate}
\item
\begin{description}
\ditem{reflexivita}
$a\leq a\Lequiv a\SA a=a$.
\ditem{antisymetrie}
$a\SA b=a$ a $b\SA a=b$, a z~komutativity plyne $a=b$.
\ditem{transitivita}
Nechť $a\leq b$ a $b\leq c$, pak $a\SA c=a\SA b\SA c=a\SA b=a$.
\ditem{je svazové}
Ukážeme, že $\inf\{a,b\}=a\SA b$.
%TODO
Obdobně $\sup\{a,b\}=a\SV b$.
\end{description}
\item
\begin{description}
\ditem{komutativita}
$a\SA b=\inf\{a,b\}=\inf\{b,a\}=b\SA a$.
\ditem{asociativita}
$(a\SA b)\SA c=\inf\{\inf\{a,b\},c\}=\inf\{a,b,c\}=\inf\{a,\inf\{b,c\}\}=a\SA(b\SA c)$
s~využitím následujícího lemmatu a faktu, že každá 2prvková má infimum.
\ditem{pohlcení}
$\inf\{a,\sup\{b,a\}\}=a$ z~definice. %TODO 1.,2.
\end{description}
Druhý z~každé dvojice axiomů dokážeme podobně.
\end{enumerate}
\QED
\lemma
Mějme uspořádanou množinu $(M,\leq)$ a $a,b,c\in M$.
Potom pokud existuje $\inf\{\inf\{a,b\},c\}=:i$, je $i=\inf\{a,b,c\}$.
Pokud je navíc $(M,\leq)$ svazově uspořádaná, platí $i=\inf\{a,\inf\{b,c\}\}$.
\proof
\begin{description}
\ditem{$i\leq a,b,c$}
Je $i\leq c$ a $i\leq\inf\{a,b\}$, tedy $i\leq a,b$.
\ditem{$d\leq a,b,c\Limpl d\leq i$}
Neboť $d\leq a$ a $d\leq b$, je $d\leq\inf\{a,b\}$ a současně je $d\leq c$,
tedy \hbox{$d\leq\inf\{c,\inf\{a,b\}\}=i$}.
\end{description}
Pokud je navíc uspořádaní svazové, pak existuje infimum 2prvkové množiny $\{b,c\}$ a také infimum 2prvkové množiny
$\{a,\inf\{b,c\}\}$.
A tedy je podle prvního tvzení $\inf\{a,\inf\{b,c\}\}=\inf\{a,b,c\}=i$.
\QED
\remark
Operace jsou jednoznačně svázané, neboť např. pomocí $\SA$ definujeme $\leq$ a to nám definuje $\SV$.
\lemma
Buď $S=(M,\SA,\SV)$ svaz a nechť $a,b,c\in M$.
Potom platí
$$(a\leq b)\Limpl(a\SA c\leq b\SA c \;\Tand\; a\SV c \leq b\lor c).$$
\proof
Z definice: $a\SA c\SA b\SA c=a\SA c$, $a\SV c\SV b\SV c=b\SV c$.
\QED
\define
Mějme svaz $S=(M,\SA,\SV)$.
Pak pro $N\sse M$ je $T=(N,\SA,\SV)$ \defined[podsvaz]{podsvazem} svazu $S$,
pokud je $T$ svazem, tj. pokud je $N$ neprázdná a uzavřená vůči oběma operacím.
\example
\begin{enumerate}
\item
\defined[svaz!množinový]{Množinový svaz} $S=(M,\cap,\cup)$, kde $M$ je systém množin uzavřený na operace.
Speciálním případem je $M=\PP A$, kde snadno ověříme platnost axiomů svazu.
Svazové uspořadání množinového svazu je inkluze $\sse$.
Mějme $A$ množinu a $B\sse A$ její podmnožinu.
Pak $(\PP B,\cap,\cup)$ je podsvazem svazu $(\PP A,\cap,\cup)$.
Dále např. $\varsigma$-algebry tvoří množinové svazy.
\item
Pro libovolné $a\in S\supdot$ je $(\{a\},\SA,\SV)$ podsvazem $S$.
Pro libovolné $a,b\in S\supdot$ je $(\{a,b\},\SA,\SV)$ podvazem $S$, pokud jsou srovnatelné.
\item
Úplně uspořádaná množina je uspořádaná svazově a supremum a infimum přecházi v~maximum a minimum
(vždy to bude jeden z obou prvků).
Příkladem jsou číselné množiny $(\Nz,\leq)$ či $(\R,\leq)$.
\item
Mějme uspořádání $(\Nz,\divides)$ s~uspořádáním \uv{dělí}.
Pak $k\SA l$ je největší (podle $\divides$) takové $d$, že $d\divides k$ a $d\divides l$, tj. $k\SA l=\gcd(k,l)$.
Obdobně $k\SV l=\lcm(k,l)$.
\item
Mějme $G=(M,\cdot)$ grupu a označme $M_G$ systém všech jejích podgrup.
Označme $(\SA)=(\cap)$.
Pak umíme definovat $(\leq)$ jako $a\leq b\Lequiv a\cap b=a \Lequiv a\sse b$.
Tedy průsek i relace jsou stejné jako v množinovém svazu, ale víme, že sjednocení nemůže být spojením.
Definujeme ji $a\SV b:=\sup\{a,b\}$, to je nejmenší podgrupa $G$ obsahující $a$ i $b$, což je $ab$.
Tedy platí $(\SV)=(\cdot)$.
\item
$N_G=(N_G\supdot,\cap,\cdot)$ je svaz všech normálních podgrup grupy $G$.
Pak $N_G$ je podsvazem svazu $S_G$.
\item
Podobně tvoří svazy systémy podokruhů, ideálů, podtěles, podprostorů vektorového prostoru, doplněné o průnik a součet.
\end{enumerate}
\define
Mějme $a,b\in S\supdot$, $a<b$.
Pak \defined[interval]{intervalem} nazveme množinu $\anglecouple ab=\set x{a\leq x\leq b}$.
\lemma
Interval $\anglecouple ab$ je podsvazem $S$.
\proof
Mějme $x,y\in\anglecouple ab$.
Ukážeme, že $x\SA y\in\anglecouple ab$.
Platí $x\geq a$ a $y\geq a$, tedy $x\SA y\geq a\SA y\geq a\SA a=a$.
Obdobně pro $b$ a pro druhou operaci.
\QED
\xxxx{Ideály}
\define
Buď $S=(M,\SA,\SV)$ svaz.
\defined[ideál (svazy)]{Ideálem} rozumíme libovolný jeho podsvaz $I$ takový, že platí
$$(\AA a\in I)(\AA s\in M)(a\SA s\in I).$$
\lemma[lattice123]
Buďte $S=(M,\SA,\SV)$ svaz a $I$ jeho podsvaz.
Následující tvrzení jsou ekvivalentní:
\begin{enumerate}
\item $(\AA a\in I)(\AA s\in M)(a\SA s\in I)$ \quad (tj. $I$ je ideál);
\item $(\AA a\in I)(\AA b\in S)(b\leq a \Limpl b\in I)$;
\item $(\AA a,b\in S)(a\SV b\in I \Limpl a,b\in I)$.
\end{enumerate}
\proof
\begin{description}
\ditem{$1\Limpl2$}
Mějme $a\in I$ a $b\leq a$.
Pak podle předpokladu $a\SA b\in I$, ale současně $a\SA b=b$, tedy $b\in I$.
\ditem{$2\Limpl3$}
Buď $a\SV b\in I$.
Platí $a\leq a\SV b$ a $b\leq a\SV b$ a podle (2) je $a\SV b\in I$.
\ditem{$3\Limpl1$}
Mějme $a\in I$ a $s\in M$.
Pak $a=a\SV(a\SA s)\in I$, a tedy $a\SA s\in I$.
\end{description}
\QED
\consequence
Ideály ve svazu $S$ jsou takové $I\sse M$, $I\neq\emptyset$, že platí $(\AA a,b\in M)(a,b\in I\Lequiv a\SV b\in I)$.
\lemma
Buďte $S$ svaz a $a\in M$.
Pak množina $I_a:=\set{x\in M}{x\leq a}$ je ideálem.
\proof
$I_a$ je uzavřená vůči $\SV$ a platí (2) v~\ref{lattice123}.
\QED
\define
Ideál $I_a:=\set{x\in M}{x\leq a}$ nazýváme \defined[ideál (svazy)!hlavní]{hlavní ideál} generovaný prvkem $a$.
Je-li ve svazu každý ideál hlavní, nazveme jej \defined[svaz!hlavních ideálů]{svaz hlavních ideálů}.
\define
Buď $S=(M,\SA,\SV)$ svaz.
\defined[filtr]{Filtrem} rozumíme libovolný jeho podsvaz $F$ takový, že platí
$$(\AA a\in F)(\AA s\in M)(a\SV s\in F).$$
\xxxx{Izomorfismus svazů}
\define
Buďte $S_1=(M_1,\SA,\SV)$ a $S_2=(M_2,\SA,\SV)$ svazy.
Zobrazení $\map h{M_1}{M_2}$ nazveme \defined[homomorfismus (svazy)]{homomorfismus}, platí-li
$$(\AA x,y\in M_1)(h(x\SA y)=h(x)\SA h(y)\Tand h(x\SV y)=h(x)\SV h(y)).$$
\defined[izomorfismus (svazy)]{Izomorfismus} je takový homomorfismus, který je bijektivní.
\lemma
Homomorfismus svazů je izotonní zobrazení.
\proof
Mějme $\map h{S_1}{S_2}$ a $x,y\in S_1\supdot$, $x\leq y$.
Potom $h(x)\SA h(y)=h(x\SA y)=h(x)$, tedy $h(x)\leq h(y)$.
\QED
\theorem
Buďte $S_1=(M_1,\SA,\SV)$ a $S_2=(M_2,\SA,\SV)$ svazy.
Zobrazení $\map h{M_1}{M_2}$ je izomorfismem svazů právě tehdy, je-li izomorfismem svazově uspořádaných množin.
\proof
Pro obě implikace je předpokladem bijekce, a tedy existence $h^\1$.
\begin{description}
\ditem{$\Rightarrow$}
Podle předchozího lemmatu je $x\leq y\Limpl h(x)\leq h(y)$.
Zbývá tedy opačná implikace.
Předpokládejme $h(x)\SA h(y)=h(x)$.
Potom díky bijekci je $x\SA y=x$, a tedy $x\leq y$.
\ditem{$\Leftarrow$}
Platí $x\SA y\leq x$, tedy $h(x\SA y)\leq h(x)$ a $h(x\SA y)$ je dolní závora $h(x)$
a podobně je dolní závorou $h(y)$.
Mějme libovolné $d\in S_2\supdot$ takové, že $d\leq h(x)$ a $d\leq h(y)$.
Neboť $h$ je bijekce, existuje $c\in S_1$ takové, že $h(c)=d$.
Platí $h(c)\leq h(x)$ a $h(c)\leq h(y)$, čili $c\leq x$ a $c\leq y$,
a tedy $c\leq\inf\{x,y\}$ a konečně $d=h(c)\leq h(x\SA y)$.
Tedy každá dolní závora $h(x),h(y)$ je nejvýše rovna $h(x\SA y)$.
Tedy $h(x)\SA h(y)=h(x\SA y)$.
Obdobně ukážeme, že $h(x)\SV h(y)=h(x\SV y)$.
\end{description}
\QED
\define
Má-li svaz nejmenší (první), resp. největší (poslední) prvek, nazveme jej \defined[nula (svazy)]{nulou}, resp.
\defined[jednotka (svazy)]{jednotkou} a značíme $0$, resp. $1$.
\example
\begin{enumerate}
\item Mějme množinu $A$ a množinový svaz $(\PP A,\cap,\cup)$ s~uspořádáním $\sse$.
Pak jednotkou je $A$ a nulou je $\emptyset$.
\item Mějme svaz $(\Nz,\gcd,\lcm)$ s uspořádáním $({\divides})$.
Pak jednotkou je číslo $0$ (platí $n\divides0$) a nulou je číslo $1$ (platí $1\divides n$).
\end{enumerate}
\lemma
Libovolný minimální prvek svazu je nulou.
Libovolný maximální prvek svazu je jednotkou.
\proof
Ukážeme pouze první tvrzení, druhé lze ukázat obdobně.
Mějme $m$ minimální a libovolné $x\in S\supdot$.
Pak $x\SA m\leq m$, ale to je možné jen tehdy, když $x\SA m=m$, a tedy $m\leq x$.
Tedy $m$ je první a je nulou.
\QED
\xxxx{Úplné svazy}
\define
Svaz $S=(M,\SA,\SV)$ nazveme \defined[svaz!úplný]{úplným svazem},
má-li v~něm libovolná podmnožina $N\sse M$ infimum i supremum.
\remark
V každém svazu existuje infimum a supremum konečné podmnožiny.
V úplném svazu vyžadujeme existenci infima a suprema pro každou (prázdnou, konečnou, spočetnou, nespočetnou) podmnožinu.
\lemma
Úplný svaz má nulu a jednotku.
\proof
\begin{enumerate}
\item $1=\sup M=\inf\emptyset$.
\item $0=\inf M=\sup\emptyset$.
\end{enumerate}
\QED
\example
V~množinovém svazu $S=(\PP M,\cap,\cup)$ je infimem $\calA\sse\PP M$ množina $\bigcap\calA\sse M$
a supremem $\bigcup\calA\sse M$, tedy $S$ je úplný svaz.
\theorem(o pevném bodě)
Buď $S=(M,\SA,\SV)$ úplný svaz a buď $\map fMM$ izotonie.
Pak existuje pevný bod izotonie $f$, tj. $$(\EE u\in M)(f(u)=u).$$
\proof
Definujeme $U=\set{a\in M}{f(a)\geq a}$.
Jistě $0\in U$, tedy $U$ je neprázdná.
Označme $u:=\sup U$.
Mějme libovolné $a\in U$, pak $u\geq a$ a z izotonie je $f(u)\geq f(a)\geq a$,
tedy $f(u)$ je horní závora $U$, a tedy $u\leq f(u)$.
Z~izotonie dále dostáváme, že $f(u)\leq f(f(u))$, a tedy $f(u)\in U$, tedy $f(u)\leq u$.
Celkově máme $f(u)=u$.
\QED
\theorem
Buď $(M,\leq)$ uspořádaná množina.
Má-li každá podmnožina $M$ infimum, pak má každá podmnožina $M$ supremum.
\proof
Mějme $N\sse M$.
Nechť $Z$ je množina horních závor $N$.
Dále $Z\neq\emptyset$, neboť v~ní je největší prvek $M$, což je $\inf\emptyset$.
Pokud $N=\emptyset$, pak $\sup N$ je $\inf M$.
Nyní máme $(\AA n\in N)(\AA z\in Z)(n\leq z)$.
Tedy každý prvek $N$ je dolní závorou $Z$ a platí $n\leq\inf Z$, jehož existenci předpokládáme.
A neboť $(\AA n\in N)(n\leq\inf Z)$, tedy $\inf Z$ je horní závora a je nemenší z~nich.
Tedy $\sup N=\inf Z$.
\QED
\consequence
Buď $(M,\leq)$ uspořádaná množina.
Má-li každá podmnožina $M$ supremum, pak má každá podmnožina $M$ infimum.
\consequence
Buď $(M,\leq)$ uspořádaná množina.
Má-li každá podmnožina $M$ infimum, nebo má-li každá podmnožina $M$ supremum, pak $(M,\SA,\SV)$ je úplný svaz.
\lemma
Buď $S=(M,\SA,\SV)$ úplný svaz.
Potom průnik libovolného systému ideálů v~$S$ je ideál.
\proof
Označme $J_\alpha$ jednotlivé ideály a $I:=\bigcap J_\alpha$.
Neboť $0\in M$ a $0\in J_\alpha$, je $0\in I$ a $I\neq\emptyset$.
Dále platí $a\in I\Lequiv(\AA\alpha)(a\in J_\alpha)$
a pro všechna $\alpha$ je $(\AA a\in J_\alpha)(\AA s\in M)(a\SA s\in I)$,
tedy máme $(\AA a\in I)(\AA s\in M)(a\SA s\in I)$, což je definiční podmínka ideálu.
\QED
\define
Řekneme, že svaz $S_1$ lze \defined[vnoření!izomorfní (svazy)]{izomorfně vnořit} do svazu $S_2$,
existuje-li monomorfismus $\map h{S_1}{S_2}$.
Potom platí $S_1\cong h(S_1)\sg S_2$.
\theorem
Libovolný svaz lze izomorfně vnořit do úplného svazu.
\proof
Předpokládejme, že svaz $S_0=(M_0,\SA,\SV)$ nemá nulu.
Pak definujeme množinu $M:=M_0\cup\{0\}$ a pokládáme $(\AA x\in M_0)(0<x)$.
Tedy $S_0\sg S:=(M,\SA,\SV)$.
\def\NN{{\mathscr N}}
\def\II#1{{\mathscr I}_{#1}}
\def\ZZ#1{{\mathscr Z}_{#1}}
\def\UU#1{{\mathscr U}_{#1}}
\def\HH#1{{\mathscr H}_{#1}}
Označme $\II S$ množinu všech ideálů svazu $S$.
Je neprázdná, neboť např. $\{0\},S\in\II S$.
Pak $(\II S, \sse)$ je uspořádaná množina.
Pro libovolné $\NN\sse \II S$ je $\inf\NN=\bigcap\NN\in\II S$,
a pokud označíme $\ZZ\NN$ množinu všech horních závor $\NN$, platí
$\sup\NN=\inf\ZZ\NN=\bigcap\set{I\in\II S}{(\AA J\in\NN)(J\sse I)}$.
Tedy pokud položíme $I\SA J:=I\cap J$ a $I\SV J:=\bigcap\set{K\in\II S}{I,J\sse K}$,
je $\UU S:=(\II S,\SA,\SV)$ úplný svaz.
Definujeme zobrazení $\map hM{\II S}$ jako $h(a)=I_a$.
Ukážeme, že $h$ je monomorfismus svazů, tj. pokud označíme $\HH S$ množinu všech hlavních ideálů $S$,
máme $\maptype hM{na}{\HH S}$.
\begin{description}
\ditem{$h$ je prosté}
Nechť $h(a)=h(b)$.
Pak $I_a=I_b$, tedy $a\leq b$ a $b\leq a$, tedy $a=b$.
\ditem{$h$ je množinový izomorfismus $(M,\leq)$ a $(\HH S,\sse)$}
Mějme $a, b\in M$.
Pak $a\leq b \Lequiv I_a\sse I_b \Lequiv h(a)\sse h(b)$.
\ditem{$h$ je svazový izomorfismus}
Vyplývá z~předchozího bodu a předchozího výkladu.
\end{description}
\QED
\example
Věta nám umožňuje přechod od $\Q$ k $\R$.
Hlavními ideály v~$(\Q,\leq)$ jsou $I_a=\set{x\in\Q}{x\leq a}$.
A všemi ideály jsou $\set{x\in\Q}{x\leq r}$ a $\set{x\in\Q}{x<r}$ pro všechna $r\in\R$.
\xxxx{Distributivní svazy}
\theorem
Buď $S=(M,\SA,\SV)$ libovolný svaz.
Pak pro libovolné prvky $a,b,c\in M$ platí:
\begin{enumerate}
\item $a\SA(b\SV c)\geq (a\SA b)\SV(a\SA c)$;
\item $a\SV(b\SA c)\leq (a\SV b)\SA(a\SV c)$;
\item je-li $a\leq c$, platí $a\SV(b\SA c)\leq(a\SV b)\SA c$.
\end{enumerate}
\proof
\begin{enumerate}
\item
Platí $b\leq b\SV c \Limpl a\SA b\leq a\SA(b\SV c)$ a podobně $a\SA c\leq a\SA(b\SV c)$.
Tedy $a\SA(b\SV c)$ je horní závora $\{a\SA c, a\SA b\}$, a tedy je větší nebo rovno než
$\sup \{a\SA c, a\SA b\}=(a\SA c)\SV(a\SA b)$.
\item
Symetricky z~duality.
\item
Platí $a\SV c=c$, tedy podle (2) je $a\SV(b\SA c)\leq (a\SV b)\SA(a\SV c)=(a\SV b)\SA c$.
\end{enumerate}
\QED
\define
Svaz $S=(M,\SA,\SV)$ nazveme \defined[svaz!distibutivní]{distributivní}, pokud pro libovolné $a,b,c\in M$ platí:
\begin{enumerate}
\ditem{D1} $a\SA(b\SV c)=(a\SA b)\SV(a\SA c)$;
\ditem{D2} $a\SV(b\SA c)=(a\SV b)\SA(a\SV c)$.
\end{enumerate}
\remark
Pro rovnosti máme ve všech svazech zaručeno platnost jedné nerovnosti.
Stačí tedy dokázat nerovnosti opačné než v~předchozí větě.
\lemma
$\text{(D1)} \Limpl \text{(D2)}$.
\proof
Vyjdu z pravé strany (D2) a použiji (D1):
$(a\SV b)\SA(a\SV c)=((a\SV b)\SA a)\SV((a\SV b)\SA c)=a\SV((a\SV b)\SA c)
=a\SV((a\SA c)\SV(b\SA c))=(a\SV(a\SA c))\SV(b\SA c)=a\SV(b\SA c)$.
\QED
\example
Příklady distributivních svazů:
\begin{enumerate}
\item
množinové svazy;
\item
úplně uspořádané množiny;
\item
$(\Nz,\divides)=(\Nz,\gcd,\lcm)$.
\end{enumerate}
\example
Svazy podgrup, normálních podgrup, \ldots nejsou obecně distributivní.
\theorem
Libovolný podsvaz i libovolný homomorfní obraz distributivního svazu je distributivní.
\proof
Distributivita je obecná podmínka, tedy se nemůže po zmenšení nosiče porušit.
Homomorfismus zachovává průsek i spojení, tedy zachovává distributivitu.
\QED
\define
Buď $S=(M,\SA,\SV)$ svaz.
Filtr $F$ se nazývá \defined[ultrafiltr]{ultrafiltr}, je-li $F\neq M$ a platí
$$(\AA a,b\in M)(a\SV b\in F \Limpl (a\in F \Tor b\in F)).$$
Množinu všech ultrafiltrů na $S$ označujeme $\UM S$.
\remark
V definiční podmínce ultrafiltru platí z~definice filtru i zpětná implikace.
\remark
V matematické logice hrají filtry důležitou roli, pokud položíme spojení jako \uv{nebo} a průsek jako \uv{a zároveň},
pak podmínka ultrafiltru vyjadřuje, kdy je konjunkce pravdivá.
Podmínka filtru pak bude $a\SA b\in F \Lequiv (a\in F \Tand b\in F)$.
\example
Mějme $S=(\PP A,\cap,\cup)$ a $a\in A$, tedy $\{a\}\in\PP A$.
Pak definujeme hlavní filtr $F_{\{a\}}:=\set{B\in\PP A}{\{a\}\sse B}=\set{B\sse A}{a\in B}$.
Pak $F_{\{a\}}\not\ni\emptyset$, tedy $F_{\{a\}}\neq\PP A$.
Mějme $B_1,B_2\in\PP A$ a nechť $a\in B_1\cup B_2$, pak $a\in B_1$ nebo $a\in B_2$,
tedy $B_1\in F_{\{a\}}$ nebo $B_2\in F_{\{a\}}$.
Tedy $F_{\{a\}}$ je ultrafiltr.
Ale $F_{\{a,b\}}$ pro $a\neq b$ není ultrafiltr.
\define
Buď $S=(M,\SA,\SV)$ a nechť $\emptyset\neq N\sse M$.
Pak definujeme $\anglevector N$ jako nejmenší filtr ve svazu $S$ obsahující $N$:
$$\anglevector N=\bigcap\set{F\in\FM S}{N\sse F}.$$
\lemma
Buďte $S$ svaz, $F$ filtr ve svazu $S$ a buď $a_0\in S\supdot$,
dále označme $H:=\set{x\in S\supdot}{(\EE d\in F)(x\geq d\SA a_0)}$
Potom $\anglevector{F\cup\{a_0\}}=H$.
\proof
\begin{description}
\ditem{$\supseteq$}
Pokud $d\in F$, je $d\SA a_0\in\anglevector{F\cup\{a_0\}}$, a tedy
$x=x\SV(d\SA a_0)\in\anglevector{F\cup\{a_0\}}$.
\ditem{$\sse$}
Ukážeme, že $F\cup\{a_0\}\sse H$.
Pro $d\in F$ platí, že $d\geq d\SA a_0$.
Dále mějme libovolné $d\in F$, pak $a_0\geq d\SA a_0$.
Pokud ukážeme, že $H$ je filtr, bude nutně nejmenší filtr nad $F\cup\{a_0\}$ jeho podmnožinou.
Mějme $x_1\geq d_1\SA a_0$ a $x_2\geq d_2\SA a_0$ pro nějaká $d_{1,2}\in F$, pak
$x_1\SA x_2\geq d_1\SA a_0\SA x_2\geq d_1\SA a_0\SA d_2\SA a_0$.
Položme $d:=d_1\SA d_2\in F$, pak $x_1\SA x_2\geq d\SA a_0$, tedy $x_1\SA x_2\in H$.
\end{description}
\QED
\lemma
Sjednocení řetězce filtrů $\calR$ je filtr.
\proof
\begin{enumerate}
\item $a\in\bigcup\calR, b\in S\supdot, b\geq a$.
$(\EE F)(a\in F\in\calR)$, tedy $b\in F$, tedy $b\in\bigcup\calR$.
\item $a,b\in\bigcup\calR$. Pak $a\in F_1$, $b\in F_2$, bez újmy na obecnosti nechť $F_1\sse F_2$.
Potom $a,b\in F_2$, a tedy $a\SA b\in F_2\sse\bigcup\calR$.
\end{enumerate}
\QED
\lemma
Buďte $S=(M,\SA,\SV)$ distributivní svaz, $a,b\in M$ a nechť neplatí $a\leq b$ (tedy $a>b$ nebo nejsou srovnatelné).
Potom existuje ultrafiltr $F$ svazu $S$ tak, že $a\in F$ a současně $b\notin F$.
\proof
Nechť $\calF$ je množina všech filtrů, které obsahují $a$, ale neobsahují $b$,
tedy platí $\calF=\set{F\in\FM S}{a\in F\Tand b\notin F}$.
Nutně $F_a=\set{x\in S}{x\geq a}\not\owns b$, tedy $F_a\in\calF$.
V~$\calF$ uspořádané inkluzí má libovolný řetězec $\calR$ horní závoru $F=\bigcup\calF$,
která podle předcházejícího lemmatu je opět filtrem, a tedy triviálně $F\in\calF$, neboť $a\in F\Tand b\notin F$.
Dle Zornova lemmatu existuje v~$\calF$ maximální prvek $F_0$.
Ukážeme sporem, že $F_0$ je ultrafiltr.
Nechť $F_0$ není ultrafiltr.
Tedy existují $a_1,a_2\in S$ takové, že $a_1\SV a_2\in F_0$, ale $a_1\notin F_0$ ani $a_2\notin F_0$.
Definujme $F_1:=\anglevector{F_0\cup\{a_1\}}$ a $F_2:=\anglevector{F_0\cup\{a_2\}}$, přičemž $F_i\varsupsetneq F_0$
Ukážeme sporem, že $F_1\in\calF\Tor F_2\in\calF$ a tím vytvoříme spor s~maximalitou $F_0$.
Tedy musíme ukázat, že $b\notin F_1\Tor b\notin F_2$.
Nechť $b\in F_1\Tand b\in F_2$.
Platí $F_i=\set{x}{(\EE c_i\in F_0)(x\geq c_i\SA a_i)}$, tedy i pro $b$ existují $c_i$ tak, že
$b\geq c_1\SA a_1$ a $b\geq c_2\SA a_2$.
Položme $c:=c_1\SA c_2\in F_0$, tedy $b\geq c\SA a_1$ a $b\geq c\SA a_2$,
tedy $b\geq(c\SA a_1)\SV(c\SA a_2)$ a díky distributivitě je
$b\geq c\SA(a_1\SV a_2)\in F_0$, neboť $c\in F_0$, $a_1\SV a_2\in F_0$.
Ale filtr je uzavřený vůči větším prvkům, tedy $b\in F_0$, což je spor.
Tedy máme $F_1\in\calF\Tor F_2\in\calF$, což je spor s~maximalitou $F_0$ v $\calF$.
\QED
\theorem(Stone)
Libovolný distributivní svaz je izomorfní s nějakým množinovým svazem.
Jinými slovy: libovolný distributivní svaz lze izomorfně vnořit do svazu všech podmnožin nějaké množiny.
\proof
Mějme $S=(M,\SA,\SV)$ distributivní svaz.
Označme $\calU=(\PP{\UM S},\cap,\cup)$.
Definujeme $\map hM{\PP{\UM S}}$ jako $h(x):=\set{F\in\UM S}{x\in F}$.
Ukážeme, že $h$ je monomorfismus.
\begin{description}
\ditem{injekce}
Mějme $a,b\in M$, $a\neq b$, tj. $(\Tnot a\leq b)\Tor(\Tnot b\leq a)$.
Pak $(\EE F_1\in\UM S)(a\in F_1 \Tand b\notin F_1) \Tor (\EE F_2\in\UM S)(b\in F_1 \Tand a\notin F_2)$,
tedy $(\EE F_1\in h(a)\sm h(b)) \Tor (\EE F_2\in h(b)\sm h(a))$, tedy $h(a)\neq h(b)$.
\ditem{$h(a\SA b)=h(a)\cap h(b)$}
Mějme libovolné $F\in\UM S$. Pak $F\in h(a\SA b)\Lequiv a\SA b\in F
\stackrel{\text{filtr}}\Lequiv (a\in F\Tand b\in F) \Lequiv (F\in h(a) \Tand F\in h(b)) \Lequiv F\in h(a)\cap h(b)$.
\ditem{$h(a\SV b)=h(a)\cup h(b)$}
Mějme libovolné $F\in\UM S$. Pak $F\in h(a\SV b)\Lequiv a\SV b\in F
\stackrel{\text{ultrafiltr}}\Lequiv (a\in F\Tor b\in F) \Lequiv (F\in h(a)\Tor F\in h(b)) \Lequiv F\in h(a)\cup h(b)$.
\end{description}
Celkově tedy máme $S\cong h(S)\stackrel{\text{svaz}}\sg U$.
\QED
\xxxx{Modulární svazy}
\define
Svaz $S=(M,\SA,\SV)$ nazveme \defined[svaz!modulární]{modulární}, platí-li pro libovolné $a,b,c\in M$, $a\leq c$
vztah $a\SV(b\SA c)=(a\SV b)\SA c$.
\theorem
Libovolný distributivní svaz je modulární.
\proof
Nechť $a\leq c$, tedy $c=a\SV c$
Pak $a\SV(b\SA c)\stackrel{\text{(D2)}}=(a\SV b)\SA(a\SV c)=(a\SV b)\SA c$.
\QED
\lemma
Svaz $S$ je modulární právě tehdy, když pro libovolné $a,b,c\in S\supdot$ platí
$$a\SV(b\SA(a\SV c))=(a\SV b)\SA(a\SV c).$$
\proof
\begin{description}
\ditem{$\Rightarrow$}
V definičním vztahu položíme místo $c$ spojení $a\SV c\geq a$.
Dostaneme přímo dokazovanou rovnost.
\ditem{$\Leftarrow$}
Pro libovolné $c\geq a$ je $a\SV c=c$, a tedy $a\SV(b\SA c)=a\SV(b\SA(a\SV c))=(a\SV b)\SA(a\SV c)=(a\SV b)\SA c$.
\end{description}
\QED
\theorem
Svaz všech normálních podgrup libovolné grupy $G$ je modulární.
\proof
Nerovnost $\geq$ v definiční podmínce platí vždy, tedy ukážeme, že
$$(\AA A,B,C\nsg G, A\supdot\sse C\supdot)(AB\cap C\sse A(B\cap C)).$$
Mějme libovolné $x\in (AB\cap C)\supdot$, tedy $x\in (AB)\supdot=A\supdot B\supdot$ a existují $x=ab$, kde $a\in A\supdot\sse C\supdot$ a $b\in B\supdot$, tedy $b=a^\1 x$, ale $a^\1$ i $x$ leží v~$C\supdot$, tedy $b\in C\supdot$.
Tedy $x=ab$, kde $a\in A\supdot$ a $b\in B\supdot\cap C\supdot=(B\cap C)\supdot$.
\QED
\theorem
Svaz všech ideálů libovolného okruhu je modulární.
Svaz všech podprostorů libovolného vektorového prostoru je modulární.
\define
Buď $S=(M,\SA,\SV)$ svaz s~nulou a jednotkou.
\defined[rzada@řada!normální]{Normální řada} ve svazu $S$ je libovolná posloupnost $(a_i)_{i=0}^m$ prvků z $M$
taková, že $1=a_0>a_1>\cdots>a_m=0$. Číslo $m$ nazveme \defined[délka normální řady]{délkou normální řady}.
\define
Řekneme, že normální řada $(b_j)_{i=0}^n$ je \defined[zjemnění]{zjemněním} normální řady $(a_i)_{i=0}^m$, pokud
$\{a_i\}_{i=0}^m\sse\{b_j\}_{i=0}^n.$
Zjemnění nazveme \defined[zjemnění!vlastní]{vlastní}, pokud $n>m$.
\define
Normální řada, která nemá žádné vlastní zjemnění, se nazývá \defined[rzada@řada!hlavní]{hlavní řada}.
\theorem(Schreier)
Libovolné 2 normální řady v modulárním svazu mají zjemnění stejných délek.
\theorem(Jordan, H\H older)
\begin{enumerate}
\item Libovolné 2 hlavní řady v modulárním svazu mají stejnou délku.
\item Existuje-li v modulárním svazu hlavní řada, pak libovolnou normální řadu lze zjemnit na hlavní řadu.
\end{enumerate}
\proof
\begin{enumerate}
\item
Nechť je $(a_i)$ kratší hlavní řada.
Pak ji podle Schreierovy věty lze zjemnit (vlastním zjemněním), což je spor s~tím, že je hlavní.
\item
Buď $(a_i)$ hlavní řada a $(b_j)$ libovolná normální řada.
Nechť $(b_j)$ nelze zjemnit na hlavní řadu.
Pak existuje zjemnění $(c_k)$ delší, než $(a_i)$ a podle Schreierovy věty lze najít jejich zjemnění stejných délek.
Protože $(c_k)$ je delší než $(a_i)$, museli bychom $(a_i)$ zjemnit, což je spor s~tím, že je hlavní.
\end{enumerate}
\QED
\define
Buďte $S=(M,\SA,\SV)$ svaz a $a,b\in M$.
Pro interval $\anglecouple ab$ použijeme označení $b/a$,
tedy $b/a:=\anglecouple ab=\set{x\in M}{x\geq a \Tand x\leq b}$.
\theorem
Buďte $S=(M,\SA,\SV)$ modulární svaz s nulou a jednotkou a $a,b\in M$, $a<b$.
Pak $(a\SV b)/a\cong b/(a\SA b)$.
\proof
Definujme 2 zobrazení, $\map f{\anglecouple a{a\SV b}}{\anglecouple{a\SA b}b}$ jako $f(x)=x\SA b$
a $\map g{\anglecouple{a\SA b}b}{\anglecouple a{a\SV b}}$ jako $g(y)=y\SV a$.
Ukážeme korektnost definice, tedy mějme $a\leq x\leq a\SV b$, pak $x\SA b\geq a\SA b$ a $x\SA b\leq(a\SV b)\SA b=b$;
korektnost druhé definice ukážeme obdobně.
Zkoumejme zobrazení $g\circ f$, tedy mějme $x\in\anglecouple a{a\SV b}$, pak
$g(f(x))=g(x\SA b)=(x\SA b)\SV a$, a neboť $x\geq a$, je $g(f(x))=x\SA(b\SV a)$, a neboť $x\leq a\SV b$,
je $g(f(x))=x$.
Podobně ukážeme, že $f\circ g=\id$, a tedy $f$ i $g$ jsou bijekce.
Ukážeme, že $f$ a $g$ jsou izomorfismy uspořádaných množin, tedy $x\leq y\Lequiv f(x)\leq f(y)\Lequiv g(x)\leq g(y)$.
Směr vpravo je snadný, pokud $x\leq y$, je $f(x)=x\SA b\leq y\SA b=f(y)$ a podobně pro $g$.
Pro směr vlevo předpokládejme, že $f(x)\leq f(y)$, pak dostáváme $x=g(f(x))\leq g(f(y))=y$, a podobně pro $g$.
Tedy jsme našli množinový, a tím i svazový izomorfismus obou intervalů.
\QED
\theorem
Mějme modulární svaz, ve kterém existují hlavní řady (tedy svaz musí mít nulu a jednotku).
Definujeme-li $\abs a$ jako délku libovolné hlavní řady hlavního ideálu prvku $a$, pak platí
$\abs{a\SV b}+\abs{a\SA b}=\abs a+\abs b$.
\proof
Dle předchozí věty je $\abs{a\SV b}-\abs a=\abs b-\abs{a\SA b}$.
\QED
\consequence
1. věta o dimenzi.
\remark
Pokud ve svazu najdeme 2 hlavní řady různé délky, tak víme, že svaz není modulární.
\xxxx{Komplement}
\define
Buď $S=(M,\SA,\SV)$ svaz s~nulou a jednotkou.
Řekneme, že prvek $a'\in M$ je \defined[komplement]{komplementem} prvku $a\in M$, platí-li:
\begin{enumerate}
\item $a\SA a'=0$;
\item $a\SV a'=1$.
\end{enumerate}
\remark
Zvláště v množinových svazech používáme často pro komplement prvku $A$ značku $\CO A$.
\example
Ve svazu $S=(\PP A,\cap,\cup)$ platí pro $B\sse A$, že $B'=A\sm B$ a komplement existuje právě jeden.
\example
$0'=1$; $1'=0$.
\example
Komplement nemusí existovat, ale může jich i existovat více.
\begin{enumerate}
\item Mějme svaz s prvky $\{0,a,1\}$, pak prvek $a$ nemá komplement.
\item Mějme svaz $\Nf$ nazývaný \defined[pentagon]{pentagon}:
\begin{center}
\setlength{\unitlength}{\stdunitlength}
\begin{picture}(24,35)(-12,0)
\put(2,3){\line(2,3){8}}
\put(-2,3){\line(-2,1){8}}
\put(2,31){\line(2,-3){8}}
\put(-2,3){\line(-2,1){8}}
\put(-10,13){\line(0,1){8}}
\put(-2,31){\line(-2,-1){8}}
\put(0,1){\makebox(0,0){$c$}}
\put(0,33){\makebox(0,0){$d$}}
\put(10,17){\makebox(0,0){$a$}}
\put(-10,10){\makebox(0,0){$a_2$}}
\put(-10,24){\makebox(0,0){$a_1$}}
\put(10,12){\makebox(0,0){$\relax$}}
\end{picture}
\end{center}
Prvek $c$ představuje nulu, prvek $d$ jednotku. K~prvku $a$ existují 2 různé srovnatelné komplementy $a_1$ a $a_2$.
Dále svaz $\Nf$ má 2 hlavní řady různé délky ($d, a, c$ a $d, a_1, a_2, c$), tedy není modulární, a není ani distributivní.
\end{enumerate}
\theorem
V~modulárním svazu nemá žádný prvek 2 různé srovnatelné komplementy.
\proof
Nechť $a_1$ a $a_2$ jsou komplementy $a$ a nechť $a_1\leq a_2$.
Pak platí $a_1=a_1\SA 1=a_1\SA(a\SV a_2)=(a_1\SA a)\SV a_2=0\SV a_2=a_2$.
\QED
\theorem
Svaz je modulární právě tehdy, když neobsahuje jako podsvaz $\Nf$.
\proof
\begin{description}
\ditem{$\Rightarrow$} Sporem, tedy nechť obsahuje pentagon.
Pak platí $(a_2\SV a)\SA a_1=d\SA a_1=a_1\neq a_2=a_2\SV c=a_2\SV(a\SA a_1)$,
což je protipříklad proti podmínce modularity.
\ditem{$\Leftarrow$} Sporem, tedy nechť není modulární.
Tedy existují $a,b,c$ takové, že $a\leq c$ ale $a\SA(b\SV c)<(a\SA b)\SV c$.
Ukážeme, že $a\neq c$ a $b$ je s~nimi nesrovnatelný.
Nechť $a=c$, pak $a\SA(b\SV a)=a=(a\SA b)\SV a$, což je spor, tedy $a<c$.
Nechť $b<a\Tor b<c$, pak jistě $b<c$ a $a\SA(b\SV c)\leq a<c\leq(a\SA b)\SV c$.
\end{description}
\QED
\remark (algebraický vtip, který nezazněl na přednášce)
Víte, proč je Sovětský svaz modulární? Protože nemá Pentagon.
\example
Definujeme svaz $\Mf$ nazývaný \defined[diamant]{diamant}:
\begin{center}\setlength{\unitlength}{\stdunitlength}
\begin{picture}(40,24)(-20,0)
\put(3,3){\line(2,1){14}}
\put(-3,3){\line(-2,1){14}}
\put(0,3){\line(0,1){7}}
\put(-3,21){\line(-2,-1){14}}
\put(3,21){\line(2,-1){14}}
\put(0,21){\line(0,-1){7}}
\put(0,1){\makebox(0,0){$c$}}
\put(0,23){\makebox(0,0){$d$}}
\put(0,12){\makebox(0,0){$a$}}
\put(-17,12){\makebox(0,0){$a_1$}}
\put(17,12){\makebox(0,0){$a_2$}}
\end{picture}
\end{center}
Pak $\Mf$ je modulární, ale není distributivní, prvek $a$ má 2 komplementy, které nejsou srovnatelné.
\theorem
V libovolném distributivním svazu s nulou a jednotkou má každý prvek nejvýše jeden komplement.
\proof
Mějme $a$ a $a_1$, $a_2$ jeho komplementy.
Pak $a_1=a_1\SA 1=a_1\SA(a\SV a_2)=(a_1\SA a)\SV(a_2\SA a_1)=0\SV(a_2\SA a_1)=a_1\SA a_2$, tedy
$a_1\leq a_2$.
Ale distributivní svaz je modulární a $a_1$, $a_2$ jsou komplementy stejného prvku, tedy $a_1=a_2$.
\QED
\theorem
Svaz je distributivní právě tehdy, když neobsahuje jako podsvaz ani $\Nf$, ani $\Mf$.
\define
Řekneme, že svaz s nulou a jednotkou je \defined[svaz!komplementární]{komplementární},
má-li v~něm libovolný prvek alespoň jeden komplement.
\define
Řekneme, že svaz s nulou a jednotkou je \defined[svaz!Booleův]{Booleův}, je-li distributivní a komplementární.
\example
Příkladem Booleových svazů jsou svazy množinové.
\example
Vraťme se k~12prvkové alternující grupě $\AM 4$, která není jednoduchá a nemá žádnou 6prvkovou podgrupu
(přestože $6\divides12$), a nakresleme schéma svazu jejích podgrup.
\begin{center}
\setlength{\unitlength}{\stdunitlength}
\begin{picture}(80,63)(-30,-3)
\put(0,-1){\makebox(0,0){$E_{\vphantom1\;}$}}
\put(15,-1){\makebox(0,0){1 prvek}}
\put(1,2){\line(1,4){6}}
\put(1,2){\line(2,3){16}}
\put(1,2){\line(1,1){24}}
\put(1,2){\line(3,2){36}}
\put(4,28){\makebox{$\AM 3^{(1)}$}}
\put(14,28){\makebox{$\AM 3^{(2)}$}}
\put(24,28){\makebox{$\AM 3^{(3)}$}}
\put(34,28){\makebox{$\AM 3^{(4)}$}}
\put(47,28){\makebox{3 prvky}}
\put(1,56){\line(1,-4){6}}
\put(1,56){\line(2,-3){16}}
\put(1,56){\line(1,-1){24}}
\put(1,56){\line(3,-2){36}}
\put(-1,2){\line(-1,4){3}}
\put(-1,2){\line(-3,4){9}}
\put(-1,2){\line(-4,3){16}}
\put(-22,16){\makebox{$\LM 2^{(1)}$}}
\put(-13,16){\makebox{$\LM 2^{(2)}$}}
\put(-5,16){\makebox{$\LM 2^{(3)}$}}
\put(-42,16){\makebox{2 prvky}}
\put(-18,21){\line(6,5){12}}
\put(-10,21){\line(1,2){5}}
\put(-4,21){\line(0,1){10}}
\put(-7,32){\makebox{$\KM 4$}}
\put(-30,32){\makebox{4 prvky}}
\put(0,56){\line(-1,-5){4}}
\put(0,59){\makebox(0,0){$\AM 4$}}
\put(17,59){\makebox(0,0){12 prvků}}
\end{picture}
\end{center}
Vidíme, že svaz všech podgrup $\AM 4$ není modulární, neboť má hlavní řady různé délky.
Je to protipříklad, kdyby si někdo myslel, že svaz všech (nejen normálních) podgrup je modulární.
Dále svaz podgrup $\AM 4$ ani svaz podgrup $\KM 4$ není distributivní.
Navíc všechny podgrupy $\KM 4$ jsou normální, tedy neplatí, že by libovolný svaz normálních podgrup byl distributivní.
\xxxx{Booleova algebra}
\define
Mějme Booleův svaz $S=(M,\SA,\SV)$.
Pak algebru $Q=(M,\SA,\SV,{'},0,1)$, kde operace $({'})$ je komplement a je unární
a operace $0$ a $1$ jsou nulární, tedy konstanty, nazveme \defined[algebra!Booleova]{Booleova algebra}.
\theorem
Buď $A$ Booleova algebra a nechť $a,b\in A\supdot$.
Pak:
\begin{enumerate}
\item $0'=1$,\quad $1'=0$;
\item $\qlb{a'}'=a$;
\item $a\SA b=0\Lequiv b\leq a'$,\quad $a\SV b=1\Lequiv b\geq a'$;
\item $(a\SA b)'=a'\SV b'$,\quad $(a\SV b)'=a'\SA b'$ (\defined[zákon!De Morganův]{De Morganovy zákony}).
\end{enumerate}
\proof
Ukážeme pouze tvrzení 3 a 4.
\begin{enumerate}
\addtocounter{enumi}{2}
\item
$b=b\SA 1=b\SA(a\SV a')=(b\SA a)\SV(b\SA a')=0\SV(b\SA a')=b\SA a' \Lequiv b\leq a'$
\item
$(a\SA b)\SA(a'\SV b')=(a\SA b\SA a')\SV(a\SA b\SA b')=0\SV0=0$,\\
$(a\SA b)\SV(a'\SV b')=(a\SV a\SV b')\SA(b\SV a'\SV a')=1\SA1=1$;
%\item
$a\leq b$; $b'\SA a'=(b\SV a)'=b'$; $b'\leq a'$.
\end{enumerate}
\QED
\lemma
Filtr $F$ ve Booleově svazu je ultrafiltr právě tehdy, platí-li
$$(\AA x\in S\supdot)(x\in F \Lequiv x'\notin F).$$
\proof
\begin{description}
\ditem{$\Rightarrow$}
Mějme libovolné $x$.
Pak $x\SV x'=1\in F$, tedy $x\in F\Tor x'\in F$.
Kdyby $x,x'\in F$, pak $0=x\SA x'\in F$, což je spor s tím, že $F\neq S\supdot$.
\ditem{$\Leftarrow$}
Mějme libovolné prvky $a,b$.
Nechť $a\SV b\in F$, ale $a,b\notin F$.
Pak $a',b'\in F$, tedy $a'\SA b'=(a\SV b)'\in F$, což je spor.
\end{description}
\QED
\theorem
Libovolná Booleova algebra je izomorfní s~nějakou množinovou Booleovou algebrou.
\proof
Definujeme zobrazení $f(x)=\set{F\in\UM S}{x\in F}$.
Víme, že $f$ zachovává průsek a spojení.
\begin{description}
\ditem{${'}$} $f(x')=\set{F\in\UM S}{x\in F}=\set{F\in\UM S}{x\notin F}=\CO f(x)$
\ditem{$0$} $f(0)=\set{F\in\UM S}{0\in F}$, ale $0\in F\Limpl F=S\supdot$, což není filtr. Tedy $f(0)=\emptyset$.
\ditem{$1$} $f(1)=\set{F\in\UM S}{1\in F}=\UM S$.
\end{description}
\QED
\theorem
Libovolná konečná Booleova algebra je izomorfní množinové Booleově algebře tvořené všemi podmnožinami vhodné množiny.
\theorem
\begin{enumerate}
\item
Libovolná konečná Booleova algebra má počet prvků roven číslu $2^n$, $n\in\N$.
\item
K libovolnému $n\in\N$ existuje až na izometrii právě jedna Booleova algebra s~$2^n$ prvky.
\end{enumerate}
\example
2-, 4- a 8prvková Booleova algebra.
\setlength{\unitlength}{\stdunitlength}
\begin{center}
\def\POINT(#1,#2){\put(#1,#2){\circle{1}}}
~
\hfill
\begin{picture}(4,18)(-9,-1)
\POINT(0,0)
\POINT(0,16)
\put(0,0){\line(0,1){16}}
\end{picture}
\hfill
\begin{picture}(20,18)(-10,-1)
\POINT(0,0)
\POINT(0,16)
\POINT(8,8)
\POINT(-8,8)
\put(0,0){\line(1,1){8}}
\put(0,0){\line(-1,1){8}}
\put(0,16){\line(1,-1){8}}
\put(0,16){\line(-1,-1){8}}
\end{picture}
\hfill
\begin{picture}(22,18)(-11,-1)
\def\LINEA(#1,#2){\put(#1,#2){\line(-3,2){9}}} %(-9,6)
\def\LINEB(#1,#2){\put(#1,#2){\line( 0,1){4}}} %( 0,4)
\def\LINEC(#1,#2){\put(#1,#2){\line( 3,2){9}}} %( 9,6)
%0 (0,0)
\POINT(0,0)
\LINEA(0,0)
\LINEB(0,0)
\LINEC(0,0)
%A (-9,6)
\POINT(-9,6)
\LINEB(-9,6)
\LINEC(-9,6)
%B (0,4)
\POINT(0,4)
\LINEA(0,4)
\LINEC(0,4)
%C (9,6)
\POINT(9,6)
\LINEA(9,6)
\LINEB(9,6)
%AB (-9,10)
\POINT(-9,10)
\LINEC(-9,10)
%AC (0,12)
\POINT(0,12)
\LINEB(0,12)
%BC (9,10)
\POINT(9,10)
\LINEA(9,10)
%ABC (0,16)
\POINT(0,16)
\end{picture}
\hfill
~
\end{center}