DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Definition: Eine geordnete Menge (V,) heißt verbandsgeordnet falls zu je zwei Elementen x, y das Supremum x y und das Infimum x y existieren.

Beispiel 1: Auf der Mengen N der natürlichen Zahlen ist die Teilbarkeitsrelation "|" eine Ordnungsrelation. Bzgl. dieser Relation ist eine obere Schranke von {a,b} ein gemeinsames Vielfaches, und eine untere Schranke ein gemeinsamer Teiler. Da es zu je zwei natürliche Zahlen a und b ein kleinstes gemeinsames Vielfaches kgV(a,b) und einen größten gemeinsamen Teiler ggT(a,b), ist (N, | ) verbandsgeordnet.

Beispiel 2: Für jede Menge M ist die Teilmengenrelation "" eine Ordnungsrelation auf der Potenzmenge P(M). A B ist gerade A B, A B ist A B.

Für x,y V gilt genau dann x y falls y = x y ist (genau dann wenn x = x y ist), (siehe hier).

Für "" und "" gelten eine Reihe von Eigenschaften: Kommutativität a b = b a, a b = b a und Idempotenz a a = a, sowie a a = a sind wegen der Symmetrie der Definition von Supremum und Infimum offensichtlich. Auch die Assoziativgesetze a(bc)= (ab)c, a(bc)= (ab)c, folgen mit diesem Lemma leicht: a(bc)= sup{a,b,c} = sup{c,a,b} = c(ab)= (ab)c, und genauso fürs Infimum.
Die Absorptionsgesetze bedürfen einen Beweis: Nach Definition des Supremums als obere Schranke gilt a a b. Deshalb ist a größte untere Schranke von {a,a b}, also a = a (a b). Genauso zeigt man a = a (a b).

In verbandsgeordneten Mengen hat jede endliche Menge {a₁, ... , a_k} ein Supremum a₁ (a₂ ... (a_k-1 a_k)...)), und entsprechend ein Infimum, wie sich durch mehrmaliges Anwenden des vorigen Lemmas ergibt. Trotzdem kann es unendliche Mengen geben, die kein Supremum oder Infimum haben. Verbandsgeordnete Mengen, bei denen jeder Menge ein Supremum und ein Infimum existiert, werden vollständig genannt. Endliche verbandsgeordnete Mengen sind also immer vollständig.

Übungsaufgabe: Gibt es in Beispiel 1 (N, | ) zu jeder Menge ein Supremum oder zu jeder Menge ein Infimum?

Übungsaufgabe: Für eine Menge M sei T(M) die Menge aller transitiven Relationen auf M. Zeigen Sie, daß  (T(M), ) ein Verband ist. Hinweis

Übungsaufgabe: Sei (M,) eine geordnete Menge. Wir haben schon gesehen, daß die Menge der primitiven Ideale, geordnet durch "", eine zu (M,) isomorphe geordnete Menge ist. Zeigen Sie, daß die Menge aller Ideale von (M,) einen Verband bildet.

Definition: Gegeben sei eine Menge V und zwei binäre Verknüpfungen "" und "" auf V. Falls folgende Gesetze gelten (jeweils für alle a,b,c V): Assoziativgesetze: a(bc)= (ab)c, sowie a(bc)= (ab)c . Kommutativgesetze: a b = b a, sowie a b = b a . Absorptionsgesetze: a ( a b ) = a, sowie a ( a b) = a. Idempotenz: a a = a, sowie a a = a. so nennt man (V,,) einen Verband

Für jeden Verband (V,,) kann man eine Relation auf V definieren durch x y falls x y = y.

Dann ist (V,) verbandsgeordnet. Beweis:

Dualitätsprinzip für Verbände: Da die Verbansdefinition völlig symmetrisch in '', '' ist, erhält man aus jeder richtigen Aussage in Verbänden wieder eine richtige Aussage durch Vertauschen der Symbole '' und ''.

i I

i I

Interessant ist nun, daß beide so entstehenden Strukturen übereinstimmen. Damit ist gemeint: Die verbandsgeordnete Menge des kartesischen Produkts des Verbandes einer verbandsgeordneten Menge ist gleich dem kartesischen Produkt der ursprünglichen verbandsgeordneten Menge, und umgekehrt ...

Test

Was ist ggT(3150,kgV(6600,3150))?