Verband (Mathematik)

Inhaltsverzeichnis

1 Definition 2 Ordnungsstruktur 2.1 Hasse-Diagramme 3 Spezielle Verbände 3.1 Eigenschaften 4 Homomorphismen und Unterverbände 5 Beispiele für Verbände 5.1 Total geordnete Menge 5.2 Teilerverband 5.3 Teilmengenverband 5.4 Untergruppenverband 5.5 Diagramme einiger Verbände 6 Begriffe im Zusammenhang mit Verbänden

Definition

Man sollte von Anfang an klarmachen dass Verband (äquivalent und dabei anschaulicher) auch über Ordnungsstruktur definiert werden kann).

Wir sollten diesen Artikel unbedingt so umschreiben die Verknüpfungen im allgemeinen Fall als ∨ ∧ und nicht als ∪ und ∩ werden denn die Rechenregeln zumindest bestimmter nichtdistributiver stimmen nicht mit denen der Mengenoperationen ∪ ∩ überein.

Ein (algebraischer) Verband ( V <math>\cap</math> <math>\cup</math>) ist eine nichtleere Menge V mit zwei inneren binären Verknüpfungen <math>\cap</math> (Durchschnitt engl. meet Infimum) und <math>\cup</math> (Vereinigung engl. join Supremum) die folgenden Bedingungen für alle u v w aus V genügen:

Kommutativität :

• u <math>\cap</math> v = v <math>\cap</math> u und
• u <math>\cup</math> v = v <math>\cup</math> u ;

Assoziativität :

• u <math>\cap</math> ( v <math>\cap</math> w ) = ( u <math>\cap</math> v ) <math>\cap</math> w und
• u <math>\cup</math> ( v <math>\cup</math> w ) = ( u <math>\cup</math> v ) <math>\cup</math> w ;

Absorptionsgesetze :

• u <math>\cap</math> ( u <math>\cup</math> v ) = u und
• u <math>\cup</math> ( u <math>\cap</math> v ) = u .

Aus diesen Bedingungen folgt die Idempotenz beider Verknüpfungen:

• u <math>\cap</math> u = u und
• u <math>\cup</math> u = u .

V ist also bezüglich jeder einzelnen Verknüpfung kommutative Halbgruppe in der jedes Element idempotent ist. Verknüpfungen treten bei den Absorptionsgesetzen in Wechselwirkung.

Vertauscht man die beiden Verknüpfungen erhält den zu V dualen Verband .

Ordnungsstruktur

Mit dem Absorptionsgesetz erkennt man die der Äquivalenz

v <math>\cap</math> w = v gdw. v <math>\cup</math> w = w .

Man kann auf V eine partielle Ordnung definieren durch

v ≤ w genau dann wenn v <math>\cap</math> w = v .

Bezüglich dieser Halbordnung hat jede zweielementige { v w } ein Supremum s = v <math>\cup</math> w und ein Infimum i = v <math>\cap</math> w . Dabei ist ein Element s ein Supremum von { v w } wenn gilt

• 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 bei der jede zweielementige Teilmenge ein Infimum ein Supremum hat zwei Verknüpfungen definieren die Verbandsaxiome erfüllen.

Die Ordnung des dualen Verbandes ist umgekehrte Ordnung (aus kleinergleich wird größergleich).

Hasse-Diagramme

Eine endliche halbgeordnete Menge ( M ≤) kann man durch einen gerichteten Graphen darstellen den man Hasse-Diagramm nennt. Dieser Graph enthält alle Elemente M als Knoten. Die Kanten werden nach Regel eingefügt:

Sind a und b Elemente von M so dass a < b ist und es kein Element zwischen a und b gibt (d.h. kein c mit a < c < b ) dann geht von a nach b eine Kante.

Vom Aussehen diese Diagramme leitet sich englische Name lattice (Gitter) für Verband ab.

Spezielle Verbände

Im folgenden meinen wir mit dem V " stets den Verband ( V <math>\cap</math> <math>\cup</math>).

Ein Verband V heißt vollständig wenn jede (auch unendliche und die leere) Teilmenge ein Supremum ein Infimum hat.

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

<math>\bigcap M = \bigcup \{ x \in : (\forall\ y\in M: y \le x)

Ein Verband V heißt distributiv wenn jede Verknüpfung distributiv über der anderen ist d.h.

u <math>\cap</math> ( v <math>\cup</math> w ) = ( u <math>\cap</math> v ) <math>\cup</math> ( u <math>\cap</math> w )

u <math>\cup</math> ( v <math>\cap</math> w ) = ( u <math>\cup</math> v ) <math>\cap</math> ( u <math>\cup</math> w )

Falls die Verknüpfung <math>\cap</math> ein neutrales Element 1 hat

a <math>\cap</math> 1 = a

a <math>\cup</math> 1 = 1.

Falls die Verknüpfung <math>\cup</math> ein neutrales 0 hat

a <math>\cup</math> 0 = a

a <math>\cap</math> 0 = 0.

Das neutrale Element der einen Verknüpfung also ein absorbierendes Element der anderen Verknüpfung. Ein Verband heißt beschränkt wenn er nach oben und nach beschränkt ist also für beide Verknüpfungen ein Element hat.

Für ein gegebenes Element a eines beschränkten Verbandes nennt man ein b mit der Eigenschaft

a <math>\cap</math> b = 0 und a <math>\cup</math> b = 1

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

Eigenschaften

Jeder vollständige Verband V ist beschränkt mit

<math>1 := \bigcap \emptyset = \bigcup V</math>

<math>0 := \bigcup \emptyset = \bigcap V</math>

Jeder endliche Verband V ist vollständig und beschränkt mit 1 0 wie eben.

In einem distributiven beschränkten Verband ist Komplement eines Elements a im Falle seiner Existenz eindeutig bestimmt schreibt es oft als a ^c (vor allem bei Teilmengenverbänden) oder ¬ a (vor allem bei Anwendungen in der

Beweis: Angenommen b und c wären verschiedene Komplemente von a dann ist auch d := b <math>\cap</math> c ein Komplement von a (folgt mit Distributivität). Es ist d ≤ b und d ≤ c o.E. sei d < b . Dann ist b <math>\cap</math> ( d <math>\cup</math> a ) = b und ( b <math>\cap</math> d ) <math>\cup</math> ( b <math>\cap</math> a ) = d im Widerspruch zur Distributivität.

In einem distributiven beschränkten Verband gilt

¬0 = 1 ¬1 = 0.

¬(¬ a ) = a .

Für weitere Eigenschaften Boolescher Verbände siehe dort.

Homomorphismen und Unterverbände

Sind ( V ^ v) und ( W <math>\cap</math> <math>\cup</math>) zwei Verbände und f : V -> W eine Funktion so dass für alle a b aus V gilt

f ( a ^ b ) = f ( a ) <math>\cap</math> f ( b )

f ( a v b ) = f ( a ) <math>\cup</math> f ( b )

Die Klasse aller Verbände bildet mit diesem Homomorphismusbegriff Kategorie .

Ein Verbandshomomorphismus ist gleichzeitig ein Ordnungshomomorphismus 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 <math>\cap</math> b und a <math>\cup</math> b in W

Jeder Unterverband ist wieder eine halbgeordnete mit Supremum und Infimum für endliche Teilmengen nicht jede halbgeordnete Teilmenge mit Supremum und für endliche Teilmengen ist auch ein Unterverband gilt erst wenn es dieselben Infima und wie im großen Verband sind.

Zum Beispiel ist die rechts dargestellte Abbildung f zwischen den Verbänden V und W kein Homomorphismus da f ( b <math>\cup</math> c ) = n aber f ( b ) <math>\cup</math> f ( c ) = m . Außerdem ist aus demselben Grund das f ( V ) = { j k l n } zwar ein Verband (mit k <math>\cup</math> l = n ) aber kein Unterverband von W .

Beispiele für Verbände

Hier fehlen Beispiele für den allgemeinsten Fall nichtdistributiven Verbands.

Total geordnete Menge

Jede total geordnete Menge M ist ein distributiver Verband mit den Minimum und Maximum . Insbesondere gilt für alle a b c aus M :

min( a max( b c )) = max(min( a b ) min( a c ))

max( a min( b c )) = min(max( a b ) max( a c )).

Nur im Fall einer einelementigen Menge M ist der Verband komplementär.

Beispiele für die übrigen Eigenschaften:

• Das abgeschlossene reelle Intervall [0 1] und die erweiterte reelle ( R mit ∞ und -∞) sind jeweils distributive Verbände (und damit beschränkt).
• Das offene reelle Intervall (0 1) die R Q und Z sind jeweils unvollständige unbeschränkte distributive Verbände.
• Das rationale Intervall [0 1] <math>\cap</math> Q ist ein unvollständiger beschränkter distributiver Verband.
• Die Menge N ₀ ist ein unvollständiger distributiver Verband mit 0.

Teilerverband

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 Einselement n (neutralem Element für ggT) und Nullelement (neutralem Element für kgV). Er heißt Teilerverband von n . Die Absorptionsgesetze und Distributivgesetze für ggT kgV folgen dabei z.B. mit der Primfaktorzerlegung den Eigenschaften von min und max man sie aber auch durch Teilbarkeitsbetrachtungen herleiten. Der ist genau dann komplementär (und damit boolesch ) wenn n quadratfrei ist d.h. wenn n keine Quadratzahl als Teiler hat. Die auf T ist die Teiler-Relation:

a ≤ b gdw. a | b (gdw. ggT( a b ) = a ).

Die Menge N ₀ aller natürlichen Zahlen mit 0 bildet mit ggT und einen vollständigen distributiven beschränkten Verband mit Nullelement und Einselement 0.

Teilmengenverband

Für eine Menge M bildet die Potenzmenge P( M ) mit den Verknüpfungen Durchschnitt <math>\cap</math> und <math>\cup</math> einen vollständigen booleschen Verband mit Einselement M (neutralem Element für <math>\cap</math>) und Nullelement (neutralem Element für <math>\cup</math>) sowie Komplement A ^c = M \ A für A . Er heißt Teilmengenverband von M . Die Halbordnung auf T ist die Mengeninklusion:

A ≤ B gdw. A ⊆ B (gdw. A <math>\cap</math> B = A ).

Man kann auch echte Teilmengen von M ) betrachten. Diese sind jedoch nicht alle Die Teilmengen die Verbände sind sind distributiv jedoch weder vollständig sein noch neutrale Elemente Komplemente haben. (Ein Beispiel dafür ist der der rechts-unendlichen reellen Intervalle [ a ∞) mit a aus R .) Sie zu studieren ist jedoch nützlich gilt:

Jeder endliche distributive Verband ist isomorph zu einem Mengenverband.

Untergruppenverband

Für eine Gruppe ( G *) bildet die Menge A aller Untergruppen von G einen beschränkten distributiven Verband mit den "Durchschnitt" und "Erzeugnis der Vereinigung". Er heißt Untergruppenverband von G .

Ebenso bilden

• die Unterringe eines Ringes
• die Unterkörper eines Körpers
• die Untermoduln eines Moduls
• die Ideale eines Ringes

Schränkt man die Menge der Untergruppen Obergruppen einer festen Untergruppe U ein so bilden alle diese Zwischengruppen V : U ≤ V ≤ G } einen beschränkten distributiven Verband. Analog dazu es Verbände von Zwischenringen Zwischenkörpern Zwischenmoduln Zwischenidealen.

Besonderes Interesse hat man am Untergruppenverband Galoisgruppe einer galoisschen Körpererweiterung L / K denn er ist isomorph zum dualen von L / K .

Diagramme einiger Verbände

Beispiele für Teilerverbände und dazu isomorphe

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 = 2 2 ·3 Mengenverband { {} {1} {2} {1 {1 3} {1 2 3} } - distributiv mit neutralen Elementen - nicht komplementär	12 / \ 4 6 | | 2 3 \ / 1	{1 2 3} / \ {1 {1 2} | / | {1} {2} / { }

Andere Beispiele für Verbände sind:

Verband ( N 0 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 a und b nicht vergleichbar sind.
a / | \ b c \ | / e	Verband mit Nullelement a und Einselement e ; nicht distributiv. Die Komplemente von b sind c und d .

Begriffe im Zusammenhang mit Verbänden

Siehe auch Hierarchie mathematischer Strukturen

Verbände spielen eine fundamentale Rolle in einem möglichen Aufbau) der universellen Algebra .

Auf der englischen Seite steht noch einiges Idealen und Filtern.

Bücher zum Thema Verband (Mathematik)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.