KAPITEL I Grundbegriffe der Mengenlehre

1. Mengen

An den Anfang der Mathematik stellt man gemeinhin die Mengenlehre. Sie bietet die Sprache an, mit der sich Mathematiker verständigen können, präzise, kurz, exakt, aber für den Außenstehenden auch oft unverständlich. Ihre elementaren Grundbegriffe sind jedoch leicht verständlich. Mit der Sprache der Mengen können alle mathematischen Ergebnisse und Einsichten formuliert werden. Über diese Sprachenfunktion und Hilfsfunktion hinaus ist die Mengenlehre aber auch ein Teilgebiet der Mathematik, in der wesentliche Forschung vor sich geht und besonders tiefliegende Resultate in den letzten Jahrzehnten erzielt worden sind. Wir werden uns lediglich mit den Anfangsgründen der Mengenlehre befassen und dabei die der Mathematik zugrunde liegende Sprache einüben.

Als Grundbegriffe verwendet die Mathematik den Begriff des Elements und den der Menge, die man sich aus Elementen zusammengefügt vorstellt. Elemente können im wesentlichen alles sein, was wir uns vorstellen können. Und ihre Zusammenfassung zu einer Menge scheint eine fast triviale Angelegenheit zu sein. Man kann von der Menge der Hörer einer Vorlesung sprechen, von der Menge aller Elementarteilchen des Universums, von der Menge der Speicherplätze eines Computers, von der Menge aller natürlichen Zahlen, von der Menge aller denkbaren Computerprogramme und von vielen anderen Mengen.

Eine erste Definition des Begriffes einer Menge geht auf Georg Cantor zurück. Er definierte wie folgt:

Definition 1.1. (Georg Cantor, 1845 - 1918; Vater der Mengenlehre): Eine Menge ist eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens – welche Elemente der Menge genannt werden – zu einem Ganzen.

Die Bedeutung dieser Definition für die Mathematik wird durch einen Ausspruch Hilberts unterstrichen.

Zitat 1.2. (David Hilbert, 1862-1943): Niemand soll uns aus dem Paradies der Mengenlehre vertreiben, das Cantor für uns geschaffen hat.

Daß dieser Begriff einer Menge jedoch problematisch ist, sieht man schon daran, daß zu seiner Definition Begriffe herangezogen wurden, deren Definition selbst fehlt: Zusammenfassung zu einem Ganzen, bestimmte Objekte, wohlunterschiedene Objekte, Denken, Anschauung. Tatsächlich wurde zu Beginn unseres Jahrhunderts erkannt, daß dieser Begriff der Menge schnell zu Widersprüchen führen kann. Wir geben einen solchen Widerspruch, die Russelsche Antinomie, am Ende dieses Paragraphen an. Der Ausweg aus diesem Dilemma war eine strenge Fassung der Mengenlehre in einem axiomatischen System, so wie auch die Geometrie axiomatisch gefaßt wurde, und das mit großem Erfolg. Wir werden daher auch eine (nicht ganz strenge) axiomatische Fassung der Mengenlehre angeben. Sie wird uns entscheiden helfen zu sagen, welche Mengen gebildet werden dürfen. Man wird daher nur mit denjenigen Mengen und Elementen operieren dürfen, deren Existenz nach unserer Axiomatik garantiert wird. Wir legen zunächst einige Bezeichnungen fest.

Bezeichnung 1.3. Im allgemeinen werden Mengen mit großen lateinischen Buchstaben A, B, C, …, A_{1}, A_{2}, A_{3}, …, Elemente mit kleinen lateinischen Buchstaben a, b, c, …, a_{1}, a_{2}, a_{3}, … bezeichnet. Die Zugehörigkeit eines Elements x zu einer Menge A wird durch x ∈ A angegeben, die Nicht-Zugehörigkeit durch x ∉ A. Die folgenden Axiome legen elementare Regeln über den Umgang mit Mengen, Elementen und den Zeichen ∈ bzw. ∉ fest. Jede Kollektion von Objekten, die wir Elemente, Mengen, ∈ und ∉ nennen, die den Axiomen genügt, kann als eine Realisierung der Mengenlehre angesehen werden. Wir geben keine konkrete derartige Realisierung an, d.h. wir geben keine exakte Definition von Elementen und Mengen an. Es genügt, sich auf die naive Vorstellung zu stützen, formal in Beweisen jedoch nur die Regeln aus den Axiomen zu verwenden. Die bewiesenen Aussagen sind dann für jede Realisierung (Modell) richtig.

Axiom 1. (Elementebezeichnung und Existenz)

(1) Für jedes Element x und jede Menge A besteht genau eine der beiden Beziehungen (genauer: ist genau einer der beiden Ausdrücke eine wahre, der andere eine falsche Aussage):

x ∈ A; x ∉ A.

Im Falle x ∈ A (d.h. wenn x ∈ A wahr ist) sagen wir ”x ist Element der Menge A“, ”x liegt in A“, ”x ist in A enthalten“, ”x in A“ oder ”x aus A“. Im Falle x ∉ A (d.h. wenn x ∈ A falsch ist) sagen wir ”x ist nicht Element der Menge A“.

(2) Es gibt mindestens eine Menge.

(3) Zu jedem Element x gibt es mindestens eine Menge A mit x ∈ A (ist wahr).

Wir werden bei der Formulierung des nächsten Axioms gewisse Symbole verwenden, die den mathematischen Text abkürzen sollen. Schon im vorhergehenden Axiom haben wir bestimmte mathematische Formulierungen verwendet, die sich häufig wiederholen werden. Wir werden zunächst folgende Abkürzungen verwenden:

für alle  ∀
es gibt  ∃
und  ∧
oder  ∨
dann und nur dann, wenn  ⟺
daraus folgt  ⟹
gilt nur, wenn  ⟸

Im Klartext verwenden wir als Synonyme

für alle  für jedes
es gibt  es existiert
dann und nur dann, wenn ist notwendig und hinreichend
dann und nur dann, wenn gilt genau dann, wenn
daraus folgt  impliziert
daraus folgt  ist hinreichend für
gilt nur, wenn  ist notwendig für

Es bedarf immer einiger Gewöhnung, bis man den Umgang mit diesen Zeichen, Symbolen und Begriffen eingeübt hat und sich ein korrektes logisches Schließen angewöhnt hat. Wenn wir die Zeichen ∀ oder ∃ verwenden, dann werden unmittelbar danach immer die Elemente genannt werden, über die wir etwas aussagen wollen. Die Aussage, die wir dann über diese Elemente machen, wird in Klammern [ und ] angegeben^{1}.

1Man kann eine präzise Syntax für die Verwendung (und Umformung)

dieser Zeichen und der Mengensymbole ineinander angeben. Dann kann die Mathematik in großen Teilen lediglich als Manipulation solcher Zeichenreihen durchgeführt werden. Mehr dazu im Kapitel über Logik.

Axiom 2. (Axiom der Gleichheit oder Extensionsaxiom) Seien A, B Mengen. Wenn für alle Elemente x die Aussage x ∈ A genau dann gilt, wenn x ∈ B gilt, so folgt A = B. In mathematischer Kurzschreibweise:

∀x[x ∈ A ⟺ x ∈ B] ⟹ A = B.

Der umgekehrte Schluß A = B ⟹ ∀x[x ∈ A ⟺ x = B] folgt aus den Eigenschaften der Gleichheit. Wenn nämlich A und B gleich sind, dann darf man an jeder Stelle, wo A verwendet wird, dieses durch B ersetzen, ohne die logische Bedeutung zu ändern.

Das Axiom 2 bedeutet, daß zwei Mengen genau dann gleich sind, wenn sie dieselben Elemente besitzen. Damit ist klargestellt, daß eine Menge allein durch die Angabe ihrer Elemente beschrieben wird und keine zusätzliche Information besitzen soll. Wenn man sich den Begriff der Menge als ”Behälter“ für ihre Elemente vorstellt, dann gibt es keine verschiedenen ”Behälter“. Man sammelt Elemente grundsätzlich in gleicher Weise. Um festzustellen, ob zwei Mengen gleich sind, genügt es daher, nur alle ihre Elemente zu überprüfen. Das wird in Zukunft häufig so geschehen, daß man zunächst zeigt, daß alle Elemente einer Menge A auch Elemente einer weiteren Menge B und weiter daß alle Elemente der Menge B auch Elemente der Menge A sind. Wenn man das bewiesen hat, kann man dann wegen Axiom 2 unmittelbar A = B folgern.

Damit haben wir schon einen weiteren elementaren Begriff angesprochen. Es kommt oft vor, daß alle Elemente einer Menge A auch Elemente einer Menge B sind. Wir definieren daher wie folgt:

Definition 1.4. (1) Die Menge A heißt eine Teilmenge oder Untermenge der Menge B (Kurzbezeichnung: A ⊂ B) genau dann, wenn jedes Element von A auch Element von B ist:

A ⊂ B :⟺ ∀x[x ∈ A ⟹ x ∈ B]^{2}.

(2) Ist A nicht Teilmenge von B, so wird A ⊄ B geschrieben.

(3) A heißt eine echte Teilmenge von B (Kurzbezeichnung: A ⫋ B), wenn A ⊂ B ∧ (und) A ≠ B gelten.

Bemerkung: Das Zeichen ⊂ heißt Inklusion und wird gelesen ”ist Teilmenge von“. Es ist

A ⊂ B ⟺ ∀x[x ∈ A ⟹ x ∈ B]
⟺ ∀x ∈ A[x ∈ B].
A ⫋ B ⟺ A ⊂ B ∧ ∃x ∈ B[x ∉ A]
⟺ ∀x ∈ A[x ∈ B] ∧ ∃x ∈ B[x ∉ A].

Folgerung 1.5. Die folgenden Gesetze gelten für die Inklusion von Mengen A, B und C:

(1) Reflexivität: A ⊂ A.

(2) Transitivität: A ⊂ B ∧ B ⊂ C ⟹ A ⊂ C.

(3) Antisymmetrie: A ⊂ B ∧ B ⊂ A ⟹ A = B.

Beweis. Wir geben diesen leichten Beweis ausschließlich in mathematischer Kurzschreibweise an. Der Leser mag sich an dieser Stelle in das Lesen dieser Kürzelsprache einarbeiten.

(1) ∀x[x ∈ A ⟹ x ∈ A] ⟹ A ⊂ A.

(2) A ⊂ B ∧ B ⊂ C ⟹ ∀x[x ∈ A ⟹ x ∈ B] ∧ ∀x[x ∈ B ⟹ x ∈ C] ⟹ ∀x[(x ∈ A ⟹ x ∈ B) ∧ (x ∈ B ⟹ x ∈ C)] ⟹ ∀x[x ∈ A ⟹ x ∈ C] ⟹ A ⊂ C.

(3) A ⊂ B ∧ B ⊂ A ⟹ ∀x[x ∈ A ⟹ x ∈ B] ∧ ∀x[x ∈ B ⟹ x ∈ A] ⟹ ∀x[(x ∈ A ⟹ x ∈ B) ∧ (x ∈ B ⟹ x ∈ A)] ⟹ ∀x[x ∈ A ⟺ x ∈ B] ⟹ A = B.

2Das Zeichen :⟺ soll bedeuten, daß die linke Aussage durch die rechte Aussage definiert wird, d.h. daß sie durch Definition äquivalent zur rechten Aussage ist.

Bemerkung 1.6. (Notation und Schreibweise von Mengen) Sind a_{1}, a_{2}, …, a_{t} genau alle Elemente einer Menge A, so schreibt man A = {a_{1}, a_{2}, …, a_{t}}. Die Zeichen { und } heißen dabei Mengenklammern. Dann gelten {1, 2} = {2, 1} und {1, 2} = {2, 1, 2, 1, 1}, weil jeweils beide Mengen dieselben Elemente haben (vgl. jedoch Kapitel I.3 über Multimengen).

Allerdings wissen wir noch nicht, ob diese Mengen überhaupt existieren. Aus dem Axiom 1 können wir nur entnehmen, daß es mindestens eine Menge gibt. Mengen, wie die eben beschriebenen, werden wir erst bilden dürfen, wenn wir das Axiom 5 zur Verfügung haben werden. Wir können also die angegebenen Mengen zunächst nur mit Vorbehalt hinschreiben. Wir tun dies, um dem Leser schon jetzt Beispiele an die Hand zu geben, an denen er sich die Begriffe klar machen kann. Noch komplizierter ist die Situation bei den Zahlenmengen, die wir auch gleich angeben werden. Ihre Existenz wird erst durch das Unendlichkeitsaxiom 6 (in Kapitel II.1) gesichert werden. Dennoch wollen wir diese Zahlenmengen als veranschaulichende Beispiele auch hier schon heranziehen.

Es gelten folgende Elementbeziehungen:

5 ∈ {1, 2, 3, 5, 7},
XZ ∈ {UY, UZ, XY, XZ, ZY, ZZ},
6 ∉ {1, 2, 3}.

Wir verwenden in den folgenden Beispielen Mengen, die allgemein bekannt sind, deren genaue Definition, Konstruktion bzw. Existenz wir erst später diskutieren werden. Die natürlichen Zahlen bilden die Menge ℕ = {1, 2, 3, 4, … } nach Axiom 6. Wir verwenden weiter als Bezeichnung ℤ = {0, 1, −1, 2, −2, … } = Menge der ganzen Zahlen, ℚ = Menge der rationalen Zahlen, ℝ = Menge der reellen Zahlen, ℂ = Menge der komplexen Zahlen.

Für eine Menge A ist {A} eine neue Menge mit genau einem Element A, also gilt A ∈ {A}. Mengen können also auch als Elemente von anderen Mengen auftreten. Es ist {1, 2} ∈ {{1, 2}}, 1 ∉ {{1, 2}} und 1 ∈ {1, 2}. Es gilt nicht {1, 2} ⊂ {{1, 2}}. Wir bemerken nochmals, daß die Existenz der oben angegebenen Mengen noch nicht gesichert ist.

Ein wichtiges Prinzip zur Bildung von Mengen ist die Konstruktion von Teilmengen. Wenn man die Elemente einer gegebenen Menge A auf bestimmte Eigenschaften hin untersucht, natürliche Zahlen z.B. darauf hin, ob sie gerade sind oder nicht, so möchte man diejenigen Elemente, die die gegebene Eigenschaft besitzen, zu einer neuen Menge B zusammenfassen. Diese wird natürlich eine Teilmenge von A sein. Eine Eigenschaft für Elemente wird häufig auch ein Prädikat oder eine Aussage genannt. Es muß für die betrachteten Elemente feststehen, ob sie die Eigenschaft besitzen, bzw. ob sie die Aussage erfüllen.

Axiom 3. (Teilmengenaxiom oder Prinzip der Abstraktion) Sei B eine Menge und 𝔄(x) ein Prädikat für Elemente x (d.h. eine Aussage für Elemente x, für die bei fester Wahl von x feststeht, ob sie wahr oder falsch ist). Dann gibt es eine Teilmenge A von B, die genau die Elemente b ∈ B enthält, für die 𝔄(b) wahr ist. Für A wird

A = {b|b ∈ B ∧ 𝔄(b)} = {b ∈ B|𝔄(b)}

geschrieben.

Bemerkung 1.7. Beispiele für Teilmengen sind {x ∈ ℕ|x gerade} = Menge der geraden natürlichen Zahlen, {x|x ∈ ℕ ∧ x < 10} = {1, 2, 3, …, 9}, {x|x ∈ ℕ ∧ x ist Primzahl} = Menge der Primzahlen, {x|x ∈ ℝ ∧ 1 ≤ x ≤ 2} = [1, 2] abgeschlossenes Intervall, {x|x ∈ ℝ ∧ 1 < x < 2} = (1, 2) offenes Intervall. Seien b_{1}, …, b_{n} ∈ B. Dann ist

{b_{1}, …, b_{n}} := {x|x ∈ B ∧ (x = b_{1} ∨ x = b_{2} ∨ … ∨ x = b_{n})}^{3}

eine Teilmenge von B. Für b ∈ B ist {b} ⊂ B. Eine weitere Teilmenge von B ist

∅ := {x|x ∈ B ∧ x ∉ B}.

Sie heißt leere Menge. Es gibt genau eine leere Menge. Diese ist Untermenge jeder Menge B (wegen Axiom 2 und Axiom 3). Nach Axiom 1 ist bisher allein die Existenz von ∅ sichergestellt. Für b ∈ B ist {b} ⊂ B. Die Mengenbildung {x|1 ≤ x ≤ 5} ist nicht sinnvoll, weil nicht klar ist, aus welcher Grundmenge U die Elemente zu wählen sind. Wir halten daher oft eine solche Grundmenge U, genannt Universum, fest, aus der alle betrachteten Elemente stammen sollen. Ist also U = {1, 3, 5, 7, 9, … } = Menge der ungeraden Zahlen, so ist {x|1 ≤ x ≤ 5} = {1, 3, 5}. Für U = ℝ ist {x|1 ≤ x ≤ 5} = [1, 5] (abgeschlossenes Intervall von 1 bis 5).

Definition 1.8. Seien A, B Mengen.

(1) Der Durchschnitt von A und B ist die Teilmenge derjenigen Elemente aus A, die auch in B liegen:

A ∩ B : = {x ∈ A|x ∈ B} = {x|x ∈ A ∧ x ∈ B}
= {x ∈ B|x ∈ A}.

(2) Die Komplementärmenge von B in A ist die Teilmenge der Elemente aus A die nicht in B liegen (”A ohne B“): A \ B := {x ∈ A|x ∉ B}.

(3) Zwei Mengen A, B heißen disjunkt oder fremd, wenn A ∩ B = ∅.

(4) Die Komplementärmenge von B im Universum U wird mit \overline{B} bezeichnet.

3Mit dem Zeichen := wird das linke Symbol durch die rechte Seite definiert.

An dieser Stelle sollte angemerkt werden, daß die Zeichen = und ⇔ gänzlich unterschiedliche Bedeutung haben. Wenn wir jetzt von Elementen und Mengen als mathematischen Objekten sprechen, so steht fest, ob zwei beliebig vorgegebene Objekte gleich sind oder nicht. Das Gleichheitszeichen ist damit zwischen Elementen bzw. Mengen definiert. Mehr noch, wir können sogar einen Test angeben, mit dem man feststellen (auf eine einfachere Frage zurückführen) kann, ob zwei Mengen gleich sind, nämlich den im Axiom der Gleichheit (Axiom 2) angegebenen Test. So sind z. B. die folgenden Mengen gleich:

\begin{aligned}\{1, 2, 3\} & = \{x|x ∈ ℕ ∧ x < 4\} \\ & = \{x|x ∈ ℕ ∧ ∃y ∈ \{1, 2, 3\}[x = 4 − y]\}. \end{aligned}

Die Mengenlehre basiert jedoch auf dem Umgang mit logischen Sätzen, sogenannten Aussagen, über die feststeht, ob sie wahr oder falsch sind. Verschiedene solche Aussagen können logisch äquivalent sein, d.h. von zwei logischen Aussagen P und Q ist P genau dann wahr, wenn Q wahr ist. Wir schreiben dann P ⇔ Q. Solche logisch äquivalenten Aussagen kommen in der Praxis verhältnismäßig selten in der Mathematik jedoch sehr häufig vor. Ein Beispiel ist:

”n ist die kleinste Primzahl.“ ⇔ ”n ist die kleinste gerade

natürliche Zahl.“

Das Gleichheitszeichen kann also nur zwischen Elementen bzw. Mengen stehen, die doppelte Implikation nur zwischen logischen Aussagen. Insbesondere beachte man, daß A ∩ B eine Menge ist, während A ⊂ B eine Aussage ist. Wir bemerken auch noch, daß sowohl P ⇔ Q als auch A = B Aussagen sind, d. h. daß bei beiden Ausdrücken der Wahrheitsgehalt festgesteht.

Wir geben in der nächsten Folgerung eine Reihe von Regeln für das Rechnen mit Mengen an. Viele der Rechenregeln sind unmittelbar klar, andere benötigen einen etwas ausführlicheren Beweis. Wir verzichten hier auf Beweise dieser Aussagen, da wir sie zum Teil auch später in allgemeinerer Form in Kapitel I.3 wieder finden werden. Lediglich eine Aussage beweisen wir, damit der Leser sieht, wie er solche Beweise führen sollte.

Folgerung 1.9. (Rechenregeln der Mengenalgebra)

(1) A ∩ B = B ∩ A, (Kommutativgesetz)

(2) (A ∩ B) ∩ C = A ∩ (B ∩ C), (Assoziativgesetz)

(3) A ∩ A = A, (Idempotenzgesetz)

(4) A ∩ B ⊂ A, A ∩ B ⊂ B.

(5) Gilt für eine Menge C: C ⊂ A ∧ C ⊂ B, dann folgt C ⊂ A ∩ B.

(6) A \ B = A \ (A ∩ B),

(7) A \ (A \ B) = A ∩ B,

(8) A \ ∅ = A, A \ A = ∅,

(9) (A \ B) ⊂ A,

Beweis. Die meisten Beweisschritte sind unmittelbar einsichtig. Als Muster beweisen wir den ersten Teil von (8): Wegen 1.5 (3) ist A \ ∅ ⊂ A und A ⊂ A \ ∅ zu zeigen. A \ ∅ ⊂ A gilt wegen 1.8 (2). Für A ⊂ A \ ∅ haben wir nach Definition zu zeigen: ∀x[x ∈ A ⟹ x ∈ A \ ∅]. Sei a ∈ A. Dann ist a ∈ A und a ∉ ∅ (Eigenschaft der leeren Menge), also a ∈ {x ∈ A|x ∉ ∅} = A \ ∅. Also gilt ∀x[x ∈ A ⟹ x ∈ A \ ∅] und damit ist A ⊂ A \ ∅ gezeigt. Also gilt A \ ∅ = A.

In der folgenden Definition verwenden wir eine typische Schlußweise der Mengenlehre. Wenn eine Menge M nicht leer ist, dann muß sie ja mindestens ein Element enthalten. Wir können also ein (ansonsten beliebiges) Element a_{0} aus dieser Menge M finden und damit weitere Untersuchungen durchführen.

Definition 1.10. Sei 𝔐 eine Menge, deren Elemente selbst Mengen sind, und sei 𝔐 ≠ ∅. Sei A_{0} ∈ 𝔐. Dann ist der Durchschnitt der Mengen aus 𝔐 definiert als

⋂{A|A ∈ 𝔐} : = {a|a ∈ A_{0} ∧ ∀A ∈ 𝔐[a ∈ A]}
= {a|∀A ∈ 𝔐[a ∈ A]}.

Die erste Gleichung zeigt, daß ⋂{A|A ∈ 𝔐} als Teilmenge von A_{0} existiert. Dann kann ⋂{A|A ∈ 𝔐} aber durch die zweite Gleichung beschrieben werden und ist daher von der Wahl von A_{0} unabhängig.

Der Leser möge sich klarmachen, daß für Durchschnitte die folgende Folgerung gilt.

Folgerung 1.11. Sei B eine Menge. Es gilt ∀A ∈ 𝔐[B ⊂ A] genau dann, wenn B ⊂ ⋂{A|A ∈ 𝔐}. Weiter ist der Durchschnitt ⋂{A|A ∈ 𝔐} die größte Menge X mit der Eigenschaft: ∀A ∈ 𝔐[X ⊂ A].

Axiom 4. (Vereinigungsmengenaxiom)

(1) Sind A und B zwei Mengen, dann gibt es eine Menge, Vereinigungsmenge von A und B genannt und mit A ∪ B bezeichnet, die genau die Elemente enthält, die in A oder B enthalten sind:

A ∪ B = {x|x ∈ A ∨ x ∈ B}.

(2) Sei 𝔐 eine Menge, deren Elemente selbst Mengen sind. Dann gibt es eine Menge, Vereinigungsmenge genannt und mit ⋃{A|A ∈ 𝔐} bezeichnet, die genau die Elemente enthält, die in mindestens einem A ∈ 𝔐 liegen:

⋃{A|A ∈ 𝔐} = {x|∃A ∈ 𝔐[x ∈ A]}.

Bemerkung: (1) folgt nicht aus (2), weil wir nicht wissen, ob es eine Menge {A, B} gibt. Es ist ⋃{A|A ∈ ∅} = ∅, denn mit 𝔐 = ∅ ist {x|∃A ∈ 𝔐[x ∈ A]} = ∅: wäre diese Menge nicht leer, so gäbe es ein x in ihr, also wäre x ∈ A für ein A ∈ 𝔐, also wäre 𝔐 ≠ ∅. Das ist ein Widerspruch!

Wir geben jetzt eine Reihe weiterer wichtiger Regeln für das Rechnen mit Mengen an. Auch hier verzichten wir auf ausführliche Beweise, verweisen dazu aber auf Kapitel I.3.

Folgerung 1.12. (Weitere Rechenregeln der Mengenalgebra) Seien A, B, C Mengen und U ein Universum. Dann gelten

(1) A ∪ B = B ∪ A, (Kommutativgesetz)

(2) (A ∪ B) ∪ C = A ∪ (B ∪ C), (Assoziativgesetz)

(3) A ∪ A = A, (Idempotenzgesetz)

(4) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), (Distributivgesetze) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),

(5) A\(B ∩C) = (A\B)∪(A\C), (de Morgansche Gesetze) A \ (B ∪ C) = (A \ B) ∩ (A \ C), \overline{(B ∩ C)} = \overline{B} ∪ \overline{C}, \overline{(B ∪ C)} = \overline{B} ∩ \overline{C},

(6) \overline{\overline{A}} = A, (Gesetz vom doppelten Komplement)

(7) A ∪ ∅ = A, A ∩ U = A, (Gesetz von der Identität)

(8) A ∪ \overline{A} = U, A ∩ \overline{A} = ∅, (Gesetz vom Inversen)

(9) A ∪ U = U, A ∩ ∅ = ∅, (Dominierungsgesetz)

(10) A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A, (Absorptionsgesetz).

(11) (A \ B) ∪ B = A ∪ B.

Definition 1.13. Seien A, B Mengen. Die symmetrische Differenz von A und B ist die Menge

AΔB := {x ∈ A ∪ B)|x ∉ A ∩ B} = (A ∪ B) \ (A ∩ B).

Folgerung 1.14. (Weitere Rechenregeln der Mengenalgebra) (1) AΔB = (A \ B) ∪ (B \ A),

(2) AΔB = BΔA,

(3) AΔ(BΔC) = (AΔB)ΔC,

(4) AΔA = ∅,

(5) AΔ∅ = A.

Bemerkung 1.15. (Venn Diagramme) Man stellt sich Mengen oft als Teilmengen der Ebene, eingegrenzt durch Kurven, vor. Diese Vorstellung hilft Beweise für die genannten Rechenregeln zu finden. Sie ersetzt aber nicht einen exakten Beweis.

Einzelne Menge:

A = [figure: A]

Durchschnitt:

A ∩ B = [figure: A] [figure: B]

Vereinigung:

A ∪ B = [figure: A] [figure: B]

Komplement:

A \ B = [figure: A; B]

Symmetrische Differenz:

AΔB = [figure: A; B]

\overline{(A ∪ B) ∩ C} = (\overline{A} ∩ \overline{B}) ∪ \overline{C} :

[figure: A; B; C; 1; 2; 3; 4; 5; 6; 7; 8]

führt zu folgendem Beweis:

A ∪ B = 2 ∪ 3 ∪ 5 ∪ 6 ∪ 7, C = 4 ∪ 6 ∪ 7 ∪ 8, (A ∪ B) ∩ C = 6 ∪ 7 ∪ 8, ⟹ \overline{(A ∪ B) ∩ C} = 1 ∪ 2 ∪ 3 ∪ 4 ∪ 5. \overline{A} = 1 ∪ 3 ∪ 4 ∪ 6, \overline{B} = 1 ∪ 2 ∪ 4 ∪ 7, \overline{A} ∩ \overline{B} = 1 ∪ 4, \overline{C} = 1 ∪ 2 ∪ 3 ∪ 5 ⟹ (\overline{A} ∩ \overline{B}) ∪ \overline{C} = 1 ∪ 2 ∪ 3 ∪ 4 ∪ 5.

Bemerkung 1.16. (Mengen im Computer) Im Computer werden Mengen von Zahlen oder Daten gespeichert, z.B. die Adressdaten von Geschäftspartnern, die statistisch verteilten Werte von wiederholten Strahlungsmessungen, die Buchstaben des Alphabets, die natürlichen Zahlen.

Sie werden dann als Menge im obigen Sinn aufgefaßt werden müssen, wenn mengentheoretische Operationen vorkommen, z.B. {Buchstaben des Alphabets} ∪{ Ziffern 0, …, 9}.

Es bieten sich grundsätzlich zwei verschiedene Arten an, wie man Mengen im Computer realisieren und speichern kann. Einmal kann man alle Elemente einer Menge einzeln abspeichern. Aufgrund der Endlichkeit des Speichers kann man so natürlich nur verhältnismäßig kleine Menge erfassen, wie das Alphabet, die Einträge eines Lexikons oder die Daten einer statistischen Erhebung, zum Beispiel einer Volkszählung. Durch die Speicherung aller Elemente einer Menge sind auch wiederholte Einträge desselben Elements möglich, die Ordnung des Speichers bedingt auch eine Ordnung der Elemente der Menge. Es entsteht eine geordnete Liste, deren Definition und Struktur wir später untersuchen.

Ist die Datenmenge jedoch zu groß, gar unendlich, wie z.B. ℕ oder 2ℕ, so muß das Bildungsgesetz selbst abgespeichert werden. Die natürlichen Zahlen betrachtet man als die Menge, die 1 enthält und durch fortlaufendes Addieren von 1 zu immer neuen Zahlen kommt, die geraden Zahlen entstehen aus 2 und den Zahlen, die man durch fortlaufendes Addieren von 2 erhält. Man hat damit zwar nicht alle Elemente ”gleichzeitig“ im Computer zur Verfügung, kann aber im Beispiel der natürlichen Zahlen jede einzelne beliebig gewählte natürliche Zahl nach endlicher Rechenzeit erhalten und zum Beispiel auf dem Drucker ausdrucken. Auf diese Weise kann man auch noch sogenannte abzählbare Mengen elementweise beherrschen. Schliesslich kann man statt der Angabe eines Bildungsgetzes und damit der Konstruktionsmöglichkeit jedes einzelnen Elements viel größere Mengen dadurch beherrschen, daß man lediglich einen Algorithmus angibt, der von einem vorgegebenen Element feststellt, ob es der definierten Menge angehört. Diese Darstellung von Mengen fällt jedoch schon unter die Möglichkeiten, Teilmengen (des Universums ”aller Elemente“) darzustellen.

Die Menge 2ℕ erhält man auch als {t ∈ ℕ|∃s ∈ ℕ[2s = t]}. Diese endliche Zeichenfolge kann gespeichert werden. Häufig stellt man sich also auf den Standpunkt, daß ein Universum als Grundmenge gegeben ist, beschrieben etwa durch den Aufbau der verwendeten Elemente (z.B. alle Worte, die man mit Buchstaben und Ziffern – alphanumerisch – schreiben kann), und beschreibt die interessierenden Teilmengen A von U durch ein Prädikat 𝔄(x), also A = {x|𝔄(x)} = {x ∈ U|𝔄(x)}, durch das festgestellt werden kann, ob ein gegebenes Element der Teilmenge angehört. 𝔄(x) ist dann ein Algorithmus, der für ein gegebenes Element x einen Wert wahr (x ∈ A) oder falsch (x ∉ A) ausgibt.

Für endliche elementweise im Computer gespeicherte Mengen U gibt es noch ein weiteres häufig verwendetes Verfahren, um Teilmengen A ⊂ U zu definieren. Man stellt einen weiteren Speicher zur Verfügung mit ebenso vielen Bits Speicherraum, wie die Grundmenge Elemente hat. Jedem Element x von U steht damit also sein eigener zusätzlicher Speicher von 1 Bit Länge zur Verfügung. Um jetzt eine Teilmenge A zu bilden, schreibt man für diejenigen Elemente x ∈ U, die in A liegen, eine 1 in den zu x gehörigen Speicher. Für die Elemente x ∈ U mit x ∉ A schreibt man eine 0 in den zugehörigen Speicher. Man hat damit eigentlich eine Funktion χ_{A} : U ⟶ {0, 1} definiert mit

χ_{A}(x) = \begin{cases}1, & für x ∈ A, \\ 0, & für x ∉ A. \end{cases}

Dadurch ist die Teilmenge A aber offensichtlich vollständig bestimmt. Die Funktion χ_{A} nennt man auch charakteristische Funktion von A (vgl. auch Kapitel I.3).

Zum Beispiel kann man bei der Beschreibung von Farbmischungen aus den 3 Farben U := {blau, grün, rot} insgesamt 2^{3} = 8 verschiedene Teilmengen finden. Die Teilmenge {blau, rot} wird dabei dann durch die Bitfolge 101 definiert.

Bemerkung 1.17. (Mengenoperationen im Computer)

(1) Der Fall endlicher Mengen: Sind zwei endliche Mengen A und B als geordnete Listen gegeben, so kann man A ∪ B darstellen durch Bildung einer neuen Liste, in die alle Elemente aus A und B aufgenommen werden, im einfachsten Fall durch ein Aneinanderhängen der Listen, oder dadurch, daß man sich merkt, daß die Elemente aus A ∪ B solche sind, die in A oder in B liegen, beide Mengen also zur Wahl eines Elements zuläßt. Der Durchschnitt A ∩ B ist für die Bildung einer neuen Gesamtmenge schwieriger, weil man hier tatsächlich eine neue Liste konstruieren muß, zum Beispiel nach dem Verfahren, alle Elemente aus A zu durchlaufen (das sind nur endlich viele!) und zu untersuchen, ob sie in B liegen, und die dabei gefundenen Elemente in eine neue Liste aufzunehmen. Aber auch hier kann man stattdessen die abstrakte Beschreibung des Durchschnitt verwenden, also nur solche Elemente, die man sowohl in A als auch in B vorfindet (in A und in B). Ähnliche Überlegungen gelten für das Komplement A \ B und die symmetrische Differenz AΔB. Wenn man Teilmengen A und B eines Universums U betrachtet und diese durch Bitfolgen, d.h. durch ihre charakteristischen Funktionen χ_{A} bzw. χ_{B} darstellt, so ist die Vereinigung einfach durch die charakteristische Funktion

χ_{A∪B}(x) = max(χ_{A}(x), χ_{B}(x))

oder durch die OR Operation auf den Bitfolgen zu erhalten. Ähnlich erhält man den Durchschnitt durch

χ_{A∩B}(x) = min(χ_{A}(x), χ_{B}(x))

oder durch die AND Operation auf den Bitfolgen (vgl. hierzu Kapitel I.3).

(2) Der Fall großer und unendlicher Mengen gestattet nicht mehr eine elementweise Aufbereitung der neuen Menge A ∪ B, A ∩ B, A \ B bzw. AΔB, allein schon weil die Ausgangsmengen A und B nicht elementweise, sondern durch ein Prädikat gegeben sind. Von den neuen Mengen sind also wieder die entsprechenden Prädikate zu bilden. Dazu verwenden wir die logischen Zeichen ∨ (oder), ∧ (und) und ¬ (nicht). Wir legen außerdem ein Universum U zugrunde, in dem sich alles abspielt. Seien die Mengen A = {x ∈ U|𝔄(x)} und B = {x ∈ U|𝔅(x)} gegeben. Dann gelten

A ∪ B  = {x ∈ U|𝔄(x) ∨ 𝔅(x)},
A ∩ B  = {x ∈ U|𝔄(x) ∧ 𝔅(x)},
A \ B  = {x ∈ U|𝔄(x) ∧ ¬𝔅(x)},
AΔB = {x ∈ U|(𝔄(x) ∨ 𝔅(x)) ∧ ¬(𝔄(x) ∧ 𝔅(x))}.

Das Rechnen mit Mengenoperationen kann also übersetzt werden in ein Rechnen mit Prädikaten. Die Vereinigung entspricht dabei dem logischen OR, der Durchschnitt dem logischen AND. Die Komplementärmenge kann mit den logischen Operationen AND NOT erhalten werden und die symmetrische Differenz mit ( OR ) AND NOT ( AND ). Mit diesen Zusammenhängen werden wir uns später noch genauer beschäftigen, vor allem bei der Untersuchung von Strukturen in der Logik. Bis dahin fassen wir die logischen Operationen und Aussagen in ihrer ursprünglichen, naiven Bedeutung auf.

Axiom 5. (Potenzmengenaxiom) Zu jeder Menge A gibt es eine Menge, Potenzmenge von A genannt und mit P(A) bezeichnet, die genau alle Teilmengen von A als Elemente enthält. Diese wird auch mit

P(A) = {B|B ⊂ A}

bezeichnet.

Beispiele 1.18. P(∅) = {∅} ist eine Menge mit einem Element. P({a}) = {∅, {a}} ist eine Menge mit zwei Elementen. P({a, b}) = {∅, {a}, {b}, {a, b}} ist eine Menge mit vier Elementen.

Folgerung 1.19. (Rechenregeln)

(1) P(A) ∩ P(B) = P(A ∩ B),

(2) P(A) ∪ P(B) ⊂ P(A ∪ B),

(3) A ⊂ B ⟹ P(A) ⊂ P(B),

(4) ⋂{B|B ∈ P(A)} = ∅, ⋃{B|B ∈ P(A)} = A.

Jetzt sind wir endlich soweit, daß wir die Existenz von gewissen interessanten Mengen beweisen können, die wir früher schon in Beispielen betrachtet haben, ohne zu wissen, ob sie existieren.

Folgerung 1.20. Seien a_{1}, …, a_{n} Elemente. Dann gibt es eine Menge {a_{1}, …, a_{n}}. Seien A_{1}, …, A_{n} Mengen. Dann gibt es eine Menge {A_{1}, …, A_{n}}.

Beweis. Nach Axiom 1 (3) gibt es zu jedem Element a_{i} eine Menge A_{i} mit a_{i} ∈ A_{i}. Nach Axiom 4 (1) kann man die Mengen B_{1} := A_{1}, B_{2} := B_{1} ∪ A_{2}, B_{3} := B_{2} ∪ A_{3}, …, B_{n} := B_{n−1} ∪ A_{n} bilden, also B_{n} = (… ((A_{1}∪A_{2})∪A_{3})∪… A_{n−1})∪A_{n} = A_{1}∪A_{2}∪ A_{3} ∪ … ∪ A_{n−1} ∪ A_{n} (nach 1.12 (2)). Damit gilt a_{1} ∈ B_{n}, a_{2} ∈ B_{n}, …, a_{n} ∈ B_{n}. Dann ist {a_{1}, a_{2}, …, a_{n}} := {x ∈ B_{n}|x = a_{1} ∨ x = a_{2} ∨ … x = a_{n}} nach Axiom 3 eine Menge.

Die Mengen A_{1}, A_{2}, …, A_{n} sind selbst Elemente, denn es gilt A_{i} ∈ P(A_{i}). Dann kann die erste Aussage dieser Folgerung verwendet werden, um die Existenz der Menge {A_{1}, …, A_{n}} zu erhalten.

Wir beenden diesen Paragraphen mit der berühmten Russelschen Antinomie. In der naiven Mengenlehre, die versucht, auf der Mengendefinition von Georg Cantor aufzubauen, kann man die Menge aller Mengen ebenfalls bilden. Russel hat dann gezeigt, daß dieser Begriff einen Widerspruch in sich trägt. In einem axiomatischen Aufbau, wie wir ihn hier betrachten, löst sich dieser Widerspruch in der Aussage, daß es nicht die Menge aller Mengen geben kann. Dieser Beweis der Nicht-Existenz einer bestimmten Menge wird in ähnlicher Form in der Informatik dazu verwendet, zu zeigen, daß es gewisse Programme, die bestimmte Forderungen erfüllen sollen, nicht geben kann, etwa Programme, die von beliebigen vorgegebenen Programmen mit zugehörigen Dateneingaben feststellen können, ob sie abbrechen oder nicht.

Bemerkung 1.21 (Das Russelsche Paradoxon). Die Menge aller Mengen existiert nicht. Wenn es nämlich eine Menge Ω = {A|A ist eine Menge} aller Mengen gäbe, dann wäre auch X := {A ∈ Ω|A ∉ A} eine Menge und ebenso Y := Ω \ X = {A ∈ Ω|A ∈ A}. Wäre nun X ∈ X, so folgte nach der Definition von Y daraus X ∈ Y. Da weiter Y = Ω \ X gilt, kann X nicht Element von X sein; es gilt also X ∉ X. Wäre umgekehrt X ∉ X, so folgte daraus X ∈ X nach der Definition von X. In beiden Fällen haben wir einen Widerspruch zu Axiom 1 erhalten. Deshalb kann X nicht existieren und damit auch nicht Ω.

2. Relationen und Abbildungen

Wir beginnen mit einer Vorbemerkung zum naiven Begriff eines Paares. Seien a und b zwei nicht notwendig verschiedene Elemente. Ein Paar (a, b) hat zwei Elemente, eines, a, an erster Stelle, und ein weiteres, b, an zweiter Stelle. Dabei dürfen a und b auch gleich sein. Zwei Paare werden als gleich angesehen: (a, b) = (x, y) genau dann, wenn a = x und b = y gelten. Häufig spricht man auch von einem geordneten Paar (im Unterschied zu einer Menge {a, b} mit einem (a = b) oder zwei (a ≠ b) Elementen). Es gilt für a ≠ b zwar {a, b} = {b, a}, aber (a, b) ≠ (b, a). Die exakte mengentheoretische Erfassung dieses Begriffs gibt die

Definition 2.1. Seien a und b zwei nicht notwendig verschiedene Elemente. Dann wird das (geordnete) Paar (a, b) definiert durch

(a, b) := {{a}, {a, b}}.

a heißt erstes Element des Paares (a, b), b heißt zweites Element des Paares (a, b).

Bemerkung: Diese Menge existiert nach 1.20.

Der Wert dieser recht unanschaulichen Definition liegt darin, daß man den Begriff eines Paares so mit Hilfmitteln der Mengenlehre ausdrücken kann und das folgende fundamentale Lemma beweisen kann.

Lemma 2.2. (a, b) = (c, d) ⟺ a = c ∧ b = d.

Beweis. ”⟸“: Folgt aus der Eigenschaft der Gleichheit, da man in einem Ausdruck gleiche Elemente a = c bzw b = d ersetzen darf und dabei der Ausdruck gleich bleibt. ”⟹“: Wir unterscheiden zwei Fälle:

1. Fall: a = b. Dann ist (a, b) = (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. Wegen {{c}, {c, d}} = (c, d) = (a, b) = {{a}} folgt {c} = {a} und {c, d} = {a}, also c = a und d = a = b.

2. Fall: a ≠ b. Dann hat {a, b} genau zwei Elemente. Wegen {{a}, {a, b}} = (a, b) = (c, d) = {{c}, {c, d}} folgt daher {a, b} ∈ {{c}, {c, d}}, also muß {a, b} = {c, d} gelten (denn {a, b} = {c} würde a = c = b implizieren, was nach Voraussetzung nicht möglich ist). Damit ist auch c ≠ d. Dann folgt {a} = {c} und a = c. Aus {a, b} = {c, d} folgt dann b = d.

Definition und Lemma 2.3. Zu je zwei (nicht notwendig verschiedenen) Mengen A und B gibt es die Menge

A × B := {(a, b)|a ∈ A ∧ b ∈ B},

genannt Produkt der Mengen A und B (auch Produktmenge, kartesisches Produkt, direktes Produkt).

Beweis. Die Existenz ergibt sich aus der Tatsache (a, b) ∈ P(P(A ∪ B)), denn {a} ∈ P(A) ⊂ P(A ∪ B) und {a, b} ∈ P(A ∪ B) impliziert (a, b) = {{a}, {a, b}} ∈ P(P(A ∪ B)). Dann setzen wir

A × B := {x ∈ P(P(A ∪ B))|∃a ∈ A, b ∈ B[x = (a, b)]}.

Das ist genau die Menge aller Paare (a, b) mit erstem Element in A und zweitem Element in B.

Wenn die Menge A oder die Menge B leer ist, passiert etwas Merkwürdiges. Es kann dann nämlich kein Paar in A × B geben, denn das erste Element a eines solchen Paares (a, b) wäre ein Element in A und das zweite Element b wäre ein Element in B, was nicht gleichzeitig sein darf. Andrerseits gibt es sicher Paare der Form (a, b), wenn A und B nicht leer sind. Also gilt:

Folgerung 2.4. A × B = ∅ ⟺ A = ∅ oder B = ∅.

Bemerkung 2.5. Wir verwenden in Zukunft lediglich die Tatsache, daß wir zu je zwei Elementen a und b ein Paar (a, b) (als Menge) bilden können (Existenz), daß die Produktmenge A × B von Paaren existiert und daß zwei Paare genau dann gleich sind, wenn ihre Komponenten gleich sind (2.2). Die exakte Definition wird nicht mehr weiter benötigt.

Definition 2.6. Seien a, b, c drei (nicht notwendig verschiedene) Elemente. Ein Tripel (a, b, c) ist definiert durch

(a, b, c) := ((a, b), c).

Bemerkung 2.7. Analog zu den Paaren gilt

(a, b, c) = (x, y, z) ⟺ a = x ∧ b = y ∧ c = z.

Wir kommen jetzt zu dem zentralen Begriff dieses Paragraphen. Wir wollen möglichst allgemein Beziehungen zwischen Elementen in zwei Mengen A und B beschreiben. Wie kann man eine Beziehung, eine Verbindung, einen Zusammenhang oder Ähnliches zwischen einem Element a ∈ A und einem Element b ∈ B möglichst allgemein fassen? Das tun wir, indem wir schlicht und einfach sagen, ob die gewünschte Beziehung zwischen a und b existiert oder nicht. Dann können wir diejenigen Paare (a, b), für die a in der gewünschten Beziehung zu b steht, in einer Menge R zusammenfassen und können dann genau feststellen, ob eine Beziehung zwischen a und b besteht, indem wir nämlich (a, b) ∈ R überprüfen. Auf diese Weise legen wir den Begriff der Beziehung, oder wie wir dann sagen werden, der Relation, in keiner Weise weiter fest, als daß zwischen Elementen aus A und solchen aus B eine Beziehung bestehen kann. Um Relationen gut unterscheiden zu können, fügen wir in der Definition auch noch die beiden Mengen A und B hinzu und definieren wie folgt:

Definition 2.8. Eine Relation ρ = (A, B, R) ist ein Tripel von Mengen A, B, R mit R ⊂ A × B. Ist ρ = (A, B, R) eine Relation, so schreiben wir gelegentlich auch

aρb :⟺ (a, b) ∈ R.

ρ heißt auch Relation von A in B, von A nach B oder zwischen A und B. Eine Relation der Form ρ = (A, A, R) heißt binäre Relation auf A.

Da der Begriff der Relation so allgemein formuliert worden ist, wird es viele Beispiele dafür geben. Wir geben hier nur einige wenige an, weitere werden sich später ergeben.

Beispiele 2.9. (1) ρ = (A, B, A × B) heißt die größte Relation zwischen A und B. Jedes Element a ∈ A steht in Relation oder Beziehung zu jedem Element b ∈ B.

(2) ρ = (A, B, ∅) heißt die kleinste oder leere Relation zwischen A und B. Dieses ist eine Relation, weil ∅ ⊂ A × B. Bei ihr steht kein Element aus A in Relation zu einem Element in B.

(3) ρ = (A, A, {(a, a)|a ∈ A}) heißt die identische oder Gleichheitsrelation von A. Zwei Elemente stehen in Relation zueinander genau dann, wenn sie gleich sind. Diese Relation ist also aus dem Gleichheitszeichen entstanden.

(4) ρ = (ℝ, ℝ, {(x, x^{2})|x ∈ ℝ}) ist die reelle Funktion x^{2}. Jedes x ∈ ℝ steht nämlich in Relation zu x^{2} ∈ ℝ.

(5) Die Relation

ρ = (P(A), P(A), {(B, C) ∈ P(A) × P(A)|B ⊂ C)

ist die Teilmengenrelation auf der Menge der Teilmengen von A, d.h. auf der Potenzmenge von A.

(6) Die Relation ρ = (ℕ, ℕ, {(m, n)|m, n ∈ ℕ ∧ m ≤ n}) ist die Anordnungsrelation ≤ auf den natürlichen Zahlen. Es gilt mρn ⟺ (m, n) ∈ ρ ⟺ m ≤ n. Man schreibt daher auch ρ = ≤. Eine graphische Darstellung für diese Relation ist

4 ∘ ∘ ∘ • • • • •
3 ∘ ∘ • • • • • •
2 ∘ • • • • • • •
1 • • • • • • • •
1 2 3 4 5 6 7 8

wobei die Elemente aus R = {(m, n)|m, n ∈ ℕ ∧ m ≤ n} durch dicke Punkte dargestellt sind und die Elemente aus ℕ×ℕ, die nicht in R liegen, durch kleine Kreise dargestellt sind. An dieser Darstellung sieht man auch deutlich, wie die Relation R als Teilmenge des Produkts ℕ×ℕ aufgefaßt wird.

(7) Ist B ⊂ C eine Teilmenge, so ist ρ = (B, C, R) mit R = {(b, b) ∈ B × C|b ∈ B} eine Relation, genannt Inklusionsrelation.

Bemerkung 2.10. Zwei Relationen ρ_{1} = (A_{1}, B_{1}, R_{1}) und ρ_{2} = (A_{2}, B_{2}, R_{2}) sind genau dann gleich, wenn A_{1} = A_{2}, B_{1} = B_{2} und R_{1} = R_{2} gelten. Es sind daher die Relationen (ℕ, ℕ, {(n, n)|n ∈ ℕ}) und (ℕ, ℝ, {(n, n)|n ∈ ℕ}) verschieden. Ist eine der Mengen A oder B leer, so gibt es genau eine Relation zwischen A und B, nämlich die leere Relation. Für A = ∅ und eine Relation ρ = (∅, B, R) ist nämlich R ⊂ ∅ × B = ∅ (vgl. 2.4), also R = ∅.

Definition 2.11. Sei ρ = (A, B, R) eine Relation. Wir definieren

(1) Quelle von ρ = Qu(ρ) := A,

(2) Ziel von ρ = Zi(ρ) := B,

(3) Graph von ρ = Gr(ρ) := R,

(4) Urbild von ρ = Ur(ρ) := {a|a ∈ A ∧ ∃b ∈ B[(a, b) ∈ R]},

(5) Bild von ρ = Bi(ρ) := {b|b ∈ B ∧ ∃a ∈ A[(a, b) ∈ R]}.

Definition 2.12. Seien die Relationen ρ = (A, B, R) und σ = (B, C, S) gegeben. Dann heißt die Relation

σρ := (A, C, T)

mit

T := {(a, c)|(a, c) ∈ A × C ∧ ∃b ∈ B[(a, b) ∈ R ∧ (b, c) ∈ S]}

die Produkt- oder Verknüpfungsrelation von ρ und σ. Gelegentlich schreibt man für die Produktrelation auch σ ∘ ρ := σρ. Man beachte, daß σρ nur definiert ist, wenn Zi(ρ) = Qu(σ) gilt. Man beachte weiterhin die Reihenfolge von ρ und σ in der Produktschreibweise σρ.

Ist ρ die Teilmengenrelation von Beispiel 2.9 (5), so gilt ρρ = ρ, weil B ⊂ C und C ⊂ D impliziert B ⊂ D.

Besonders wichtige Relationen in der Mathematik sind die Abbildungen, die Äquivalenzrelationen und die Ordnungen. Wir besprechen zunächst den Begriff der Abbildung. In der Informatik werden oft Abbildungen benötigt, die nicht total definiert sind. Das sind die partiellen Abbildungen.

Definition 2.13. Eine Relation α = (A, B, R) heißt eine partielle Abbildung, wenn gilt

∀a ∈ A ∀b_{1}, b_{2} ∈ B[(a, b_{1}) ∈ R ∧ (a, b_{2}) ∈ R ⟹ b_{1} = b_{2}]. (1)

In Worten ausgedrückt heißt das, daß zu jedem Element a ∈ A höchstens ein Element b ∈ B mit (a, b) ∈ R existiert. Wenn (a, b) ∈ R gegeben ist, dann schreiben wir für das eindeutig durch a definierte b auch α(a) (Funktionsschreibweise). Es gilt also mit dieser Festlegung

(a, b) ∈ R ⟺ b = α(a).

Eine weitere Bezeichnungsweise für (a, b) ∈ R = Gr(α) ist auch a ↦^{α} b oder a ↦ b mit der Sprechweise ”dem Element a wird durch α das Element b zugeordnet.“ Man nennt b auch das Bild von a bei α und a ein Urbild von b bei α. Man beachte, daß b zwar durch die Vorgabe von a eindeutig bestimmt ist, daß aber a keinesfalls eindeutig durch b bestimmt ist, wenn b = α(a) gilt. Das Bild von α ist eine Teilmenge von B, das Urbild von α eine Teilmenge von A. Beide Teilmengen können echte Teilmengen sein. Man nennt das Bild von α auch den Wertebereich (engl. range) und das Urbild von α den Definitionsbereich (engl. domain). Eine partielle Abbildung α = (A, B, R) wird auch mit der Schreibweise α : A ⇀ B oder A ⇀^{α} B bezeichnet. Gelegentlich schreiben wir auch α : A ∋ a ↦ b ∈ B oder A ∋ a ↦ α(a) ∈ B, wobei häufig α(a) auch ersetzt wird durch eine Formel mit der α(a) aus a berechnet werden kann.

Eine wesentliche Aufgabe wird es wieder sein festzustellen, ob zwei partielle Abbildungen gleich sind oder nicht, so wie wir schon Kriterien dafür haben, ob zwei Mengen gleich sind (Axiom 2), zwei Paare gleich sind (2.2) oder ob zwei Relationen gleich sind (2.10).

Bemerkung 2.14. Zwei partielle Abbildungen α = (A, B, R) und β = (C, D, S) sind genau dann gleich, wenn gelten

Qu(α) = Qu(β),
Zi(α) = Zi(β),
Ur(α) = Ur(β) und
∀a ∈ Ur(α)[α(a) = β(a)].

Definition 2.15. Eine Relation α = [A, B, R] heißt eine Abbildung, eine Funktion oder eine Familie, wenn α eine partielle Abbildung ist und gilt

∀a ∈ A∃b ∈ B[(a, b) ∈ R].  (2)

Benutzt man für α die Bezeichnung Familie, dann heißt A die Indexmenge der Familie. Die Bedingungen (1) und (2) können wie folgt ausgedrückt werden: Zu jedem a ∈ A existiert genau ein b ∈ B mit (a, b) ∈ R. Bei einer Abbildung stimmen Definitionsbereich und Quelle überein: Ur(α) = Qu(α)^{4}.

Warum sind hier drei verschiedene Ausdrücke, nämlich Abbildung, Funktion und Familie, für denselben Begriff eingeführt worden? Man verwendet diese Begriffe in verschiedenem Zusammenhang. Von einer Funktion, statt von einer Abbildung, spricht man oft, wenn das Ziel der Abbildung eine Menge von Zahlen ist. Man denkt dabei z.B. an die Sinusfunktion (sin(x)) oder die Exponentialfunktion (e^{x} = exp(x)). Zum Begriff der Familie werden wir noch mehr im Zusammenhang mit Produkten sagen.

4Wir werden häufiger Aussagen von der Form ”es gibt genau ein Element mit ...“ benötigen und verwenden dafür die Abkürzung ∃_{1}.

Wir können jetzt schon andeuten, daß man sich bei einer Familie mehr die Kollektion der Bildelemente vorstellt, während man bei einer Abbildung mehr an eine Zuordnungsvorschrift denkt.

Definition 2.16. Sei α : A ⟶ B eine Abbildung und A_{0} ⊂ A. Dann heißt α|_{A_{0}} := (A_{0}, B, Gr(α)∩(A_{0} ×B)) die Einschränkung von α auf A_{0}. Weiter definieren wir

α(A_{0}) := {α(x)|x ∈ A_{0}}.

Für B_{0} ⊂ B definieren wir

α^{−1}(B_{0}) := {x ∈ A|α(x) ∈ B_{0}}.

Schließlich sei

α^{−1}(b) := α^{−1}({b}),

genannt Urbild von b.

Unter den vielen verschiedenen Abbildungen spielen die folgenden eine herausragende Rolle.

Definition 2.17. (1) Eine Abbildung α : A ⟶ B heißt surjektiv oder eine Surjektion oder eine Abbildung von A auf B, wenn gilt

∀b ∈ B∃a ∈ A[(a, b) ∈ R],  (3)

das heißt, alle Elemente aus dem Ziel von α sind Bilder von Elementen aus der Quelle von α, also Bi(α) = Zi(α).

(2) Eine Abbildung α : A ⟶ B heißt injektiv oder eine Injektion oder eine eineindeutige Abbildung, wenn gilt:

∀b ∈ B∀a_{1}, a_{2} ∈ A[(a_{1}, b) ∈ R ∧ (a_{2}, b) ∈ R ⟹ a_{1} = a_{2}],

(4)

das heißt, je zwei verschiedene Elemente aus A werden auf verschiedene Elemente aus B abgebildet.

(3) Eine Abbildung α : A ⟶ B heißt bijektiv oder eine Bijektion, wenn α injektiv und surjektiv ist.

Bemerkung 2.18. Ist α = (A, B, R) eine Relation, so definieren wir eine Relation α′ := (B, A, R′) durch die Bedingung (b, a) ∈ R′ :⟺ (a, b) ∈ R und bezeichnen α′ als Umkehrrelation. Ist α eine bijektive Abbildung, so ist α′ ebenfalls eine bijektive Abbildung. Die Gesetze (3) und (4) für die Relation α sind nämlich die Gesetze (2) bzw (1) für die Umkehrrelation α′ und die Gesetze (1) und (2) für α sind die Gesetze (4) bzw. (3) für α′.

Beispiele 2.19. (1) Die identische Relation 2.9 (3) ist eine Abbildung, die identische Abbildung oder Identität, bezeichnet mit 1_{A} : A ⟶ A oder id_{A} : A ⟶ A.

(2) ℕ ∋ n ↦ 2 · n ∈ ℕ ist eine Abbildung.

(3) ℕ ∋ n ↦ 2 · n ∈ {2, 4, 6, 8, … } ist verschieden von der Abbildung unter (2) (die Ziele sind verschieden). Die Abbildung unter (2) ist injektiv, aber nicht surjektiv. Die Abbildung unter (3) ist bijektiv.

(4) ℝ ∋ r ↦ [r] ∈ ℤ, wobei [r] die größte ganze Zahl ≤ r sei, ist surjektiv, aber nicht injektiv.

(5) ℚ ∋ q ↦ q ∈ ℝ ist eine (injektive) Inklusionsabbildung.

(6) ℝ ∋ r ↦ 2^{r} ∈ ℝ^{+} := {r ∈ ℝ|r > 0} ist eine bijektive Abbildung.

Lemma 2.20. Seien α : A ⟶ B und β : B ⟶ C Abbildungen. Dann ist das Produkt oder die Komposition βα : A ⟶ C wieder eine Abbildung.

Beweis. Wir wissen aus der Diskussion in 2.12, daß A die Quelle der Produktrelation βα ist, und daß C das Ziel ist. Es bleibt zu zeigen, daß die Produktrelation eine Abbildung ist. Zu jedem a ∈ A gibt es genau ein b ∈ B mit α(a) = b (d.h. (a, b) ∈ Gr(α)). Zu diesem b ∈ B gibt es genau ein c ∈ C mit β(b) = c (d.h. (b, c) ∈ Gr(β)), also auch mit (βα)(a) = c (d.h. (a, c) ∈ Gr(βα)). Das Element c ∈ C ist auch durch die Bedingung (a, c) ∈ Gr(βα) eindeutig festgelegt. Ist nämlich c′ ∈ C mit (a, c′) ∈ Gr(βα), so gibt es nach Definition 2.12 ein b′ ∈ B mit (a, b′) ∈ Gr(α) und (b′, c′) ∈ Gr(β). Aus der ersten Bedingung folgt b′ = b, weil α eine Abbildung ist. Damit ist (b, c′) ∈ Gr(β), also c′ = c, weil β eine Abbildung ist. Daher ist c ∈ C mit der Eigenschaft (a, c) ∈ Gr(βα) durch a eindeutig bestimmt. Wir können jetzt insbesondere einfach schreiben (βα)(a) = c = β(b) = β(α(a)).

Lemma 2.21. (1) Seien α : A ⟶ B, β : B ⟶ C und γ : C ⟶ D Abbildungen. Dann ist (γβ)α = γ(βα) (Assoziativgesetz).

(2) Für Abbildungen α : A ⟶ B und β : C ⟶ A und 1_{A} gelten: 1_{A}β = β und α1_{a} = α. (Gesetz von der Identität).

Beweis. Es ist leicht zu sehen, daß die Komposition der Abbildungen möglich ist, Quelle und Ziel jeweils übereinstimmen. Es genügt daher ((γβ)α)(a) = γ(β(α(a))) = (γ(βα))(a), (1_{A}β)(c) = 1_{A}(β(c)) = β(c) und (α1_{A})(a) = α(1_{A}(a)) = α(a) zu sehen.

Satz 2.22. Sei α : A ⟶ B eine Abbildung. α ist genau dann bijektiv, wenn es eine Abbildung β : B ⟶ A mit αβ = 1_{B} und βα = 1_{A} gibt. β ist eindeutig durch α bestimmt.

Bemerkung: Wir verwenden die Bezeichnung α^{−1} := β und nennen α^{−1} die inverse Abbildung oder Umkehrabbildung.

Beweis. Sei α eine bijektive Abbildung. Nach 2.18 wissen wir, daß die Umkehrrelation α′ = β wieder bijektiv ist. Weiter ist (a, b) ∈ Gr(α) ⟺ (b, a) ∈ Gr(β). Damit gilt α(a) = b ⟺ β(b) = a. Daraus folgt βα(a) = β(b) = a, also βα = 1_{A}, und ebenso αβ(b) = α(a) = b, also αβ = 1_{B}. Ist umgekehrt β : B ⟶ A mit βα = 1_{A} und αβ = 1_{B} gegeben, so schließen wir so: α(a_{1}) = α(a_{2}) ⟹ βα(a_{1}) = βα(a_{2}) ⟹ a_{1} = a_{2}, weil βα = 1_{A} gilt. Damit ist α injektiv. Für b ∈ B ist α(β(b)) = b, also ist α surjektiv.

Ist β′ eine weitere Umkehrabbildung mit αβ′ = 1_{B} und β′α = 1_{A}, so ist mit 2.21 β′ = 1_{A}β′ = βαβ′ = β1_{A} = β, also ist β eindeutig durch α bestimmt.

Mit der Bezeichnung α^{−1} muß man vorsichtig umgehen. Sie war auch schon in 2.16 eingeführt worden. Dort hatten wir für eine beliebige Abbildung α definiert α^{−1}(b) := α^{−1}({b}) = {x ∈ A|α(x) ∈ {b}}. Diese Notation darf keinesfalls zu dem Schluß verführen, daß damit α^{−1} die Umkehrabbildung von α sei, und damit gar vorausgesetzt werde, daß die Abbildung α bijektiv sei. Wenn die Abbildung α jedoch tatsächlich bijektiv ist, dann ist mit der Definition von 2.16 α^{−1}(b) := α^{−1}({b}) = {a ∈ A|α(a) = b}, d.h. α^{−1}(b) = {a}, wenn α(a) = b gilt. Verwenden wir die Definition der Umkehrabbildung, so erhalten wir α^{−1}(b) = a, wenn α(a) = b gilt. Wir erhalten also aus diesen gleich benannten Ausdrücken statt einer einelementigen Teilmenge von A nur das eine Element dieser Teilmenge. Es wird sich aber aus dem Zusammenhang jeweils ergeben, welche der beiden Definitionen gemeint ist.

Folgerung 2.23. (1) Ist α : A ⟶ B bijektiv, so ist α^{−1} :

B ⟶ A bijektiv, und es gilt (α^{−1})^{−1} = α.

(2) Sind α : A ⟶ B und β : B ⟶ C bijektiv, so ist βα : A ⟶ C bijektiv, und es gilt (βα)^{−1} = α^{−1}β^{−1}.

Beweis. (1) Wegen 2.22 ist α^{−1} eine bijektive Abbildung und es gilt α^{−1}α = 1 und αα^{−1} = 1. Für die Umkehrabbildung von α^{−1} erhalten wir dann (α^{−1})^{−1}α^{−1} = 1 = αα^{−1} und α^{−1}(α^{−1})^{−1} = 1 = α^{−1}α. Damit sind (α^{−1})^{−1} und α Umkehrabbildungen von α^{−1} und daher nach 2.22 gleich: (α^{−1})^{−1} = α.

(2) Wir verwenden 2.21 und zeigen mit 2.22, daß α^{−1}β^{−1} die eindeutig bestimmte Umkehrabbildung von βα ist: α^{−1}β^{−1}βα = α^{−1}1_{B}α = α^{−1}α = 1_{A} und βαα^{−1}β^{−1} = β1_{B}β^{−1} = ββ^{−1} = 1_{C}. Daraus folgt, daß βα bijektiv ist und daß (βα)^{−1} = α^{−1}β^{−1} gilt.

Wir wenden uns jetzt dem Begriff der Familie zu. Nach Definition ist eine Familie eine Abbildung. Wir verbinden mit einer Familie jedoch eine andere Vorstellung, als mit einer Abbildung. Das wird schon aus der Vielzahl der verschiedenen Schreibweisen für eine Familie deutlich. Wir definieren zunächst wie folgt.

Definition 2.24. Sei f : I ⟶ A eine Familie mit Indexmenge I. Dann heißt f =: (f(i)|i ∈ I) = (f(i)) = (f_{i}|i ∈ I) = (f_{i}) = (a_{i}) (mit a_{i} = f(i)) eine Familie mit Koeffizienten a_{i} aus A. Ist die Indexmenge ℕ, so heißt f eine Folge. Ist I = {1, …, n}, so heißt f eine endliche Folge (der Länge n) oder ein n-Tupel.

Ein Beispiel ist die Familie (\frac{1}{i}|i ∈ ℕ) = (1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, …) = f mit f : ℕ ⟶ ℚ und f(i) := \frac{1}{i}. Hier wird deutlich, daß wir uns eine Familie als Kollektion ihrer Koeffizienten vorstellen. Die Koeffizienten sind mit einem Index versehen, der den Platz angibt, den der Koeffizient in der Familie einnimmt. Koeffizienten können dabei mehrfach in einer Familie vorkommen, anverschiedenen Plätzen vesteht sich, oder mit verschiedenen Indizes. Damit ist eine Familie nicht einfach eine Menge. Die Familien (1, 3, 5, 6) und (3, 6, 5, 1) sind verschieden, die Mengen {1, 3, 5, 6} und {3, 6, 5, 1} sind jedoch gleich. Ebenso sind die Familien (1, 2, 1) und (1, 2) verschieden, während die Mengen {1, 2, 1} und {1, 2} gleich sind. Das sind Eigenschaften, die wir von Familien haben wollen. Sie sind durch den Begriff der Abbildung erfüllt. Das erste gegebene Beispiel wird durch die Abbildung

f : {1, 2, 3, 4} ⟶ ℕ
1 ↦ 1;
2 ↦ 3;
3 ↦ 5;
4 ↦ 6

ausgesdrückt. Der Leser möge sich die weiteren Beispiele von Familien als Abbildungen darstellen.

Bei einer Familie wird die Indexmenge häufig explizit angegeben, nicht jedoch die Menge, aus der die Koeffizienten stammen. Durch die Definition einer Familie als Abbildung sind die Familien (1, 3, 5, 6) von natürlichen Zahlen und (1, 3, 5, 6) von reellen Zahlen verschieden, denn es handelt sich im ersten Fall um eine Abbildung f : {1, 2, 3, 4} ⟶ ℕ und im zweiten Fall um eine Abbildung g : {1, 2, 3, 4} ⟶ ℝ. Es stimmen zwar deren Graphen überein, nicht jedoch die Ziele der beiden Abbildungen.

Man sollte eine Familie auch nicht etwa als eine geordnete Menge ansehen, denn in einer Familie können (wie in einem Paar) Koeffizienten mehrfach auftreten. Und eine Ordnung wird nur dann suggeriert, wenn die Indexmenge schon geordnet ist.

Ähnlich wie wir Paare (,die wir später auch als Familien, genauer als 2-Tupel auffassen werden,) zur einer Menge von Paaren, der Produktmenge, zusammengefaßt haben, können wir auch Familien zu größeren Mengen, den Produkten, zusammenfassen.

Definition 2.25. Sei (A_{i}|i ∈ I) eine Familie von Mengen A_{i}. Das Produkt ist definiert als

∏_{i∈I} A_{i} := {f : I ⟶ ⋃_{i∈I} A_{i}|∀i ∈ I[f(i) ∈ A_{i}]} .

Die Abbildungen p_{j} : ∏_{i∈I} A_{i} ⟶ A_{j}, f ↦ f(j) heißen Projektionen, die A_{j} die Faktoren des Produkts. Wenn I = {1, …, n} endlich ist, dann schreiben wir auch

A_{1} × … × A_{n} = ∏_{i=1}^{n} A_{i} := ∏_{i∈I} A_{i}.

Bemerkung 2.26. Das Produkt existiert als Menge, weil {f : I ⟶ ⋃_{i∈I} A_{i}} ⊂ {I} × {⋃_{i∈I} A_{i}} × P(I × ⋃_{i∈I} A_{i}) existiert. Die Elemente des Produktes ∏_{i∈I} A_{i} sind Familien mit einer gemeinsamen Indexmenge I. Der i-te Koeffizient einer solchen Familie kann aus der Menge A_{i} beliebig gewählt werden. Alle Familien, die so entstehen, bilden dann das Produkt.

Beispiele 2.27. (1) Die Menge aller Abbildungen von einer Menge A in eine Menge B ist ein Produkt und wird mit {f : A ⟶ B|f Abbildung} = Abb(A, B) = ∏_{i∈A} B_{i} = B^{A} bezeichnet. (Dabei sei B_{i} := B für alle i ∈ A.)

(2) {f : ℕ ⟶ ℝ} ist die Menge der Folgen von reellen Zahlen und wird auch als ∏_{ℕ} ℝ = ℝ^{ℕ} geschrieben.

(3) {f : ℝ ⟶ ℝ} ist die Menge der reellen Funktionen.

(4) {f : {1, …, n} ⟶ ℂ} ist die Menge der komplexen n-Trupel und wird auch mit ℂ × … × ℂ = ℂ^{n} bezeichnet.

(5) Es gibt eine bijektive Abbildung zwischen den Mengen {f : {1, 2} ⟶ A} und A × A. Sie ordnet jedem 2-Tupel (a_{1}, a_{2}) = (f : {1, 2} → A) das Paar (a_{1}, a_{2}) zu.

Damit haben wir die wesentlichen Grundtatsachen über Abbildungen und Relationen zusammengestellt. Zum Abschluß diskutieren wir jetzt den Begriff der endlichen und der unendlichen Menge. Da wir die Menge der natürlichen Zahlen noch nicht zur Verfügung haben, müssen wir eine recht unanschauliche Definition einer endlichen Menge geben. Um diese Definition zu motivieren, nehmen wir zunächst an, daß die Menge ℕ der natürlichen Zahlen schon zur Verfügung steht. Dann wird man eine Menge A endlich nennen, wenn sie eine endliche Anzahl von Elementen hat. Wie soll man das aber feststellen? Man muß sie abzählen, und das kann man mit den natürlichen Zahlen so machen, daß man jedem Element von A genau eine natürliche Zahl, von 1 beginnend und aufsteigend in ℕ, zuordnet. Wenn dieser Prozeß bei einer Zahl n ∈ ℕ abbricht, so wird man sagen, daß A genau n Elemente hat. Zwei Probleme ergeben sich hier. Zunächst ist ein solcher Abzählprozeß noch nicht klar mit unseren Hilfsmitteln definiert. Weiter ist auch nicht klar, ob die Anzahl der Elemente von A von der Reihenfolge, in der wir gezählt haben, abhängt. Das letzte Problem werden wir erst beim Studium der natürlichen Zahlen in Kapitel II behandeln. Das erste Problem wird dadurch gelöst, daß man sagt, A sei endlich, wenn es ein n ∈ ℕ und eine bijektive Abbildung von {1, …, n} in A gibt, nämlich die vorher verwendete Zählabbildung. Das folgende Lemma wird also diese Grundkenntnis der natürlichen Zahlen zunächst voraussetzen.

Lemma 2.28. Seien A und B zwei Mengen mit n Elementen (n ∈ ℕ). Dann sind für eine Abbildung α : A ⟶ B äquivalent

(1) α ist surjektiv,

(2) α ist injektiv,

(3) α ist bijektiv.

Beweis. Es genügt offenbar (1) ⟺ (2) zu zeigen, da eine bijektive Abbildung injektiv und surjektiv ist. Sei α injektiv. Die n verschiedenen Elemente aus A haben also n verschiedene Bilder in B. Da B nur n Elemente enthält, sind die Bildelemente schon alle Elemente von B, also ist α surjektiv. Sei umgekehrt α surjektiv. Seien b_{1}, …, b_{n} die Elemente von B. Jedes b_{i} ist Bild eines Elementes a_{i} von A, also α(a_{i}) = b_{i}. Da α eine Abbildung ist, sind die Elemente a_{1}, …, a_{n} alle voneinander verschieden und daher genau alle Elemente von A. α(a_{i}) = b_{i} besagt dann, daß verschiedene Elemente aus A verschiedene Bilder besitzen, also ist α injektiv.

Es folgt aus dem vorausgehenden Lemma insbesondere für eine Menge A mit n Elementen, daß jede injektive Abbildung von A nach A surjektiv ist. Diese Eigenschaft nehmen wir zum Anlaß der folgenden Definition von endlichen Mengen, die wir jetzt ohne Verwendung der natürlichen Zahlen geben können.

Definition 2.29. Eine Menge A heißt endlich, wenn jede injektive Abbildung α : A ⟶ A surjektiv ist. Wenn eine Menge nicht endlich ist, so heißt sie unendlich.

Die Existenz einer unendlichen Menge werden wir in Kapitel II axiomatisch fordern. Sie ist äquivalent zur Existenz der Menge der natürlichen Zahlen.

Die für endliche Mengen gegebene Definition ist bei näherem Hinsehen etwas schwächer, als die Aussage des Lemmas. Aus dem Lemma geht nämlich für Mengen A mit n Elemente hervor, daß auch jede surjektive Abbildung α : A ⟶ A injektiv ist. Tatsächlich kann man das für endliche Mengen jetzt aber beweisen. Es gilt sogar

Satz 2.30. Für eine Menge A sind äquivalent (1) A ist endlich;

(2) jede surjektive Abbildung von A nach A ist injektiv (bijektiv);

(3) jede injektive Abbildung von A nach A ist surjektiv (bijektiv).

Beweis. Ist A = ∅ , so sind (2) und (3) trivialerweise erfüllt, also auch äquivalent. Sei also A ≠ ∅ und a_{0} ∈ A.

(3) ⟺ (1) ist die vorhergehende Definition.

(2) ⟹ (3): Sei α : A ⟶ A injektiv. Wir müssen zeigen, daß α auch surjektiv ist. Zur Verfügung haben wir die Bedingung, daß jede surjektive Abbildung von A nach A auch injektiv ist. Wie sollen wir diese beiden Bedingungen verbinden? Offenbar müssen wir uns zusätzlich zu α eine weitere Abbildung verschaffen, die surjektiv ist, um die Bedingung (2) ausnützen zu können, denn von α wissen nicht, daß es surjektiv ist. Und wenn wir das schon wüßten, dann brauchten wir nichts mehr zu zeigen. Wir definieren also eine neue Abbildung β : A ⟶ A durch

β(b) := \begin{cases}a, & falls ∃a ∈ A[α(a) = b], \\ a_{0}, & sonst \end{cases}

3. MULTIMENGEN UND FUZZY-MENGEN (FUZZY SETS) 37

und hoffen, daß wir von ihr nachweisen können, daß sie surjektiv ist. Da α injektiv ist, gibt es zu vorgegebenem b höchstens ein a mit α(a) = b, damit ist β eine Abbildung. Da es zu jedem a ein b gibt mit α(a) = b und damit β(b) = a, ist β surjektiv und wegen (2) dann auch injektiv. Sei nun b ∈ A. Dann ist β(b) = a mit α(a) = b oder β(b) = a_{0}. Es ist aber auch β(α(a_{0})) = a_{0}, denn für b_{0} := α(a_{0}) gilt nach Definition β(b_{0}) = a_{0}. Da β injektiv ist, kann β(b) = a_{0} also nur für b = b_{0} eintreten. Damit gibt es aber für jedes b ∈ A ein a ∈ A mit α(a) = b. Das bedeutet, daß α surjektiv ist. (3)⟹(2): Sei α : A ⟶ A surjektiv. Hier müssen wir ähnlich wie im vorhergehenden Teil eine weitere Abbildung definieren, um die Voraussetzung ausnutzen zu können. Wir definieren daher β : A ⟶ A wie folgt. Für jedes a ∈ A ist α^{−1}(a) ≠ ∅. Wir wählen also zu jedem a ∈ A ein a′ ∈ α^{−1}(a) aus^{5} und definieren β(a) := a′. Dann gilt αβ(a) = α(a′) = a für alle a ∈ A, also gilt β(a_{1}) = β(a_{2}) ⟹ αβ(a_{1}) = αβ(a_{2}) ⟹ a_{1} = a_{2}. Damit ist β injektiv, nach (3) also bijektiv. Sei jetzt α(a_{1}) = α(a_{2}). Dann gibt es b_{1}, b_{2} mit β(b_{1}) = a_{1} und β(b_{2}) = a_{2}, weil β surjektiv ist. Es folgt b_{1} = αβ(b_{1}) = α(a_{1}) = α(a_{2}) = αβ(b_{2}) = b_{2} und daraus a_{1} = β(b_{1}) = β(b_{2}) = a_{2}. Damit ist α injektiv.

Folgerung 2.31. (1) Eine Menge A ist genau dann unendlich, wenn es eine injektive Abbildung α : A ⟶ A gibt, die nicht surjektiv ist.

(2) Eine Menge A ist genau dann unendlich, wenn es eine surjektive Abbildung α : A ⟶ A gibt, die nicht injektiv ist.

3. Multimengen und Fuzzy-Mengen (fuzzy sets)

In diesem Abschnitt werden die Gesetze des Rechnens mit Multimengen und Fuzzy-Mengen (fuzzy sets) entwickelt. Multimengen und Fuzzy-Mengen werden häufig in der Informatik benötigt. Wir verallgemeinern diese beiden Begriffe in einer Weise, daß auch der gewöhnliche Mengenbegriff darunter fällt und definieren daher zunächst den Begriff der gewichteten Menge und führen sodann die üblichen mengentheoretischen Rechenoperationen ein, die die Operationen Durchschnitt, Vereinigung und Teilmenge von den gewöhnlichen Mengen auf gewichtete Mengen verallgemeinern. Schließlich leiten wir hierfür einige fundamentale Rechengesetze her und verwenden diese dann, um andere Rechengesetze der Mengenalgebra auch in dieser allgemeineren Situation von gewichteten Mengen zu entwickeln. Damit geben wir auch gleichzeitig Beweise für die Rechengesetze, die wir ursprünglich für gewöhnliche Mengen lediglich behauptet aber nicht bewiesen hatten.

5Diese Schlußweise verwendet eigentlich das sogenannte Auswahlaxiom, das wir später erst in Axiom 7 und Kapitel II. 3.7 besprechen werden.

Wir stellen uns eine Multimenge im Gegensatz zum Begriff der Menge als eine Zusammenfassung von Elementen zu einem Ganzen vor, in der auch einzelne Elemente mehrfach ”auftreten“ können. Da das aber mit gewöhnlichen Mengen nicht durchführbar ist, ordnen wir jedem Element vermöge einer Abbildung eine natürliche Zahl zu, die angibt, wie oft das jeweilige Element in der Menge ”auftritt“. Man kann sich etwa an das folgende Beispiel (der Menge) aller Buchstaben des Wortes MIS-SISSIPPI halten. Die Menge der Buchstaben ist lediglich A = {I, M, P, S}. Wir wollen jedoch eine Zusammenfassung der Form {I, I, I, I, M, P, P, S, S, S, S} erhalten. Deshalb definieren wir die Abbildung χ : A ⟶ ℕ durch χ(I) = 4, χ(M) = 1, χ(P) = 2 und χ(S) = 4, mit der wir die Vielfachheit der Elemente zählen können.

Fuzzy-Mengen gehen zunächst von einem anderen Konzept aus, nämlich von einer graduellen oder ungenauen Zugehörigkeit eines Elements a zu einer Menge A. Der Grad oder das Gewicht der Zugehörigkeit wird mit einer reellen Zahl zwischen 0 und 1 angegeben. Die Zahl soll die Sicherheit angeben, mit der man weiß, ob das Element der Menge angehört. Damit kann man in der Informatik, insbesondere in Expertensystemen, Aussagen und Eigenschaften subjektiv gewichten mit Wörtern wie ”sehr“, ”ungefähr“, ”typisch“, ”im wesentlichen“,”viel größer als“, ”wird beeinflußt von“, ”ist relevant für“, ”ist ähnlich“, ”ist nahe zu“, “besonders groß“ und vielen anderen.

Man kann zum Beispiel für Raumtemperaturen im Intervall von 2^{∘} C bis 40^{∘} C die Fuzzy-Menge W der warmen Temperaturen definieren. Man bestimmt den Grad Zugehörigkeit einer Temperatur von x^{∘} C zu W oder allgemeiner zu dem Interval [2, 40] durch den Wert von

χ_{W} (x) = \begin{cases}0, & für x ≤ 8, \\ 2 (\frac{x − 8}{24})^{2} , & für 8 ≤ x ≤ 20, \\ 1 − 2 (\frac{x − 32}{24})^{2} , & für 20 ≤ x ≤ 32, \\ 1 & für 32 ≤ x. \end{cases}

Danach wäre also ein Raum mit 32^{∘} C und mehr definitiv als warm anzusehen, ein Raum mit 8^{∘} C und weniger definitiv als nicht warm und in dem Intervall [8, 32] in verschiedenem Grade als warm (weniger, etwas, ziemlich, sehr) anzusehen. Die Temperaturen x^{∘} mit dem Wert χ_{W} (x) = 0 gehören der Menge der warmen Temperaturen W nicht an. Die übrigen Temperaturen gehören W mit dem durch χ_{W} gegebenen Gewicht an.

In beiden Fällen, dem einer Multimenge und dem von Fuzzy-Mengen, wird jedem Element einer Menge eine Zahl zugeordnet. Wir verallgemeinern die Begriffe daher. Dazu benötigen wir an dieser Stelle schon die Menge ℝ der reellen Zahlen. Wir stellen uns auf den Standpunkt, daß diese allgemein mit ihren Recheneigenschaften bekannt sind. Ein exakte Einführung wird jedoch erst am Ende des zweiten Katitels erfolgen. Wir behandeln aus Gründen der Systematik diesen Abschnitt über Multimengen und Fuzzy-Mengen schon an dieser Stelle. Wir definieren dazu wie folgt Definition 3.1. Sei G, die Gewichtsmenge, eine nichtleere Teilmenge der Menge der nicht-negativen reellen Zahlen ℝ_{0}^{+} = {r ∈ ℝ|0 ≤ r} mit 0 ∈ G. Sei U eine fest vorgegebene Menge, ein Universum (des Discourses). Eine G-gewichtete Menge über U ist der Graph einer Abbildung A = Gr(χ_{A} : U ⟶ G), genannt Gewicht oder Vielfachheit. Die dem Graphen zugehörige Abbildung χ_{A} = (U, G, A) heißt charakteristische Funktion von A.

Der Graph einer solchen Abbildung A besteht nach der Definition von Abbildungen aus Elementen der Form (u, χ_{A}(u)), also aus Paaren, bestehend aus einem Element u ∈ U und seinem Gewicht oder seiner Vielfachheit. Da das Universum und die Gewichtsmenge fest vorgegeben sind, bestimmt der Graph A die Abbildung χ_{A} vollständig. Obwohl die betrachteten Mengen U und die gewichteten Mengen A unendlich sein können, können einzelne Elemente doch nur mit endlichem Gewicht (Vielfachheit) vorkommen. Wenn man dieses Gewicht darüberhinaus vergrößern möchte, so muß man eine Abbildung in eine größere geordnete Menge G betrachten, z.B. eine Menge von Ordinalzahlen. Das soll hier aber nicht weiter verfolgt werden.

Gewöhnliche Mengen kann man hier einordnen mit der Gewichtsmenge G = {0, 1}. Da man sich auf ein Universum bezieht, sprechen wir eigentlich immer nur von Teilmengen. Eine gewöhnliche Teilmenge A ⊂ U kann man beschreiben durch die Abbildung χ_{A} : U ⟶ {0, 1} mit

χ_{A}(u) = \begin{cases}0, & für u ∉ A, \\ 1, & für u ∈ A. \end{cases}

Die Abbildung χ_{A} heißt auch bei gewöhnlichen Mengen charakteristische Funktion von A ⊂ U. Auch hier ist A offenbar vollständig durch die Angabe seiner charakteristischen Funktion festgelegt. Jede Abbildung χ : U ⟶ {0, 1} definiert eine Teilmenge A ⊂ U und ist die charakteristische Funktion dieser Teilmenge.

Definition 3.2. (1) Eine Multimenge mit der Basis U ist ei-

ne G- gewichtete Menge mit G = ℕ_{0}.

(2) Eine Fuzzy-Menge (oder Fuzzy-Teilmenge von U) ist eine G-gewichtete Menge mit G = [0, 1], dem abschlossenen Intervall von 0 bis 1.

Häufig verwendet man für Fuzzy-Mengen die Bezeichnung

A = ∫_{U} χ_{A}(u)/u,

falls U ein Kontinuum ist, und

A = χ_{A}(u_{1})/u_{1} + … + χ_{A}(u_{n})/u_{n} = ∑_{i=1}^{n} χ_{A}(u_{i})/u_{i},

falls U eine endliche Menge ist.

Wir haben damit gesehen, daß wir mit dem Begriff der gewichteten Menge einen gemeinsamen Oberbegriff für gewöhnliche Teilmengen von U, für Fuzzy- (Teil-)Mengen in U und für Multimengen über U gefunden haben. Wir wollen für diesen allgemeinen Begriff die meisten Regeln der Mengenalgebra (Booleschen Algebra) entwickeln. Dabei beweisen wir auch eine Reihe von Rechenregeln für gewöhnliche Mengen, die wir im ersten Abschnitt nicht bewiesen, sondern nur behauptet haben.

Definition 3.3. Der Träger (engl. support) einer gewichteten Menge A ist die Teilmenge supp(A) := {u ∈ U|χ_{A}(u) > 0}. Die Höhe (engl. height) einer gewichteten Menge A ist das Supremum hgt(A) := sup{χ_{A}(u)|u ∈ U}, falls ein solches Supremum existiert, sonst wird die Höhe als unendlich angenommen.

Definition 3.4. Die Vereinigung von gewichteten Mengen A und B mit charakteristischen Funktionen χ_{A} und χ_{B} ist definiert durch Angabe der charakteristischen Funktion von A ∪ B mit

χ_{A∪B} := max(χ_{A}, χ_{B}),

wobei max(χ_{A}, χ_{B})(u) = max(χ_{A}(u), χ_{B}(u)) das Maximum der Gewichte von u in A bzw. in B sei. Der Durchschnitt von gewichteten Mengen A und B mit charakteristischen Funktionen χ_{A} und χ_{B} ist definiert durch Angabe der charakteristischen Funktion von A ∩ B mit

χ_{A∩B} := min(χ_{A}, χ_{B}),

wobei min(χ_{A}, χ_{B})(u) = min(χ_{A}(u), χ_{B}(u)) das Minimum der Gewichte von u in A bzw. in B sei. Die leere gewichtete Menge ∅ ist χ_{∅} = 0, also χ_{∅}(u) = 0 für alle u ∈ U. Eine gewichtete Menge A heißt (gewichtete) Teilmenge A ⊂ B der gewichteten Menge B, wenn χ_{A} ≤ χ_{B}, d.h. wenn für alle u ∈ U gilt χ_{A}(u) ≤ χ_{B}(u).

Zwei gewichtete Teilmengen A und B des Universums sind genau dann gleich, wenn A ⊂ B und B ⊂ A gelten. Es ist nämlich χ_{A} = χ_{B} genau dann, wenn χ_{A} ≤ χ_{B} und χ_{B} ≤ χ_{A}.

In der Informatik wird häufiger auch der Begriff der disjunkten Vereinigung von Multimengen verwendet und dann einfach nur Vereinigung genannt.

Definition 3.5. Die disjunkte Vereinigung A ˙∪B von Multimengen A und B ist definiert durch χ_{A ˙∪B} = χ_{A} + χ_{B}, d.h. durch χ_{A ˙∪B}(u) = χ_{A}(u) + χ_{B}(u) für alle u ∈ U.

Die Bildung einer disjunkten Vereinigung ist in dieser Weise für Fuzzy-Mengen und gewöhnliche Mengen nicht möglich, da bei diesen Mengen die Gewichtsmenge G nicht gegenüber der Addition abgeschlossen ist.

Definition 3.6. Für gewöhnliche Mengen A und B definiert man die disjunkte Vereinigung als A ˙∪B := {(a, 1)|a ∈ A} ∪ {(b, 2)|b ∈ B}.

Man beachte, daß die Mengen A_{1} := {(a, 1)|a ∈ A} und B_{2} := {(b, 2)|b ∈ B} keine Elemente gemeinsam haben und jeweils eine bijektive Abbildung auf die Mengen A bzw. B gestatten. Es werden also vor der Bildung der Vereinigung von A und B deren Elemente so umbenannt, daß nach der Umbenennung keine gemeinsamen Elemente mehr vorhanden sind. Erst nachdem man die Mengen auf diese Weise disjunkt gemacht hat, wird die Vereinigung gebildet.

Wir beweisen jetzt einige Gesetze über das Rechnen mit diesen Operationen, aus denen wir dann die übrigen Gesetze der Mengenalgebra herleiten.

Satz 3.7. Für gewichtete Mengen A, B, C gelten folgende Gesetze (Axiome der Mengenalgebra):

(1) (a) A ∪ B = B ∪ A, (b) A ∩ B = B ∩ A, (Kommutativgesetze)

(2) (a) A ∪ (B ∪ C) = (A ∪ B) ∪ C, (b) A ∩ (B ∩ C) = (A ∩ B) ∩ C, (Assoziativgesetze)

(3) (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), (b) A∩(B ∪C) = (A∩B)∪(A∩C), (Distributivgesetze)

(4) A ∪ ∅ = A, (Gesetz von der Identität)

(5) A ∩ ∅ = ∅, (Dominierungsgesetz)

(6) A ∪ (A ∩ B) = A, (Absorptionsgesetz)

(7) A ∩ A = A, (Idempotenzgesetz).

Beweis. (1) (a) Es ist max(χ_{A}, χ_{B})(u) = max(χ_{B}, χ_{A})(u) für alle u ∈ U zu zeigen, also

max(χ_{A}(u), χ_{B}(u)) = max(χ_{B}(u), χ_{A}(u)), was aus der Formel max(a, b) = max(b, a) unmittelbar folgt.

(1) (b) folgt aus der Formel min(a, b) = min(b, a).

(2) (a) folgt aus max(a, max(b, c)) = max(a, b, c) = max(max(a, b), c).

(2) (b) folgt aus min(a, min(b, c)) = min(a, b, c) = min(min(a, b), c).

(3) (a) Für das Minimum und Maximum von Zahlen a, b, c gilt das Distributivgesetz

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

wenn man nämlich die Fälle a ≤ b ≤ c, b ≤ a ≤ c und b ≤ c ≤ a einsetzt, erhält man jeweil die Resultate b = b, a = a und a = a. Wegen der Kommutativität brauchen keine weiteren Fälle diskutiert zu werden. Ganz analog sieht man min(a, max(b, c)) = max(min(a, b), min(a, c)).

(4) und (5) folgen aus max(a, 0) = a bzw. min(a, 0) = 0.

(6) folgt aus max(a, min(a, b)) = a.

(7) folgt aus min(a, a) = a.

Satz 3.8. Es ist A ⊂ B genau dann, wenn A ∩ B = A.

Beweis. Es ist a ≤ b genau dann, wenn min(a, b) = a. Also ist auch χ_{A} ≤ χ_{B} genau dann, wenn min(χ_{A}, χ_{B}) ≤ χ_{A}.

Man könnte durch die im Satz angegebene Bedingung den Begriff der gewichteten Teilmenge auch einführen (definieren) und brauchte dann garnichts zu beweisen. Wir haben hier also lediglich überprüft, daß unsere obige Definition sich vernüftig in die Entwicklung der Rechenregeln der Mengenalgebra einfügt. In den späteren Beweisen werden wir ausschließlich auf die im Satz gegebene Charakterisierung einer gewichteten Teilmenge zurückgreifen, d.h. den obigen Satz als Definition des Begriffes der Teilmenge ansehen.

Satz 3.9. (Die übrigen Rechenregeln der Mengenalgebra) (1) A ⊂ A.

(2) A ⊂ B und B ⊂ C ⇒ A ⊂ C.

(3) A ⊂ B und B ⊂ A ⇒ A = B.

(4) A ∩ B ⊂ A.

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

(6) A ⊂ A ∪ B.

(7) A ∪ A = A.

(8) A ⊂ B ⇔ A ∪ B = B.

(9) A ⊂ B ⇒ A ∩ C ⊂ B ∩ C, A ∪ C ⊂ B ∪ C.

(10) C ⊂ A und C ⊂ B ⇒ C ⊂ A ∩ B.

(11) A ⊂ C und B ⊂ C ⇒ A ∪ B ⊂ C.

(12) ∅ ⊂ A.

(13) A ⊂ ∅ ⇒ A = ∅.

Beweis. Wir werden keine speziellen Hinweise auf die Kommutativgesetze und die Assoziativitätsgesetze geben. Alle anderen Gesetze werden, wo sie im Beweis angewendet werden, durch ihre Numerierung zitiert werden.

(1) A ∩ A = A ⇒(3.8) A ⊂ A.

(2) A ⊂ B und B ⊂ C ⇒(3.8) A ∩ B = A und B ∩ C = B ⇒ A ∩ C = (A ∩ B) ∩ C = A ∩ (B ∩ C) = A ∩ B = A ⇒(3.8) A ⊂ C.

(3) A ⊂ B und B ⊂ A ⇒ A ∩ B = A und B ∩ A = B ⇒ A = A ∩ B = B ∩ A = B.

(4) (A ∩ B) ∩ A = A ∩ (A ∩ B) = (A ∩ A) ∩ B =(3.7(7)) A ∩ B ⇒(3.8) Beh.

(5) A ∩ (A ∪ B) =(3.7(3) (b)) (A ∩ A) ∪ (A ∩ B) =(3.7(7)) A ∪ (A ∩ B) =(3.7(6)) A.

(6) A ∩ (A ∪ B) = A ⇒(3.8) Beh.

(7) A ∪ A =(3.7(7)) A ∪ (A ∩ A) =(3.7(6)) A.

(8) A ⊂ B ⇒(3.8) A∩B = A ⇒ (A∪B)∩B =(5) (A∩B)∪B = A ∪ B ⇒(3.8) A ∪ B ⊂ B und (6) ⇒ A ∪ B = B. Umgekehrt gilt A ∩ B = A ∩ (A ∪ B) =(5) A ⇒(3.8) A ⊂ B.

(9) A ∩ C ∩ B ∩ C = A ∩ B ∩ C ∩ C = A ∩ C, A ∪ C ∪ B ∪ C = A ∪ B ∪ C ∪ C =(8) B ∪ C ⇒(8) Beh.

(10) C ⊂ A und C ⊂ B ⇒(3.8) C ∩ A = C und C ∩ B = C ⇒ C ∩ (A ∩ B) = (C ∩ A) ∩ B = C ∩ B = C ⇒(3.8) C ⊂ A ∩ B.

(11) A ⊂ C und B ⊂ C ⇒(8) A ∪ C = C und B ∪ C = C ⇒ (A ∪ B) ∪ C = A ∪ (B ∪ C) = A ∪ C = C ⇒(8) A ∪ B ⊂ C.

(12) ∅ ∩ A = ∅(3.7(5)) ⇒(3.8) Beh.

(13) A ⊂ ∅ ⇒(3.8) A = A ∩ ∅ =(3.7(5)) ∅.

Wenn die Menge G bezüglich weiterer Verknüpfungen abgeschlossen, wenn also weitere Abbildungen G × G ⟶ G (außer max und min) gegeben sind, so übertragen sich diese jeweils auch auf entsprechend gewichtete Mengen. So haben wir die disjunkte Vereinigung von Multimengen oben aus der Addition in den natürlichen Zahlen erhalten. Da sowohl ℕ_{0} als auch [0, 1] als auch {0, 1} gegenüber der Multiplikation abgeschlossen sind, kann man das Produkt von diesen gewichteten Mengen bilden durch χ_{A·B} := χ_{A} · χ_{B}, ebenso die Potenz χ_{A^{p}} := (χ_{A})^{p}. Das Produkt entspricht allerdings nicht dem in 2 besprochenen (kartesichen) Produkt von Mengen. Für gewöhnliche Mengen, also für G = {0, 1}, ist das so definierte Produkt der Durchschnit wegen χ_{A} · χ_{B} = min(χ_{A}, χ_{B}). Insbesondere ist χ_{A}^{p} = χ_{A}.

Bei Fuzzy-Mengen nennt man das Quadrat A^{2} einer Fuzzy-Menge A auch ihre Konzentration. Dann ist A^{2} ⊂ A, weil alle Werte von χ_{A} kleiner als 1 sind. Man verwendet A^{2} oft, um eine stärkere Eigenschaft ”sehr“ auszudrücken. In unserem Beispiel der warmen Temperaturen nennt man dann die Fuzzy-Menge der Temperaturen

χ_{W^{2}}(x) = \begin{cases}0, & für x ≤ 8, \\ 4 (\frac{x − 8}{24})^{4} , & für 8 ≤ x ≤ 20, \\ (1 − 2 (\frac{x − 32}{24})^{2})^{2}, & für 20 ≤ x ≤ 32, \\ 1 & für 32 ≤ x. \end{cases}

”sehr warm“. Wenn man vereinbart, eine Temperatur erst ab einem Grad der Zugehörigkeit von 0.5 als warm zu bezeichnen, so sind die Temperaturen über 20^{∘} C als ”warm“ zu bezeichnen und die Temperaturen über 22.8^{∘} C als ”sehr warm“.

Wenn das Universum U als Menge aller Menschen gewählt wird und die Fuzzy- Mengen A der alten Menschen und J der jungen Menschen bekannt ist, dann kann man die Fuzzy-Mengen A^{2} der sehr alten Menschen, J^{2} der sehr jungen Menschen, A^{1/2} der etwas älteren Menschen, J^{1/2} der mehr oder weniger jungen Menschen, U \ J^{2} der nicht sehr alten Menschen usw. bilden, wobei A \ B definiert ist durch χ_{A\B} := max(χ_{A} − χ_{B}, 0) und U durch χ_{U} = 1.

Definition 3.10. Seien A_{1}, …, A_{n} gewichtete Mengen in den Universen U_{1}, …, U_{n}. Das kartesische Produkt A_{1} ×…×A_{n} der Mengen A_{1}, …, A_{n} wird definiert durch

χ_{A_{1}×...×A_{n}}(u_{1}, …, u_{n}) := min(χ_{A_{1}}(u_{1}), …, χ_{A_{n}}(u_{n})).

Gelegentlich verwendet man bei der Definition des Durchschnitts statt des Minimums auch das Produkt in G. Dann verwendet man bei der Definition des kartesischen Produkts ebenfalls das Produkt in G, also χ_{A_{1}×...×A_{n}}(u_{1}, …, u_{n}) := χ_{A_{1}}(u_{1}) · . . . · χ_{A_{n}}(u_{n}).

Definition 3.11. Sei U = U_{1} × … × U_{n} ein (mengentheoretisches oder kartesisches) Produkt von Universen. Eine gewichtete Relation R ist eine gewichtete (Teil-)Menge von U. Ist n = 2, so heißt die gewichtete Relation R auch gewichtete binäre Relation. Die Komposition oder Verknüpfung R ∘ S (in U × W) von gewichteten binären Relationen R in U × V und S in V × W wird definiert durch

χ_{R∘S}(u, w) := max{min(χ_{R}(u, v), χ_{S}(v, w))|v ∈ V }.

Wir betrachten in den letzten Definitionen dieses Abschnitts nur noch Fuzzy- Mengen. Für die kann man Fuzzy-Äquivalenzrela-tionen, -Ordnungen und - Abbildungen definieren.

Definition 3.12. Eine binäre Fuzzy-Relation R in U × U heißt reflexiv, wenn ∀u ∈ U[χ_{R}(u, u) = 1], symmetrisch, wenn ∀u, u′ ∈ U[χ_{R}(u, u′) = χ_{R}(u′, u)], antisymmetrisch, wenn

∀u, u′ ∈ U[χ_{R}(u, u′) > 0 ∧ χ_{R}(u′, u) > 0 ⟹ u = u′], transitiv, wenn

∀u, u′, u′′ ∈ U[χ_{R}(u, u′′) ≥ min(χ_{R}(u, u′), χ_{R}(u′, u′′))]. Eine reflexive, symmetrische Fuzzy-Relation heißt Nähe-Bezie-hung. Eine reflexive, symmetrische und transitive Fuzzy- Relation heißt Ähnlichkeits-Relation. Der transitive Abschluß R^{+} einer reflexiven Fuzzy-Relation R ist definiert durch

R^{+} := sup(R, R^{2}, R^{3}, …, R^{n}, …)

mit R^{n+1} = R^{n} ∘ R.

Für diese Definitionen wollen wir keine weiteren Beispiele angeben. Sie haben jedoch eine weitreichende Bedeutung für die Anwendungen der Theorie der Fuzzy- Mengen. Wir schließen diesen Abschnitt mit einer Bemerkung zu Abbildungen von Fuzzy-Mengen.

Definition 3.13. Seien U und V Universen und α : U ⟶ V eine Abbildung. Sei A eine Fuzzy-Teilmenge von U. Dann ist das Bild B von A unter α : U ⟶ V definiert durch χ_{B}(b) := sup{χ_{A}(a)|α(a) = b}. (Dabei sei sup(∅) = 0.)

4. Äquivalenzrelationen

Eine besonders wichtige Art von Relationen ist die Äquivalenzrelation. Sie verallgemeinert den Begriff der Gleichheit. In sehr vielen mathematischen Begriffen ist sie im Hintergrund verborgen. So kommen die Definitionen der Menge der ganzen Zahlen, der rationalen Zahlen und der reellen Zahlen kaum ohne diesen Begriff aus. Man stelle sich eine Äquivalenzrelation so vor, daß sie lediglich gewisse Eigenschaften von Elementen überprüft und gemäß dieser Überprüfung feststellt, ob die Elemente ”gleich“ sind oder nicht. Da die Gleichheit eine ganz bestimmte logische Bedeutung hat und feststeht, ob gewisse Elemente gleich sind, dürfen wir das Ergebnis, das bei der Überprüfung von nur wenigen Eigenschaften so herauskommt, natürlich nicht auch als Gleichheit ausdrücken. Wir sagen dann, daß Elemente äquivalent sind, wenn sie sich in den überprüften Eigenschaften nicht unterscheiden. Wir werden jedoch weiter unten sehen, daß man mit Hilfe des Begriffs der Partition tatsächlich eine echte Gleichheitsrelation bei solchen Betrachtungen konstruieren kann.

Definition 4.1. Eine Äquivalenzrelation auf einer Menge A ist eine Relation ρ = (A, A, R) mit den folgenden Eigenschaften:

(1) ∀a ∈ A[(a, a) ∈ R], (Reflexivität)

(2) ∀a, b, c ∈ A[(a, b) ∈ R ∧ (b, c) ∈ R ⟹ (a, c) ∈ R], (Transitivität)

(3) ∀a, b ∈ A[(a, b) ∈ R ⟹ (b, a) ∈ R], (Symmetrie).

Wir schreiben häufig auch a ∼ b, wenn (a, b) ∈ R gilt (lies: a ist äquivalent zu b). Dann können (1), (2) und (3) auch ausgedrückt werden als

(1’) ∀a ∈ A[a ∼ a],

(2’) ∀a, b, c ∈ A[a ∼ b ∧ b ∼ c ⟹ a ∼ c], (3’) ∀a, b ∈ A[a ∼ b ⟹ b ∼ a].

Beispiele 4.2. (1) id_{A} = (A, A, {(a, a)|a ∈ A}) ist die Gleichheits- (äquivalenz-)relation. Es gilt a ∼ b ⟺ a = b. Diese Äquivalenzrelation ist wegen der Reflexivität in jeder Äquivalenzrelation auf A enthalten.

(2) (A, A, A × A) ist die totale Äquivalenzrelation. Jede weitere Äquivalenzrelation auf A ist in ihr enthalten.

(3) Für n ∈ ℤ, n ≠ 0 und a, b ∈ ℤ definieren wir

a ∼ b ⟺ n/a − b (n teilt a − b).

Dabei bedeutet n/a − b, daß es ein q ∈ ℤ gibt mit a − b = qn. Statt a ∼ b schreibt man in diesem Falle auch

a ≡ b (mod n) (a ist kongruent b modulo n).

Man rechnet leicht nach, daß dieses eine Äquivalenzrelation ist. Für die Transitivität gilt beispielsweise: a ≡ b (mod n) und b ≡ c (mod n) ⟹ ∃q_{1}, q_{2} ∈ ℤ[a − b = q_{1}n ∧ b − c = q_{2}n] ⟹ a − c = (a − b) + (b − c) = (q_{1} + q_{2})n ⟹ a ≡ c (mod n).

(4) Es gibt viele Beispiele aus der Praxis, die man hier nennen könnte. Wenn immer wir Elementen gewisse Eigenschaften zuschreiben können, können wir sagen, daß die Elemente äquivalent sind, wenn sie alle gegebenen Eigenschaften gemeinsam haben. So ist zum Beispiel der Text einer Adresse in einer Adressensammlung eine Eigenschaft. Wenn zwei Adressen in der Adressensammlung dieselben Text-Einträge haben, dann kann man sie äquivalent nennen. Eigentlich ist man bei einer Sammlung von Adressen nur an den zugehörigen Aquivalenzklassen interessiert. Ein Doppeleintrag einer Adresse an verschiedenen Stellen der Adressenliste ist uninteressant.

Wir haben anfangs dieses Abschnitts bemerkt, daß Äquivalenzrelationen häufig daraus entstehen, daß man Objekte bezüglich gewisser Eigenschaften vergleicht. Die Zuordnung einer Eigenschaft zu einem gegebenen Objekt kann aber aufgefaßt werden als eine Abbildung von der Menge aller betrachteten Objekte in die Menge der möglichen Eigenschaften (z.B. in die Menge der Farben). Wir werden jetzt sehen, daß sich allgemein aus jeder Abbildung eine Äquivalenzrelation ergibt. Es gilt nämlich

Lemma 4.3. Sei α : A ⟶ B eine Abbildung. Für a_{1}, a_{2} ∈ A sei a_{1} ∼ a_{2} :⟺ α(a_{1}) = α(a_{2}). Dieses definiert eine Äquivalenzrelation auf A.

Beweis. Reflexivität: Es gilt α(a) = α(a) für alle a ∈ A. Daraus folgt a ∼ a für alle a ∈ A.

Transitivität: Aus a ∼ b und b ∼ c folgt α(a) = α(b) und α(b) = α(c), also α(a) = α(c) und damit a ∼ c. Symmetrie: Aus a ∼ b folgt α(a) = α(b), also α(b) = α(a) und damit b ∼ a.

Das Gegenstück zum Begriff der Äquivalenzrelation ist der Begriff der Partition. Wir werden sogleich sehen, daß diese beiden Begriffe im Wesentlichen dasselbe beinhalten.

Definition 4.4. Eine Partition oder Klasseneinteilung 𝔓 ist eine Menge von nichtleeren, paarweise disjunkten Teilmengen von A, deren Vereinigung A ist, in Zeichen:

𝔓 ⊂ P(A) \ {∅} und

∀X, Y ∈ 𝔓[X ≠ Y ⟹ X ∩ Y = ∅] und
⋃{X|X ∈ 𝔓} = A.

Die Elemente X ∈ 𝔓 einer Partition heißen auch Klassen der Partition. Ein Element a ∈ X heißt ein Repräsentant der Klasse X. Eine Teilmenge R ⊂ A heißt ein vollständiges Repräsentantensystem für die Partion 𝔓, wenn für jedes X ∈ 𝔓 genau ein a ∈ R existiert mit a ∈ X. Die zweite Bedingung ∀X, Y ∈ 𝔓[X ≠ Y ⟹ X ∩ Y = ∅] wird oft auch in der gleichwertigen Form ∀X, Y ∈ 𝔓[X ∩ Y ≠ ∅ ⟹ X = Y] verwendet.

Definition 4.5. Sei ρ eine Äquivalenzrelation auf A. Wir schreiben a ∼ b für (a, b) ∈ Gr(ρ). Für a ∈ A bezeichne

ā := {b ∈ A|b ∼ a}

die Menge der zu a äquivalenten Elemente. Die Menge ā heißt Äquivalenzklasse von a. Die Menge der Äquivalenzklassen wird mit

A/∼ := {ā|a ∈ A}

(lies: A modulo ∼-Relation) bezeichnet, wenn aus dem Zusammenhang klar ist, zu welcher Äquivalenzrelation ρ das Zeichen ∼ gehört. Sonst schreibt man auch A/ρ = {ā|a ∈ A}.

Mit dieser Definition haben wir jetzt die Möglichkeit geschaffen, das Äquivalenzzeichen durch das Gleichheitszeichen auszudrücken. Mit Teil (1) des folgenden Lemmas wird klar, daß durch das Zusammenfassen von Elementen mit gemeinsamen Eigenschaften, d.h. von Elementen, die äquivalent sind, wir tatsächlich von Gleichheit (nämlich der Äquivalenzklassen) sprechen können, wenn zwei Elemente lediglich äquivalent sind.

Lemma 4.6. Sei ρ eine Äquivalenzrelation auf A. Dann gelten (1) a ∼ b ⟺ a ∈ b̄ ⟺ ā = b̄ für alle a, b ∈ A.

(2) A/∼ ist eine Partition, die sogenannte Äquivalenzklasseneinteilung.

Beweis. (1) Sei ā ⊂ b̄. Dann gilt sofort a ∈ ā ⊂ b̄. Daraus folgt ebenso unmittelbar a ∼ b. Gilt nun a ∼ b und ist c ∈ ā, so ist c ∼ a, also wegen der Transitivität c ∼ b oder c ∈ b̄, womit ā ⊂ b̄ bewiesen ist. Damit sind die Aussagen a ∼ b, a ∈ b̄ und ā ⊂ b̄ äquivalent. Da aber a ∼ b genau dann gilt, wenn b ∼ a gilt, folgt auch ā = b̄.

(2) Wenn ā ∈ A/∼ , dann ist a ∈ ā, also ā ≠ ∅. Ist ā∩b̄ ≠ ∅, dann wählen wir ein c ∈ ā ∩ b̄ und es folgt c ∼ a und c ∼ b, also auch a ∼ b oder nach (1) ā = b̄. Schließlich ist jedes a ∈ A Element in einer Äquivalenzklasse: a ∈ ā. Also ist A ⊂ ⋃{ā|a ∈ A} ⊂ A, d.h. A = ⋃{ā|a ∈ A}.

Wir kommen jetzt zu dem Eingangs dieses Paragraphen erwähnten Zusammenhang zwischen Äquivalenzrelationen und Partionen. Es ist nach dem folgenden Satz gleichgültig, ob auf einer Menge A eine Äquivalenzrelation oder eine Partition vorgegeben wird. Man kann jeweils die eine Angabe in die andere umrechnen.

Satz 4.7. Bezeichne R_{A} die Menge aller Äquivalenzrelationen auf A und P_{A} die Menge aller Partitionen auf A. Dann ist

Φ : R_{A} ∋ ρ ↦ A/ρ ∈ P_{A}

eine bijektive Abbildung.

Beweis. Wir definieren die Umkehrabbildung Ψ : P_{A} ⟶ R_{A}. Sei 𝔓 ∈ P_{A} eine Partition. Wir definieren die zugehörige Äquivalenzrelation Ψ(𝔓) durch a ∼_{𝔓} b :⟺ ∃X ∈ 𝔓[a, b ∈ X]. Dann gelten ∀a ∈ A[a ∼_{𝔓} a], weil A = ⋃{X|X ∈ 𝔓}, ∀a, b, c ∈ A[a ∼_{𝔓} b ∧ b ∼_{𝔓} c ⟹ a ∼_{𝔓} c] wegen X ≠ Y ⟹ X ∩ Y = ∅ und ∀a, b ∈ A[a ∼_{𝔓} b ⟹ b ∼_{𝔓} a] unmittelbar aus der Definition. Damit ist eine Abbildung Ψ : P_{A} ⟶ R_{A} definiert. Wir zeigen jetzt, daß die Komposition ΦΨ : P_{A} ⟶ R_{A} ⟶ P_{A} die Identität ist. Sei dazu 𝔓 ∈ P_{A} gegeben und ∼_{𝔓} durch 𝔓 induziert. Sei ā ∈ A/∼ und a ∈ ā ein Repräsentant. Dann gilt ā = {b|b ∼_{𝔓} a} = {b|∃X ∈ 𝔓[a, b ∈ X]} = X, denn es gibt nur ein X ∈ 𝔓 mit a ∈ X. Also gilt (A/ ∼ ) ⊂ 𝔓. Ist aber X ∈ 𝔓 und a ∈ X, so ist X = ā wie zuvor, also gilt (A/∼ ) = 𝔓. Es bleibt zu zeigen, daß auch ΨΦ : R_{A} ⟶ P_{A} ⟶ R_{A} die Identität ist. Das folgt unmittelbar daraus, daß für ∼ ∈ R_{A} und 𝔓 die zugehörige Partition der Äquivalenzklassen gilt ∃c̄[a, b ∈ c̄] ⟺ a ∼ b.

Beispiel 4.8. Die Äquivalenzklassen der Äquivalenzrelation modulo n auf ℤ (Beispiel 4.2 (3)) sind von der Form ā = {a, a ± n, a ± 2n, … } = a + n · ℤ.

Nachdem wir neue Elemente eingeführt haben, die Äquivalenzklassen, deren Gleichheit die Äquivalenzrelation ausdrückt, wollen wir jetzt untersuchen, wie Abbildungen mit diesen neuen Elementen fertig werden. Ein besonders wichtiger Satz in diesem Zusammenhang ist der Faktorisierungssatz. Er wird in späteren Kapiteln sehr häufig verwendet werden.

Der Satz ist durch die folgende Fragestellung motiviert. Wir betrachten rationale Zahlen an der Form

\frac{a}{b} ∈ ℚ.

Ein rationale Zahl ist also durch ein Paar (a, b) ∈ ℤ × (ℤ \ {0}) gegeben. Dabei ist b ≠ 0, weil es im Nenner steht. Es gibt aber verschiedene Paare (a, b) ≠ (c, d), die dieselbe rationale Zahl \frac{a}{b} = \frac{c}{d} beschreiben. Zwei Paare (a, b) und (c, d) beschreiben genau dann dieselbe rationale Zahl, wenn gilt ad = cb. Dadurch wird eine Äquivalenzrelation definiert, wie man leicht nachrechnet, oder durch Anwendung von 4.3 sieht. Wenn wir uns nun auf den Standpunkt stellen, daß die ganzen Zahlen schon mit ihren Rechenregeln bekannt sind, nicht jedoch die rationalen Zahlen, so könnte man die rationalen Zahlen gerade durch Äquivalenzklassen bezüglich dieser Äquivalenzrelation definieren: eine rationale Zahl ist eine Äquivalenzklasse eines Paares (a, b) und wir schreiben für die zugehörige Äquivalenzklasse auch \frac{a}{b}. Tatsächlich werden so die rationalen Zahlen später eingeführt.

Ein Problem ergibt sich nun mit der Addition. Wir wollen lediglich den Spezialfall ℚ ∋ \frac{a}{b} ↦ \frac{a}{b} + \frac{1}{2} = \frac{2a+b}{2b} ∈ ℚ betrachten. Um zu zeigen, daß dieses eine Abbildung ist, müssen wir z.B. zeigen, daß \frac{2}{4} + \frac{1}{2} = \frac{1}{2} + \frac{1}{2}, oder allgemeiner, daß für verschieden dargestellte rationale Zahlen \frac{a}{b} = \frac{c}{d} das Ergebnis der Addition \frac{2a+b}{2b} = \frac{2c+d}{2d} gleich wird, sonst kann die Addition keine Abbildung werden. Wir haben nämlich das Ergebnis der Addition unter Benutzung von den einzelnen Zahlen a und b beschrieben. Zu diesem Zweck definieren wir die Abbildung zunächst auf ℤ × (ℤ \ \{0\}) ∋ (a, b) ↦ \frac{2a+b}{2b} ∈ ℚ. Das ist sicherlich eine Abbildung. Es ergibt sich die Frage, ob wir daraus dann eine Abbildung ℚ ⟶ ℚ bilden können. Das tut der folgende Satz.

Satz 4.9. (Faktorisierungssatz) Sei α : A ⟶ B eine Abbildung und ∼ eine Äquivalenzrelation auf A mit der Eigenschaft

∀a, b ∈ A[a ∼ b ⟹ α(a) = α(b)],

(d.h. α ist konstant auf den Äquivalenzklassen). Dann gibt es genau eine Abbildung ᾱ : A/∼ ⟶ B, so daß das Diagramm

[figure: A; A/∼; ν; α; B; ᾱ]

mit ν(a) := ā kommutiert, d.h. ᾱν = α. Die Abbildung ν ist surjektiv und heißt kanonische Surjektion oder Restklassenabbildung.

Mit Hilfe dieses Satzes bekommen wir nun sofort die gewünschte Abbildung ℚ ∋ \frac{a}{b} ↦ \frac{a}{b} + \frac{1}{2} = \frac{2a+b}{2b} ∈ ℚ, denn wenn (a, b) ∼ (c, d) gilt, so ist ad = cb, also folgt (2a+b)2d = 4ad+2bd = 4cb+2bd = (2c + d)2b und damit auch \frac{2a+b}{2b} = \frac{2c+d}{2d}.

Folgerung 4.10. (1) Unter den Voraussetzungen von 4.9 ist ᾱ genau dann injektiv, wenn

∀a, b ∈ A[a ∼ b ⟺ α(a) = α(b)],

d.h. wenn die Äquivalenzrelation die von α gemäß 4.3 induzierte Äquivalenzrelation ist. Insbesondere läßt sich jede Abbildung α in ein Produkt ᾱν = α einer surjektiven mit einer injektiven Abbildung zerlegen.

(2) Ist α im Satz surjektiv, so ist auch ᾱ surjektiv.

(3) Ist ∼ die durch α induzierte Äquivalenzrelation, so gibt es eine bijektive Abbildung zwischen A/∼ und Bi(α).

Beweis der Folgerung.

(1) α injektiv ⟺ ∀a, b ∈ A[ᾱ(ā) = ᾱ(b̄) ⟹ ā = b̄] ⟺ ∀a, b ∈ A[ᾱν(a) = ᾱν(b) ⟹ a ∼ b]

⟺ ∀a, b ∈ A[α(a) = α(b) ⟹ a ∼ b],

die fehlende Implikation.

(2) Wenn α surjektiv ist, dann ist jedes Element von B im Bild von α = ᾱν, insbesondere also auch im Bild von ᾱ. Damit ist auch ᾱ surjektiv.

(3) Ist α : A ⟶ B gegeben, so sei α′ : A ⟶ Bi(α) die Einschränkung der Abbildung α auf das Bild, die surjektiv ist. α und α′ definieren dieselbe Äquivalenzrelation auf A. Also ist ᾱ′ : A/ ∼ ⟶ Bi(α) injektiv und surjektiv und damit bijektiv.

Beweis des Satzes. Wir definieren ᾱ(ā) := α(a). Um zu zeigen, daß ᾱ damit eine Abbildung wird, muß festgestellt werden, daß es zu ā nur ein Paar (ā, α(a)) in Gr(ᾱ) gibt, daß also α(a) nicht von der Wahl des Repräsentanten a ∈ ā abhängt. Seien (ā, α(a)), (b̄, α(b)) mit ā = b̄ gegeben. Dann folgt a ∼ b und damit nach Voraussetzung des Satzes α(a) = α(b). Damit ist ᾱ : A/∼ ⟶ B eine Abbildung. Weiter gilt α(a) = ᾱ(ā) = ᾱν(a) für alle a ∈ A, also α = ᾱν. Ist β : A/∼ ⟶ B eine weitere Abbildung mit α = βν, so gilt β(ā) = βν(a) = α(a) = ᾱ(ā) für alle ā ∈ A/∼ , also ist ᾱ = β.

5. Ordnungen

In diesem letzten Paragraphen des Kapitels führen wir noch kurz den Begriff der Ordnung ein. Er wird uns später vor allem in zwei Beispielen begegnen, bei Zahlenmengen und bei Potenzmengen.

Definition 5.1. Eine Ordnung (oder Anordnung) (gelegentlich auch: teilweise oder partielle Ordnung) auf einer Menge A ist eine Relation ρ = (A, A, R) mit folgenden Eigenschaften:

(1) ∀a ∈ A[(a, a) ∈ R], (Reflexivität)

(2) ∀a, b, c ∈ A[(a, b) ∈ R ∧ (b, c) ∈ R ⟹ (a, c) ∈ R], (Transitivität)

(3) ∀a, b ∈ A[(a, b) ∈ R ∧ (b, a) ∈ R ⟹ a = b], (Antisymmetrie).

Wir führen die übliche Bezeichnungsweise für die Ordnungsrelation ein. Für Elemente a, b ∈ A schreiben wir

\begin{aligned}a ≤ b & :⟺ & (a, b) ∈ R, \\ a < b & :⟺ & a ≤ b ∧ a ≠ b, \\ a ≰ b & :⟺ & (a, b) ∉ R. \end{aligned}

Weiter verwenden wir wie üblich die Zeichen in umgekehrter Richtung, also z.B. b ≥ a :⟺ a ≤ b. Die Eigenschaften (1), (2), (3) können dann in folgender Form geschrieben werden:

(1’) ∀a ∈ A[a ≤ a],

(2’) ∀a, b, c ∈ A[a ≤ b ∧ b ≤ c ⟹ a ≤ c], (3’) ∀a, b ∈ A[a ≤ b ∧ b ≤ a ⟹ a = b].

Eine geordnete Menge ist ein Paar (A, ≤), bestehend aus einer Menge A und einer Ordnung ≤ = (A, A, R) auf der Menge A.

Beispiele 5.2. (1) Ist (A, ≤) eine geordnete Menge und B ⊂ A eine Teilmenge, so ist (B, B, R∩(B ×B)) ebenfalls eine Ordnung.

(2) Die Gleichheitsrelation ist eine Ordnung.

(3) Die Potenzmenge einer Menge ist durch ⊂ geordnet.

Definition 5.3. Sei (A, ≤) eine geordnete Menge.

(1) a_{0} ∈ A heißt maximales (minimales) Element in A genau dann, wenn gilt:

\begin{matrix}∀a ∈ A[a_{0} ≤ a ⟹ a_{0} = a] \\ (∀a ∈ A[a ≤ a_{0} ⟹ a = a_{0}]). \end{matrix}

(2) a_{0} ∈ A heißt größtes (kleinstes) Element in A genau dann, wenn gilt:

∀a ∈ A[a ≤ a_{0}] (∀a ∈ A[a_{0} ≤ a]).

(3) a_{0} ∈ A heißt obere (untere) Schranke der Teilmenge B in A genau dann, wenn gilt:

∀b ∈ B[b ≤ a_{0}] (∀b ∈ B[a_{0} ≤ b]).

(4) Sei B ⊂ A. Besitzt die Menge der oberen Schranken von B in A ein kleinstes Element, so heißt dieses kleinste obere Schranke oder Supremum von B in A, in Zeichen sup(B).

(5) Besitzt die Menge der unteren Schranken von B in A ein größtes Element, so heißt dieses größte untere Schranke oder Infimum von B in A, im Zeichen inf(B).

Bemerkung 5.4. Eine geordnete Menge (A, ≤) braucht weder maximale noch minimale Elemente zu enthalten (z.B. (ℝ, ≤)). Wenn A ein größtes Element besitzt, so ist dieses eindeutig bestimmt und ein maximales Element von A. Wenn A genau ein maximales Element besitzt, so braucht dieses kein größtes Element zu sein (z.B. ℕ ∪ {x} mit n ≤ x für n ≤ 2). A kann viele maximale Elemente besitzen (z.B. Gleichheitsrelation auf A).

Definition 5.5. Eine geordnete Menge (A, ≤) heißt total geordnet oder eine Kette, wenn

(4) ∀a, b ∈ A[a ≤ b ∨ b ≤ a].

Beispiele 5.6. (1) (ℝ, ≤) ist totalgeordnet.

(2) Jede Teilmenge einer totalgeordneten Menge ist totalgeordnet.

(3) (ℕ, ≤) ist totalgeordnet.

(4) Sind A und B totalgeordnete Mengen, so ist auch A × B total geordnet mit der lexikographischen Ordnung

(a, b) ≤ (a′, b′) ⟺ (a < a′) ∨ (a = a′ ∧ b ≤ b′)).