VerbandstheorieSkriptum zur Vorlesung im Sommersemester 2011

Thomas VetterleinInstitut für Wissensbasierte Mathematische Systeme

Johannes-Kepler-Universität LinzAltenberger Straße 694040 Linz,Österreich

Thomas.Vetterlein@jku.at

Zusammenfassung

Wir geben einen̈Uberblick über die Theorie der Verbände. Es handelt sich um einealgebraische Struktur, die in vielen Bereichen der Mathematik auftaucht, ja mitderen Hilfe man viele Teile der Mathematik begründen kann.Unser Schwerpunktliegt auf der Logik sowie auf der Geometrie.

Inhaltsverzeichnis

1 Einleitung 3

2 Distributive Verb ände 5

2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Verbände . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Distributive Verbände . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Darstellungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.6 Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Boolesche Algebren 36

3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Komplemente in Verbänden . . . . . . . . . . . . . . . . . . . . . . . 37

3.3 Boolesche Algebren . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.4 Darstellungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.5 Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

1

4 Äquivalenzrelationen und Partitionsverbände 46

4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2 Partitionsverbände . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3 Darstellungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 Modulare Verbände 54

5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.2 Modulare und lineare Verbände . . . . . . . . . . . . . . . . . . . . .55

5.3 Atomistische Verbände . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Projektive Geometrien . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.5 Darstellungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2

1 Einleitung

Verbandstheorie – ist das etwas Abgehobenes? Zu den Zielen dieser Vorlesung gehörtes, das Gegenteil zu demonstrieren. Wenn man will, kann man im Gegenteil den Begriffdes Verbandes als etwas eher Banales ansehen.

In der Tat basiert der Begriff auf recht schlichtenÜberlegungen. Man gehe von ei-ner Menge aus, deren Elemente irgendeine Art von Information repräsentieren. Wennman von inhaltlichen Aspekten einmal absieht, bleibt immernoch eines, was die innereStruktur einer solchen Menge kennzeichnet: die relative Aussagekraft. Eine Informati-on kann mehr aussagen als eine andere, d.h. letztere in ersterer enthalten sein. Durchdiese Beziehung wird die Menge, wie es heißt, partiell geordnet. Setzt man nun vor-aus, daß mit je zwei Informationsstücken auch deren gemeinsamer Durchschnitt sowiederen Vereinigung vorliegt, gelangen wir zum Begriff des Verbandes.

Die Definition mag schlicht sein; sie führt zu einer Theorie, die es in sich hat. Ver-bandstheorie ist ein umfangreiches Gebiet der Algebra und betrifft nicht nur die letzte-re; Bezüge bestehen zur Logik und zur linearen Algebra (in Abgrenzung zur abstraktenAlgebra so bezeichnet) und damit auch zu Geometrie und Analysis.

Was die Theorie aber so faszinierend macht, ist der Umstand,daß Verbände in den ge-nannten Bereichen nicht einfach nur irgendwie auftauchen;dies träfe auf wohl fast alleGebiete der Mathematik zu. Vielmehr ist es in vielen Gebieten möglich, mit Verbändengewissen Typs zu beginnen und zu derjenigen Struktur zu gelangen, die in der jeweili-gen Theorie im Mittelpunkt steht.

Paradebeispiel sind die linearen Räume. Man kann denRn als Menge vonn-Tupelnreeller Zahlen verstehen und reelle Zahlen ihrerseits als Ergebnis eines nichttrivia-len Konstruktionsprozesses. Man kann lineare Räume, und nicht nur solche überR,aber auch durch die inneren Eigenschaften ihrer Unterräume charakterisieren. Die Un-terräume bilden einen Verband; die verwendete Beziehung zwischen Unterräumen istschlicht die, ineinander enthalten zu sein. Projektive Geometrie ist hier das Stichwort,deren Anwendungen bis zu den Grundlagen der Quantenphysik reichen.

Ablauf der Vorlesung

Abschnitt 2 behandelt distributive Verbände, die sich durch Systeme von Teilmengenrealisieren lassen. Wir fügen im nachfolgenden Abschnitt3 eine Komplementfunktionhinzu und gelangen zu booleschen Algebren. Abschnitt 4 hat eine Brückenfunktion zudem, was anschließend folgt. Wir wenden uns der Theorie derÄquivalenzrelationenzu; denn diese bietet sozusagen einen Schirm für die Theorie der Verbände, und zwarohne jede einschränkende Bedingung. Verbände und Unterverbände von̈Aquivalenz-relationen zerfallen in drei Gruppen; der sogenannte Typ 3 (und höher) umfaßt (in zupräzisierendem Sinn) alle Verbände, Typ 2 die modularen und der Typ 1 die linearen.Die modularen und noch mehr die linearen Verbände, die in Kapitel 5 besprochen wer-den, sind von eminentem geometrischem Interesse. Hier ist die projektive Geometrieeinzuordnen, hier ergeben sich die Verbindungen zur linearen Algebra.

3

Wenn eine neue Sorte Verbände eingeführt wird, gehen wir immer nach dem folgendenSchema vor. Wir betrachten erstens ein prototypisches Beispiel; mit diesem wird dieAnwendung der Theorie spezifiert und ermöglicht, sich manchen reichlich abstraktenBegriff konkret vorstellen zu können. Wir entwickeln zweitens die jeweilige Darstel-lungstheorie; das bedeutet zu zeigen, daß sich die betrachtete, abstrakt definierte Klassevon Verbänden mit einer gewissen Klasse von Beispielen exakt deckt. Und drittens gehtes um die Frage, wie man hinsichtlich der betrachteten Verb¨ande Schlüsse ziehen kann,was also daraus gefolgert werden kann, daß zwischen gewissen Elementen eines Ver-bandes gewisse Beziehungen bestehen. Das bedeutet, eine zugehörige Logik anzuge-ben, sofern eine solche existiert. Im Fall der booleschen Algebren ist dies die klassischeAussagenlogik, ansonsten ergeben sich speziellere oder allgemeinere Schlußsysteme.

4

2 Distributive Verb ände

2.1 Motivation

Befassen wir uns zunächst mit den Grundlagen mathematischer Modellierung. Wieentsteht ein mathematisches Modell, was ist überhaupt einmathematisches Modell?

Gegeben sei uns ein Gegenstand, den wir formal beschreiben möchten. Es kann sich umein technisches System handeln, dessen Verhalten es zu beschreiben gilt; es kann sichum einen Körper handeln, dessen Aufenthalt im Raum zu beschreiben ist; es kann sichum eine bestimmte Art von Ereignis handeln, dessen Auftreten zeitlich zu erfassen ist.In einem ersten Schritt hin zu einer Formalisierung des Sachverhaltes müssen wir dieMenge von Situationen spezifieren, die wir unter Bezugnahmeauf ausgewählte Aspek-te erfassen wollen. Dies kann dadurch erfolgen, daß wir gewisse Merkmale auswählen,die manchmal erfüllt sind und manchmal nicht und die zusammengenommen zur Cha-rakterisierung einer Situation ausreichen. Beim technischen System handle es sich bei-spielsweise um eine Waage und interessiere die Gesamtheit möglicher Meßergebnisse.Ein Merkmal wäre, daß sich das Gewicht in einem gewissen Bereich befindet. Beimbeweglichen Körper interessiert der Raumpunkt, in dem er sich aufhält. Je einem mehroder weniger weit ausgedehnten Raumbereich ist ein Merkmalzuordenbar. Beim zeit-lich auszuwertenden Ereignis könnte es sich etwa um radioaktiven Zerfall handeln;von Interesse wären dann die Zeitpunkte der einzelnen Zerfallsvorgänge. Ein Merkmalkann einem Zeitintervall entsprechen, daß innerhalb dessen ein Zerfall stattgefundenhat.

Wir gehen also von einer gewissen Grundmenge zu unterscheidender Situationen aus;man spricht häufig von einer sogenanntenMengen m̈oglicher Welten. Dieser Mengeerfaßbarer Situationen sind des weiteren Merkmale zugeordnet, die in einer gegebenenunter den Situationen gelten oder nicht; wir sprechen im weiteren vonEigenschaften.Formal haben wir es mit einer abstrakten Menge zu tun, deren Elemente möglicheWelten heißen, sowie mit einem System von Teilmengen dieserMenge, welche, wie esheißt, je eine Eigenschaftmodellierenoderrepräsentieren. Im Fall des ersten obigenBeispiels besteht die Menge möglicher Welten aus reellen Zahlen, die je ein Gewichtrepräsentieren; die Eigenschaft, sich in einem Gewichtsbereich aufzuhalten, wird durchje ein Zahlenintervall modelliert.

Was bedeutet nun, den so erfaßten Gegenstand zu”beschreiben“? Beschreiben bedeu-

tet, die hergenommenen Situationen in wechselseitige Zusammenhänge zu setzen. Esgibt zwei Möglichkeiten. Zum einen können die wechselseitigen Beziehungen zwi-schen den möglichen Welten beschrieben werden. Auf den Elementen der reellen Zah-len gilt eine Ordnungsrelation und ist eine Addition definierbar. Dies bedeutet, dieMenge möglicher Welten mit einer Struktur auszustatten, was uns zur Prädikatenlogikerster Stufe führt.

Dies ist jedoch nicht das uns bewegende Thema. Je eine mögliche Welt kann mitder Gesamtheit der in ihr geltenden Eigenschaften identifiziert werden. Beispielsweisekann je ein Gewicht mit dem – einelementigen – Durchschnitt all dieses enthaltenderGewichtsbereiche identifiziert werden. Wir wollen im weiteren auf der Ebene der Ei-

5

genschaften bleiben, die zu den möglichen Welten überhaupt erst geführt haben. Inwechselseitige Beziehungen setzen wir im Rahmen dieser bescheideneren und grund-legenderen Herangehensweise die Eigenschaften selbst.

Es seiW unsere Menge möglicher Welten. Es mögenϕ undψ zwei Eigenschaftensymbolisieren. Die MengeAmodelliereϕ, die MengeB modelliereψ. Die Beziehung,die zwischenA undB herrschen kann, ist die mengentheoretische Inklusion: daßA inB enthalten ist. Ist dies der Fall, giltψ stets, wennϕ gilt. Gemäß unserem Modell stehtϕ für eine Eigenschaft, die stärker ist alsψ; wir sagen auch, daßϕ ψ impliziert.

Wenn man des weiteren mit einer ganzen Reihe von Eigenschaften zu tun hat, kannman im Rahmen des Modells aus diesen neue konstruieren. Wirdwiederumϕ durchA undψ durchB repräsentiert, kann ich die MengenA ∩ B sowieA ∪ B bilden. Esliegt nahe festzulegen, daß diese Mengen die Eigenschaften

”ϕ undψ“ bzw.

”ϕ oder

ψ“ repräsentieren.

Wenn wir genau so weit und nicht weiter gehen – dann gelangen wir zum Begriffdes distributiven Verbandes, der in diesem ersten Kapitel unser Thema ist. Sehen wirzunächst, wie eine Menge von Teilmengen hinsichtlich der Teilmengenbeziehungstruk-turiert werden kann.

Lemma 2.1.1. Es seiW eine nichtleere Menge. Weiter seiL eine Menge von Teilmen-gen vonW . Dann gilt f̈ur alleA,B,C ∈ L:

(i) A ⊆ A.

(ii) AusA ⊆ B undB ⊆ A folgtA = B.

(iii) AusA ⊆ B undB ⊆ C folgtA ⊆ C.

Sehen wir sodann, welche Eigenschaften die beiden Mengenoperationen∩ und∪ ha-ben.

Definition 2.1.2. Es seiW eine nichtleere Menge. Weiter besteheL aus TeilmengenvonW dergestalt, daß mitA undB jeweils auchA∩B undA∪B in L ist. Dann heiße(L;∩,∪) einTeilmengenverband.

Insbesondere ist der Fall denkbar, daßL die PotenzmengePW vonW ist. PW , zu-sammen mit∩ und∪, ist ein Teilmengenverband..

Wir werden später beweisen, daß die im Folgenden aufgeführten Eigenschaften füreinen Teilmengenverband charakteristisch sind.

Lemma 2.1.3. Es sei(L;∩,∪) ein Teilmengenverband. Dann gilt für alle A,B,C ∈L:

(i) A ∩ A = A ∪ A = A.

(ii) A ∩B = B ∩ A undA ∪B = B ∪ A.

(iii) A ∩ (B ∩C) = (A ∩B) ∩ C undA ∪ (B ∪ C) = (A ∪B) ∪C.

6

(iv) A ∩ (A ∪B) = A ∪ (A ∩B) = A.

(v) A ∩ (B ∪C) = (A ∩B) ∪ (A ∩ C) undA ∪ (B ∩ C) = (A ∪B) ∩ (A ∪C).

Es sind tatsächlich”nur“ genau die in Lemma 2.1.3 aufgeführten Eigenschaften,um

die es im weiteren geht. Wenn in den Kapiteln 2 und 3 von Verbänden die Rede seinwird, braucht man sich nichts als die vorstehende Struktur eines Teilmengenverbandesvor Augen zu halten.

2.2 Posets

Wir beginnen den formalen Teil.

Wir abstrahieren vom vorstehenden Beispiel; wir tragen dieEigenschaften eines Sy-stems von Teilmengen einer fixen Menge zusammen. Wir haben gesehen, daß wir ei-nerseits von der⊆-Beziehung und andererseits von den Operationen∩ und∪ ausgehenkönnen. Wir wenden uns zunächst der ersteren Möglichkeit zu.

Definition 2.2.1. Es sei(L;≤) eine Algebra mit der zweistelligen Relation≤. DannheißeL einepartiell geordnete Menge[engl. partially ordered set], oder kurzPoset,falls für allea, b, c ∈ L Folgendes gilt:

(P1) a ≤ a (Reflexitiviẗat).

(P2) Ausa ≤ b undb ≤ a folgt a = b (Antisymmetrie).

(P3) Ausa ≤ b undb ≤ c folgt a ≤ c (Transitivität).

Je zwei Elementea, b ∈ L, für die entwedera ≤ b oderb ≤ a gilt, heißenvergleichbar.Sind je zwei Elemente vergleichbar, heißt(L;≤) eine linear geordnete Menge[engl.linearly odertotally ordered set].

Für Elemente eines Posets schreiben wir im weiterena < b, falls a ≤ b, aber nichta = b gilt. Zudem schreiben wir gelegentlichb ≥ a für a ≤ b.

Lemma 2.2.2.Es seiL eine Menge von Teilmengen einer nichtleeren Menge. Dann ist(L;⊆) ein Poset.

Beweis.Siehe Lemma 2.1.1.

Beispiel 2.2.3.Wir geben zwei weitere immer wiederkehrende Beispiele von Posetsan.

(i) Es sei[0, 1] = {r ∈ R : 0 ≤ r ≤ 1} dasreelle Einheitsintervall. Es gelter ≤ s,falls r kleiner oder gleichs gemäß der üblichen Ordnung reeller Zahlen ist. Dannist ([0, 1];≤) ein Poset. Es handelt sich um dienatürliche Ordnungauf [0, 1].

Für je zwei Elementer, s ∈ [0, 1] gilt entwederr ≤ s oders ≤ r: [0, 1] ist sogareine linear geordnete Menge.

7

(ii) Es seiM eine nichtleere Menge. EineFuzzymengëuberM ist eine AbbildungvonM nach[0, 1]. Es seiF(M) die Menge aller Fuzzymengen überM . Wirdefinieren für zwei Fuzzymengenu undv

u ≤ v falls u(m) ≤ v(m) für allem ∈M.

Dies ist diepunktweise OrdnungvonF(M). Dann ist(F(M);≤) ein Poset.

Visualisierung von Posets

Um sich über die Bedeutung von Resultaten über Posets ins klare zu setzen, kann manjederzeit eines der Standardbeispiele verwenden, wozu insbesondere die Teilmengen-posets gehören. Darüberhinaus ist es häufig nützlich, sich Fakten anhand endlicherPosets klarzumachen oder auch an endlichen Teilstrukturenvon Posets.

Zu diesem Zweck besteht eine einfache Möglichkeit der Visualisierung. Man stelltjedes Element des endlichen Posets(L;≤) durch einen Punkt dergestalt dar, daß, fallsfür zwei Elementea, b ∈ L a ≤ b gilt, b ∈ L höher zu liegen kommt alsa ∈ L.Sodann verbindet mana undb, falls a ≤ b gilt und es keinc mit a < c < b gibt. DasErgebnis nennt sichHassediagramm.

Betrachtet sei beispielsweise die Menge{0, 1, 2, 3}, versehen mit der natürlichen Ord-nung, des weiteren die Potenzmenge der zweielementigen Menge{0, 1}, versehen mitder Mengeninklusion, und schließlich die Potenzmenge der zweielementigen Menge{0, 1} ohne die Menge{0, 1}, ebenfalls versehen mit der Mengeninklusion.

({0, 1, 2, 3},≤) (P{0, 1},⊆) ({∅, {0}, {1}},⊆)

Konstruktionen mit Posets

Von einem Poset kann man zu einer Teilmenge übergehen; dannläßt sich die partielleOrdnung der größeren Menge problemlos auf die kleinere übertragen.

Lemma 2.2.4.Es sei(L;≤) ein Poset undA ⊆ L. Für a, b ∈ A setzen wira ≤ b, fallsdies inL gilt. Dann ist(A;≤) wiederum ein Poset.

Beweis.Reflexitivität, Antisymmetrie und Transitivität geltenin A, da sie inP gelten.

Definition 2.2.5. Es sei(L;≤) ein Poset undA ⊆ L. Für je zwei Elementea, b ∈ Aerklären wir, daßa ≤ b gilt, wenn dies füra und b als Elemente vonL der Fall ist.Dann heiße(A;≤) UnterposetvonL.

8

Weiter setzen wir für Elementep, q ∈ L mit p < q

[p, q] = {a ∈ L : p ≤ a ≤ q}.

Dann heißt der Unterposet vonL mit dem Grundbereich[p, q] Intervall des PosetsL.

Wir betrachten im weiteren jede Teilmenge eines Posets ohneexpliziten Hinweis im-mer als Unterposet.

Beispiel 2.2.6.Zu beachten ist, daß ein Intervall eines Posets, auch wenn esdie Be-zeichnung nahelegen mag, keineswegs linear geordnet sein muß. Z.B. seien die folgen-den Posets betrachtet:

L [a, e]

Dann besteht das Intervall[a, e] vonL aus allen Elementen vonL außerd.

Weiter kann man in einem Poset die Ordnung umdrehen; es ergibt sich wiederum einPoset.

Lemma 2.2.7. Es sei(L;≤) ein Poset. F̈ur a, b ∈ A setzen wira ≤′ b, falls b ≤ a gilt.Dann ist(L;≤′) wiederum ein Poset.

Beweis.Die Gültigkeit der Axiome (P1) bis (P3) bleibt erhalten, wenn man”≤“ überall

durch”≥“ ersetzt.

Definition 2.2.8. Es sei(L;≤) ein Poset. Füra, b ∈ L erklären wir, daßa ≤′ b gilt,falls b ≤ a. Dann heiße(L;≤′) der zu(L;≤) duale Poset.

Besondere Eigenschaften von Poset-Elementen

Wir stellen im weiteren besondere Eigenschaften von Elementen oder Elementpaarenin Posets oder Unterposets zusammen.

Definition 2.2.9. Es sei(L;≤) ein Poset, und es seiA eine (nicht notwendig nichtleereund nicht notwendig echte) Teilmenge vonL.

(i) Ein b ∈ L heißeuntere Schranke[engl. lower bound] vonA, falls b ≤ a für allea ∈ A.

Ein c ∈ L heißeobere Schranke[engl.upper bound] vonA, falls a ≤ c für allea ∈ A.

9

(ii) Ein b ∈ A heißekleinstes Element[engl. least element] von A, falls b ≤ a fürallea ∈ A.

Ein c ∈ A heißegrößtes Element[engl.greatest element] vonA, falls a ≤ c fürallea ∈ A.

(iii) Ein b ∈ Amit der Eigenschaft, daßa ∈ A unda ≤ b stetsa = b impliziert, heißtminimales Element[engl.minimal element] in A.

Ein c ∈ Amit der Eigenschaft, daßa ∈ A undc ≤ a stetsa = c impliziert, heißtmaximales Element[engl.maximal element] in A.

Minimale und maximale Elemente dürfen nicht mit kleinstenbzw. größten Elementenverwechselt werden. An letzteren gibt es nur je eines; erstere kann es viele geben.

Lemma 2.2.10. Es sei(L;≤) undA ⊆ L. Dann gibt es ḧochstens ein kleinstes undhöchstens ein gr̈oßtes Element vonA.

Ein kleinstes Element vonA ist minimales Element vonA. Ein größtes Element vonAist maximales Element vonA.

Beweis.Es seib1 ∈ L undb2 ∈ L jeweils kleinstes Element vonA. Dann giltb1 ≤ b2und b2 ≤ b1, alsob1 = b2. Also gibt es nicht mehr als ein kleinstes Element, undähnlich folgt, daß es nicht mehr als ein größtes Element gibt.

Es seib das kleinste Element vonA unda ≤ b für ein a ∈ A. Da dann auchb ≤ agilt, folgt a = b. Also ist b minimal. Ebenso folgt, das ein größtes Element maximalist.

Definition 2.2.11. Es sei(L;≤) ein Poset undA ⊆ L. Existiert ein kleinstes ElementvonA, wird dieses mitminA bezeichnet. Existiert ein größtes Element vonA, wirddieses mitmaxA bezeichnet.

Besitzt der gesamte Poset ein kleinstes oder/und ein größtes Element vorhanden, spieltdieses i.a. ein herausgehobene Rolle. Diese Elemente erhalten standardmäßig die Be-zeichnung0 bzw.1.

Definition 2.2.12. Es sei(L;≤) ein Poset. BesitztL ein kleinstes Element0, heißt0dasNullelement. BesitztL ein größtes Element1, heißt1 dasEinselement.

Beispiel 2.2.13.Wir betrachten zwei endliche Posets sowie einige der Posetsaus Bei-spiel 2.2.3.

(i) Gegeben seien folgende Posets.

M3 L

10

Im PosetM3 ist e kleinstes unda größtes Element. Weitere minimale und maxi-male Elemente vonM3 gibt es nicht. Der PosetL besitzt das kleinste Elemente,jedoch kein größtes Element. Hingegen sinda undd maximale Elemente vonL.

(ii) Das reelle Einheitsintervall[0, 1], versehen mit der natürlichen Ordnung, hat einNull- und ein Einselement – die ebenso bezeichneten reellenZahlen.

(iii) Das offene reelle Intervall(0, 1), versehen mit der natürlichen Ordnung, hat we-der ein Null- noch ein Einselement. Das gleiche gilt fürR, die ganze reelle Zah-lenachse.

(iv) Die MengeF(M) der Fuzzymengen über einer MengeM , versehen mit derpunktweisen Ordnung, hat Null- wie Einselement, die wir mit0̄ und 1̄ bezeich-nen:

0̄ : M → [0, 1], m 7→ 0,

1̄ : M → [0, 1], m 7→ 1.

Hat ein Poset kein Null- oder Einselement, läßt sich ein solches hinzufügen; folgendeKonstruktion ist möglich.

Satz 2.2.14.Es sei(L;≤) ein Poset.L besitze kein Nullelement. Es sei0 ein neuesElement undL0 = L∪̇{0}; für a, b ∈ L0 geltea ≤ b, falls entwedera, b ∈ L ist unddies inL gilt oder wenna = 0 ist. Dann istL0 ein Poset.

Die entsprechende Konstruktion ist möglich, wennL kein Einselement besitzt. Schließ-lich ist auch das gleichzeitige Hinzufügen von Null- und Einselement möglich.

Beweis.Es ist leicht nachzuprüfen, daß(L0;≤) ein Poset ist.

Man beachte, daß im Fall, daß Satz 2.2.14 zum Zuge kommt, der VerbandL notwendi-gerweise unendlich ist; ein endlicher Verband hat ohnehin immer ein Null- und Eins-element.

Aufeinanderfolgende Elemente von Posets

Das reellle Einheitsintervall[0, 1], versehen mit der natürlichen Ordnung, ist das Bei-spiel eines Posets mit der folgenden Eigenschaft: Für jedes Paar von Elementena, bmit a < b gibt es ein drittes Elementc mit a < c < b; man spricht daher von einerdichtenpartiellen Ordnung. Im Gegensatz dazu betrachte man den Poset{0, 1

n, . . . , 1}

für ein n ≥ 2, ebenfalls versehen mit der natürlichen Ordnung. Hier treten Paarea, bvon Elementen auf, so daßa < b gilt und es keinc mit a < c < b gibt. In einem nahe-liegenden Sinne hat hier jedes von0 und1 verschiedene Element einen unmittelbarenVorgänger und Nachfolger. Mit Posets solcher Art stellen wir einige Begrifflichkeitenzusammen.

11

Definition 2.2.15. Es sei(L;≤) ein Poset. Dann heißta ∈ L unmittelbarer Vorg̈angervonb ∈ L undb unmittelbarer Nachfolgervona, in Zeichen

a

Beispiel 2.2.19. (i) Die PosetsM3 und L aus Beispiel 2.2.13 haben jeweils dieLänge2.

(ii) Das reelle Einheitsintervall[0, 1], versehen mit der natürlichen Ordnung, ist vonunendlicher Länge.

Homomorphismen von Posets

Vielfach werden wir es zu tun haben mit Funktionen, die einenPoset auf einen anderenabbilden. Dabei interessiert der Fall, daß die Ordnungsrelation erhalten bleibt.

Definition 2.2.20. Es seien(P ;≤) und(Q;≤) zwei Posets. Eine Abbildungϕ : P →Q heißeOrdnungshomomorphismusoderordnungserhaltendodermonoton, falls fürallea, b ∈ P gilt:

Ausa ≤ b folgt ϕ(a) ≤ ϕ(b).

ϕ : P → Q heißeOrdnungsisomorphismus, falls ϕ bijektiv ist und für allea, b ∈ PFolgendes gilt:

a ≤ b genau dann, wennϕ(a) ≤ ϕ(b).

Ebenfalls von regelmäßigem Interesse ist der Fall, daß sich die Ordnungsrelation untereiner Abbildung umdreht.

Definition 2.2.21. Es seien(P ;≤) und(Q;≤) zwei Posets. Ein Ordnungshomomor-phismus vonP auf den zuQ dualen Poset heißtOrdnungsantihomomorphismusoderantiton.

Ein Ordnungsisomorphismus zwischenP und dem zuQ dualen Poset heißtOrdnungs-antiisomorphismus.

Mit anderen Worten ist eine antitone Abbildung zwischen PosetsP undQ dergestalt,daß für allea, b ∈ P gilt:

Ausa ≤ b folgt ϕ(b) ≤ ϕ(a).

Und um einen Ordnungsantiisomorphismus zu charakterisieren, ist hierin die Implika-tion durch eineÄquivalenz zu ersetzen.

2.3 Verbände

Die im weiteren zentrale Definition ist die folgende.

Definition 2.3.1. Es sei(L;≤) ein Poset, und es seiA eine Teilmenge vonL. Dannheißeb ∈ L Infimum[engl. infimum] von A, falls b größtes Element der Menge derunteren Schranken vonA ist. Existiert dieses Element, bezeichnen wir es durch

∧

A

13

oder alternativa1 ∧ . . . ∧ an,

fallsA = {ai : i = 1, . . . , n}, n ≥ 2.

Ebenso heißec ∈ L Supremum[engl.supremum] vonA, falls c kleinstes Element derMenge der oberen Schranken vonA ist. Existiert dieses Element, bezeichnen wir esdurch

∨

A

oder alternativa1 ∨ . . . ∨ an,

fallsA = {ai : i = 1, . . . , n}, n ≥ 2.

Gemäß Lemma 2.2.10 hat jede Menge höchstens ein größtes und ein kleinstes Element;nur deshalb ist die vorstehende Definition sinnvoll. Man beachte, daß, wennA Teilmen-ge eines Posets ist, der Ausdruck

∧

A für sich genommen nicht notwendig einen Sinnergibt; das Infimum einer Teilmenge kann existieren, muß aber nicht. Dasselbe gilt für∨

A, das Supremum.

Infimum und Supremum interessieren am häufigsten für Paarea1, a2 eines Posets. Manmache sich für diesen Fall die Definition klar. Istb deren Infimum, istb größte untereSchranke vona1 unda2. Das heißt zweierlei:

(1) b ≤ a1, a2;

(2) wennb′ ≤ a1, a2 für ein weiteres Element gilt, folgtb′ ≤ b.

Analoges gilt fürs Supremum; istc Supremum vona1 und a2, ist c kleinste obereSchranke vona1 unda2:

(1) a1, a2 ≤ c;

(2) wenna1, a2 ≤ c′ für ein weiteres Element gilt, folgtc ≥ c′.

Beispiel 2.3.2.Wir betrachten Beispiel 2.2.3 sowie gewisse Modifikationen.

(i) Sind Elementea undb eines Posets vergleichbar, besitzen sie stets Infimum undSupremum. Gilt etwaa ≤ b, ist a ∧ b = a unda ∨ b = b.

Insbesondere besitzen in der linear geordneten Menge([0, 1];≤) je zwei Ele-mente ein Infimum und ein Supremum.

(ii) Es sei(F(M);≤) die Menge der Fuzzymengen überM , versehen mit der punkt-weisen Ordnung. Es seienu, v : M → [0, 1] Fuzzymengen überM . Die Ziel-menge[0, 1] ist standardmäßig mit der natürlichen Ordnung ausgestattet; fürr, s ∈ [0, 1] schreiben wirr ∧ s für das kleinere undr ∨ s für das größereElement.

14

Wir setzen

s : M → [0, 1], m 7→ u(m) ∧ v(m),

t : M → [0, 1], m 7→ u(m) ∨ v(m).

Wir behaupten, daßs das Infimum undt das Supremum vonu und v ist. Wirzeigen ersteres.

(1) Für jedesm gilt s(m) = u(m) ∧ v(m) ≤ u(m), alsos ≤ u. Ebenso folgts ≤ v.

(2) Die Fuzzymenges′ sei dergestalt, daßs′ ≤ u, v. Dann ist für jedesm ∈Ms′(m) ≤ u(m), v(m). Für das Infimumu(m)∧v(m), als die größte untereSchranke vonu(m) undv(m), folgt s′(m) ≤ u(m) ∧ v(m) = s(m). Alsos′ ≤ s.

Wir haben gezeigt, daßs größte untere Schranke vonu undv ist, d.h.s = u∧ v.

(iii) Es sei(C1(R);≤) die Menge aller stetig differenzierbaren Funktionen, versehenmit der punktweisen Ordnung. Für zwei Funktionenf, g ∈ C1(R) existiert imallgemeinen weder Infimum noch Supremum.

Um dies zu sehen, betrachte man die Funktionenf undg, definiert durchf(x) =x undg(x) = −x. Es seih ∈ C1(R) eine untere Schranke vonf undg. Dann isth(0) < 0; denn im Fallh(0) = 0 wäreh am Punkt0 nicht differenzierbar. Dannaber läßt sich zeigen, daß es eine Funktionh′ ∈ C1(R) mit h < h′ ≤ f, g gibt.Es folgt, daß es keine größte untere Schranke vonf undg gibt, d.h.f undg keinInfimum besitzen.

Wir kommen zur zentralen Definition.

Definition 2.3.3. Es sei(L;≤) ein Poset, so daß Infimum und Supremum je zweierElemente existieren. Dann heißeL verbandsgeordnet.

Wir fassen in diesem Fall∧ und ∨ als zwei binäre Operationen aufL auf. Die soentstandene Algebra(L;∧,∨) heißeVerband.

M.a.W. ist ein Verband eine Algebra(L;∧,∨) mit zwei binären Operationen∧ und∨, welche mittels Definition 2.3.1 aus einer partiellen Ordnung aufL hervorgegangensind. Sinnvoll ist der zweite Teil von Definition 2.3.3 deshalb, weil sich die partielleOrdnung, von der man ausgegangen ist, aus∧ oder∨ eindeutig wieder zurückgewinnenläßt.

Lemma 2.3.4. Es sei(L;≤) ein Poset, undL sei verbandsgeordnet. Dann gilt für allea, b ∈ L

a ≤ b, gdw a ∧ b = a, gdw a ∨ b = b. (1)

Insbesondere gilt: Ist(L;∧,∨) ein Verband, gibt es genau eine partielle Ordnung aufL, bez̈uglich deren∧ und∨ je zwei Elementen deren Infimum und Supremum zuordnen.

15

Beweis.Ausa ≤ b folgt offenbara ∧ b = a. Umgekehrt heißta ∧ b = a, daß

a = a ∧ b ≤ b.

Damit ist die erstëAquivalenz gezeigt. DiëAquivalenz vona ≤ b unda ∨ b = b folgtanalog.

Auf ≤ als diejenige Relation, aus der der Verband(L;∧,∨) hervorgeht, nehmen wirals die unterliegende partielle Ordnung Bezug.

Lemma 2.3.5. Ein Teilmengenverband(L;∩,∪) ist ein Verband. Die unterliegendepartielle Ordnung ist die Teilmengenbeziehung⊆.

Beweis.Gemäß Lemma 2.2.2 ist(L;⊆) ein Poset. Nach Lemma 2.3.4 ist die partielleOrdnung, die einem Verband unterliegt, eindeutig bestimmt. Wir behaupten, daß essich im vorliegenden Fall um⊆ handelt.

FürA,B ∈ L sind gemäß VoraussetzungA∩B wieA∪B in L.A∩B ist die größte inA undB enthaltende Menge; m.a.W. istA∩B das Infimum vonA undB bezüglich⊆.Ähnlich istA ∪B deren Supremum. Also ist(L;∩,∪) ein Verband mit unterliegenderOrdnung⊆.

Die nächste Frage ist, wie sich ein Verband ohne Rückgriffauf die unterliegende parti-elle Ordnung charakterisieren läßt.

Satz 2.3.6.Es sei(L;∧,∨) ein Verband. Dann gilt f̈ur alle a, b, c ∈ L Folgendes:

(V1) a ∧ a = a ∨ a = a.

(V2) a ∧ b = b ∧ a unda ∨ b = b ∨ a.

(V3) a ∧ (b ∧ c) = (a ∧ b) ∧ c unda ∨ (b ∨ c) = (a ∨ b) ∨ c.

(V4) a ∧ (a ∨ b) = a ∨ (a ∧ b) = a.

Umgekehrt sei(L;∧,∨) eine Algebra mit den zweistelligen Operationen∧ und∨, sodaß f̈ur alle a, b, c ∈ L die Bedingungen(V1) bis (V4) erfüllt sind. Dann istL einVerband, dessen unterliegende partielle Ordnung durch(1) gegeben ist.

Beweis.Zum Beweis des ersten Teils nehmen wir an, daß(L;∧,∨) ein Verband ist.Füra, b ∈ L sind danna ∧ b unda ∨ b Infimum und Supremum vona undb bezüglichder partiellen Ordnung, die durch (1) bestimmt ist. Wir zeigen jeweils die erste Hälfteder Behauptungen in (V1), ..., (V4); die zweite folgt jeweils analog.

(V1): a ∧ a ist das Infimum der einelementigen Menge{a}; dieses ist offenbar gleicha.

(V2): Sowohla ∧ b also auchb ∧ a bezeichnen das Infimum der Menge{a, b}.

(V3): Wir zeigen, daßa ∧ (b ∧ c) das Infimum der Menge{a, b, c} ist, womit dieBehauptung folgt. Für jedesx ∈ L folgt ausx ≤ a undx ≤ b ∧ c, daßx ≤ a, b, c

16

gilt; und umgekehrt folgt ausx ≤ a, b, c, daßx ≤ a, b ∧ c gilt. Also ist die Menge derunteren Schranken von{a, b∧c} gleich der Menge der unteren Schranken von{a, b, c}.Also ist auch das größte Element der unteren Schranken in beiden Fällen dasselbe, d.h.a ∧ (b ∧ c) = a ∧ b ∧ c.

(V4): Ausa ≤ a ∨ b folgt a ∧ (a ∨ b) = a.

Um den zweiten Teil des Satzes zu beweisen, nehmen wir nunmehr an, daß(L;∧,∨)eine Algebra ist, die (V1) bis (V4) erfüllt. Füra, b ∈ L setzen wira ≤ b, fallsa = a∧b.

Wir haben zu zeigen, daß(L;≤) ein Poset ist.a ≤ a folgt aus (V1). Gilta ≤ b undb ≤ a, soa = a∧ b undb = b∧ a, unda = b folgt aus (V2). Schließlich seia ≤ b undb ≤ c. Dann gilta = a ∧ b undb = b ∧ c, alsoa = a ∧ (b ∧ c) = (a ∧ b) ∧ c = a ∧ cgemäß (V3).

Als nächstes zeigen wir (1); dafür ist nachzuweisen, daßa ≤ b, gdwa ∨ b = b. Ausa ≤ b folgt a ∨ b = (a ∧ b) ∨ b = b ∨ (b ∧ a) = b gemäß (V4) und dem zweimalangewendeten (V2). Umgekehrt folgt ausa ∨ b = b, daßa ∧ b = a ∧ (a ∨ b) = a,wiederum gemäß (V4).

Weiter ist zu zeigen, daß füra, b ∈ L a∧b das Infimum bezüglich≤ ist. Da(a∧b)∧a =a ∧ (a ∧ b) = (a ∧ a) ∧ b = a ∧ b gemäß (V2), (V3) bzw. (V1) gilt, ista ∧ b ≤ a. Daauch(a ∧ b) ∧ b = a ∧ (b ∧ b) = a ∧ b gilt, ist a ∧ b ≤ b. Weiter seix ≤ a, b. Dann istx ∧ (a ∧ b) = (x ∧ a) ∧ b = x ∧ b = x, alsox ≤ a ∧ b. Die Behauptung folgt.

Als letztes ist zu zeigen, daß füra, b ∈ L a ∨ b das Supremum bezüglich≤ ist. Es gilta∧ (a ∨ b) = a gemäß (V4), alsoa ≤ a∨ b. Ebenso giltb∧ (a ∨ b) = b∧ (b∨ a) = bgemäß (V2) und (V4), alsob ≤ a ∨ b. Weiter seia, b ≤ x. Wir hatten (1) gezeigt; esfolgt (a ∨ b) ∨ x = a ∨ (b ∨ x) = a ∨ x = x und damita ∨ b ≤ x. Die Behauptungfolgt.

Satz 2.3.6 besagt, daß sich Verbände auch mittels der Axiome (V1) bis (V4) definierenließen. Dies wäre technisch sogar einfacher, hieße allerdings das Pferd von hinten heraufzuzäumen. Verbände wollen wir als partiell geordneteMengen betrachten mit derZusatzeigenschaft, daß Infima und Suprema je zweier Elemente existieren. Daraus undvon nirgendwo andersher ergeben sich die Eigenschaften (V1) bis (V4).

Anmerkung 2.3.7. Unter den Verbände charakterisierenden Eigenschaften (V1) bis(V4) ist (V1) redundant. In der Algebra(L;∧,∨) gelte (V4). Dann gilta ∧ a = a ∧(a ∨ (a ∧ a)) = a. Ähnlich folgt a ∨ a = a.

Man könnte meinen, daß in Anwendungen auftretende Posets typischerweise Verbändesind. Dieser Eindruck ist auch mit dem Umstand konsistent, daß in dieser VorlesungVerbände und nicht Posets im Mittelpunkt stehen. Auch wenndem in Wahrheit nichtso sein mag – Beispiele von Posets, die keine Verbände sind,wirken häufig künstlich.

Beispiel 2.3.8.Wir rekapitulieren Beispiel 2.3.2 und ergänzen dieses.

(i) Jede linear geordnete Menge ist ein Verband.

(ii) Die MengeF(M) der Fuzzymengen über einer MengeM , versehen mit derpunktweisen Ordnung, ist ein Verband.

17

(iii) Die Menge(C1(R);≤) aller stetig differenzierbaren Funktionen aufR, versehenmit der punktweisen Ordnung, ist kein Verband.

(iv) Wir betrachten verschiedene partielle Ordnungen auf demRn, n ≥ 1.

(α) Wir setzen(a1, . . . , an) ≤ (b1, . . . , bn), falls

a1 ≤ b1, . . . , an ≤ bn.

Dies ist die komponentenweise natürliche Ordnung auf demRn und machtdiesen zu einem Verband. Es handelt sich um einen Spezialfall von (ii).

(β) Wir setzen(a1, . . . , an) ≤lex (b1, . . . , bn), falls

a1 < b1 oder

a1 = b1 und a2 < b2 oder

a1 = b1, a2 = b2 und a3 < b3 oder

. . .

a1 = b1, . . . , an−1 = bn−1 und an < bn oder

a1 = b1, . . . , an = bn.

≤lex ist die lexikographische Ordnung auf demRn. Man überprüfe, daß≤lex denRn zu einer linear geordneten Menge macht, insbesondere also zueinem Verband.

(γ) Fürs dritte Teilbeispiel setzen wir der Einfachheit halbern = 2. Wir setzen(a1, a2) 4 (b1, b2), falls

(a1, a2) = (b1, b2) oder a1 < b1, und b1 < b2.

Dies ist die sogenannte strikte Ordnung auf demR2. Man überzeuge sich,daß4 überhaupt eine partielle Ordnung ist.

Wir behaupten weiter, daß(R2;4) kein Verband ist. In der Tat besitzt bei-spielsweise das Paar(0, 1) und(1, 0) kein Supremum. Die Menge der obe-ren Schranken ist nämlich

{(r, s) ∈ R2 : r > 1, s > 1};

diese Menge hat in bezug auf4 kein kleinstes Element.

Wir haben Verbände als Algebren eingeführt, die je zwei (nicht notwendig verschie-denen) Elementen bezüglich einer partiellen Ordnung das Infimum und Supremum zu-ordnen. Wie das folgende Lemma zeigt, reichen die zweistelligen Operationen aus,dasselbe für jede endliche Menge von Elementen zu tun.

Lemma 2.3.9. Es sei(L;∧,∨) ein Verband, und es seiena1, . . . , an ∈ L, n ≥ 1.Dann ist

(...(a1 ∧ a2) ∧ a3) ∧ . . . ∧ an−1) ∧ an (2)

18

das Infimum der Menge{a1, . . . , an}. Weiter k̈onnen in(2) die Klammern nach Belie-ben versetzt werden und die Reihenfolge der Elemene nach Belieben ver̈andert werden,ohne daß sich der Wert verändern ẅurde. Analoges gilt f̈ur das Supremum.

Beweis.Im Beweis von (V3), s. Satz 2.3.6, hatten wir gezeigt, daß für a, b, c ∈ L dasInfimum vona ∧ b undc gleich dem Infimum vona, b undc ist. Ähnlich können wirersehen, daß füra, b, c1, . . . , ck ∈ L, worink ≥ 1 ist, das Infimum vona∧b, c1, . . . , ckgleich dem Infimum vona, b, c1, . . . , ck ist.

Mittels wiederholter Anwendung dieser Tatsache erschließen wir, daß (2) das Infimumvon a1, . . . , an ist. Dabei kommt es offensichtlich weder darauf an, wie geklammertist, noch, in welcher Reihenfolge dieai stehen.

Hinsichtlich des Supremums gelten die analogenÜberlegungen.

Lemma 2.3.9 impliziert zweierlei. Erstens lassen sich beliebige endliche Infima undSuprema durch die zweistelligen Verbandsoperationen∧ bzw.∨ ausdrücken. Es seiennämlicha1, . . . , an Elemente des Verbandes(L;∧,∨); dann ist (2) deren Infimum.Zweitens ist klar, daß die Klammerung nicht unbedingt gerade so wie in (2) erfolgenmuß; geklammert werden kann nach Belieben.

So sind die Klammern in (2) eigentlich überflüssig, und wirwerden sie im Folgendengrundsätzlich weglassen. Wir verwenden stattdessen den ¨ubersichtlicheren Ausdruck

a1 ∧ . . . ∧ an

und legen fest, daß dieser stellvertretend für (2) steht. Wenn wir L als einen Posetbetrachten, ista1∧ . . .∧an ohnehin bereits als das Infimum von{a1, . . . , an} definiertund damit als dasselbe Element wie (2).

Posets, die die Bildung beliebiger Infima und Suprema erlauben, werden nunmehrerwähnt.

Definition 2.3.10. Es sei(L;∧,∨) ein Verband. Für jede beliebige TeilmengeA vonL existiere das Infimum und das Supremum vonA. Dann heißeL ein vollständigerVerband.

Man braucht in diesem Fall nicht zu fordern, daß sowohl Infimaals auch Supremaexistieren; es reicht, wenn z.B. alle Infima existieren.

Lemma 2.3.11.Es sei(L;∧,∨) ein Verband. F̈ur jede beliebige TeilmengeA vonLexistiere das Infimum vonA. Dann istL ein vollsẗandiger Verband.

Beweis.Es seiA ⊆ L. Wir müssen zeigen, daß das Supremum vonA existiert. Wirsetzen

c =∧

{b ∈ L : b ≥ a für allea ∈ A};

dies ist das nach Voraussetzung existierende Infimum aller oberen Schranken vonA.Insbesondere istc selbst obere Schranke und damit die kleinste obere Schranke.

19

Wir ergänzen ein paar im Folgenden immer wieder stillschweigend verwendeten Ei-genschaften von Verbänden.

Lemma 2.3.12.Es sei(L;∧,∨) ein Verband. Dann gilt f̈ur alle a, b, c ∈ L:

(i) Ausa ≤ b unda ≤ c folgt a ≤ b ∧ c.

Ausb ≤ a undc ≤ a folgt b ∨ c ≤ a.

(ii) Ausb ≤ c folgt a ∧ b ≤ a ∧ c sowiea ∨ b ≤ a ∨ c.

Beweis.(i) a ≤ b, c bedeutet, daßa untere Schranke vonb undc ist. Da deren Infimumdie größte untere Schranke ist, folgta ≤ b ∧ c. Ähnlich ist für den zweiten Teil zuargumentieren.

(ii) Es seib ≤ c. Dann ist jede untere Schranke vona undb auch eine solche vona undc. Also ist aucha ∧ b, die größte untere Schranke vona undb, eine untere Schrankevona undc. Nach Teil (i) folgta ∧ b ≤ a ∧ c.

Visualisierung von Verbänden

Um an endlichen Posets bestimmte Eigenschaften zu prüfen,bietet sich stets die Mög-lichkeit an, eine entsprechende Eigenschaft des zugehörigen Hassediagramms auszu-machen. Es gibt kein sonderlich elegantes Verfahren, um festzustellen, ob ein Hasse-diagramm einen Verband repräsentiert – wir erwähnen dennoch ein solches.

Lemma 2.3.13.Es sei(L;≤) ein endlicher Poset. Dann istL ein Verband genau dann,wenn es kein Paara, b ∈ L verschiedener Elemente gibt, die eine der folgenden Bedin-gungen erf̈ullen:

(i) a undb besitzen keine untere oder keine obere Schranke.

(ii) Es gibt vier Elementea, b, c, d mit a, b ≤ c, d, so daß es keine ∈ L mit a, b ≤e ≤ c, d gibt.

Beweis.Es seiL ein Verband. Füra, b ∈ L gibt es dann eine kleinste obere Schrankea∧ b und eine größte untere Schrankea∨ b. Dies widerspricht sowohl (i) als auch (ii).

Es seiL kein Verband. Dann gibt es ein Paara, b ∈ L, so daß die MengeU der unterenSchranken vona undb kein größtes Element hat oder die MengeO der oberen Schran-ken kein kleinstes. Wir nehmen den letzteren Fall an; für den ersteren argumentierenwir analog. Notwendigerweise mußa 6= b gelten. IstO leer, gilt (i).O sei nichtleer.DaO endlich ist, gibt es für jedesx ∈ O ein minimales Elementy in U mit y ≤ x.Also enthältO mindestens ein minimales Element. EnthielteO genau ein minimalesElement, wäre dies das kleinste Element vonO, entgegen der Annahme. Also gibt eszwei verschiedene minimale Elementec undd in U , und es folgt (ii).

Insofern ist ersichtlich, daß folgendes BeispielL1 ein Verband ist,L2 mangels Existenzeiner oberen Schranke vona undb kein Verband ist undL3, dad, e ≤ b, c gilt, es jedochkein Elementx gibt mit d, e ≤ x ≤ b, c, ebenfalls kein Verband ist.

20

L1 L2 L3

Konstruktionen mit Verb änden

Wir betrachten als nächstes die Möglichkeit, den Grundbereich eines Verbandes zuverkleinern. Im Fall eines Posets stellt dies kein Problem dar; im Fall eines Verbandesist etwas Vorsicht geboten.

Definition 2.3.14. Es sei(L;∧,∨) ein Verband. Weiter seiA ⊆ L, und mita, b ∈ Asei aucha ∧ b ∈ A und a ∨ b ∈ A. Wir erklären die Operationen∧ und∨ durchEinschränkung dieser Operationen vonL aufA. Dann heißt(A;∧,∨) UnterverbandvonL.

Lemma 2.3.15. Der Unterverband(A;∧,∨) eines Verbandes(L;∧,∨) ist ebenfallsein Verband.

Beweis.Die Gleichungen (V1) bis (V4) gelten inL, also auch inA.

Allerdings ist Folgendes zu beachten. IstL ein Verband undA ⊆ L, istA stets ein Un-terposet. Dieser Unterposet ist im allgemeinen kein Unterverband:A ist unter den aufL erklärten Operationen∧ und∨ nicht notwendig abgeschlossen. WennA kein Unter-verband vonL ist, kannA nichtsdestoweniger verbandsgeordnet sein. Dieser Fall trittauf, wennA unter den aufL erklärten Operationen∧ und∨ zwar nicht abgeschlossenist, inA aber alle Infima und Suprema von Paaren existieren.

Man betrachte das folgende Beispiel:

L L′

Der aus der TeilmengeL′ = {a, b, c, g} gebildete Unterposet vonL ist ein Verband,aber kein Unterverband von(L;∧,∨). Das Infimum vonb undc ist e in L, in L′ aberg.

Weiter können wir von einem Verband, als Poset gesehen, zumdualen Poset übergehen;das Ergebnis ist wieder ein Verband.

21

Lemma 2.3.16.Es sei(L;∧,∨) ein Verband. Es sei≤ die unterliegende Ordnung und≤′ die zugeḧorige duale Ordnung. Dann ist(L;≤′) wiederum verbandsgeordnet. Esseien∧′ und∨′ die zugeḧorigen Verbandsoperationen; dann ist∧′ = ∨ und∨′ = ∧.

Beweis.Ein Elementc ∈ L ist bezüglich≤′ das Infimum vona undb, wennc ≤′ a, bgilt und ausx ≤′ a, b stetsc ≤′ x folgt; wenn alsoa, b ≤ c gilt und ausa, b ≤ x stetsx ≤ c folgt; wenn alsoc das Supremum vona undb bezüglich≤ ist.

Also ist a ∨ b das Infimum vona undb bezüglich≤′, und ebenso ist zu ersehen, daßa ∧ b das Suprumum vona undb bezüglich≤′ ist.

Definition 2.3.17. Es sei(L;∧,∨) ein Verband. Dann heiße(L;∧′,∨′) der zuL dualeVerband, worin∧′ = ∨ und∨′ = ∧.

Der Übergang von einem Verband zum dualen Verband bedeutet also, daß∧ und∨vertauscht werden. Daß sich dadurch wiederum ein Verband ergibt, ist im übrigen anden Bedingungen (V1) bis (V4) zu ersehen; diese sind in∧ und∨ symmetrisch.

Wir schließen mit einer in der Algebra häufig angewandten Konstruktion.

Definition 2.3.18. Es seien(Lι;∧ι,∨ι), ι ∈ I, Verbände. Wir setzen

L =∏

ι∈I

Lι

und definieren für(aι)ι, (bι)ι ∈ L

(aι)ι ∧ (bι)ι = (aι ∧ι bι)ι,

(aι)ι ∨ (bι)ι = (aι ∨ι bι)ι.

Dann heißt(L;∧,∨) dasdirekte Produkt[engl.direct product] der VerbändeLι.

Lemma 2.3.19.Das direkte Produkt von Verbänden ist wiederum ein Verband.

Beweis.Jede Gleichung, die in jedem der Verbände gilt, gilt auch imProdukt. Alsogelten die Verbandsaxiome.

Definition 2.3.20. Wir sagen, daß ein VerbandL unzerlegbarist, falls L nicht demdirekten Produkt mindestens zweielementiger VerbändeL1 undL2 isomorph ist.

Homomorphismen von Verb̈anden

Wir definieren strukturerhaltende Abbildungen zwischen Verbänden.

Definition 2.3.21. Es seien(P ;∧,∨) und (Q;∧,∨) zwei Verbände. Eine Abbildungϕ : P → Q heißeVerbandshomomorphismus, falls für allea, b ∈ P gilt:

ϕ(a ∧ b) = ϕ(a) ∧ ϕ(b),

ϕ(a ∨ b) = ϕ(a) ∨ ϕ(b).

22

Ist ϕ : P → Q injektiv, heißtϕ auch eineEinbettung, und wir sagen, daß sichP in Qeinbetten läßt.

Ist ϕ : P → Q surjektiv, sagen wir, daßQ einhomomorphes BildvonP ist.

Ist ϕ : P → Q bijektiv, heißtϕ einVerbandsisomorphismus.

Da jeder Verband auch ein Poset ist, ist das Verhältnis zwischen Verbands- und Po-sethomomorphismus zu klären.

Lemma 2.3.22.Es seien(P ;∧,∨) und(Q;∧,∨) Verbände.

(i) ϕ : P → Q sei ein Verbandshomomorphismus. Dann istϕ ordnungserhaltend.

(ii) ϕ : P → Q sei ein Ordnungsisomorphismus. Dann istϕ ein Verbandsisomor-phismus.

Beweis.(i) Ist a ≤ b, soa = a ∧ b, alsoϕ(a) = ϕ(a ∧ b) = ϕ(a) ∧ ϕ(b) ≤ ϕ(b).

(ii) Wir zeigen, daßϕ(a ∧ b) das Infimum vonϕ(a) undϕ(b) ist. Daa ∧ b ≤ a, b,gilt ϕ(a ∧ b) ≤ ϕ(a), ϕ(b). Es seix ≤ ϕ(a), ϕ(b). Wegen der Bijektivität vonϕ istx = ϕ(c) für ein c ∈ P ; und weilϕ ein Ordnungsisomorphismus ist, folgt ausϕ(c) ≤ϕ(a), ϕ(b), daßc ≤ a undc ≤ b gilt. Also c ≤ a∧ b und weiterx = ϕ(c) ≤ ϕ(a ∧ b).

Alsoϕ(a∧b) = ϕ(a)∧ϕ(b), und ähnlich erschließen wirϕ(a∨b) = ϕ(a)∨ϕ(b).

Hingegen ist zu beachten, daß eine ordnungserhaltendeAbbildung zwischen Verbändennicht notwendig ein Verbandshomomorphismus ist.

2.4 Distributive Verbände

Wir kommen zu einer weiteren Eigenschaft, die Verbände erfüllen können. Wie wir ge-zeigt haben, sind für Verbände die Eigenschaften (i) bis (iv) eines Teilmengenverbandesmaßgeblich, s. Lemma 2.1.3. Die Eigenschaft (v) ist bislangaber nicht aufgetaucht.

Definition 2.4.1. Ein Verband(L;∧,∨) heißedistributiv, falls für alle a, b, c ∈ LFolgendes gilt:

(D) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) unda ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Lemma 2.4.2. Es sei(L;∩,∪) ein Teilmengenverband. Dann istL ein distributiverVerband.

Beweis.Gemäß Lemma 2.3.5 ist(L;∩,∪) ein Verband. Infolge Lemma 2.1.3(v) istdieser Verband distributiv.

Anmerkung 2.4.3. Die Ungleichungen

a ∧ (b ∨ c) ≥ (a ∧ b) ∨ (a ∧ c) (3)

a ∨ (b ∧ c) ≤ (a ∨ b) ∧ (a ∨ c) (4)

23

gelten in jedem Verband. Daher betrifft Axiom (D) nur die jeweils umgekehrte Unglei-chung.

(3) beweist sich folgendermaßen. Gemäß Lemma 2.3.12(ii) folgt ausb ≤ b ∨ c, daßa∧ b ≤ a∧ (b∨ c); und ebenso gilta∧ c ≤ a∧ (b∨ c). Gemäß Lemma 2.3.12(i) folgt(3).

Entsprechend läßt sich auch (4) zeigen.

Wir zeigen weiter, daß von den die Distributivität definierenden (Un)gleichungen sogarnur eine reicht.

Lemma 2.4.4.Es sei(L;∧,∨) ein Verband. Dann ist Folgendes paarweiseäquivalent:

(i) L ist distributiv.

(ii) Für alle a, b, c ∈ L gilt

a ∧ (b ∨ c) ≤ (a ∧ b) ∨ (a ∧ c). (5)

(iii) Für alle a, b, c ∈ L gilt

a ∨ (b ∧ c) ≥ (a ∨ b) ∧ (a ∨ c). (6)

Beweis.Definitionsgemäß impliziert (i) sowohl (ii) als auch (iii). Mit Blick auf Be-merkung 2.4.3 impliziert (ii) und (iii) zusammengenommen (i). Zu zeigen ist also, daß(ii) und (iii) äquivalent sind.

Wir zeigen, daß aus (ii) (iii) folgt.̈Ahnlich ist für die andere Richtung vorzugehen.

Es gelte also (ii). Gemäß Bemerkung 2.4.3 gilt damit die Gleichheit beider Seiten in(5). Wir rechnen unter zweimaliger Verwendung von (ii)

(a ∨ b) ∧ (a ∨ c) = ((a ∨ b) ∧ a) ∨ ((a ∨ b) ∧ c)

= a ∨ (c ∧ (a ∨ b)

= a ∨ (c ∧ a) ∨ (c ∧ b)

= a ∨ (b ∧ c).

Hier heißt es allerdings aufzupassen: (6) folgt daraus, daß(5) für alle a, b, c eines Ver-bandesL gilt, und umgekehrt. Gilt hingegen (5) nur für gewisse Elementea, b, c ∈ L,heißt dies nicht, daß für diese auch (6) gilt.

Beispiel 2.4.5.Alle in Beispiel 2.3.8 besprochenen Verbänden sind distributiv.

Nichtdistributive Verbände sind erst das Thema ab Kapitel4. Wir nehmen dennocheinen Fall vorweg, nur um zu demonstrieren, daß die distributiven Verbände innerhalbder Verbände eine eher spezielle Teilklasse bilden.

24

Es seiL die Menge aller linearen Unterräume desR2.L enthält also den0-dimensionalenUnterraum{0}; die 1-dimensionalen Unterräume[(r, s)] = {λ(r, s) : λ ∈ R} für(r, s) ∈ R2; und den ganzen RaumR2. Wir ordnenL durch mengentheoretische In-klusion. Dann istL ein Verband; das Infimum zweier UnterräumeA undB ist derenDurchschnittA ∩B und das SupremumA ∨B der vonA undB aufgespannte Unter-raum. Es gilt

[(1, 1)] ∩ ([(1, 0)] ∨ [(0, 1)]) = [(1, 1)] ∩R2 = [(1, 1)],

aber([(1, 1)] ∩ [(1, 0)]) ∨ ([(1, 1)] ∩ [(0, 1)]) = {0} ∨ {0} = {0}.

Folglich ist der Verband(L;∩,∨) nicht distributiv.

Lemma 2.4.6.Der Unterverband(A;∧,∨) eines distributiven Verbandes(L;∧,∨) istebenfalls ein distributiver Verband.

Beweis.Gemäß Lemma 2.3.15 istL ein Verband. Des weiteren gilt die Gleichung (D)in L, folglich auch inA.

Schließlich stellt sich die Frage, wie man aus einem Hassediagramm herauslesen kann,ob ein Verband distributiv ist. Es gilt folgendes Lemma.

Lemma 2.4.7.Ein VerbandL ist genau dann distributiv, wenn er keinen Unterverbandder folgenden Form enthält:

N5 M3

Beweis.Ausgelassen.

0, 1-Verbände

Null- und Einselement eines Verbandes werden zuweilen zum Teil der Struktur ge-macht, d.h. es werden Konstanten hinzugefügt, die durch das Null- bzw. Einselementinterpretiert werden.

Definition 2.4.8. Eine Struktur(L;∧,∨, 0, 1) heiße0, 1-Verband, falls (L;∧,∨) einVerband ist und0 das Null- und1 das Einselement vonL ist.

Hat ein Verband kein Null- oder Einselement, läßt sich gem¨aß Lemma 2.2.14 ein sol-ches hinzufügen. Das Ergebnis ist ein0, 1-Verband.

25

Satz 2.4.9.Es sei(L;∧,∨) ein Verband.L besitze kein Nullelement. Es sei0 ein neuesElement undL0 = L∪̇{0}; für a, b ∈ L0 geltea ≤ b, falls entwedera, b ∈ L ist unddies inL gilt oder wenna = 0 ist. Dann istL0 verbandsgeordnet, und die identischeAbbildung vonL nachL0 ist eine Einbettung von Verbänden.

Die entsprechende Konstruktion ist möglich, wennL kein Einselement besitzt. Schließ-lich ist auch das gleichzeitige Hinzufügen von Null- und Einselement möglich.

Beweis.Gemäß Lemma 2.2.14 ist(L0;≤) ein Poset. Weiter seia, b ∈ L0.

Sinda undb beide inL, ist das inL berechnete Infimumc auch das Infimum inL0;denn inL0 gilt c ≤ a, b, und istx ≤ a, b, ist x ≤ c unabhängig davon, obx ∈ L oderx = 0 ist. Ebenso ist das inL berechnete Supremum auch das Supremum inL0.

Ist a = 0 oderb = 0, sind a und b gemäß Konstruktion vergleichbar und besitzendeshalb Infimum wie Supremum. Wir haben gezeigt, daßL0 verbandsgeordnet ist.Gleichfalls haben wir bewiesen, daß die identische AbbildungL → L0 Infimum undSupremum erhält. Damit ist der Beweis des ersten Teils komplett.

Fehlt ein Einselement, gehen wir in exakter Analogie vor. Die Konstruktion ist an-wendbar aufL ebenso wie aufL0.

Man beachte, daß im Fall, daß Satz 2.4.9 zum Zuge kommt, der VerbandL notwendi-gerweise unendlich ist; ein endlicher Verband hat immer einNull- und Einselement.

2.5 Darstellungstheorie

Das grundlegende Beispiel eines distributiven Verbandes ist der Teilmengenverband.Wir zeigen nun, daß es keine weiteren Beispiele gibt; jeder distributive Verband ist alsTeilmengenverband darstellbar.

Um dies zu zeigen, müssen wir, ausgehend von einem distributiven VerbandL, eineMenge konstruieren und jedes Element vonL mit einer Teilmenge identifizieren. Zuüberlegen ist, wie man in einem Teilmengenverband von den Teilmengen zu den ein-zelnen Elementen der Menge gelangt. Das geht ganz einfach: Man identifiziert jedesElement der Menge mit dem System dieses enthaltender Teilmengen. Dieses Systemist offenbar unter Durchschnitt und Vergrößerung abgeschlossen und führt uns zu fol-gender Definition.

Definition 2.5.1. Es sei(L;∧,∨) ein Verband. Eine nichtleere TeilmengeF von LheißeFilter, falls die folgenden Bedingungen gelten:

(F1) Ista, b ∈ F , so aucha ∧ b ∈ F .

(F2) Ista ∈ F undb ≥ a, so auchb ∈ F .

Ein FilterF heißeeigentlich, fallsF nicht ganzL umfaßt.

Ein eigentlicher FilterF vonL heißePrimfilter, falls Folgendes gilt:

26

(F3) Ist füra, b ∈ L a ∨ b ∈ F , gilt entwedera ∈ F oderb ∈ F .

Wir sehen, daß für ein beliebiges Elementa eines VerbandesL beispielsweise das Sy-stem aller Elemente, die größer alsa sind, einen Filter bilden;{b ∈ L : b ≥ a} heißtder Prinzipalfilter vona. Insofern taugt der Begriff des Filters schon einmal, um ein-zelne Elemente vonL zu identifizieren. Der Prinzipalfilter vona ist jedoch nach untenhin begrenzt;a wird sozusagen nicht weiter aufgesplittet. Dies wiederum ist notwendi-gerweise der Fall für einen Primfilter; ista = c∨ d, muß auch eines der beiden unteraliegenden Elementec oderd in F liegen. So können wir in einem Teilmengenverbandmit zugrundeliegender MengeW einen Punktx ∈W wählen; dann ist die Menge allerx enthaltenden Elemente vonL ein Primfilter.

In der Tat wollen wir als Grundmenge für den zu konstruierenden Teilmengenverbanddie Menge der Primfilter verwenden. Worauf es ankommt, ist zuzeigen, daß es derenhinreichend viele gibt. Mit Bezug auf einen Teilmengenverband: Sind die zwei ver-schiedenen Elementen der Grundmenge zugeordneten Primfilter immer verschieden?Das ist in der Tat der Fall, wennL distributiv ist, wie Lemma 2.5.4 zeigen wird.

Lemma 2.5.2. Es seiF Filter eines VerbandesL unda ∈ L nicht inF . Dann ist

Fa = {b ∈ L : b ≥ a ∧ f für einf ∈ F }

der kleinsteF unda enthaltende Filter.

Beweis.Ein Filter ist abgeschlossen unter der Bildung von Infima undder Vergröße-rung von Elementen. Ein Filter, derF ∪ {a} enthält, muß demzufolge auchFa enthal-ten.

Auf der anderen Seite istFa ein Filter. Denn istb, c ∈ Fa, folgt b ≥ a ∧ f1 undc ≥ a ∧ f2 für f1, f2 ∈ F und weiterb ∧ c ≥ a ∧ f1 ∧ f2, d.h.b ∧ c ∈ Fa. Und mitb ∈ Fa ist zudem klarerweise auch jedesc ≥ b in Fa.

Im weiteren benötigen wir das Zornsche Lemma, welches seinerseits mit dem mengen-theoretischen Auswahlaxiom, kurz (AC), gleichwertig ist.

Lemma 2.5.3. (AC) Es sei(P ;≤) ein Poset mit folgender Eigenschaft: Jeder lineargeordnete Unterposet hat eine obere Schranke. Dann hatP mindestens ein maximalesElement.

Lemma 2.5.4. Es seiF Filter eines distributiven VerbandesL unda ∈ L nicht inF .Dann gibt es einen Primfilter, derF umfaßt unda nicht entḧalt.

Beweis.Es seiF die Menge aller Filter vonL, diea nicht enthalten. DaF ∈ F , istFnicht leer.F wird mittels⊆ zu einem Poset. Es seiC ⊆ F linear geordnet, d.h. besteheaus das Elementa nicht enthaltenden Filtern, so daß je zwei von diesen ineinanderenthalten sind. Dann ist offenbar

⋃

C ebenfalls ein Filter, dera nicht enthält; und⋃

Cist eine obere Schranke vonC.

27

Folglich können wir Lemma 2.5.3, das Zornsche Lemma, auf den Poset(F ;⊆) anwen-den; es seiP ein maximales Element inF . Daa /∈ P , istP ein eigentlicher Filter. Wirbehaupten, daßP sogar ein Primfilter ist.

Dies zu zeigen, seic, d ∈ L undc ∨ d ∈ P . Wir nehmen an, daß wederc nochd in Pliegt.P ist maximal inF ; das bedeutet, daß der vonP zusammen mitc oderd gemäßLemma 2.5.2 erzeugte Filter nicht mehr inF liegt, alsoa enthält. Nach Lemma 2.5.2bedeuteta ∈ Pc, daßa ≥ c ∧ f1 für ein f1 ∈ P , unda ∈ Pd, daßa ≥ c ∧ f2 fürein f2 ∈ P . Aus der Distributivität vonL folgt a ≥ (c ∧ f1 ∧ f2) ∨ (d ∧ f1 ∧ f2) =(c∨d)∧ f1 ∧ f2. Daf1 ∧ f2 ∈ P undc∨d ∈ P , heißt dies abera ∈ P . Wir schließen,daß entwederc oderd in P liegt.

Schließlich geben wir noch folgende Charakterisierungen der Begriffe Filter und Prim-filter:

Lemma 2.5.5. Es sei(L;∧,∨) ein Verband.

(i) Eine nichtleere TeilmengeF vonL ist genau dann ein Filter, wenn Folgendesgilt: F ür alle a, b ∈ L ist a ∧ b ∈ F äquivalent zua ∈ F undb ∈ F .

(ii) L enthalte ein Nullelement0. Dann ist ein FilterF vonL genau dann eigentlich,wenn0 /∈ F .

(iii) Ein eigentlicher FilterF vonL ist genau dann ein Primfilter, wenn Folgendesgilt: F ür alle a, b ∈ L ist a ∨ b ∈ F äquivalent zua ∈ F oderb ∈ F .

Beweis.(i) Es seiF ein Filter unda, b ∈ L. Ausa ∧ b ∈ F folgt a, b ∈ F aus (F2).Ausa, b ∈ F folgt a ∧ b ∈ F aus (F1).

Es seiF ⊆ L, und es geltea ∧ b ∈ F , gdwa, b ∈ F . (F1) folgt unmittelbar. Ista ∈ Fundb ≥ a, so ista ∧ b = a ∈ F und folglichb ∈ F .

(ii) Daß F uneigentlich ist, heißtF = L und insbesondere0 ∈ F . Gilt 0 ∈ F , folgtF = L aus (F2).

(iii) Aus a ∈ F oder b ∈ F folgt a ∨ b ∈ F gemäß (F2). Der Rest folgt aus derDefinition eines Primfilters.

Wir kommen zum Darstellungssatz für distributive Verbände.

Satz 2.5.6.Es sei(L;∧,∨) ein distributiver Verband. Dann istL zu einem Teilmen-genverband isomorph.

Beweis.Es seiP die Menge aller Primfilter vonL. Wir ordnen jedem Elementa ∈ Ldie Menge allera enthaltenden Primfilter zu:

ϕ(a) = {P ∈ P : a ∈ P}. (7)

28

Wir behaupten, daß dies ein Homomorphismus vonL in den Verband aller TeilmengenvonP ist. In der Tat ergibt sich füra, b ∈ L unter Verwendung von Lemma 2.5.5:

ϕ(a ∧ b) = {P ∈ P : a ∧ b ∈ P}

= {P ∈ P : a ∈ P undb ∈ P}

= {P ∈ P : a ∈ P} ∩ {P ∈ P : b ∈ P}

= ϕ(a) ∩ ϕ(b)

sowie im Hinblick auf Lemma 2.5.5(iii)

ϕ(a ∨ b) = {P ∈ P : a ∨ b ∈ P}

= {P ∈ P : a ∈ P oderb ∈ P}

= {P ∈ P : a ∈ P} ∪ {P ∈ P : b ∈ P}

= ϕ(a) ∪ ϕ(b)

Weiter istϕ injektiv. Denn es seiena, b ∈ L zwei verschiedene Elemente. O.E.d.A. neh-men wira 6< b an. Dann istb im Prinzipalfilter vona nicht enthalten; dieser kann nachLemma 2.5.4 zu einemb weiterhin nicht enthaltenden PrimfilterP erweitert werden.Also istP ∈ ϕ(a), aberP /∈ ϕ(b).

Es sei nunL′ das Bild vonϕ in der Potenzmenge vonP . L′ bildet den Teilmengen-verband(L′;∩,∪), undϕ, aufgefaßt als Abbildung vonL nachL′, ist ein Isomorphis-mus.

Leicht läßt sich der Fall ergänzen, daß das Null- und Einselement durch Konstantenvertreten sind. Enthält ein Teilmengenverband die leere und ganze Menge, bezeichnenwir diese mit∅ bzw. 1r.

Satz 2.5.7.Es sei(L;∧,∨, 0, 1) ein distributiver0, 1-Verband. Dann istL zu einemTeilmengenverband isomorph, wobei0 durch die leere und1 durch die ganze Mengerepräsentiert sind.

Beweis.Gemäß Satz 2.5.6 ist(L;∧,∨) isomorph zu einem Teilmengenverband(L′;∩,∪).Der Isomorphismusϕ : L→ L′ war durch (7) definiert worden. Wir lesen ab:ϕ(0) ={P ∈ P : 0 ∈ P} = ∅, weilP nur aus eigentlichen Filtern besteht; s. Lemma 2.5.5(ii).Weiter gilt:ϕ(1) = {P ∈ P : 1 ∈ P} = P ; denn aufgrund Bedingung (F2) enthältjeder eigentliche Filter1.

Also ist (L;∧,∨, 0, 1) isomorph zu(L′;∩,∪,∅, 1r).

2.6 Logik

Nach den algebraisch-theoretischenÜberlegungen des letzten Abschnitts kehren wirnunmehr zum ursprünglichen Verständnis distributiver Verbände zurück: Wir fassendiesen als ein System auf, der gewisse Aussagen repräsentiert.

29

Weiterhin ist das Bild eines Teilmengenverbandes(L;∩,∪) maßgeblich. Deren Grund-mengeW repräsentiert eine Menge hinsichtlich irgendwelcher Aspekte unterschiede-ner Situationen; wir hattenW eingangs Menge möglicher Welten genannt. JedesA ∈ List eine Teilmenge vonW und repräsentiert eine Eigenschaft: diejenige Eigenschaft,die in denjenigen möglichen Welten gilt, dieA enthält, und die in den übrigen Weltennicht gilt.

Es mögen beispielsweiseϕ, ψ, ζ, η vier Eigenschaften symbolisieren. Zu deren Re-präsentierung sei eine MengeW möglicher Welten gegeben, undϕ, ψ, ζ, η seien durchdie TeilmengenA, B, C bzw.D ausL dargestellt. Die Struktur(L;∧,∨) bietet nunzwei Operationen, die es ermöglicht, aus gegebenen Teilmengen neue zu konstruie-ren, sowie die Möglichkeit, mengentheoretische Inklusion auszudrücken. AusA undB wird A ∩ B, welches als die Konjunktion der Eigenschaftenϕ undψ interpretier-bar ist:

”ϕ undψ“. Ebenso kannA ∪ B mit der Disjunktion vonϕ undψ identifiziert

werden:”ϕ oderψ“. Weiterhin können Eigenschaften ihrer Ausdruckskraft gemäß zu-

einander in Bezug gesetzt werden. Es gelte inL etwa

A ∩B ⊆ C ∪D; (8)

dies kann interpretiert werden als die Aussage”Ausϕ undψ folgt, daßζ oderη“.

Diesem Verständnis logischer Zusammenhänge wollen wir nun einen formalen Rah-men verleihen. Wir werden es zu tun haben mit Aussagen wie z.B.

ϕ ∧ ψ → ζ ∨ η (9)

und diese genau so verstehen wie vorstehend skizzirt:ϕ, ψ, ζ, η werden durch Teilmen-gen einer fixen Menge modelliert, und (9) wird für gültig erklärt, wenn (8) zutrifft.

Was ist hierbei die Fragestellung? Herausfinden wollen wir,was aus Postulaten von derForm (9) zu schließen ist. Eine TheorieT wird eine Menge von Implikationen wie (9)sein; z.B.T = {ϕ → α, ϕ → β}; dann werden wir in der Lage sein, hierausϕ →α ∧ β abzuleiten. Es geht mit anderen Worten darum zu ergründen,welche Schlüsseaus Zusammenhängen gezogen werden, die in einer Sprache formuliert sind, welchenichts als das logische

”und“, das logische

”oder“ sowie die Implikation enthält – dies

ist die Sprache der Verbandstheorie.

Wir werden eine spezielleAussagenlogikdefinieren. Eine solche konstituiert sich ausdreierlei:

• Durch die Wahl einer formalenSprachewird festgelegt, welcher Art Aussagenbetrachtet werden. Die Sprache besteht aus Variablensymbolen, welche beliebi-ge Aussagen bezeichnen, aus Konstantensymbolen, welche bestimmte Aussagenbezeichnen, sowie aus Verknüpfungssymbolen,mit welchenaus gegebenen Aus-sagen neue konstruiert werden.

• Weiter wird spezifiert, in welcher Art formalenStrukturendie Aussagen der for-malen Sprache zuinterpretierensind. Es handelt sich um Algebren, deren Ele-mente Aussagen modellieren und die mit Operationen versehen sind, die je eineVerknüpfung modellieren.

30

• Ein Beweissystembesteht aus Regeln, wie aus in der gewählten formalen Spra-che formulierten Aussagen weitere solche generiert werdenkönnen. Wenn dabeierstere unter einer Interpretation in einer Struktur gelten, so muß dies auch fürdie abgeleiteten gelten.

Am Beispiel der distributiven0, 1-Verbände demonstrieren wir nun dieses allgemeineSchema. Wir spezifieren im Folgenden dieLogik distributiver Verb̈ande, abgekürztLDV.

Definition 2.6.1. Die Termeder LogikLDV sind die gemäß folgenden Regeln zustan-dekommenden Zeichenketten.

(i) EineVariableist eines der Symboleϕ1, ϕ2, . . .; eineKonstanteist eines der Sym-bole⊥,⊤. Jede Variable und jede Konstante ist ein Term; und zwar ein sogenanntatomarerTerm.

(ii) Sindα undβ Terme, so auchα∧β undα∨β, wobei im Fall, daßα oderβ nichtatomar ist, diese von Klammern zu umschließen sind.

Die Menge aller Terme seiA.

Weiter ist eineAussagevon LDV ein Paar, bestehend aus einer nichtleere endlicheMenge von Termenα1, . . . , αn sowie einem einzelnen weiteren Termβ. Diese notierenwir gemäß

α1, . . . , αn → β.

Beispiele für Terme sind etwaϕ23, ϕ2 ∧ (ϕ4 ∨ ϕ3), ⊥. Beispiele für Aussagen sindϕ2 → ϕ5 oderϕ1, ϕ2 → ϕ3 ∨ ϕ4. An letzterer läßt sich die beabsichtigte Bedeutungeiner Aussage demontrieren:

”Wennϕ1 undϕ2 gilt, so ϕ3 oderϕ4“. Die logischen

Verknüpfungen∧ und∨ spiegeln mithin”und“ und

”oder“ wieder; das Komma hat wie

∧ die Bedeutung”und“.

Wir legen nun so, wie oben angedeutet, die Interpretation der Aussagen vonLDV fest.

Definition 2.6.2. Es sei(L;∩,∪,∅, 1r) ein Teilmengenverband. Weiter seiv eine Ab-bildung von der MengeA aller Terme nachL, so daß folgende Bedingungen erfülltsind:

(i) v(⊥) = ∅ undv(⊤) = 1r;

(ii) v(α ∧ β) = v(α) ∩ v(β) undv(α ∨ β) = v(α) ∪ v(β) für alle Termeα, β.

Dann heißev eineBelegung[engl.evaluation] (der Terme) vonLDV. Der Teilmengen-verbandL heiße dann auchModellvonLDV.

Eine Aussageα1, . . . , αn → β sei gültig unter einer Belegungv, falls

v(α1) ∩ . . . ∩ v(αn) ⊆ v(β).

31

Eine Belegung ist damit eine Interpretation der Terme der Logik LDV in einem Teil-mengenverband. Letzterer wird auf diese Weise zu einem Modell von LDV. Eine Aus-sage gilt unter einer gegebenen Interpretation, falls der Durchschnitt auf der linkenSeite eine kleinere Menge ergibt als auf der rechten Seite steht; das heißt inhaltlich,daß die Konjunktion der linken Seite die rechte Seite impliziert.

Zur modelltheoretischen Definition der LogikLDV fehlt nun nur noch die Folgebezie-hung.

Definition 2.6.3. EineTheorievonLDV sei eine Menge von Aussagen vonLDV.

Es seiT ein Theorie undΦ eine Aussage vonLDV. Wir sagen, daßT Φ semantischimpliziert, in ZeichenT |= Φ, falls Φ unter jeder Belegung gültig ist, unter der jedeAussage inT gültig ist.

M.a.W. impliziert eine Menge von Aussagen semantisch eine weitere solche, falls letz-tere in jedem Modell gilt, in dem jede ersterer gilt.

Damit haben wir festgelegt, was Aussagen vonLDV beinhalten und was es heißt, daßsolche andere nach sich ziehen. Die Frage ist nun, ob es Regeln gibt, mit denen manaus gegebenen Aussagen all diejenigen ableiten kann, die semantisch impliziert sind.FürLDV ist dies der Fall; wir stellen einBeweissystemfür LDV vor.

Eine Regel ist ein Paar, bestehend aus einer endlichen Menge von Aussagen, denPrämissen, und einer weiteren Aussage, derKonsequenz. Das Paar wird übereinandernotiert, durch einen horizontalen Strich getrennt. Eine Regel mit leerer Prämissenmen-ge heißtAxiome; in diesem Fall wird allein die Konsequenz notiert.

Weiter ist die linke Seite einer Aussage stets definitionsgemäß eine nichtleere endlicheMenge;

”α1, . . . , αk“ ist die α1, . . . , αk enthaltende Menge, und Doppeltnennungen

sind möglich. Wir werden außer Termen auch Teilmengen von Termen durch Kommatareihen. Es steht dann z.B.

”Γ, α, β“ für Γ∪ {α, β}. Γ kann dabei leer sein, andererseits

könnenα undβ auch inΓ enthalten sein.

Definition 2.6.4. Die Regeln vonLDV sind die folgenden, worinΓ eine beliebigeendliche Menge von Termen ist undα, β, γ beliebige Terme sind:

(A1) ⊥ → α (A2) α → α (A3) α → ⊤

(Cut)Γ1 → α Γ2, α→ β

Γ1,Γ2 → β

(lw)Γ → β

Γ, α → β(∧ →)

Γ, α, β → γ

Γ, α ∧ β → γ(→ ∧)

Γ → α Γ → β

Γ → α ∧ β

(∨ →)Γ, α→ γ Γ, β → γ

Γ, α ∨ β → γ(→ ∨1)

Γ → α

Γ → α ∨ β(→ ∨2)

Γ → β

Γ → α ∨ β

Weiter seiT eine Theorie undΦ eine Aussage. EinBeweisvonΦ ausT ist eine endli-che Sequenz von Regeln, so daß jeder Prämisse einer Regel entweder ausT oder gleichder Konsequenz einer vorhergehenden Regel ist undΦ die Konsequenz der letzten Re-gel ist.Φ heißt ausT beweisbar, in ZeichenT ⊢ Φ, falls es einen Beweis vonΦ ausTgibt.

32

Liegt für eine semantisch begründete Logik ein Beweissystem vor, stellen sich zweiFragen. Als wichtigstes ist erstens zu fragen, ob die Regelnkorrekt sind: Kann ich mitden Regeln nur das ableiten, was auch semantisch impliziertist? Zweitens stellt sichdie manchmal nur akademische, aus Sicht der Logiker aber alles entscheidende Frage,ob die Regeln vollständig sind: Kann ich mit den Regelnallesableiten, was semantischimpliziert ist? Im vorliegenden Fall ist die Antwort zweimal positiv.

Der folgende Satz beinhaltet die sogenannteKorrektheitunseres Beweissystems.

Satz 2.6.5.Es seiT eine Theorie vonLDV. IstΦ ausT beweisbar, so impliziertT Φsemantisch.

Beweis.Wir müssen für jede Regel Folgendes prüfen: Gelten untereiner Belegung allePrämissen, so auch die Konsequenz.

Die drei Axiome müssen demgemäß unter jeder Belegung gelten. Wir betrachten dasAxiom (A1), d.h.⊥ → α. Dieses gilt unter einer Belegungv, falls v(⊥) ⊆ v(α). vbildet⊥ nach∅ undα in das ElementA einer Teilmengenalgebra ab; da∅ ⊆ A immergilt, ist die Bedingung also erfüllt.̈Ahnlich ist für die übrigen Axiome vorzugehen.

Wir betrachten die Regel (lw), d.h.Γ→βΓ,α→β . Es seiΓ = {γ1, . . . , γk}. Es seiv eineBelegung; wir setzenG1 = v(γ1), . . . , Gk = v(γk) undA = v(α), B = v(β).Weiter seien die Prämissen der Regel unterv erfüllt; das bedeutet definitionsgemäßv(γ1) ∩ . . . ∩ v(γk) ⊆ v(β), d.h.

G1 ∩ . . . Gk ⊆ B.

Hieraus folgtG1 ∩ . . . Gk ∩ A ⊆ B,

also gilt auch die Konsequenz. Nach dem gleichen Schema ist für die übrigen Regelnvorzugehen; letztlich sind nur triviale mengentheoretische Fakten benötigt.

Wir kommen nun zurVollständigkeitunseres Beweissystems. Vollständigkeitsbeweisekönnen sehr lang und knifflig sein; der vorliegende Fall gibt einen Geschmack davon.

Wir verwenden im Beweis den Begriff der̈Aquivalenzrelation. Definiert und in allerAusführlichkeit besprochen wird dieser jedoch erst in anderem Zusammenhang in Ka-pitel 4.2. Wer ihn nicht kennt, sei auf Abschnitt 4.2 verwiesen, der sich vom Rest un-abhängig lesen läßt; relevant sind hier nur die Definitionen 4.2.1 und 4.2.2 sowie Lem-ma 4.2.3. Alternativ kann der vorliegende sowie der späternoch folgende Vollständig-keitsbeweis beim ersten Lesen auch übersprungen werden.

Satz 2.6.6.Es seiT eine Theorie vonLDV. ImpliziertT Φ semantisch, so istΦ ausT beweisbar.

Beweis.Der Beweis verläuft indirekt. Wir nehmen an, daßΦ ausT nicht beweisbarist. Unser Ziel ist es, zu zeigen, daß es eine Belegung gibt, unter alle Elemente vonT ,nicht aberΦ erfüllt ist.

33

Für zwei Termeα undβ ausF setzen wir

α ∼ β falls T ⊢ α→ β undT ⊢ β → α.

Dann ist∼ eineÄquivalenzrelation aufF ; Reflexitivität gilt wegen (A1), Symmetrienach Konstruktion und Transitivität wegen (Cut). Es sei〈α〉 dieÄquivalenzklasse einesα ∈ F , und es sei〈F〉 = {〈α〉 : α ∈ F}.

Wir behaupten weiter, daß∼ eine mit∧ und∨ kompatibleÄquivalenzrelation ist. Dasbedeutet Folgendes:

(⋆) Es seiα, α′, β, β′ ∈ F . Ausα ∼ α′ undβ ∼ β′ folgt dannα ∧ β ∼ α′ ∧ β′ sowieα ∨ β ∼ α′ ∨ β′.

Zum Beweis nehmen wir alsoα ∼ α′ undβ ∼ β′ an.T beweist dannα → α′. Esfolgt α, β → α′ mit (lw). Weiter istβ → β Axiom, aus welchemα, β → β folgt. Mit(→ ∧) ergibt sichα, β → α′ ∧ β und mit (→ ∧) α ∧ β → α′ ∧ β. Entsprechend istauchα′ ∧ β → α′ ∧ β′ herleitbar, und mit (Cut) folgtα∧ β → α′ ∧ β′. Ebenso zeigenwir, daßT auchα′ ∧ β′ → α ∧ β beweist; alsoα ∧ β ∼ α′ ∧ β′.

Im Fall von∨ gehen wir ähnlich vor. Ausα → α′ folgt α → α′ ∨ β mit (→ ∨1). Ausβ → β folgt β → α′ ∨ β mit (→ ∨2). Also α ∨ β → α′ ∨ β mittels (∨ →). NachWiederholung dieser Schritte gelangen wir schließlich zuα ∨ β ∼ α′ ∨ β′.

Wir nutzen nun (⋆) aus, um die Operationen∧ und∨ auf 〈F〉 wie folgt zu erklären.Fürα, β ∈ F setzen wir

〈α〉 ∧ 〈β〉 = 〈α ∧ β〉,

〈α〉 ∨ 〈β〉 = 〈α ∨ β〉.

Damit haben wir eine Algebra(〈F〉;∧,∨, 〈0〉, 〈1〉) konstruiert. Wir zeigen, daß dieseein distributiver Verband ist.

Zunächst statten wir〈F〉 mit der Relation

〈α〉 ≤ 〈β〉, falls T ⊢ α→ β

aus. Dann ist≤ eine partielle Ordnung; Reflexivität gilt wegen (A1), Antisymmetrienach Konstruktion und Transitivität wegen (Cut).

Wir zeigen als nächstes, daß∧ und∨ in bezug auf≤ Infimums- und Supremumsope-ration sind. Es gilt〈α ∧ β〉 ≤ 〈α〉, 〈β〉; dies zeigt im ersteren Fall der Beweis

α→ αα, β → α

(lw)

α ∧ β → α,(∧→)

der letztere Fall geht analog. Weiter sei〈γ〉 ≤ 〈α〉, 〈β〉 angenommen; das bedeutet,daßT γ → α undγ → β beweist. Es folgtγ → α ∧ β, d.h.〈γ〉 ≤ 〈α ∧ β〉.

Ähnlich gilt 〈α〉, 〈β〉 ≤ 〈α ∨ β〉, und aus〈α〉, 〈β〉 ≤ 〈γ〉 folgt 〈α ∨ β〉 ≤ 〈γ〉. Damitist gezeigt, daß(〈F〉;∧,∨) ein Verband ist.

34

Wegen (A1) und (A3) sind〈⊥〉 und〈⊤〉 Null- und Einselement. Es verbleibt, das Dis-tributivgesetz nachzuweisen. Wir gehen wie folgt vor:

α→ αα, β → α

(lw)β → β

α, β → β(lw)

α, β → α ∧ β(→∧)

α, β → (α ∧ β) ∨ (α ∧ γ)(→∨)

Ähnlich sehen wirα, γ → (α ∧ β) ∨ (α ∧ γ). Es folgtα, β ∨ γ → (α ∧ β) ∨ (α ∧ γ)und schließlichα∧ (β ∨γ) → (α∧β)∨ (α∧γ). Im Hinblick auf Lemma 2.4.4 ist derBeweis komplett.

Wir definieren nunv′ : F → 〈F〉, α 7→ 〈α〉.

Dann istv′(⊥) = 〈⊥〉 undv′(⊤) = 〈⊤〉, und es giltv′(α∧β) = v′(α)∧ v′(β) sowiev′(α∨β) = v′(α)∨v′(β). Schließlich ist der distributive Verband(〈F〉;∧,∨, 〈0〉, 〈1〉)einem Teilmengenverband isomorph. Istϕ der Isomorphismus, istv = ϕ ◦ v′ eineBelegung.

Es sei weiterα1, . . . , αk → β eine Aussage ausT . Diese ist trivialerweise ausTbeweisbar und damit auchα1 ∧ . . .∧αk → β. Dies bedeutet wiederumv′(α1) ∧ . . .∧v(αk) = 〈α1〉 ∧ . . . ∧ 〈αk〉 = 〈α1 ∧ . . . ∧ αk〉 ≤ 〈β〉 = v′(β). Also ist die Aussageunterv erfüllt.

Weiter seiΦ die Aussageγ1, . . . , γl → δ. WäreΦ unterv erfüllt, hieße dies〈γ1 ∧ . . . ∧ γl〉 =〈γ1〉 ∧ . . . ∧ 〈γl〉 = v(γ1) ∧ . . . ∧ v(γl) ≤ v(δ) = 〈δ〉; also wäreΦ ausT beweisbar.Es folgt, daßΦ unterv nicht erfüllt ist.

35

3 Boolesche Algebren

3.1 Motivation

Ein weiteres Mal gehen wir davon aus, daß wir eine Menge von Situationen zu model-lieren haben, repräsentiert durch eine Menge möglicher WeltenW . Mögliche Weltensind durch Eigenschaften charakterisiert, die in jeder solchen entweder zutreffen odernicht. Ja-Nein-Aussagen besagen, daß eine gewisse Eigenschaft zutrifft. Eine Aussageϕ wird demgemäß durch eine Teilmenge vonW modelliert, etwaA; eine möglicheWelt ist in A genau denn, wenn dieϕ zugeordnete Eigenschaft in dieser möglichenWelt zutrifft.

Wir haben Aussagen ihrer Stärke nach verglichen. Es sei etwaϕ durchA undψ durchB modelliert. Dann kannA in B enthalten sein; in diesem Fall istϕ die stärkere derbeiden Aussagen undψ die schwächere; in der Tat giltψ in allen möglichen Welten, indeneϕ gilt, und in diesem Sinne impliziertϕ ψ. Die zugehörige abstrakte Struktur istdie eines Posets.

Mittels der partiellen Ordnung kann man weiter je zwei Aussagen deren Konjunktionzuordnen. Als Konjunktion können wir die schwächste Aussage ansehen, die stärkerist als beide diese Aussagen; im Poset ist dies das Infimum derbeiden Teilmengen vonW , der mengentheoretische Durchschnitt vonA undB, d.h.A ∩ B. Als Disjunktionkönnen wir die stärkste Aussage ansehen, die schwächer ist alsϕ undψ; es ergibt sichdas Supremum, die Vereinigung vonA undB, d.h.A ∪B.

Wir haben die Negation von Aussagen bislang noch nicht betrachtet. Nahe liegt, wennϕ durchA repräsentiert wird, die Negation vonϕ durch das mengentheoretische Kom-plement darzustellen, d.h.∁A. Genau dies werden wir im weiteren tun. Man beachte,daß damit das Gebiet der Posets nicht verlassen; so wie das Infimum und das Supre-mum ist auch das Komplement allein durch die partielle Ordnung festgelegt. Die Ne-gation vonϕ ist die schwächste Aussage, deren Konjunktion mitϕ die falsche Aussageist; demgemäß wird sie durch die größte Menge modelliert,deren Durchschnitt mitAdie leere Menge ergibt – dies ist∁A.

Wenn wir die so verstandene Negation hinzufügen, gelangenwir vom distributiven0, 1-Verband zur booleschen Algebra.

Definition 3.1.1. Es seiW eine nichtleere Menge. Weiter besteheL aus TeilmengenvonW dergestalt, daß∅ und 1r=W , mitA jeweils auch∁A und mitA undB jeweilsauchA∩B undA∪B in L ist. Dann heiße(L;∩,∪, ∁,∅, 1r) eineTeilmengenalgebra.

Insbesondere kannL die ganze PotenzmengePW vonW sein.

Wir listen im Folgenden die charakteristischen Eigenschaften einer Teilmengenalgebraauf.

Lemma 3.1.2. Es sei(L;∩,∪, ∁,∅, 1r) eine Teilmengenalgebra. Dann gilt für alleA,B,C ∈ L:

(0) ∅ ⊆ A undA ⊆ 1r.

36

(i) A ∩ A = A ∪ A = A.

(ii) A ∩B = B ∩ A undA ∪B = B ∪ A.

(iii) A ∩ (B ∩C) = (A ∩B) ∩ C undA ∩ (B ∪ C) = (A ∪B) ∪C.

(iv) A ∩ (A ∪B) = A ∪ (A ∩B) = A.

(v) A ∩ (B ∪C) = (A ∩B) ∪ (A ∩ C) undA ∪ (B ∩ C) = (A ∪B) ∩ (A ∪C).

(vi) A ∩ ∁A = ∅ undA ∪ ∁A = 1r.

3.2 Komplemente in Verb̈anden

Wir halten uns für die folgenden Definitionen die Teilmengenalgebra vor Augen.

Definition 3.2.1. Es sei(L;∧,∨, 0, 1) ein 0, 1-Verband. Es seia ∈ L. Dann heißeb ∈ L Komplementvona falls

(i) a ∧ b = 0,

(ii) a ∨ b = 1

gilt. Besitzt jedesa ∈ L ein Komplement, heißeL komplementiert.

Eine Funktion¬ : L→ L heiße eineKomplementfunktionvonL, falls für allea, b ∈ LFolgendes gilt:

(CF1) ¬a ist ein Komplement vona,

(CF2) ausa ≤ b folgt ¬b ≤ ¬a,

(CF3) ¬¬a = a.

Man könnte vielleicht meinen, daß Komplemente, wenn vorhanden, eindeutig bestimmtsind oder zumindest jedes Element ein kanonisches Komplement hat. Dies gilt für dis-tributive Verbände, keinesfalls aber allgemein.

Beispiel 3.2.2. (i) Es sei(L;∩,∪,∅, 1r) ein Teilmengenverband mit 0 und 1. Dannist L komplementiert. Wie man sich leicht überlegt, hat jedesA ∈ L genau einKomplement, und zwar∁A. Zudem istL → L, A 7→ ∁A eine Komplement-funktion.

(ii) Ein linear geordnete Menge mit mehr als zwei Elementen ist nicht komplemen-tiert. Man betrachte z.B. die vierelementige Menge{0, 1, 2, 3} mit ≤ als dernatürlichen Ordnung. Es hat1 kein Komplement;x ∧ 1 = 0 impliziert x = 0,wohingegenx ∨ 1 = 3 x = 3 bedeutet.

(iii) Der VerbandM3 (s. Beispiel 2.2.13) ist komplementiert. Die nichtextremalenElemente haben je zwei Komplemente. Z.B. besitztb das Komplementc undd.

Eine Komplementfunktion läßt sich aufM3 jedoch nicht definieren.

37

Der Begriff des Komplementes läßt sich wie folgt auch lokaldefinieren. In einem Teil-mengenverband können wir etwa eine Menge herausgreifen, das Intervall betrachten,das aus deren Teilmengen besteht, und danach fragen, ob Teilmengen innerhalb diesesIntervalls Komplemente besitzen.

Definition 3.2.3. Es sei(L;∧,∨) ein Verband. Es seip, q ∈ L mit p < q, und es seia ∈ [p, q]. Dann heißeb ∈ L relatives Komplementvona in [p, q], falls

(i) a ∧ b = p,

(ii) a ∨ b = q

gilt. Besitzt jedesa ein relatives Komplement in jedema enthaltenden Intervall, heißeL relativ komplementiert.

Dies läßt sich auch so ausdrücken: In einem Verband seip ≤ a ≤ q; dann heißtfür b, ein relatives Komplement vona im Intervall [p, q] zu sein, ein Komplement imnormalen Sinne im0, 1-Verband([p, q];∧,∨, p, q) zu sein.

Lemma 3.2.4. Ein VerbandL ist relativ komplementiert genau dann, wenn jedes In-tervall vonL komplementiert ist.

Beweis.Dies ist aus den Definitionen unmittelbar einsichtig.

In distributiven Verbänden können wir aus Komplementen leicht auch relative Kom-plemente bestimmen.

Lemma 3.2.5. Es sei(L;∧,∨) ein distributiver Verband. Es seib ∈ L Komplementvona ∈ L. Weiter seip < q unda ∈ [p, q]. Dann ist

b′ = (b ∧ q) ∨ p (10)

relatives Komplement vona in [p, q].

Beweis.Dies überprüfen wir durch Nachrechnen der Bedingungen (i), (ii) aus Defini-tion 3.2.3.

Beispiel 3.2.6. (i) Es sei(L;∩,∪,∅, 1r) ein Teilmengenverband mit 0 und 1. EsseienP,Q ∈ L mit P ⊂ Q undA ∈ L mit P ⊆ A ⊆ Q gegeben.

HatA das relative KomplementB in [P,Q], mußA ∩ B = P undA ∪ B = Qgelten. Also ist(∁A∩Q)∪P = (∁A∩(A∪B))∪(A∩B) = (∁A∩∩B)∪(A∩B) =B. Damit ist (10) bestätigt.

(ii) Der folgende VerbandL ist komplementiert. Jedoch hat das Elementc im Inter-vall [b, d] kein relatives Komplement:

38

L

3.3 Boolesche Algebren

Wir betrachten nunmehr Komplementfunktionen auf distributiven Verbänden.

Definition 3.3.1. Eine Algebra(L;∧,∨,¬, 0, 1) heißeboolesche Algebra, falls Fol-gendes gilt:

(BA1) (L;∧,∨,¬, 0, 1) ist ein distributiver0, 1-Verband.

(BA2) ¬ ist eine Komplementfunktion aufL.

Boolesche Algebren sind insbesondere komplementierte distributive Verbände. Boole-sche Algebren und komplementierte distributive Verbändesind im Grunde sogar das-selbe, wie das folgende Lemma zeigt.

Lemma 3.3.2. Es sei(L;∧,∨, 0, 1) ein komplementierter distributiver0, 1-Verband.Dann besitzt jedesa genau ein Komplement¬a, und zwar

¬a = max {c ∈ L : a ∧ c = 0}. (11)

Es gibt zudem genau eine Komplementfunktion aufL, gegeben durch die Zuordnunga 7→ ¬a. Mit dieser ist(L;∧,∨,¬, 0, 1) eine boolesche Algebra.

Beweis.Es seia ∈ L. Nach Voraussetzung besitzta das Komplementb. Daa∧ b = 0,ist b in der Menge{c ∈ L : a∧ c = 0} enthalten, welche damit insbesondere nicht leerist. Angenommen sei, daßa∧c = 0 für einc ∈ L. Dann folgtc = c∧1 = c∧(a∨b) =(c ∧ a) ∨ (c ∧ b) = c ∧ b ≤ b. Also istb das größte Element von{c ∈ L : a ∧ c = 0}.Es folgt (11) und insbesondere, daßa genau ein Komplement besitzt.

Wir zeigen, daß (11) eine Komplementfunktion definiert; dann folgt, daßL, erweitertum die Operation¬, eine boolesche Algebra ist. Nachzuprüfen sind (CF2) und (CF3).Ist a ≤ b, folgt {c ∈ L : b∧ c = 0} ⊆ {c ∈ L : a∧ c = 0}, also ist das Maximum überletztere Menge größer als das über die erstere, d.h.¬b ≤ ¬a. Ist weiterb Komplementvon a, so ist aucha Komplement vonb; wegen der Eindeutigkeit des Komplementsfolgt ¬¬a = a.

Damit ist formal gezeigt, daß die Komplementfunktion boolescher Algebra durch diepartielle Ordnung allein schon eindeutig bestimmt ist.

Lemma 3.3.3. Eine Teilmengenalgebra(L;∩,∪, ∁,∅, 1r) ist eine boolesche Algebra.

39

Beweis.Gemäß Lemma 2.3.5 ist(L;∩,∪) ein Verband. Gemäß Lemma 3.1.2(0) ist∅das Null- und 1rdas Einselement. Gemäß 3.1.2(vi) ist∁A ein Komplement einesA ∈ L.Also istL ein komplementierter distributiver0, 1-Verband, gemäß Lemma 3.3.2 alsoeine boolesche Algebra.

Beispiel 3.3.4. Über das Standardbeispiel hinaus weitere Beispiele zu geben ist garnicht einfach.

(i) Der einfachste Fall von Lemma 3.3.3 ist die ganze Potenzmenge einer MengeW . Das folgende ist ein Beispiel, wo nicht die ganze Potenzmenge zum Einsatzkommt.

Es seiW eine unendliche Menge. Es seiWf = {A ⊆ W : A ist endlich} dieMenge aller endlichen undWcf = {A ⊆ W : ∁A ist endlich} die Menge allersogenannt koendlichen Teilmengen vonW . Dann überlegt man sich leicht, daßL = Wf∪Wcf die leere und ganze Menge enthält und unter Durchschnitt, Verei-nigung sowie Komplementbildung abgeschlossen ist. Also ist (L;∩,∪, ∁,∅, 1r)eine Teilmengenalgebra, insbesondere eine boolesche Algebra.

(ii) Es seiW ein topologischer Raum und es seiL die Menge aller regulär offenenMengen:

L = {A◦ : A ⊆W ist abgeschlossen}.

Beispielsweise seiW = R mit der üblichen Topologie versehen. Dann sindoffene Intervalle inL und auch deren Vereinigungen, sofern die Randpunktenicht übereinstimmen. D.h.(0, 1) ∪ (2, 3) liegt in L, (0, 1) ∪ (1, 2) aber nicht;(0, 1) ∪ (1, 2) ist nicht das offene Innere irgendeiner abgeschlossenen Menge.

FürA ⊆W setzen wirAr = A−

◦

.

Wir behaupten, daßArr = A für jedesA ⊆W gilt. Hierfür berechnen wir

Ar = {x ∈ W : es gibt eine UmgebungU vonx, so daßU ⊆ A−}

= {x ∈ W : es gibt eine UmgebungU vonx, so daß

für jede UmgebungV eines beliebigeny ∈ U gilt V ∩ A 6= ∅}

= {x ∈ W : es gibt eine UmgebungU vonx, so daß

für jedes nichtleere offeneV ⊆ U gilt V ∩ A 6= ∅}.

Es folgt, daAr offen ist, daß

Arr = {x ∈ W : es gibt eine UmgebungU vonx, so daß

für jedes nichtleere offeneV ⊆ U gilt V ∩ Ar 6= ∅}

= {x ∈ W : es gibt eine UmgebungU vonx, so daßU ⊆ Ar gilt}

= Ar.

Wir behaupten weiter, daß eine TeilmengeA ⊆W genau dann regulär ist, wennA = Ar. Denn ausA = Ar folgt natürlich die Regularität vonA. Umgekehrt

40

seiA regulär, d.h.A = B◦ für ein abgeschlossenesB ⊆ W . Dann folgtAr =B◦r = Brr = Br = B◦ = A.

Als nächstes bemerken wir, daß für offene MengenA,B ⊆W gilt

Ar ∩Br = (A ∩B)r .

Denn, wie wir wissen, gilt

Ar ∩Br = {x ∈ W : es gibt eine UmgebungU vonx, so daß

für jedes nichtleere offeneV ⊆ U gilt V ∩ A, V ∩B 6= ∅}.

Für einx seiU eine Umgebung wie spezifiziert. Dann gilt für jdees offeneV ⊆U , daßV ∩A 6= ∅; und da auchV ∩ A offen ist, gilt auchV ∩A ∩B 6= ∅. Esfolgt

Ar ∩Br = {x ∈W : es gibt eine UmgebungU vonx, so daß

für jedes nichtleere offeneV ⊆ U gilt V ∩ A ∩B 6= ∅}

= (A ∩B)r .

L sei nun durch⊆ partiell geordnet. Wir behaupten, daß dannL ein Verband ist.Denn für reguläre MengenA,B ∈ L ist

A ∩B = Ar ∩Br

= (A ∩B)r

wiederum regulär; also istA ∩ B das Infimum vonA undB in L. Die Vereini-gung zweier regulärer Mengen ist i.a. nicht regulär; das Supremum vonA undBexistiert dennoch:

A ∨B = (A ∪B)r.

In der Tat folgt ausA ⊆ A ∪ B, daßA = Ar ⊆ (A ∪ B)r gilt; ähnlich folgtB ⊆ (A∪B)r ; also ist(A∪B)r obere Schranke vonA undB. Ist weiterC ∈ LundA,B ⊆ C, folgtA ∪B ⊆ C und weiter(A ∪B)r ⊆ Cr = C.

Klarerweise sind∅ und 1r=W regulär. Wir haben mithin gezeigt, daß(L;∩,∨,∅, 1r)ein0, 1-Verband ist.

Dieser ist sogar distributiv. Es seienA,B,C ∈ L:

A ∩ (B ∨C) = Ar ∩ (B ∪ C)r

= (A ∩ (B ∪C))r

= ((A ∩B) ∪ (A ∩C))r

= (A ∩B) ∨ (A ∩ C)

Schließlich zeigen wir, daß für jedesA ∈ L

¬A = (∁A)◦

41

ein Komplement vonA in L ist. Gemäß Lemma 3.3.2 ist somit¬ eine Komple-mentfunktion und(L;∩,∨,¬,∅, 1r) eine boolesche Algebra.

Zunächst ist klar, da߬A als offenes Innere einer abgeschlossenen Menge inLliegt. Weiter gilt

¬A ∩ A = (∁A)◦∩ A

= (∁A)r ∩ Ar

= (∁A ∩ A)r

= ∅

sowie

(¬A ∪ A)− = ((∁A)◦∪ A)

−

= (∁A)◦−

∪A−

= ∁A−◦∪ A−

= ∁A ∪ A−

= 1r

und damit¬A ∨A = (¬A ∪A)r = 1r.

Wie