Benutzer:Jürgen-Michael Glubrecht/Mengen und Klassen

Hoch zum Inhaltsverzeichnis

Mengen und Klassen

Du wirst dich vielleicht schon gewundert haben, warum wir die Cantorsche Mengendefinition „naiv“ genannt haben. Auf den ersten Blick sieht die Definition gut aus und bisher sind keine Probleme aufgetreten. Was sollte also schiefgehen?

Russells Antinomie

Ein Beispiel ist Russells Antinomie, die Bertrand Russell 1903 publizierte:

Beispiel (Russellsche Antinomie)

${\mathcal {R}}$ sei die Menge aller Mengen, die sich nicht selbst enthalten. Dann ist ${\mathcal {R}}$ keine sinnvolle Menge.

Formalisiert sieht die Definition von ${\mathcal {R}}$ so aus:

Definition (Russellsche Klasse)

${\mathcal {R}}:=\{x\,|\,x\notin x\rbrace$

Frage: Wieso definiert ${\mathcal {R}}=\{x\,|\,x\notin x\}$ keine sinnvolle Menge?

Stelle dir vor, es gäbe eine Menge ${\mathcal {R}}$, die alle Mengen enthält, die sich nicht selbst enthalten. Ist dann ${\mathcal {R}}\in {\mathcal {R}}$?

Wäre ${\mathcal {R}}$ ein Element von sich selbst, dann muss ${\mathcal {R}}$ die definierende Bedingung $x\notin x$, erfüllen, also ist ${\mathcal {R}}$ doch kein Element von sich selbst   ↯.

Ist ${\mathcal {R}}\notin {\mathcal {R}}$, dann ist nach Definition von ${\mathcal {R}}$ gerade ${\mathcal {R}}\in R$   ↯.

Wir erhalten also sowohl für ${\mathcal {R}}\in {\mathcal {R}}$ als auch für ${\mathcal {R}}\notin {\mathcal {R}}$ einen Widerspruch. Damit kann ${\mathcal {R}}$ keine sinnvolle Menge sein.

Bereits Cantor kannte ähnliche Antinomien. Er glaubte aber nicht, dass seine Definition geändert werden müsse. Er unterteilte hierzu Mengen in konsistente Vielheiten, bei denen eine Zusammenfassung zu einem Ganzen möglich ist und in inkonsistente Vielheiten, bei denen dies nicht der Fall ist. Da in Cantors Mengendefinition ausdrücklich von „Zusammenfassungen zu einem Ganzen“ die Rede ist, werden laut Cantor Mengenausdrücke ausgeschlossen, die nicht sinnvoll eine Menge definieren.

Bertrand Russell kleidete die nach ihm benannte Antinomie später in folgende Form:

Der Dorfbarbier ist derjenige, der alle Männer im Dorf rasiert, die sich nicht selbst rasieren. Frage: Rasiert der Dorfbarbier sich selbst?

Antwort: Der Dorfbarbier ist eine Frau! Und diese Antwort hilft uns hier aus dem Dilemma. Völlig egal ob sie sich nun selbst rasiert oder nicht, entscheidend ist, dass sie kein Mann des Dorfs ist.

Formal lässt sich das so darstellen:

(1)   Allgemein gilt:   $\forall x:(x\in {\mathcal {R}}\Leftrightarrow x\notin x)$

(2)   Setzen wir ${\mathcal {R}}$ für $x$ ein, folgt:   ${\mathcal {R}}\in {\mathcal {R}}\Leftrightarrow {\mathcal {R}}\notin {\mathcal {R}}$

(3)   Widerspruch:   ↯

Und nun sehen wir genau, wo das Problem entsteht: wir dürfen ${\mathcal {R}}$ nicht einfach für die Variable $x$ einsetzen. Das ist nur dann erlaubt, wenn ${\mathcal {R}}$ zum Variablenbereich von $x$ gehört.

Definition (Variablenbereich, Allklasse)

${\mathcal {V}}=\{x\,|\,x=x\rbrace$

Mit dieser Definition sieht die korrekte Argumentation dann so aus:

(1)   Allgemein gilt:   $\forall x:(x\in {\mathcal {R}}\Leftrightarrow x\notin x)$

(2)   Setzen wir ${\mathcal {R}}$ für $x$ ein, folgt:   ${\mathcal {R}}\in {\mathcal {V}}\Rightarrow ({\mathcal {R}}\in {\mathcal {R}}\Leftrightarrow {\mathcal {R}}\notin {\mathcal {R}})$

(3)   Logische Folgerung für $\Rightarrow$:   ${\mathcal {R}}\notin {\mathcal {V}}$

Die Russelsche Klasse ${\mathcal {R}}$ kann also nicht zum Variablenbereich ${\mathcal {V}}$ gehören!

Russell entwickelte zur Lösung des Problems von 1903 bis 1908 eine Typentheorie, in der die Klassenbildung stark eingeschränkt wurde. In der Mathematik durchgesetzt hat sich ein freizügiger Gebrauch von $\{x\,|\,\dotsm \}$. Das ist möglich, wenn zwischen Klassen und Mengen unterschieden wird.

Klassen

Die Russellsche Antinomie lehrt, dass die Operation $\{x\,|\,\dotsm \}$ aus dem Variablenbereich hinausführen kann! Das ist beispielsweise bei der Subtraktion auf den natürlichen Zahlen genauso. Sind $a$ und $b$ zwei natürliche Zahlen, so ist die Differenz $(a-b)$ keineswegs immer eine natürliche Zahl. Vielmehr liefert die Differenz neue Objekte, nämlich die negativen ganzen Zahlen.

Da von Mengen erwartet wird, dass sie zum Variablenbereich gehören, werden die mit $\{x\,|\,\dotsm \}$ erzeugten Objekte Klassen genannt.

Hinweis

Ist $A(x)$ eine Aussageform, so ist $\{x\,|\,A(x)\}$ eine Klasse.

Der Zusammenhang zwischen der Klassenbildung $\{x\,|\,\dotsm \}$ und der Elementrelation $\in$ wird Abstraktionsprinzip genannt. Es wurde bereits im Kapitel Mengenschreibweisen beschrieben:

Abstraktionsprinzip

$\forall y:\left(y\in \{x\,\vert A\left(x\right)\}\Leftrightarrow A\left(y\right)\right)$

Es definiert die Klassenbildung, wie wir jetzt – vorsichtig geworden! – anstelle von Mengenbildung sagen.

Mengen sind spezielle Klassen und alles, was wir bisher über Mengen gesagt haben, gilt auch für Klassen. Klassen, die keine Mengen sind, werden echte Klassen genannt. Russels Antinomie lehrt also, dass es echte Klassen gibt. Mit der Unterscheidung zwischen Klassen und Mengen konnten wir die Russellsche Antinomie auflösen. Aber was macht uns sicher, dass nicht irgendwelche Widersprüche an anderer Stelle auftreten?

Minimales Modell für die Klassen

Dazu betrachten wir ein ganz einfaches Modell der Klassenbildung $\{x\,|\,\dotsm \}$ und der Elementrelation $\in$. Der Variablenereich ${\mathcal {V}}$ hat nur eine einziges Element $a$. Es gibt ein weiteres Objekt $b$, dass ausserhalb von ${\mathcal {V}}$ liegt. Weitere Objekte gibt es nicht. Der einelementige Bereich ${\mathcal {V}}$ hat genau zwei Teilklassen: die leere Klasse $\emptyset$ und die Klasse ${\mathcal {V}}$. Für die Elementrelation $\in$ gibt es zwei Möglichkeiten:

Verständnisaufgabe: Welche Beziehungen mit $=$ und $\in$ gelten in den beiden Fällen zwischen $a$, $b$, $\emptyset$, ${\mathcal {V}}$ und ${\mathcal {R}}$?

1. $a\notin a$
2. $a\in a$

Lösungen:

1. Ist   $a\notin a$   so ist   a = $\emptyset$ := $\{x\,|\,x\neq x\}$   und   $a\in b$ = $\{a\}$ = ${\mathcal {V}}$ = ${\mathcal {R}}$.
2. Ist   $a\in a$   so ist   a = $\{a\}$ = ${\mathcal {V}}$   und   $a\notin b$ = $\emptyset$ = ${\mathcal {R}}$.

Die beiden Modelle für $\{x\,|\,\dotsm \}$ zeigen, dass wir von keiner Klasse erwarten können, dass sie eine Menge ist, das heisst, dass sie im Varablenbereich liegt. Viele Teile der Mathematik kommen mit der hier vorgestellten naiven Mengenlehre (die genauer Klassenlehre heissen sollte, wie wir jetzt wissen) aus. Doch für viele andere Teile der Mathematik werden Mengen benötigt oder sind zumindest hilfreich. Die Existenz von Mengen wird durch Axiome gewährleistet, die sicherstellen, dass bestimmte Klassen Mengen sind. Solche Axiome werden wir im nächsten Abschnitt vorstellen.

Zuvor wollen wir die formale Sprache genauer festlegen, die wir hier verwenden. Das ist deshalb wichtig, weil die Klassenbildung $\{x\,|\,A(x)\}$ davon abhängt, welche Aussageformen $A(x)$ wir zur Verfügung haben.

Wir legen eine Sprache zu Grunde, die folgendes enthält:

• die Variablen $x,y,z,\dotsc$
• die Junktoren $\neg ,\land ,\lor ,\Rightarrow ,\Leftrightarrow$
• die Quantoren $\forall ,\exists$
• die Klassenbildung $\{\;|\;\}$
• die Relationen $=,\in$

Aussagenformen bezeichnen wir mit $A(x),B(y),C(z),\dots$ und Klassen mit ${\mathcal {M}},{\mathcal {N}},{\mathcal {K}},\dots$.
Die Russelsche Klasse ${\mathcal {R}}:=\{x\,|\,x\in x\}$, die Allklasse ${\mathcal {V}}:=\{x\,|\,x=x\}$ und die leere Klasse $\emptyset :=\{x\,|\,x\neq x\}$ haben wir bereits definiert. In der Literatur werden Sprachen, die die Klassenbildung erlauben, Klassenlogik genannt.

Hinweis

Wir nennen die Klasse ${\mathcal {K}}$ dann eine Menge, wenn sie im Variblenbereich, also in der Allklasse liegt: ${\mathcal {K}}\in {\mathcal {V}}$.

Axiomatische Mengenlehre

Es wurden verschiedene axiomatische Mengenlehren entwickelt. Die aktuell gebräuchlichste ist die Zermelo-Fraenkel-Mengenlehre ZFC. Sie ist nach den beiden deutschen Mathematikern Ernst Zermelo und Abraham Fraenkel benannt, die sie von 1908 bis 1922 entwickelten. Das C in der Bezeichnung steht für "Axiom of Choice" (Auswahlaxiom). Die Axiome von ZFC sorgen dafür, dass viele Klassen Mengen sind. So viele, dass sie für die Mathematik ausreichen.

Das erste Axiom gilt bereits für Klassen:

Extensionalität

$\forall x:(x\in {\mathcal {M}}\Leftrightarrow x\in {\mathcal {N}})\Rightarrow {\mathcal {M}}={\mathcal {N}}$

Das besagt, dass zwei Klassen – und damit auch zwei Mengen! – gleich sind, wenn sie dieselben Elemente haben. Die Extensionalität haben wir bereits im 1. Kapitel der Mengenlehre kennen gelernt. Die umgekehrte Richtung ($\Leftarrow$) gilt auch, das ergibt sich aus den Eigenschaften von $=$.

Folgerung: ${\mathcal {K}}$ sei eine beliebige Klasse. Dann gilt: ${\mathcal {K}}=\{x\,|\,x\in {\mathcal {K}}\}$

Wir setzen $x\in {\mathcal {K}}$ für $A(x)$. Dann folgt aus dem Abstraktionsprinzip $\forall y:(y\in {\mathcal {K}}\Leftrightarrow y\in \{x\,|\,x\in {\mathcal {K}}\})$. Mit der Extensionalität erhalten wir ${\mathcal {K}}=\{x\,|\,x\in {\mathcal {K}}\}$. ✔

Verständnisfrage: ${\mathcal {K}}$ sei eine echte Klasse. Dann gilt: $\{{\mathcal {K}}\}=\emptyset$

Nach Definition der Einerklasse gilt $\{{\mathcal {K}}\}=\{x\,|\,x={\mathcal {K}}\}$ und die Elemente von Klassen sind Mengen. ${\mathcal {K}}$ ist aber eine echte Klasse, es gilt also $\forall x:x\neq {\mathcal {K}}$. ✔

Um die nächsten Axiome zu verstehen, hilft die Vorstellung, dass Mengen kleine Klassen sind.

Leere Menge

$\emptyset \in {\mathcal {V}}$

Die leere Klasse ist eine Menge.

Paarmengen

$\forall x,y:\{x,y\}\in {\mathcal {V}}$

Alle Klassen mit zwei Elementen sind Mengen. Da wir ja $x=y$ wählen können, sind auch die Klassen mit einem Element Mengen: $\forall x:\{x\}\in {\mathcal {V}}$.

Wir definieren die Vereinigung von ${\mathcal {K}}$ so: $\bigcup {\mathcal {K}}:=\{x\,|\,\exists y\in {\mathcal {K}}:x\in y\}$. Die Vereinigung sammelt also die Elemente der Elemente von ${\mathcal {K}}$. Die Vereinigung einer Zweierklasse ist gerade die Vereinigung der beiden Elemente: $\bigcup \{x,y\}=x\cup y$

Vereinigung

$\forall x:\bigcup x\in {\mathcal {V}}$

Die Vereinigung einer Menge ist wieder eine Menge. Insbesondere ist $x\cup y$ eine Menge.

Aufgabe: Zeige mit Hilfe des Axiom für Paarmengen: $\bigcup {\mathcal {V}}={\mathcal {V}}$.

Für jede Klasse gilt ${\mathcal {K}}\subseteq {\mathcal {V}}$, also auch $\bigcup {\mathcal {V}}\subseteq {\mathcal {V}}$.

Sei nun $x\in {\mathcal {V}}$. Aus dem Axiom für Paarmengen folgt $\{x\}\in {\mathcal {V}}$, also gibt es eine Menge aus ${\mathcal {V}}$, nämlich $\{x\}$ mit $x\in \{x\}\in \bigcup {\mathcal {V}}$. Das zeigt ${\mathcal {V}}\subseteq \bigcup {\mathcal {V}}$.

Beides zusammen ergibt $\bigcup {\mathcal {V}}={\mathcal {V}}$ ✔

Verständnisfrage: Es gilt $\bigcup \emptyset =\emptyset$. Werden für den Beweis Axiome für Mengen benötigt?

Nein, denn die leere Klasse hat keine Elemente, also $\bigcup \emptyset$ auch nicht. ✔

Aufgabe: Zeige: $\forall x_{1},x_{2},\dotsc ,x_{n}:\{x_{1},x_{2},\dotsc ,x_{n}\}\in {\mathcal {V}}$.

Die Einermengen $\{x_{1}\}$, $\{x_{2}\}$, usw. sind alle in ${\mathcal {V}}$. Dann bilden wir die Vereinigung $\{x_{1}\}\cup \{x_{2}\}$, anschliessend $(\{x_{1}\}\cup \{x_{2}\})\cup x_{3}$ usw. ✔

Der Durchschnitt von ${\mathcal {K}}$ wird so definiert: $\bigcap {\mathcal {K}}:=\{x\,|\,\forall y\in {\mathcal {K}}:x\in y\}$. Hier werden die Elemente gesammelt, die in allen Elementen von ${\mathcal {K}}$ legen. Der Durchschnitt einer Zweierklasse ist der Durchschnitt seiner beiden Elemente: $\bigcap \{x,y\}=x\cap y$

Verständnisfrage: Es gilt $\bigcap \emptyset ={\mathcal {V}}$. Warum?

Dazu müssen wir uns die Definition von $\bigcup \emptyset$ genau anschauen: $\{x\,|\,\forall y\in \emptyset :x\in y\}$ steht für $\{x\,|\,\forall y:y\in \emptyset \Rightarrow x\in y\}$. Die Prämisse von $\Rightarrow$ ist immer falsch, daher ist die Implikation immer wahr, vgl. Wahrheitstabelle von von $\Rightarrow$. Daher erfüllen alle $x$ die definierende Bedingung für $\bigcup \emptyset$. ✔

Aufgabe: Zeige: $\bigcap {\mathcal {V}}=\emptyset$.

Nach dem Axiom über die leere Menge gilt $\emptyset \in {\mathcal {V}}$. Daher müsen alle Elemente von $\bigcap {\mathcal {V}}$ in $\emptyset$ liegen. Das gilt aber für kein Element. Also ist $\bigcap {\mathcal {V}}$ leer. ✔

Potenzmenge

$\forall x:{\mathcal {P}}(x)\in {\mathcal {V}}$

Die Potenzmenge einer Menge ist ebenfalls eine Menge. Zur Erinnerung: ${\mathcal {P}}({\mathcal {K}}):=\{x\,|\,x\subseteq {\mathcal {K}}\}$.

Aussonderung

$\forall x:\{y\in x\,|\,A(y)\}\in {\mathcal {V}}$

Gegeben sei eine Menge $x$. Dann enthält $\{y\in x\,|\,A(y)\}$ nur die Elemente von $x$, für die $A(y)$ gilt. $\{y\in x\,|\,A(y)\}$ ist eine Teilmenge von $x$

Aufgabe: ${\mathcal {K}}$ sei eine beliebige Klasse. Zeige:

1. $\forall x:{\mathcal {K}}\cap x\in {\mathcal {V}}$
2. $\forall x:{\mathcal {K}}\subseteq x\Rightarrow {\mathcal {K}}\in {\mathcal {V}}$

Lösungen:

1. ${\mathcal {K}}\cap x=\{y\,|\,y\in {\mathcal {K}}\land y\in x\}=\{y\in x\,|\,y\in {\mathcal {K}}\}$ nach Definition von $\cap$ und $\{y\in x\,|\,\dotsm \}$ und mit $A(y)=y\in {\mathcal {K}}$ folgt die Behauptung aus der Aussonderung. ✔
2. Wegen ${\mathcal {K}}\subseteq x$ gilt ja ${\mathcal {K}}={\mathcal {K}}\cap x$. ✔

Verständnisfrage: Es gilt ${\mathcal {K}}\neq \emptyset \Rightarrow \bigcap {\mathcal {K}}\in {\mathcal {V}}$. Warum?

Ist ${\mathcal {K}}\neq \emptyset$ gibt es ein $x\in {\mathcal {K}}$ mit $\bigcap {\mathcal {K}}\subseteq x$. ✔

Warnung

Um das folgende Axiom zu verstehen, werden Funktionen benötigt! Vgl. dazu das Kapitel Abbildung, Funktion

Ersetzung

$\forall x:(\forall y\in x\exists !z:A(y,z)\Rightarrow \{z\,|\,\exists y\in x:A(y,z)\}\in {\mathcal {V}})$

Wir betrachten zunächst die Prämisse von $\Rightarrow$ und stellen fest: $\underbrace {\forall y\in x\exists !z:A(y,z)} _{A(y,z)\;definiert\;eine\;Funktion\;mit\;dem;\ Definitionsbereich\;x}$.

Die Konklusion von $\Rightarrow$ besagt: $\underbrace {\{z\,|\,\exists y\in x:A(y,z)\}} _{der\;Wertebereich\;zu\;A(y,z)}\quad \underbrace {\qquad \in {\mathcal {V}}\qquad \color {white}|} _{ist\;eine\;Menge}$

Insgesamt: Ist der Definitionsbereich einer Funktion eine Menge, so ist auch der Wertebereich der Funktion eine Menge.

Definition ($\in$-minimal)

$x$ ist ${\boldsymbol {\in }}$-minimal in ${\mathcal {K}}$ genau dann, wenn $x\in {\mathcal {K}}\land \forall y\in {\mathcal {K}}:y\notin x$

Wenn also ein $\in$-minimales Element in ${\mathcal {K}}$ überhaupt Elemente hat, dann liegen sie nicht in ${\mathcal {K}}$. Das folgende Axiom fordert, dass jede nichtleere Menge $\in$-minimale Elemente hat:

Fundierung

$\forall x:(x=\emptyset \lor \exists y\in x:y\cap x=\emptyset )$

Damit werden Folgen wie   $x\in x$,   $x\in y\in x$,   $x\in y\in z\in x$,   usw. ausgeschlossen.

Satz: $\forall x_{1},x_{2},\dotsc ,x_{n}:\neg (x_{1}\in x_{2}\in \dotsm \in x_{n}\in x_{1})$

Angenommen es gäbe eine solche Kette. Dann bilden wir die Klasse ${\mathcal {M}}:=\{x_{1},x_{2},\dotsc ,x_{n}\}$.
Es ist ${\mathcal {M}}\in {\mathcal {V}}$ und ${\mathcal {M}}\neq \emptyset$. Aber ${\mathcal {M}}$ hat kein $\in$-minimales Element. ↯

Verständnisfrage: Gibt es eine Menge $x$ mit: $x={\mathcal {P}}(x)$ ?

Nein. Es gilt ja insbesondere $x\in {\mathcal {P}}(x)$. Wäre $x={\mathcal {P}}(x)$, so folgte $x\in x$ im Widerspruch zur Fundierung. ↯

Bevor wir das nächste Axiom vorstellen, betrachten wir folgende Reihe von Mengen:

$\emptyset$,   $\color {Cerulean}\{\emptyset \}$,   $\{\emptyset ,\color {Cerulean}\{\emptyset \}\color {Black}\}$,   $\{\emptyset ,\color {Cerulean}\{\emptyset \},\color {Red}\{\emptyset ,\{\emptyset \}\}\color {Black}\}$,   $\{\emptyset ,\color {Cerulean}\{\emptyset \},\color {Red}\{\emptyset ,\{\emptyset \}\},\color {Green}\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\}\color {Black}\}$   $\dotsc$

Die erste Menge hat 0 Elemente, die nächste 1, die nächste 2, die nächste 3, usw. Für die auf $x$ folgende Menge $x'$ sammeln wir alle Elemente von $x$ ein und fügen zusätzlich $x$ selbst dazu: $x':=x\cup \{x\}$.

Definition (Nachfolger)

Ist ${\mathcal {K}}$ eine Klasse, dann ist ${\mathcal {K}}':={\mathcal {K}}\cup \{{\mathcal {K}}\}$.

Für eine Menge $x$ ist $x'$ ebenfalls eine Menge! Für echte Klassen bringt die Nachfolge nichts:

Verständnisfrage: Es gilt: ${\mathcal {K}}\notin {\mathcal {V}}\Rightarrow {\mathcal {K}}'={\mathcal {K}}$. Warum?

Die Einerklasse von ${\mathcal {K}}$ ist leer, wenn ${\mathcal {K}}$ eine echte Klasse ist, denn $\{K\}=\{x\,|\,x={\mathcal {K}}\}$.

Mit dieser Nachfolger-Funktion lassen sich die natürlichen Zahlen definieren! Auf diese Idee war 1923 der ungarisch-amerikanische Mathematiker John von Neumann gekommen. Er definierte:

${\boldsymbol {0}}$	$:=\emptyset$
${\boldsymbol {1}}$	$:=0'$	$=0\cup \{0\}$	$=\color {Cerulean}\{\emptyset \}$	$=\{0\}$
${\boldsymbol {2}}$	$:=1'$	$=1\cup \{1\}$	$=\{\emptyset ,\color {Cerulean}\{\emptyset \}\color {Black}\}$	$=\{0,1\}$
${\boldsymbol {3}}$	$:=2'$	$=2\cup \{2\}$	$=\{\emptyset ,\color {Cerulean}\{\emptyset \},\color {Red}\{\emptyset ,\{\emptyset \}\}\color {Black}\}$	$=\{0,1,2\}$
${\boldsymbol {4}}$	$:=3'$	$=3\cup \{3\}$	$=\{\emptyset ,\color {Cerulean}\{\emptyset \},\color {Red}\{\emptyset ,\{\emptyset \}\},\color {Green}\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\}\color {Black}\}$	$=\{0,1,2,3\}$
usw.

Auf diese Weise lässt sich jede einzelne natürliche Zahl definieren. Mit etwas Aufwand – den wir hier nicht darstellen wollen – lässt sich auch die Klasse $\mathbb {N} =\{1,2,3,\dotsc \}$ aller natürlichen Zahlen definieren. Dazu reichen die bisher vorgestellten Axiome völlig aus. Es lässt sich aber nicht zeigen, dass $\mathbb {N}$ eine Menge ist. Dazu benötigen wir ein weiteres Axiom:

Unendlichkeit

$\exists x:(\emptyset \in x\land \forall y\in x:y'\in x)$

Es gibt also eine Menge, die $0$ und alle Nachfolger enthält! Solche Klassen heissen induktiv.

Definition (Induktive Klassen)

${\mathcal {K}}$ ist induktiv $:\Leftrightarrow$ $\emptyset \in {\mathcal {K}}\land \forall x\in {\mathcal {K}}:x'\in K$.

Das Unendlichkeits-Axiom besagt also, es gibt eine induktive Menge. Damit lässt sich $\mathbb {N}$ wie folgt definieren:

Definition (Natürliche Zahlen)

$\mathbb {N} :=\bigcap \{x\,|\,x\,ist\,induktiv\}$.

Satz: $\mathbb {N} \in {\mathcal {V}}$.   Die Klasse der natürlichen Zahlen ist eine Menge.

Es gibt eine induktive Menge $x$ und nach Definition ist $\mathbb {N}$ in dieser Menge enthalten. Mit der Aussonderung folgt $\mathbb {N} \in {\mathcal {V}}$. ✔

Die natürlichen Zahlen werden durch die fünf Peano-Axiome beschrieben.

Satz: $\mathbb {N}$ erfüllt die Peano-Axiome:

1. $0\in \mathbb {N}$   (0 ist eine natürliche Zahl.)
2. $\forall x\in \mathbb {N} :x'\in \mathbb {N}$   (Jede natürliche Zahl hat eine natürliche Zahl als Nachfxolger.)
3. $\forall x\in \mathbb {N} :\neq 0$   (0 ist kein Nachfolger einer natürlichen Zahl.)
4. $\forall x\in \mathbb {N} \;\forall y\in \mathbb {N} :x'=y'\Rightarrow x=y$   (Natürliche Zahlen mit gleichem Nachfolger sind gleich.)
5. ${\mathcal {K}}$ sei eine beliebige Klasse:
   $0\in {\mathcal {K}}\land (\forall x\in \mathbb {N} :x\in {\mathcal {K}}\Rightarrow x'\in {\mathcal {K}})\Rightarrow \mathbb {N} \subseteq {\mathcal {K}}$
   (Ist 0 aus ${\mathcal {K}}$ und gilt für jede natürliche Zahl, wenn sie in ${\mathcal {K}}$ ist, dann ist auch ihr Nachfolger in ${\mathcal {K}}$, dann sind alle natürlichen Zahlen in ${\mathcal {K}}$)

Beweise: Wir zeigen 4. zum Schluss.

1. $0$ ist in jeder induktiven Menge enthalten, also auch im Durchschnit $\mathbb {N}$. ✔
2. Sei $x\in \mathbb {N}$ nach Voraussetzung. Dann ist $x$ und damit auch $x'$ in allen induktiven Mengen enthalten, also auch in $\mathbb {N}$. ✔
3. Der Nachfolger von x ist nicht leer! ✔
4. Mit 5. steht das Beweisverfahren durch vollständige Induktion zur Verfügung!
   Wir zeigen zunächst einen Hilfsatz: $\forall x\in \mathbb {N} \;\forall y\in \mathbb {N} :y\in x'\Rightarrow y\subseteq x$. Induktion über $x$.
   Induktionsanfang: Sei $x=0$ und $y\in 0'=\{\emptyset \}$. Dann ist $y=\emptyset \subseteq \emptyset$.
   Induktionsschluss: Gelte nun $y\in x'\Rightarrow y\subseteq x$ und sei $y\in x''=x'\cup \{x'\}$.
   Dann ist $y\in x'$ oder $y\in \{x'\}$.
   Im erste Fall folgt mit der Induktionsvoraussetzung $y\subseteq x$ und wegen $x\subseteq x'$ auch $y\subseteq x'$.
   Im zweiten Fall gilt $y=x'$ und somit ebenfalls $y\subseteq x'$.
   Damit ist der Hilfsatz bewiesen.
   Sei nun $x,y\in \mathbb {N}$ und gelte $x'=y'$.
   Das heisst $x'=x\cup \{x\}=y\cup \{y\}=y'$.
   Dann gilt $x\in y'$ und mit dem Hilfssatz folgt $x\subseteq y$.
   Ebenso folgt $y\in x'$ und somit $y\subseteq x$.
   Das zeigt $x=y$. ✔
5. Wir konstruieren eine induktive Menge ${\mathcal {M}}$ und zeigen, dass $\mathbb {N} \subseteq {\mathcal {M}}\subseteq {\mathcal {K}}$ gilt. Daraus folgt $\mathbb {N} \subseteq {\mathcal {K}}$.
   Sei ${\mathcal {M}}:=\mathbb {N} \cap {\mathcal {K}}$ und gelten die Voraussetzungen.
   Dann ist ${\mathcal {M}}$ eine Menge und es gilt ${\mathcal {M}}\subseteq {\mathcal {K}}$.
   Es gilt $0\in {\mathcal {K}}$, also ist $0\in {\mathcal {M}}$.
   Sei nun $x\in {\mathcal {M}}$, also $x\in \mathbb {N}$ und $x\in {\mathcal {K}}$.
   Dann ist $x'\in \mathbb {N}$ (nach 2.) und $x'\in {\mathcal {K}}$ (nach Voraussetzung).
   Daher ist $x'\in {\mathcal {M}}$ und somit ${\mathcal {M}}$ induktiv.
   Nach Definition von $\mathbb {N}$ gilt daher $\mathbb {N} \subseteq {\mathcal {M}}$. ✔

Aufgabe: Zeige dass jede natürliche Zahl selbst aus natürlichen Zahlen besteht: $\forall x\in \mathbb {N} :x\subseteq \mathbb {N}$

Induktion über $x$:
Induktionsanfang: $0\subseteq \mathbb {N}$.
Induktionsschluss: Gelte nun $x\subseteq \mathbb {N}$. Dann ist $x'=x\cup \{x\}\subseteq \mathbb {N}$, denn die Vereinigung zweier Teilmengen von $\mathbb {N}$ ist ebenfalls eine Teilmenge von $\mathbb {N}$. ✔

Anmerkung: Das 5. Peano-Axiom wird häufig mit Aussagenformen anstelle von Klassen formuliert:

$A(x)$ sei eine beliebige Aussageform:

$A(0)\land (\forall x\in \mathbb {N} :A(x)\Rightarrow A(x'))\Rightarrow \forall x\in \mathbb {N} :A(x)$

Wegen ${\mathcal {K}}=\{x\,|\,A(x)\}$ sind beide Formulierungen gleichwertig.

Warnung

Um das letzte Axiom zu verstehen, werden Kenntnisse über Partitionen (Zerlegungen) benötigt! Vgl. dazu das Kapitel Äquivalenzrelation, Funktion

Auswahl

$\forall x:(\forall y\in x:y\neq \emptyset \land \forall y,z\in x:(y\neq z\Rightarrow y\cap z=\emptyset )\Rightarrow \exists w\;\forall y\in x\exists !z\in w:z\in y)$

Wir lesen dieses Axiom schrittweise: $x$ sei eine beliebige Menge.
Die Prämisse besagt: $\underbrace {\quad \forall y\in x:\quad } _{die\;Elemente\;von\;x}$   $\underbrace {\qquad y\neq \emptyset \qquad } _{sind\;nicht\;leer}$   $\underbrace {\quad \land \quad \color {white}|} _{und}$   $\underbrace {\forall y,z\in x:(y\neq z\Rightarrow y\cap z=\emptyset )} _{paarweise\;disjunkt}$

Die Konklusion besagt: $\underbrace {\qquad \qquad \exists w\qquad \qquad \color {white}|} _{es\;gibt\;eine\;Menge\;w,\;die}$   $\underbrace {\qquad \forall y\in x\qquad } _{aus\;jedem\;Element\;von\;x}$   $\underbrace {\qquad \exists !z\in w:z\in y\qquad } _{genau\;ein\;Element\;enthalt}$

Insgesamt heisst das also: Zu einer Menge $x$ deren Elemente nicht leer und paarweise disjunkt sind, gibt es eine Menge $w$, die aus jedem Element von $x$ genau ein Element enthält, also auswählt. Die Menge $x$ ist eine Partition der Menge $\bigcup x$ und die Menge $w$ wählt aus jedem Teil der Partition einen Repräsentanten aus:

Partition (links) mit Auswahlmenge (rechts)

Das Auswahlaxiom sieht harmlos aus, hat aber erhebliche Auswirkungen. Es gibt eine Reihe von wichtigen Sätzen, die auf der Basis der übrigen Axiome zum Auswahlaxiom gleichwertig sind. Wir wollen hier aber die Vorstellung der Axiome von ZFC beenden.

Einzelnachweise

Vor zu Terme