Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 9/kontrolle

... und ein Vorlesungsminischwein diskutiert.

Verbände

In dieser Vorlesung besprechen wir eine Struktur, in der Verknüpfungseigenschaften und Ordnungseigenschaften eng miteinander verbunden sind.

Definition Referenznummer erstellen

Eine geordnete Menge ${}(M,\leq )$ mit der Eigenschaft, dass für je zwei Elemente ${}x,y\in M$ ein Infimum ${}x\sqcap y$ und ein Supremum ${}x\sqcup y$ existiert, heißt Verband.

Es muss also ${}x,y\leq x\sqcup y$ gelten und jedes ${}z$ oberhalb von ${}x$ und von ${}y$ ist auch oberhalb von ${}x\sqcup y$. Durch die allgemeine Existenz und auch dadurch, dass man oft endliche Verbände betrachtet, spielen die aus den reellen Zahlen bekannten Schwierigkeiten mit den Begriffen Infimum und Supremum hier keine Rolle.

Beispiel Referenznummer erstellen

Eine total geordnete Menge ${}(M,\leq )$ ist stets ein Verband, da ja zu zwei Elementen ${}x,y\in M$ das eine Element das Minimum und das andere das Maximum der beiden ist.

Beispiel Beispiel 9.3 ändern

Die positiven natürlichen Zahlen ${}\mathbb {N} _{+}$ bilden mit der Teilbarkeit als Ordnung und dem kleinsten gemeinsamen Vielfachen als Supremum und dem größten gemeinsamen Teiler als Infimum einen Verband. Dies gilt auch für ${}\mathbb {N}$ mit der Teilbarkeitsrelation, wobei dann der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache richtig zu definieren sind.

Beispiel Referenznummer erstellen

Es sei ${}S$ eine Menge und ${}M={\mathfrak {P}}\,(S)$ die zugehörige Potenzmenge mit der durch die Inklusion gegebenen Ordnung. Dann liegt ein Verband vor, wobei das Infimum durch den mengentheoretischen Durchschnitt und das Supremum durch die Vereinigung gegeben ist. Man spricht vom Teilmengenverband.

Das vorstehende Beispiel ist der Grund für die Wahl der Symbole ${}\sqcap$ und ${}\sqcup$ in der allgemeinen Definition eines Verbandes.

Beispiel Beispiel 9.5 ändern

Es sei ${}G$ eine Gruppe und ${}V$ die Menge aller Untergruppen von ${}G$. Dann ist ${}V$ mit der Inklusion als Ordnung ein Verband. Das Infimum ist durch den Durchschnitt von Untergruppen und das Supremum ist durch die von zwei Untergruppen erzeugte Untergruppe gegeben. Man spricht vom Untergruppenverband.

Beispiel Referenznummer erstellen

Es sei ${}K\subseteq L$ eine endliche Körpererweiterung und ${}V$ die Menge aller Zwischenkörper. Dann ist ${}V$ mit der Inklusion als Ordnung ein Verband. Das Infimum ist durch den Durchschnitt von Zwischenkörpern und das Supremum ist durch das Kompositum von zwei Zwischenkörpern (also dem durch zwei Zwischenkörper erzeugte Unterring, der wegen der Endlichkeitsvoraussetzung wieder ein Körper ist) gegeben.

Beispiel Referenznummer erstellen

Wir betrachten eine Menge ${}M$ von Aussagen, wobei wir äquivalente Aussagen miteinander identifizieren. Dies kann man informal oder aber bezogen auf die aussagenlogische Sprache zu einer Menge von Aussagenvariablen verstehen. Im letzteren Fall sind etwa die beiden Aussagen ${}p\rightarrow q$ und ${}\neg q\rightarrow \neg p$ zueinander äquivalent (Kontraposition). Über die Implikation ${}\alpha \rightarrow \beta$ ist diese Menge ${}M$ eine Ordnung. Mit der Konjunktion ${}\alpha \wedge \beta$ (und) als Infimum und der Disjunktion ${}\alpha \vee \beta$ (oder) als Supremum liegt ein Verband vor.

Lemma Referenznummer erstellen

In einem Verband gelten die folgenden Eigenschaften.

1. Die beiden Verknüpfungen ${}\sqcup$ und ${}\sqcap$ sind kommutativ und assoziativ.
2. Es ist

   ${}x\sqcup (x\sqcap y)=x\,.$

3. Es ist

   ${}x\sqcap (x\sqcup y)=x\,.$

Beweis

1. Die Kommutativität ist klar. Zum Nachweis der Assoziativität seien ${}x,y,z$ gegeben. Wir vergleichen ${}(x\sqcup y)\sqcup z$ und ${}x\sqcup (y\sqcup z)$. Es ist

   ${}x,y\leq x\sqcup y\leq (x\sqcup y)\sqcup z\,$

   und ebenso

   ${}z\leq (x\sqcup y)\sqcup z\,.$

   Damit ist also

   ${}x,y,z\leq (x\sqcup y)\sqcup z\,.$

   Da ${}y\sqcup z$ das Supremum von ${}y$ und ${}z$ ist, folgt

   ${}y\sqcup z\leq (x\sqcup y)\sqcup z\,.$

   Daher ist auch

   ${}x\sqcup (y\sqcup z)\leq (x\sqcup y)\sqcup z\,.$

   Die andere Abschätzung gilt genauso, aus der Antisymmetrie der Ordnung folgt somit die Gleichheit. Die Assoziativität für das Infimum wird entsprechend bewiesen.

2. Es ist direkt

   ${}x\leq x\sqcup (x\sqcap y)\,.$

   Ferner ist

   ${}x\sqcap y\leq x\,$

   und somit ist ${}x$ eine obere Schranke von ${}x$ und von ${}x\sqcap y$ und daher ist

   ${}x\sqcup (x\sqcap y)\leq x\,.$

   Aus der Antisymmetrie folgt

   ${}x=x\sqcup (x\sqcap y)\,.$

3. Wird wie (2) bewiesen.

$\Box$

Die beiden zuletzt genannten Eigenschaften nennt man Absorptionsgesetze.

Die zuletzt bewiesene Aussage zeigt, dass es in einem Verband zwei natürliche Verknüpfungen mit vertrauten algebraischen Eigenschaften gibt. Wir besprechen nun umgekehrt einen algebraischen Zugang zum Verbandsbegriff, der sich bald als gleichwertig herausstellen wird.

Definition Referenznummer erstellen

Eine Menge ${}M$ mit zwei kommutativen und assoziativen Verknüpfungen ${}\sqcup$ und ${}\sqcap$ heißt algebraischer Verband, wenn die Absorptionsgesetze

${}x\sqcup (x\sqcap y)=x\,$

und

${}x\sqcap (x\sqcup y)=x\,$

gelten.

Definition Referenznummer erstellen

In einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$ nennt man die durch

${}y\geq x\,,$

falls

${}x\sqcap y=x\,,$

definierte Ordnung, die zugehörige Ordnung.

Zunächst ist durch diese Definition nur eine Relation auf ${}M$ gegeben, die wir nun als Ordnung nachweisen müssen.

Lemma Referenznummer erstellen

Zu einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$

ist die zugehörige Ordnung in der Tat eine Ordnung, die ${}x\sqcap y=\operatorname {inf} (x,y)$ und ${}x\sqcup y=\operatorname {sup} (x,y)$ erfüllt.

Beweis

Zunächst ist unter Verwendung der beiden Absorptionsgesetze

${}x\sqcap x=x\sqcap (x\sqcup (x\sqcap x))=x\,,$

was die Reflexivität der Relation bedeutet. Zum Nachweis der Transitivität seien ${}z\geq y$ und ${}y\geq x$ gegeben. Das bedeutet ${}z\sqcap y=y$ und ${}y\sqcap x=x$. Damit ist

${}{\begin{aligned}z\sqcap x&=z\sqcap (y\sqcap x)\\&=(z\sqcap y)\sqcap x\\&=y\sqcap x\\&=x,\end{aligned}}$

was ${}z\geq x$ bedeutet. Zum Nachweis der Antisymmetrie sei ${}y\geq x$ und ${}x\geq y$. Daraus ergibt sich sofort ${}x=x\sqcap y=y$.

Wir zeigen nun, dass ${}x\sqcap y$ das Infimum von ${}x$ und ${}y$ in der soeben etablierten Ordnung ist. Wegen

${}x\sqcap (x\sqcap y)=(x\sqcap x)\sqcap y=x\sqcap y\,$

ist ${}x\geq x\sqcap y$ und ebenso ${}y\geq x\sqcap y$, es ist also

${}x\sqcap y\leq x,y\,.$

Es sei nun ${}z\leq x,y$. Dies bedeutet ${}x\sqcap z=z$ und ${}y\sqcap z=z$. Dann ist

${}(x\sqcap y)\sqcap z=x\sqcap (y\sqcap z)=x\sqcap z=z\,,$

also ${}z\leq x\sqcap y$. Somit ist ${}x\sqcap y$ das Infimum.

Um die Aussage über das Supremum zu beweisen, zeigt man zunächst, dass ${}x=x\sqcap y$ zu ${}y=x\sqcup y$ äquivalent ist. Wenn nämlich das erste gilt, so ist

${}x\sqcup y=(x\sqcap y)\sqcup y=y\,$

nach einem Absorptionsgesetz. Wenn das zweite gilt, so ist

${}x\sqcap y=x\sqcap (x\sqcup y)=x\,,$

ebenfalls nach einem Absorptionsgesetz. Damit folgt die Aussage über das Supremum wie die Aussage über das Infimum.

$\Box$

Von nun an wechseln wir zwischen den ordnungstheoretischen und den algebraischen Eigenschaften eines Verbandes hin und her.

Weitere Eigenschaften von Verbänden

In einem Verband ${}M$ ist ein neutrales Element bezüglich der ${}\sqcup$-Operation, also ein Element ${}0$ mit

${}0\sqcup x=x\,$

für alle ${}x$, nichts anderes als ein kleinstes Element in der Ordnung von ${}M$. Ebenso ist ein neutrales Element ${}1$ bezüglich ${}\sqcap$ nichts anderes als ein größtes Element von ${}M$.

Definition Referenznummer erstellen

Ein Verband ${}M$ heißt beschränkt, wenn es in ihm ein kleinstes Element ${}0$ und ein größtes Element ${}1$ gibt.

Definition Referenznummer erstellen

Ein beschränkter Verband ${}M$ heißt komplementär, wenn es zu jedem ${}x\in M$ ein ${}y\in M$ mit ${}x\sqcap y=0$ und ${}x\sqcup y=1$ gibt.

Definition Referenznummer erstellen

Ein Verband ${}M$ heißt distributiv, wenn in ihm die Distributivgesetze

${}x\sqcap {\left(y\sqcup z\right)}={\left(x\sqcap y\right)}\sqcup {\left(x\sqcap z\right)}\,$

und

${}x\sqcup {\left(y\sqcap z\right)}={\left(x\sqcup y\right)}\sqcap {\left(x\sqcup z\right)}\,$

gelten.

Boolesche Verbände

Definition Referenznummer erstellen

Ein Verband ${}M$ heißt boolesch, wenn er komplementär und distributiv ist.

Statt boolescher Verband sagt man auch boolesche Algebra. Ein boolescher Verband ist insbesondere ein kommutativer Halbring. Der Teilmengenverband auf einer beliebigen Menge ist ein boolescher Verband, die Komplementarität ist durch die Komplementbildung auf Teilmengen gegeben, daher der Name. Von diesem Hauptbeispiel her sind auch die folgenden Regeln vertraut.

Lemma Lemma 9.16 ändern

In einem booleschen Verband ${}M$ gelten die folgenden Rechenregeln.

1. Zu jedem Element ${}x\in M$ gibt es genau ein Element ${}y\in M$ mit ${}x\sqcap y=0$ und ${}x\sqcup y=1$. Es wird mit ${}\neg x$ bezeichnet.
2. Es ist

   ${}\neg \neg x=x\,.$

3. Es ist ${}\neg 0=1$ und ${}\neg 1=0$.
4. Es ist

   ${}\neg (x\sqcap y)=\neg x\sqcup \neg y\,.$

5. Es ist

   ${}\neg (x\sqcup y)=\neg x\sqcap \neg y\,.$

Beweis

1. Es seien ${}y$ und ${}z$ Komplemente von ${}x$. Dann ist

   ${}y=y\sqcup 0=y\sqcup (x\sqcap z)=(y\sqcup x)\sqcap (y\sqcup z)=1\sqcap (y\sqcup z)=y\sqcup z\,.$

   Da ebenso ${}z=y\sqcup z$ gilt, folgt ${}y=z$.

2. Siehe Aufgabe 9.15.
3. Siehe Aufgabe 9.16.
4. Siehe Aufgabe 9.17.
5. Siehe Aufgabe 9.22.

$\Box$

Die letzten beiden Regeln nennt man Regeln von de Morgan.

Der Einbettungssatz für endliche boolesche Verbände

Definition Referenznummer erstellen

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 Referenznummer erstellen

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

Beispiel Referenznummer erstellen

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

Lemma Lemma 9.20 ändern

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 9.18.

$\Box$

Lemma Lemma 9.21 ändern

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 Lemma 9.20  (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 Lemma 9.20  (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 Satz 9.22 ändern

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 Lemma 9.21, 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 Lemma 9.20  (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$