Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 9/kontrolle
- Verbände
In dieser Vorlesung besprechen wir eine Struktur, in der Verknüpfungseigenschaften und Ordnungseigenschaften eng miteinander verbunden sind.
Eine geordnete Menge mit der Eigenschaft, dass für je zwei Elemente ein Infimum und ein Supremum existiert, heißt Verband.
Es muss also gelten und jedes oberhalb von und von ist auch oberhalb von . 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.
Eine total geordnete Menge ist stets ein Verband, da ja zu zwei Elementen das eine Element das Minimum und das andere das Maximum der beiden ist.
Die positiven natürlichen Zahlen 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 mit der Teilbarkeitsrelation, wobei dann der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache richtig zu definieren sind.
Es sei eine Menge und 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 und in der allgemeinen Definition eines Verbandes.
Es sei eine Gruppe und die Menge aller Untergruppen von . Dann ist 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.
Es sei eine endliche Körpererweiterung und die Menge aller Zwischenkörper. Dann ist 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.
Wir betrachten eine Menge 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 und zueinander äquivalent (Kontraposition). Über die Implikation ist diese Menge eine Ordnung. Mit der Konjunktion (und) als Infimum und der Disjunktion (oder) als Supremum liegt ein Verband vor.
In einem Verband gelten die folgenden Eigenschaften.
- Die beiden Verknüpfungen und sind kommutativ und assoziativ.
- Es ist
- Es ist
- Die Kommutativität ist klar. Zum Nachweis der Assoziativität seien gegeben. Wir vergleichen und . Es ist
und ebenso
Damit ist also
Da das Supremum von und ist, folgt
Daher ist auch
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
Ferner ist
und somit ist eine obere Schranke von und von und daher ist
Aus der Antisymmetrie folgt
- Wird wie (2) bewiesen.
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.
Eine Menge mit zwei kommutativen und assoziativen Verknüpfungen und heißt algebraischer Verband, wenn die Absorptionsgesetze
und
gelten.
In einem algebraischen Verband nennt man die durch
falls
definierte Ordnung, die zugehörige Ordnung.
Zunächst ist durch diese Definition nur eine Relation auf gegeben, die wir nun als Ordnung nachweisen müssen.
Zu einem algebraischen Verband
ist die zugehörige Ordnung in der Tat eine Ordnung, die und erfüllt.
Zunächst ist unter Verwendung der beiden Absorptionsgesetze
was die Reflexivität der Relation bedeutet. Zum Nachweis der Transitivität seien und gegeben. Das bedeutet und . Damit ist
was bedeutet. Zum Nachweis der Antisymmetrie sei und . Daraus ergibt sich sofort .
Wir zeigen nun, dass das Infimum von und in der soeben etablierten Ordnung ist. Wegen
ist und ebenso , es ist also
Es sei nun . Dies bedeutet und . Dann ist
also . Somit ist das Infimum.
Um die Aussage über das Supremum zu beweisen, zeigt man zunächst, dass zu äquivalent ist. Wenn nämlich das erste gilt, so ist
nach einem Absorptionsgesetz. Wenn das zweite gilt, so ist
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.
- Weitere Eigenschaften von Verbänden
In einem Verband ist ein neutrales Element bezüglich der -Operation, also ein Element mit
für alle , nichts anderes als ein kleinstes Element in der Ordnung von . Ebenso ist ein neutrales Element bezüglich nichts anderes als ein größtes Element von .
Ein Verband heißt beschränkt, wenn es in ihm ein kleinstes Element und ein größtes Element gibt.
Ein beschränkter Verband heißt komplementär, wenn es zu jedem ein mit und gibt.
- Boolesche Verbände
Ein Verband 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.
In einem booleschen Verband gelten die folgenden Rechenregeln.
- Zu jedem Element gibt es genau ein Element mit und . Es wird mit bezeichnet.
- Es ist
- Es ist und .
- Es ist
- Es ist
- Es seien
und
Komplemente von . Dann ist
Da ebenso gilt, folgt .
- Siehe Aufgabe 9.15.
- Siehe Aufgabe 9.16.
- Siehe Aufgabe 9.17.
- Siehe Aufgabe 9.22.
Die letzten beiden Regeln nennt man Regeln von de Morgan.
- Der Einbettungssatz für endliche boolesche Verbände
Es sei eine geordnete Menge mit einem kleinsten Element . Ein Element heißt Atom, wenn ist und die Beziehung nur für und gilt.
In einer Potenzmenge zu einer Menge sind die einelementigen Mengen die Atome.
In den natürlichen Zahlen mit der Teilerbeziehung als Ordnungsrelation ist das kleinste Element und die Primzahlen sind die Atome.
Es sei eine geordnete Menge mit einem kleinsten Element und mit der Eigenschaft, dass zu je zwei Elementen das Infimum existiert. Dann gelten folgende Eigenschaften.
- Wenn ein Atom ist, so ist oder für alle .
- Wenn und verschiedene Atome sind, so ist .
- Es sei endlich. Dann gibt es zu jedem ein Atom mit .
Beweis
In einem endlichen booleschen Verband
besitzt jedes Element eine eindeutige Darstellung der Form
mit Atomen .
Jedes Element ist nur größergleich endlich vielen Atomen, wir führen zum Nachweis der Existenz Induktion über diese Anzahl. Bei nimmt man die leere Vereinigung. Ein Atom wird durch sich selbst dargestellt. Es sei ein beliebiges Element. Nach Lemma 9.20 (3) gibt es ein Atom . Wir betrachten
Wegen
liegt nicht unterhalb von . Somit liegen unterhalb von weniger Atome als unterhalb von und nach Induktionsvoraussetzung gibt es eine Darstellung
und damit
Zur Eindeutigkeit. Sei
Nehmen wir an, dass nicht in der ersten Darstellung vorkommt. Dann ist
nach Lemma 9.20 (2). Wenn man aber auf die rechte Seite anwendet, so ergibt sich , 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.
Jeder endliche boolesche Verband
ist isomorph zur Potenzmenge einer endlichen Menge.
Es sei die Menge der Atome von . Wir betrachten die Abbildung
Es ergibt sich aus Lemma 9.21, dass dies eine Bijektion ist. Dass auf die leere Menge und auf die Gesamtmenge geht, ist klar. Wegen der Eindeutigkeit der atomaren Darstellung führt diese Abbildung die -Verknüpfung in die Vereinigung über. Es sei
und
Dann ist nach dem allgemeinen Distributivgesetz und Lemma 9.20 (2)
wobei durch alle Atome läuft, die sowohl links als auch rechts vorkommen. Daher führt die Abbildung diese -Verknüpfung in den Durchschnitt über.