Zum Inhalt springen

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

Aus Wikiversity
... und ein Vorlesungsminischwein diskutiert.




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.

  1. Die beiden Verknüpfungen und sind kommutativ und assoziativ.
  2. Es ist
  3. Es ist
  1. 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.

  2. Es ist direkt

    Ferner ist

    und somit ist eine obere Schranke von und von und daher ist

    Aus der Antisymmetrie folgt

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


Ein Verband heißt distributiv, wenn in ihm die Distributivgesetze

und

gelten.



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.

  1. Zu jedem Element gibt es genau ein Element mit und . Es wird mit bezeichnet.
  2. Es ist
  3. Es ist und .
  4. Es ist
  5. Es ist
  1. Es seien und Komplemente von . Dann ist

    Da ebenso gilt, folgt .

  2. Siehe Aufgabe 9.15.
  3. Siehe Aufgabe 9.16.
  4. Siehe Aufgabe 9.17.
  5. 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.

  1. Wenn ein Atom ist, so ist oder für alle .
  2. Wenn und verschiedene Atome sind, so ist .
  3. Es sei endlich. Dann gibt es zu jedem ein Atom mit .

Beweis

Siehe Aufgabe 9.18.



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.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)