Boolescher Verband/Einbettungssatz/Atome/Textabschnitt

Definition

Es sei ${}(M,\preccurlyeq )$ eine geordnete Menge mit einem kleinsten Element ${}0$. Ein Element  ${}a\in M$  heißt Atom, wenn  ${}a\neq 0$  ist und die Beziehung  ${}x\preccurlyeq a$  nur für  ${}x=0$  und  ${}x=a$  gilt.

Beispiel

In einer Potenzmenge ${}{\mathfrak {P}}\,(A)$ zu einer Menge ${}A$ sind die einelementigen Mengen ${}\{x\}$ die Atome.

Beispiel

In den natürlichen Zahlen ${}\mathbb {N}$ mit der Teilerbeziehung als Ordnungsrelation ist ${}1$ das kleinste Element und die Primzahlen sind die Atome.

Lemma

Es sei ${}(M,\preccurlyeq )$ eine geordnete Menge mit einem kleinsten Element ${}0$ und mit der Eigenschaft, dass zu je zwei Elementen das Infimum ${}x\sqcap y$ existiert. Dann gelten folgende Eigenschaften.

1. Wenn  ${}a\in M$  ein Atom ist, so ist  ${}a\sqcap x=0$  oder  ${}a\sqcap x=a$  für alle ${}x$.
2. Wenn ${}a$ und ${}b$ verschiedene Atome sind, so ist  ${}a\sqcap b=0$. 
3. Es sei ${}M$ endlich. Dann gibt es zu jedem  ${}x\in M\setminus \{0\}$  ein Atom ${}a$ mit  ${}a\preccurlyeq x$. 

Beweis

Siehe Aufgabe.

$\Box$

Lemma

In einem endlichen booleschen Verband

besitzt jedes Element  ${}x\in B$  eine eindeutige Darstellung der Form

${}x=a_{1}\sqcup \ldots \sqcup a_{n}\,$

mit Atomen ${}a_{j}$.

Beweis

Jedes Element  ${}x\in B$  ist nur größergleich endlich vielen Atomen, wir führen zum Nachweis der Existenz Induktion über diese Anzahl. Bei  ${}x=0$  nimmt man die leere Vereinigung. Ein Atom wird durch sich selbst dargestellt. Es sei  ${}x\neq 0$  ein beliebiges Element. Nach Fakt  (3) gibt es ein Atom  ${}a\preccurlyeq x$.  Wir betrachten

${}x'=x\sqcap \neg a\,.$

Wegen

${}x'\sqcap a=(x\sqcap \neg a)\sqcap a=x\sqcap (\neg a\sqcap a)=x\sqcap 0=0\,$

liegt ${}a$ nicht unterhalb von ${}x'$. Somit liegen unterhalb von ${}x'$ weniger Atome als unterhalb von ${}x$ und nach Induktionsvoraussetzung gibt es eine Darstellung

${}x'=a_{1}\sqcup \ldots \sqcup a_{n}\,$

und damit

${}{\begin{aligned}x&=x\sqcap 1\\&=x\sqcap (\neg a\sqcup a)\\&=(x\sqcap \neg a)\sqcup (x\sqcap a)\\&=(x\sqcap \neg a)\sqcup a\\&=x'\sqcup a\\&=a_{1}\sqcup \ldots \sqcup a_{n}\sqcup a.\end{aligned}}$

Zur Eindeutigkeit. Sei

${}a_{1}\sqcup \ldots \sqcup a_{n}=b_{1}\sqcup \ldots \sqcup b_{m}\,.$

Nehmen wir an, dass ${}b_{1}$ nicht in der ersten Darstellung vorkommt. Dann ist

${}{\left(a_{1}\sqcup \ldots \sqcup a_{n}\right)}\sqcap b_{1}=(a_{1}\sqcap b_{1})\sqcup \ldots \sqcup (a_{n}\sqcap b_{1})=0\,$

nach Fakt  (2). Wenn man aber auf die rechte Seite ${}\sqcap b_{1}$ anwendet, so ergibt sich ${}b_{1}$, ein Widerspruch. Also kommen links und rechts die gleichen Atome vor.

$\Box$

Der folgende Einbettungssatz zeigt, dass alle endlichen booleschen Algebren von einer ganz bestimmten Bauart sind. Es gibt auch ähnliche Aussagen ohne die Endlichkeitsvoraussetzung.

Satz

Jeder endliche boolesche Verband ${}B$

ist isomorph zur Potenzmenge einer endlichen Menge.

Beweis

Es sei ${}A$ die Menge der Atome von ${}B$. Wir betrachten die Abbildung

$B\longrightarrow {\mathfrak {P}}\,(A),\,x\longmapsto {\left\{a\in A\mid a\preccurlyeq x\right\}}.$

Es ergibt sich aus Fakt, dass dies eine Bijektion ist. Dass ${}0$ auf die leere Menge und ${}1$ auf die Gesamtmenge geht, ist klar. Wegen der Eindeutigkeit der atomaren Darstellung führt diese Abbildung die ${}\sqcup$-Verknüpfung in die Vereinigung über. Es sei

${}x=a_{1}\sqcup \ldots \sqcup a_{n}\,$

und

${}y=b_{1}\sqcup \ldots \sqcup b_{m}\,.$

Dann ist nach dem allgemeinen Distributivgesetz und Fakt  (2)

${}x\sqcap y=(a_{1}\sqcup \ldots \sqcup a_{n})\sqcap (b_{1}\sqcup \ldots \sqcup b_{m})=\bigsqcup _{i,j}a_{i}\sqcap b_{j}=\bigsqcup c\,,$

wobei ${}c$ durch alle Atome läuft, die sowohl links als auch rechts vorkommen. Daher führt die Abbildung diese ${}\sqcap$-Verknüpfung in den Durchschnitt über.

$\Box$