Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 9/latex
\setcounter{section}{9}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Göttingen Minipig.jpg} }
\end{center}
\bildtext {... und ein Vorlesungsminischwein diskutiert.} }
\bildlizenz { Göttingen Minipig.jpg } {} {Minipigs} {Commons} {CC-by-sa 3.0} {}
\zwischenueberschrift{Verbände}
In dieser Vorlesung besprechen wir eine Struktur, in der Verknüpfungseigenschaften und Ordnungseigenschaften eng miteinander verbunden sind.
\inputdefinition
{}
{
Eine
\definitionsverweis {geordnete Menge}{}{}
\mathl{(M, \leq)}{} mit der Eigenschaft, dass für je zwei Elemente
\mavergleichskette
{\vergleichskette
{x,y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Infimum}{}{}
\mathl{x \sqcap y}{} und ein
\definitionsverweis {Supremum}{}{}
\mathl{x \sqcup y}{} existiert, heißt
\definitionswort {Verband}{.}
}
Es muss also
\mavergleichskette
{\vergleichskette
{ x,y
}
{ \leq }{ x \sqcup y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gelten und jedes $z$ oberhalb von $x$ und von $y$ ist auch oberhalb von
\mathl{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.
\inputbeispiel{}
{
Eine
\definitionsverweis {total geordnete Menge}{}{}
\mathl{(M, \leq)}{} ist stets ein
\definitionsverweis {Verband}{}{,}
da ja zu zwei Elementen
\mavergleichskette
{\vergleichskette
{x,y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das eine Element das Minimum und das andere das Maximum der beiden ist.
}
\inputbeispiel{}
{
Die positiven natürlichen Zahlen $\N_+$ bilden mit der \definitionsverweis {Teilbarkeit}{}{} als \definitionsverweis {Ordnung}{}{} und dem \definitionsverweis {kleinsten gemeinsamen Vielfachen}{}{} als Supremum und dem \definitionsverweis {größten gemeinsamen Teiler}{}{} als Infimum einen \definitionsverweis {Verband}{}{.} Dies gilt auch für $\N$ mit der Teilbarkeitsrelation, wobei dann der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache richtig zu definieren sind.
}
\inputbeispiel{}
{
Es sei $S$ eine Menge und
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \mathfrak {P} \, (S )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die zugehörige
\definitionsverweis {Potenzmenge}{}{}
mit der durch die Inklusion gegebenen
\definitionsverweis {Ordnung}{}{.}
Dann liegt ein
\definitionsverweis {Verband}{}{}
vor, wobei das
\definitionsverweis {Infimum}{}{}
durch den mengentheoretischen Durchschnitt und das
\definitionsverweis {Supremum}{}{}
durch die Vereinigung gegeben ist. Man spricht vom \stichwort {Teilmengenverband} {.}
}
Das vorstehende Beispiel ist der Grund für die Wahl der Symbole \mathkor {} {\sqcap} {und} {\sqcup} {} in der allgemeinen Definition eines Verbandes.
\inputbeispiel{}
{
Es sei $G$ eine \definitionsverweis {Gruppe}{}{} und $V$ die Menge aller \definitionsverweis {Untergruppen}{}{} von $G$. Dann ist $V$ mit der Inklusion als Ordnung ein \definitionsverweis {Verband}{}{.} Das Infimum ist durch den Durchschnitt von Untergruppen und das Supremum ist durch die von zwei Untergruppen erzeugte Untergruppe gegeben. Man spricht vom \stichwort {Untergruppenverband} {.}
}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{K
}
{ \subseteq }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {endliche Körpererweiterung}{}{}
und $V$ die Menge aller
\definitionsverweis {Zwischenkörper}{}{.}
Dann ist $V$ mit der Inklusion als Ordnung ein
\definitionsverweis {Verband}{}{.}
Das Infimum ist durch den Durchschnitt von Zwischenkörpern und das Supremum ist durch das
\definitionsverweis {Kompositum}{}{}
von zwei Zwischenkörpern
\zusatzklammer {also dem durch zwei Zwischenkörper erzeugte Unterring, der wegen der Endlichkeitsvoraussetzung wieder ein Körper ist} {} {}
gegeben.
}
\inputbeispiel{}
{
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
\mathl{p \rightarrow q}{} und
\mathl{\neg q \rightarrow \neg p}{} zueinander äquivalent
\zusatzklammer {Kontraposition} {} {.}
Über die Implikation $\alpha \rightarrow \beta$ ist diese Menge $M$ eine
\definitionsverweis {Ordnung}{}{.}
Mit der Konjunktion
\mathl{\alpha \wedge \beta}{}
\zusatzklammer {und} {} {}
als Infimum und der Disjunktion
\mathl{\alpha \vee \beta}{}
\zusatzklammer {oder} {} {}
als Supremum liegt ein
\definitionsverweis {Verband}{}{}
vor.
}
\inputfaktbeweis
{Verband/Ordnung/Algebraisch/Fakt}
{Lemma}
{}
{
\faktsituation {In einem
\definitionsverweis {Verband}{}{}
gelten die folgenden Eigenschaften.}
\faktfolgerung {\aufzaehlungdrei{Die beiden Verknüpfungen
\mathkor {} {\sqcup} {und} {\sqcap} {}
sind
\definitionsverweis {kommutativ}{}{}
und
\definitionsverweis {assoziativ}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ x \sqcup ( x \sqcap y )
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ x \sqcap ( x \sqcup y )
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungdrei{Die Kommutativität ist klar. Zum Nachweis der Assoziativität seien
\mathl{x,y,z}{} gegeben. Wir vergleichen
\mathl{(x \sqcup y) \sqcup z}{} und
\mathl{x \sqcup ( y \sqcup z)}{.} Es ist
\mavergleichskettedisp
{\vergleichskette
{x,y
}
{ \leq} { x \sqcup y
}
{ \leq} { (x \sqcup y) \sqcup z
}
{ } {
}
{ } {
}
}
{}{}{}
und ebenso
\mavergleichskettedisp
{\vergleichskette
{z
}
{ \leq} { (x \sqcup y) \sqcup z
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Damit ist also
\mavergleichskettedisp
{\vergleichskette
{x,y,z
}
{ \leq} { (x \sqcup y) \sqcup z
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Da
\mathl{y \sqcup z}{} das Supremum von
\mathkor {} {y} {und} {z} {}
ist, folgt
\mavergleichskettedisp
{\vergleichskette
{ y \sqcup z
}
{ \leq} { (x \sqcup y) \sqcup z
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Daher ist auch
\mavergleichskettedisp
{\vergleichskette
{ 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.
}{Es ist direkt
\mavergleichskettedisp
{\vergleichskette
{x
}
{ \leq} { x \sqcup (x \sqcap y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Ferner ist
\mavergleichskettedisp
{\vergleichskette
{x \sqcap y
}
{ \leq} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit ist $x$ eine obere Schranke von $x$ und von
\mathl{x \sqcap y}{} und daher ist
\mavergleichskettedisp
{\vergleichskette
{ x \sqcup (x \sqcap y)
}
{ \leq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Aus der Antisymmetrie folgt
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} { x \sqcup (x \sqcap y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Wird wie (2) bewiesen.
}
Die beiden zuletzt genannten Eigenschaften nennt man \stichwort {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.
\inputdefinition
{}
{
Eine Menge $M$ mit zwei
\definitionsverweis {kommutativen}{}{}
und
\definitionsverweis {assoziativen}{}{}
\definitionsverweis {Verknüpfungen}{}{}
\mathkor {} {\sqcup} {und} {\sqcap} {}
heißt
\definitionswort {algebraischer Verband}{,}
wenn die Absorptionsgesetze
\mavergleichskettedisp
{\vergleichskette
{ x \sqcup ( x \sqcap y )
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ x \sqcap ( x \sqcup y )
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gelten.
}
\inputdefinition
{}
{
In einem
\definitionsverweis {algebraischen Verband}{}{}
\mathl{(M, \sqcap,\sqcup)}{} nennt man die durch
\mavergleichskettedisp
{\vergleichskette
{y
}
{ \geq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
falls
\mavergleichskettedisp
{\vergleichskette
{ x \sqcap y
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
definierte
\definitionsverweis {Ordnung}{}{,}
die
\definitionswort {zugehörige Ordnung}{.}
}
Zunächst ist durch diese Definition nur eine Relation auf $M$ gegeben, die wir nun als Ordnung nachweisen müssen.
\inputfaktbeweis
{Verband/Algebraisch/Ordnung/Fakt}
{Lemma}
{}
{
\faktsituation {Zu einem
\definitionsverweis {algebraischen Verband}{}{}
\mathl{(M, \sqcap, \sqcup)}{}}
\faktfolgerung {ist die
\definitionsverweis {zugehörige Ordnung}{}{}
in der Tat eine
\definitionsverweis {Ordnung}{}{,}
die
\mavergleichskette
{\vergleichskette
{ x \sqcap y
}
{ = }{ \operatorname{inf} ( x,y )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ x \sqcup y
}
{ = }{ \operatorname{sup} ( x,y )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erfüllt.}
\faktzusatz {}
\faktzusatz {}
}
{
Zunächst ist unter Verwendung der beiden Absorptionsgesetze
\mavergleichskettedisp
{\vergleichskette
{x \sqcap x
}
{ =} { x \sqcap ( x \sqcup ( x \sqcap x))
}
{ =} { x
}
{ } {
}
{ } {
}
}
{}{}{,}
was die Reflexivität der Relation bedeutet. Zum Nachweis der Transitivität seien
\mavergleichskette
{\vergleichskette
{z
}
{ \geq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \geq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Das bedeutet
\mavergleichskette
{\vergleichskette
{z \sqcap y
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y \sqcap x
}
{ = }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Damit ist
\mavergleichskettealign
{\vergleichskettealign
{z \sqcap x
}
{ =} { z \sqcap (y \sqcap x)
}
{ =} { ( z \sqcap y) \sqcap x
}
{ =} { y \sqcap x
}
{ =} {x
}
}
{}
{}{,}
was
\mavergleichskette
{\vergleichskette
{z
}
{ \geq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bedeutet. Zum Nachweis der Antisymmetrie sei
\mavergleichskette
{\vergleichskette
{y
}
{ \geq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ \geq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daraus ergibt sich sofort
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ x \sqcap y
}
{ = }{ y
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir zeigen nun, dass
\mathl{x \sqcap y}{} das Infimum von
\mathkor {} {x} {und} {y} {}
in der soeben etablierten Ordnung ist. Wegen
\mavergleichskettedisp
{\vergleichskette
{x \sqcap (x \sqcap y)
}
{ =} { (x \sqcap x) \sqcap y
}
{ =} { x \sqcap y
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{x
}
{ \geq }{x \sqcap y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und ebenso
\mavergleichskette
{\vergleichskette
{y
}
{ \geq }{x \sqcap y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
es ist also
\mavergleichskettedisp
{\vergleichskette
{ x \sqcap y
}
{ \leq} { x,y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei nun
\mavergleichskette
{\vergleichskette
{z
}
{ \leq }{ x,y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dies bedeutet
\mavergleichskette
{\vergleichskette
{ x \sqcap z
}
{ = }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ y \sqcap z
}
{ = }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettedisp
{\vergleichskette
{ ( x \sqcap y) \sqcap z
}
{ =} { x \sqcap ( y \sqcap z)
}
{ =} { x \sqcap z
}
{ =} { z
}
{ } {
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ x \sqcap y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu
\mavergleichskette
{\vergleichskette
{y
}
{ = }{ x \sqcup y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
äquivalent ist. Wenn nämlich das erste gilt, so ist
\mavergleichskettedisp
{\vergleichskette
{ x \sqcup y
}
{ =} {( x \sqcap y) \sqcup y
}
{ =} { y
}
{ } {
}
{ } {
}
}
{}{}{}
nach einem Absorptionsgesetz. Wenn das zweite gilt, so ist
\mavergleichskettedisp
{\vergleichskette
{ 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.
Von nun an wechseln wir zwischen den ordnungstheoretischen und den algebraischen Eigenschaften eines Verbandes hin und her.
\zwischenueberschrift{Weitere Eigenschaften von Verbänden}
In einem
\definitionsverweis {Verband}{}{}
$M$ ist ein
\definitionsverweis {neutrales Element}{}{}
bezüglich der $\sqcup$-Operation, also ein Element $0$ mit
\mavergleichskettedisp
{\vergleichskette
{0 \sqcup x
}
{ =} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $x$, nichts anderes als ein
\definitionsverweis {kleinstes Element}{}{}
in der Ordnung von $M$. Ebenso ist ein neutrales Element $1$ bezüglich $\sqcap$ nichts anderes als ein
\definitionsverweis {größtes Element}{}{}
von $M$.
\inputdefinition
{}
{
Ein \definitionsverweis {Verband}{}{} $M$ heißt \definitionswort {beschränkt}{,} wenn es in ihm ein \definitionsverweis {kleinstes Element}{}{} $0$ und ein \definitionsverweis {größtes Element}{}{} $1$ gibt.
}
\inputdefinition
{}
{
Ein
\definitionsverweis {beschränkter Verband}{}{}
$M$ heißt
\definitionswort {komplementär}{,}
wenn es zu jedem
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x \sqcap y
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x \sqcup y
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
\inputdefinition
{}
{
Ein
\definitionsverweis {Verband}{}{}
$M$ heißt
\definitionswort {distributiv}{,}
wenn in ihm die Distributivgesetze
\mavergleichskettedisp
{\vergleichskette
{ x \sqcap { \left( y \sqcup z \right) }
}
{ =} { { \left( x \sqcap y \right) } \sqcup { \left( x \sqcap z \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ x \sqcup { \left( y \sqcap z \right) }
}
{ =} { { \left( x \sqcup y \right) } \sqcap { \left( x \sqcup z \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gelten.
}
\zwischenueberschrift{Boolesche Verbände}
\inputdefinition
{}
{
Ein \definitionsverweis {Verband}{}{} $M$ heißt \definitionswort {boolesch}{,} wenn er \definitionsverweis {komplementär}{}{} und \definitionsverweis {distributiv}{}{} ist.
} Statt boolescher Verband sagt man auch \stichwort {boolesche Algebra} {.} Ein boolescher Verband ist insbesondere ein \definitionsverweis {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.
\inputfaktbeweis
{Boolescher Verband/Komplementäregeln/Fakt}
{Lemma}
{}
{
\faktsituation {In einem
\definitionsverweis {booleschen Verband}{}{}
$M$}
\faktuebergang {gelten die folgenden Rechenregeln.}
\faktfolgerung {\aufzaehlungfuenf{Zu jedem Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es genau ein Element
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x \sqcap y
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x \sqcup y
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es wird mit $\neg x$ bezeichnet.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \neg \neg x
}
{ =} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es ist
\mavergleichskette
{\vergleichskette
{ \neg 0
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \neg 1
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \neg ( x \sqcap y)
}
{ =} { \neg x \sqcup \neg y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \neg ( x \sqcup y)
}
{ =} { \neg x \sqcap \neg y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungfuenf{Es seien
\mathkor {} {y} {und} {z} {}
Komplemente von $x$. Dann ist
\mavergleichskettedisp
{\vergleichskette
{y
}
{ =} { y \sqcup 0
}
{ =} { y \sqcup (x \sqcap z)
}
{ =} { (y \sqcup x) \sqcap (y \sqcup z)
}
{ =} { 1 \sqcap (y \sqcup z)
}
}
{
\vergleichskettefortsetzung
{ =} { y \sqcup z
}
{ } {}
{ } {}
{ } {}
}{}{.}
Da ebenso
\mavergleichskette
{\vergleichskette
{z
}
{ = }{ y \sqcup z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, folgt
\mavergleichskette
{\vergleichskette
{y
}
{ = }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Siehe
Aufgabe 9.15.
}{Siehe
Aufgabe 9.16.
}{Siehe
Aufgabe 9.17.
}{Siehe
Aufgabe 9.22.
}
Die letzten beiden Regeln nennt man \stichwort {Regeln von de Morgan} {.}
\zwischenueberschrift{Der Einbettungssatz für endliche boolesche Verbände}
\inputdefinition
{}
{
Es sei
\mathl{(M, \preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
mit einem
\definitionsverweis {kleinsten Element}{}{}
$0$. Ein Element
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {Atom}{,}
wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und die Beziehung
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nur für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ = }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputbeispiel{}
{
In einer
\definitionsverweis {Potenzmenge}{}{}
\mathl{\mathfrak {P} \, (A )}{} zu einer Menge $A$ sind die einelementigen Mengen $\{x\}$ die
\definitionsverweis {Atome}{}{.}
}
\inputbeispiel{}
{
In den natürlichen Zahlen $\N$ mit der Teilerbeziehung als \definitionsverweis {Ordnungsrelation}{}{} ist $1$ das kleinste Element und die \definitionsverweis {Primzahlen}{}{} sind die \definitionsverweis {Atome}{}{.}
}
{Geordnete Menge/Atome/Einfache Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(M, \preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
mit einem
\definitionsverweis {kleinsten Element}{}{}
$0$ und mit der Eigenschaft, dass zu je zwei Elementen das
\definitionsverweis {Infimum}{}{}
\mathl{x \sqcap y}{} existiert.}
\faktuebergang {Dann gelten folgende Eigenschaften.}
\faktfolgerung {\aufzaehlungdrei{Wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Atom}{}{}
ist, so ist
\mavergleichskette
{\vergleichskette
{ a \sqcap x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{ a \sqcap x
}
{ = }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle $x$.
}{Wenn
\mathkor {} {a} {und} {b} {}
verschiedene Atome sind, so ist
\mavergleichskette
{\vergleichskette
{ a \sqcap b
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es sei $M$ endlich. Dann gibt es zu jedem
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M \setminus \{0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Atom $a$ mit
\mavergleichskette
{\vergleichskette
{a
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 9.18. }
\inputfaktbeweis
{Boolescher Verband/Endlich/Eindeutige Darstellung mit Atomen/Fakt}
{Lemma}
{}
{
\faktsituation {In einem endlichen
\definitionsverweis {booleschen Verband}{}{}}
\faktfolgerung {besitzt jedes Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine eindeutige Darstellung der Form
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} { a_1 \sqcup \ldots \sqcup a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Atomen}{}{}
$a_j$.}
\faktzusatz {}
\faktzusatz {}
}
{
Jedes Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nur größergleich endlich vielen Atomen, wir führen zum Nachweis der Existenz Induktion über diese Anzahl. Bei
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nimmt man die leere Vereinigung. Ein Atom wird durch sich selbst dargestellt. Es sei
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein beliebiges Element. Nach
Lemma 9.20 (3)
gibt es ein Atom
\mavergleichskette
{\vergleichskette
{a
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir betrachten
\mavergleichskettedisp
{\vergleichskette
{x'
}
{ =} { x \sqcap \neg a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen
\mavergleichskettedisp
{\vergleichskette
{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
\mavergleichskettedisp
{\vergleichskette
{x'
}
{ =} { a_1 \sqcup \ldots \sqcup a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und damit
\mavergleichskettealign
{\vergleichskettealign
{x
}
{ =} { x \sqcap 1
}
{ =} { x \sqcap ( \neg a \sqcup a)
}
{ =} { (x \sqcap \neg a) \sqcup (x \sqcap a)
}
{ =} { (x \sqcap \neg a) \sqcup a
}
}
{
\vergleichskettefortsetzungalign
{ =} { x' \sqcup a
}
{ =} { a_1 \sqcup \ldots \sqcup a_n \sqcup a
}
{ } {
}
{ } {
}
}
{}{.}
Zur Eindeutigkeit. Sei
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ { \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.
Der folgende Einbettungssatz zeigt, dass alle endlichen booleschen Algebren von einer ganz bestimmten Bauart sind. Es gibt auch ähnliche Aussagen ohne die Endlichkeitsvoraussetzung.
\inputfaktbeweis
{Boolescher Verband/Endlich/Einbettung/Fakt}
{Satz}
{}
{
\faktsituation {Jeder endliche
\definitionsverweis {boolesche Verband}{}{}
$B$}
\faktfolgerung {ist
\definitionsverweis {isomorph}{}{}
zur
\definitionsverweis {Potenzmenge}{}{}
einer endlichen Menge.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $A$ die Menge der
\definitionsverweis {Atome}{}{}
von $B$. Wir betrachten die Abbildung
\maabbeledisp {} {B} { \mathfrak {P} \, (A )
} {x} { { \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
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} { a_1 \sqcup \ldots \sqcup a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{y
}
{ =} { b_1 \sqcup \ldots \sqcup b_m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann ist nach dem allgemeinen Distributivgesetz und
Lemma 9.20 (2)
\mavergleichskettedisp
{\vergleichskette
{ 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.