Verband (Mathematik)
In der Mathematik ist ein Verband eine bestimmte algebraische Struktur mit zwei Verknüpfungen bzw. eine halbgeordnete Menge mit bestimmten Eigenschaften.
Ein (algebraischer) Verband (V, , ) ist eine nichtleere Menge V mit zwei inneren binären Verknüpfungen (Durchschnitt, engl. meet, Infimum) und (Vereinigung, engl. join, Supremum), die folgenden Bedingungen für alle u, v, w aus V genügen:
Definition
Assoziativität:
Absorptionsgesetze:
Aus diesen Bedingungen folgt die Idempotenz beider Verknüpfungen:
V ist also bezüglich jeder einzelnen Verknüpfung eine kommutative Halbgruppe, in der jedes Element idempotent ist. Die Verknüpfungen treten bei den Absorptionsgesetzen in Wechselwirkung.
Vertauscht man die beiden Verknüpfungen, erhält man den zu V dualen Verband.
Mit dem Absorptionsgesetz erkennt man die Gültigkeit der Äquivalenz
Ordnungsstruktur
Man kann auf V eine partielle Ordnung definieren durch
- v ≤ w genau dann, wenn v w = v.
- v ≤ s und w ≤ s(d.h. s ist obere Schranke)
- aus v ≤ t und w ≤ t folgt s ≤ t (d.h. s ist die kleinste obere Schranke).
Umgekehrt kann man für eine halbgeordnete Menge, bei der jede zweielementige Teilmenge ein Infimum und ein Supremum hat, zwei Verknüpfungen definieren, die die Verbandsaxiome erfüllen.
Die Ordnung des dualen Verbandes ist die umgekehrte Ordnung (aus kleinergleich wird größergleich).
Eine endliche halbgeordnete Menge (M, ≤) kann man durch einen gerichteten Graphen darstellen, den man Hasse-Diagramm nennt.
Dieser Graph enthält alle Elemente von M als Knoten. Die Kanten werden nach folgender Regel eingefügt:
Vom Aussehen diese Diagramme leitet sich der englische Name lattice (Gitter) für Verband ab.
Im folgenden meinen wir mit dem "Verband V" stets den Verband (V, , ).
Ein Verband V heißt vollständig, wenn jede (auch unendliche und die leere) Teilmenge ein Supremum und ein Infimum hat.
Es genügt, für jede Teilmenge die Existenz des Supremums zu verlangen, denn es ist
Hasse-Diagramme
Solch ein Graph ist zyklenfrei und man kann seine Knoten so anordnen, dass alle Kanten "von unten nach oben" gerichtet sind. Ist also a < b, dann ist a unterhalb von b und durch eine Kante mit b verbunden.
Einige solcher Diagramme sind weiter unten angegeben.Spezielle Verbände
Ein Verband V heißt distributiv, wenn jede Verknüpfung distributiv über der anderen ist, d.h.
Falls die Verknüpfung ein neutrales Element 1 hat,
- a 1 = a,
- a 1 = 1.
Falls die Verknüpfung ein neutrales Element 0 hat,
- a 0 = a,
- a 0 = 0.
Das neutrale Element der einen Verknüpfung ist also ein absorbierendes Element der anderen Verknüpfung. Ein Verband heißt beschränkt, wenn er nach oben und nach unten beschränkt ist, also für beide Verknüpfungen ein neutrales Element hat.
Für ein gegebenes Element a eines beschränkten Verbandes nennt man ein Element b mit der Eigenschaft
- a b = 0 und a b = 1
Ein distributiver komplementärer Verband heißt Boolesche Algebra oder Boolescher Verband.
Jeder vollständige Verband V ist beschränkt mit
Jeder endliche Verband V ist vollständig und beschränkt mit 1 und 0 wie eben.
In einem distributiven beschränkten Verband ist das Komplement eines Elements a im Falle seiner Existenz eindeutig bestimmt, man schreibt es oft als ac (vor allem bei Teilmengenverbänden) oder ¬a (vor allem bei Anwendungen in der Logik).
In einem distributiven beschränkten Verband gilt
Eigenschaften
als Einselement und
als Nullelement.
Ist der Verband jedoch nicht distributiv, kann es mehrere Komplemente geben, ein Beispiel wird unten gegeben.
Falls a ein Komplement ¬a hat, dann hat auch ¬a ein Komplement, nämlich:
Für weitere Eigenschaften Boolescher Verbände siehe dort.
Sind (V, ^, v) und (W, , ) zwei Verbände und f: V -> W eine Funktion, so dass für alle a, b aus V gilt
Homomorphismen und Unterverbände
dann heißt f Verbands-Homomorphismus. Ist f zusätzlich bijektiv, dann heißt f Isomorphismus und die Verbände V und W sind isomorph.
Die Klasse aller Verbände bildet mit diesem Homomorphismusbegriff eine Kategorie.
Ein Verbandshomomorphismus ist gleichzeitig ein Ordnungshomomorphismus, d.h. eine monotone Abbildung:
- aus a ≤ b folgt f(a) ≤ f(b).
Ein Unterverband von V ist eine Teilmenge W, die mit den eingeschränkten Verknüpfungen von V ein Verband ist, d.h. es liegen
- a b und a b in W
Jeder Unterverband ist wieder eine halbgeordnete Menge mit Supremum und Infimum für endliche Teilmengen, aber nicht jede halbgeordnete Teilmenge mit Supremum und Infimum für endliche Teilmengen ist auch ein Unterverband, das gilt erst, wenn es dieselben Infima und Suprema wie im großen Verband sind.
Zum Beispiel ist die rechts dargestellte monotone Abbildung f zwischen den Verbänden V und W kein Homomorphismus, da f(b c) = n, aber f(b) f(c) = m. Außerdem ist aus demselben Grund das Bild f(V) = {j,k,l,n} zwar ein Verband (mit k l = n), aber kein Unterverband von W. |
|
Jede total geordnete Menge M ist ein distributiver Verband mit den Verknüpfungen Minimum und Maximum. Insbesondere gilt für alle a,b,c aus M:
Beispiele für die übrigen Eigenschaften:
Betrachtet man für eine natürliche Zahl n die Menge T aller Teiler von n, dann ist (T, ggT, kgV) ein vollständiger distributiver Verband mit Einselement n (neutralem Element für ggT) und Nullelement 1 (neutralem Element für kgV). Er heißt Teilerverband von n. Die Absorptionsgesetze und Distributivgesetze für ggT und kgV folgen dabei z.B. mit der Primfaktorzerlegung aus den Eigenschaften von min und max, man kann sie aber auch durch Teilbarkeitsbetrachtungen herleiten.
Der Verband ist genau dann komplementär (und damit boolesch), wenn n quadratfrei ist, d.h. wenn n keine Quadratzahl als Teiler hat.
Die Halbordnung auf T ist die Teiler-Relation:
Beispiele für Verbände
Total geordnete Menge
Nur im Fall einer einelementigen Menge M ist der Verband komplementär.Teilerverband
Für eine Menge M bildet die Potenzmenge P(M) mit den Verknüpfungen Durchschnitt und Vereinigung einen vollständigen booleschen Verband mit Einselement M (neutralem Element für ) und Nullelement {} (neutralem Element für ) sowie Komplement Ac = M\\A für A. Er heißt Teilmengenverband von M.
Die Halbordnung auf T ist die Mengeninklusion:
Für eine Gruppe (G, *) bildet die Menge A aller Untergruppen von G einen beschränkten distributiven Verband mit den Verknüpfungen "Durchschnitt" und "Erzeugnis der Vereinigung". Er heißt Untergruppenverband von G.
Ebenso bilden
Schränkt man die Menge der Untergruppen auf Obergruppen einer festen Untergruppe U ein, so bilden alle diese Zwischengruppen {V : U ≤ V ≤ G} einen beschränkten distributiven Verband. Analog dazu gibt es Verbände von Zwischenringen, Zwischenkörpern, Zwischenmoduln, Zwischenidealen.
Besonderes Interesse hat man am Untergruppenverband der Galoisgruppe einer galoisschen Körpererweiterung L/K, denn er ist isomorph zum dualen Zwischenkörperverband von L/K.
Beispiele für Teilerverbände und dazu isomorphe Mengenverbände:
Teilmengenverband
Untergruppenverband
mit analogen Verknüpfungen einen Verband.Diagramme einiger Verbände
Teilerverband von 3 Teilmengenverband von {1} | 3 | 1 | {1} | { } |
Teilerverband von 6 = 2·3 Teilmengenverband von {1,2} | 6 / \\ 2 3 \\ / 1 | {1,2} / \\ {1} {2} \\ / { } | ||
Teilerverband von 30 = 2·3·5 (Teilmengenverband von {1,2,3}) | ||||
Teilerverband von 12 = 22·3 Mengenverband { {}, {1}, {2}, {1,2}, {1,3}, {1,2,3} } - distributiv mit neutralen Elementen, - nicht komplementär | 12 / \\ 4 6 | 2 3 \\ / 1 | {1,2,3} / \\ {1,3} {1,2} | {1} {2} \\ / { } |
Andere Beispiele für Verbände sind:
Verband (N0, min, max): - distributiv, - Nullelement 0, - kein Einselement, - Ordnung ist die gewöhnliche Anordnung | | 2 | 1 | 0 |
Der Verband (N, ggT, kgV): - distributiv, - Nullelement 0, - Einselement 1, - nicht komplementär, - enthält jeden Teilerverband als Teilverband |
Weitere Beispiele:
a b | c d | Kein Verband, da {a, b} keine obere Schranke hat. | |
e / \\ a b | c d \\ / f | Kein Verband, da {c, d} zwar obere Schranken a, b, e hat, aber keine kleinste obere Schranke, weil a und b nicht vergleichbar sind. | |
a / | \\ b c d \\ | / e | Verband mit Nullelement a und Einselement e; nicht distributiv. Die Komplemente von b sind c und d. |
Siehe auch Hierarchie mathematischer Strukturen
Verbände spielen eine fundamentale Rolle in (zumindest einem möglichen Aufbau) der universellen Algebra.
Auf der englischen Seite steht noch einiges zu Idealen und Filtern.
Begriffe im Zusammenhang mit Verbänden