01ALG:Kapitola8

Z WikiSkripta FJFI ČVUT v Praze
Verze z 24. 8. 2010, 13:53, kterou vytvořil Karel.brinda (diskuse | příspěvky) (Založena nová stránka: \nothing{ \begin{document} } \xxx{Teorie svazů} \xxxx{Svazy} \define \defined[svaz]{Svazem} (angl. \defined{lattice}) rozumíme algebru $S=(M,\SA,\SV)$ se dvěma biná...)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání

\nothing{ \begin{document} }

\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 $N$ svazem, tj. pokud je 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ří monž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~upořá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Šablona:\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 po zmenšení nosiče nemůž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_1\}}$, 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$.

\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í stený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 Shreierovy 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á ř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}

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, 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

\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 distibutivní 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 schema 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í distibutivní. 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}