Verband (Mathematik)

Ein Verband ist in der Mathematik eine Struktur, die sowohl als Ordnungsstruktur als auch als algebraische Struktur vollständig beschrieben werden kann. Als Ordnungsstruktur ist ein Verband dadurch gekennzeichnet, dass es zu je zwei Elementen , ein Supremum gibt, d. h. ein eindeutig bestimmtes kleinstes Element, das größer oder gleich und ist, und umgekehrt ein Infimum , ein größtes Element, das kleiner oder gleich und ist. Als algebraische Struktur ist ein Verband dadurch gekennzeichnet, dass es zwei assoziative und kommutative Operationen gibt, für die die Absorptionsgesetze kennzeichnend sind: Für beliebige Elemente gilt   und   .

Für jede in der Verbandstheorie vorkommende algebraische Aussage gibt es eine direkte Übersetzung in eine Ordnungsaussage und umgekehrt. Diese Übersetzung ist in den meisten Fällen auch anschaulich nachzuvollziehen. Die Möglichkeit, Ergebnisse doppelt zu interpretieren und dadurch besser zu verstehen, macht die Untersuchung und die Verwendung von Aussagen aus der Verbandstheorie so interessant. Der Begriff Verband wurde im hier beschriebenen Sinne von Fritz Klein-Barmen geprägt.Leo Corry: Modern Algebra and the Rise of Mathematical Structures, Springer, 2004, ISBN 3-7643-7002-5, S. 267

Obwohl diese doppelte Charakterisierung auf den ersten Blick sehr speziell aussieht, treten Verbände häufig auf: Die z. B. in der Mengenlehre, der Logik und als Schaltalgebren auftretenden Booleschen Algebren sind Verbände. Totale Ordnungen, die z. B. in den verschiedenen Zahlbereichen wie (natürliche Zahlen), (ganze Zahlen), (rationale Zahlen) oder (reelle Zahlen) auftreten, sind Verbände. Für jede beliebige natürliche Zahl ist die Menge der Teiler (durch die Teilbarkeit geordnet) ein Verband. Die Unterstrukturen einer beliebigen algebraischen oder sonstigen Struktur bilden einen Verband mit der Teilmengenrelation als Ordnung.

In der Literatur sind auch die Symbole und anstelle von und verbreitet. Diese Notation wird hier aufgrund von technischen Einschränkungen allerdings nicht verwendet.

In einer früher üblichen Terminologie wurde ein Verband (nach Richard Dedekind) auch als Dualgruppe bezeichnet.

Präzisierung Verbände als algebraische Strukturen Ein Verband ist eine Menge mit zwei inneren binären Verknüpfungen (Vereinigung, engl. join) und (Durchschnitt, engl. meet), die folgenden Bedingungen für alle , , aus genügen:

Assoziativgesetze: , .

Kommutativgesetze: , .

Absorptionsgesetze: , .

Aus diesen Bedingungen folgt die Idempotenz beider Verknüpfungen: , .

ist also bezüglich jeder einzelnen Verknüpfung ein Halbverband, d. h. eine kommutative Halbgruppe, in der jedes Element idempotent ist. Die Verknüpfungen treten bei den Absorptionsgesetzen in Wechselwirkung.

Verbände als Ordnungsstrukturen Man kann nach einer Idee von Leibniz auf eine Halbordnung definieren durch:

Mit dem Absorptionsgesetz erkennt man die Gültigkeit der Äquivalenzen

Bezüglich dieser Halbordnung hat jede zweielementige Teilmenge ein Supremum (obere Grenze) und ein Infimum (untere Grenze) . Dabei ist ein Element ein Supremum von , wenn gilt: und (d. h. ist obere Schranke). Aus und folgt (d. h. ist die kleinste obere Schranke). Analoges gilt für das Infimum . Man kann per Induktion zeigen, dass jede nichtleere endliche Teilmenge ein Supremum und ein Infimum hat. Man schreibt allgemein das Supremum einer Menge als , und das Infimum von als , falls diese existieren.

Umgekehrt kann man für eine halbgeordnete Menge, bei der jede zweielementige Teilmenge ein Infimum und ein Supremum hat, definieren:   und   . Die beiden Verknüpfungen erfüllen dann die Verbandsaxiome, wie man leicht nachrechnet.

Hasse-Diagramme für einige Beispiele

Eine endliche halbgeordnete Menge kann man durch einen gerichteten Graphen darstellen, den man Hasse-Diagramm nennt.

Wenn man den Graph so anordnet, dass alle Kanten von unten nach oben gerichtet sind, dann kann man die Ordnung leicht sehen: ist dann gleichwertig mit: ist durch einen (nach oben führenden) Kantenzug mit verbunden.

Spezielle Elemente in Verbänden Neutrale Elemente Falls die Verknüpfung ein neutrales Element hat,

dann ist es eindeutig bestimmt und man nennt es das Nullelement des Verbandes. Bzgl. ist absorbierend und bzgl. der Ordnung das kleinste Element: und Man nennt den Verband dann nach unten beschränkt.

Falls die Verknüpfung ein neutrales Element hat,

dann ist es eindeutig bestimmt und man nennt es das Einselement des Verbandes. Bzgl. ist absorbierend und bzgl. der Ordnung das größte Element: und Man nennt den Verband dann nach oben beschränkt.

Ein Verband heißt beschränkt, wenn er nach unten und nach oben beschränkt ist, also für beide Verknüpfungen ein neutrales Element hat.

Komplementäre Elemente

Für ein gegebenes Element eines beschränkten Verbandes nennt man ein Element mit der Eigenschaft und ein Komplement von .

Ein beschränkter Verband, in dem jedes Element (mindestens) ein Komplement hat, heißt komplementärer Verband.

Im Allgemeinen kann es zu einem Element mehrere komplementäre Elemente geben.

Es gilt aber: In einem distributiven beschränkten Verband ist das Komplement eines Elements im Falle seiner Existenz eindeutig bestimmt. Man schreibt es oft als (vor allem bei Teilmengenverbänden), (vor allem bei Anwendungen in der Logik) oder .

In jedem beschränkten Verband gilt . In einem distributiven beschränkten Verband gilt: Falls ein Komplement hat, dann hat auch ein Komplement, nämlich: .

Spezielle Verbände Modulare Verbände mini|180px|, der minimale nicht-modulare Verband

Ein Verband heißt modular, falls gilt: für alle .

Für einen Verband sind wiederum jeweils äquivalent: ist modular. für alle . für alle . für alle . Ein nicht modularer Verband enthält immer den Verband als Unterverband.H.Gericke, Theorie der Verbände. 2. Auflage. Mannheim 1967, S. 76 (Figur dazu auf S. 70)

Distributive Verbände mini|180px|, der minimale modulare, nicht-distributive Verband

Im Folgenden meinen wir mit dem Verband stets den Verband .

Ein Verband heißt distributiv, wenn die Verknüpfungen in doppelter Hinsicht distributiv sind: für alle und für alle . Da diese beiden Aussagen zueinander äquivalent sind, genügt es, die Gültigkeit eines dieser beiden Distributivgesetze zu verlangen.

Jeder distributive Verband ist modular, aber nicht umgekehrt. Ein modularer Verband, der nicht distributiv ist, enthält immer den Verband , den Verband der Untergruppen der Kleinschen Vierergruppe als Unterverband.H.Gericke, Theorie der Verbände. 2. Auflage. Mannheim 1967, S. 111

Dies ergibt den Test: hat ein Verband weder einen Unterverband der Form noch einen der Form , dann ist er distributiv.

Distributive Verbände sind auch anders zu charakterisieren, denn Birkhoff (1933) und Stone (1936) haben gezeigt: Ein Verband ist genau dann distributiv, wenn er isomorph zu einem Mengenverband ist.G.Grätzer, Lattice Theory, 1971, S. 75

Boolesche Algebren

Ein distributiver komplementärer Verband heißt Boolesche Algebra oder Boolescher Verband.

Eine weitere Verallgemeinerung, bei der statt Komplementen nur relative Pseudokomplemente gefordert werden, heißt Heyting-Algebra.

Vollständige Verbände Ein Verband heißt vollständig, wenn jede (auch die leere ebenso wie gegebenenfalls unendliche) Teilmenge ein Supremum und ein Infimum hat.

Es genügt, für jede Teilmenge die Existenz des Supremums zu verlangen, denn es ist

Jeder vollständige Verband ist beschränkt mit   und  

Jeder endliche, nichtleere Verband ist vollständig, also auch beschränkt.

Eine minimalistische Definition ist: Ein vollständiger Verband ist eine halbgeordnete Menge , in der jede Teilmenge ein Supremum hat. So definiert, ist ein vollständiger Verband natürlich auch ein Verband, mit und .

In einem vollständigen Verband besitzt jede ordnungserhaltende (d. h. monoton wachsende) Abbildung einen größten und einen kleinsten Fixpunkt aufgrund des Fixpunktsatzes von Tarski.

Längenendliche Verbände Wenn jede bezüglich der Ordnung totalgeordnete Teilmenge (Kette) endlich ist, nennt man den Verband längenendlich.Helmuth Gericke: Theorie der Verbände. Bibliographisches Institut, Mannheim 1963, § 6.2 Für viele Beweise innerhalb der Verbandstheorie muss ein Verband nicht endlich sein, sondern es reicht, wenn er längenendlich ist.

Kompakte Elemente und algebraische Verbände Man nennt ein Element eines vollständigen Verbandes kompakt (nach der verwandten Eigenschaft kompakter Räume in der Topologie), wenn jede Teilmenge von mit

eine endliche Teilmenge enthält, für die gilt:

Ein Verband heißt algebraisch, wenn er vollständig ist und wenn jedes Element von das Supremum von kompakten Elementen ist.

Dualität in Verbänden mini|Die beiden Verbände sind dual zueinander (aber offensichtlich nicht isomorph).

Vertauscht man in einem Verband die beiden Verknüpfungen und , erhält man eine neue Struktur . Man nennt die duale Struktur.

Ersetzt man in einer beliebigen Formel der Sprache der Verbandstheorie und setzt überall die beiden Zeichen und wechselseitig füreinander ein und ersetzt außerdem überall 0 durch 1 und umgekehrt, dann nennt man die entstandene Formel die duale Formel von .

Offensichtlich gelten in dem zu dualen Verband die dualen zu den in gültigen Formeln. Da in der Definition eines Verbands zu jeder Formel auch die duale Formel vorkommt, folgt, dass ebenfalls ein Verband ist, der als der zu duale Verband bezeichnet wird.

Aus dieser Beobachtung folgt: Gilt eine Formel in allen Verbänden, dann gilt auch ihre duale Formel in allen Verbänden.

Das Modularitätsgesetz ist selbstdual und die beiden Distributiv-Gesetze sind zueinander dual und die beiden Komplementärgesetze sind zueinander dual. Daher gilt entsprechend: Gilt eine Formel in allen modularen oder in allen distributiven Verbänden oder in allen Booleschen Algebren, dann gilt auch die duale Formel in den entsprechenden Verbänden.

Unterstrukturen

Unterverbände Ein Unterverband von ist eine Teilmenge , die mit den eingeschränkten Verknüpfungen von ein Verband ist, d. h. es liegen und in für alle aus

Teilverbände Ein Teilverband von ist eine Teilmenge , die ein Verband ist, d. h. ist eine halbgeordnete Menge mit Supremum und Infimum für endliche Teilmengen.

Natürlich ist jeder Unterverband ein Teilverband, aber nicht umgekehrt.

Hier ist eine der wenigen Stellen, wo man den Unterschied in der Betrachtungsweise merkt: Für Verbände als Ordnungsstrukturen sind alle Teilverbände Unterstrukturen, für Verbände als algebraische Strukturen sind nur die Unterverbände Unterstrukturen.

Man geht weder bei Teilverbänden noch bei Unterverbänden davon aus, dass die neutralen Elemente in der Unterstruktur erhalten bleiben. Sonst muss man ausdrücklich von einem Verband mit und reden.

Ideale und Filter

Ein Ideal ist ein Unterverband eines Verbandes , der zusätzlich folgende Bedingung erfüllt: sind und , dann ist . (Die Definition entspricht also formal der Definition, die man in einem Ring erwartet).

Bezüglich der Halbordnung auf gilt aber . Daher kann man die Definition auch so interpretieren: Ein Ideal ist ein Unterverband, der zusammen mit einem Element auch alle Elemente von enthält, die kleiner als sind.

Filter werden dual zu Idealen definiert: Ein Filter ist ein Unterverband, der zusammen mit einem Element auch alle Elemente von enthält, die größer als sind.

Homomorphismen mini|Die hier dargestellte monotone Abbildung zwischen den Verbänden und ist kein Homomorphismus, da , aber . Außerdem ist aus demselben Grund das Bild zwar ein Verband (mit ), aber kein Unterverband von .

Sind und zwei Verbände und eine Funktion, sodass für alle aus gilt

dann heißt Verbandshomomorphismus. Ist zusätzlich bijektiv, dann heißt Verbandsisomorphismus und die Verbände und sind isomorph.

Falls und vollständig sind und sogar