Dieses Kapitel handelt von den natürlichen Zahlen. Diese werden axiomatisch eingeführt. Die aus der Schule vertrauten Rechenregeln werden im nächsten Kapitel aus den Axiomen gefolgert.
Die natürlichen Zahlen stellen wir uns so vor, dass jede, etwa von der Zahl 1 ausgehend, durch Zählen gewonnen werden kann, immer von einer Zahl zur nachfolgenden Zahl fortschreitend. Diese Vorstellung lässt sich mit den soeben besprochenen Begriffen der Mengentheorie präzisieren.
Definition. Es sei $\mathbb{N}$ eine Menge mit einem ausgezeichneten Element $1\in\mathbb{N}$ und versehen mit einer Abbildung $$f\colon{\mathbb{N}}\to{\mathbb{N}},n\mapsto f(n),$$ derart dass folgende Axiome erfüllt sind:
-
Die Abbildung $f$ ist injektiv und der Bildbereich ist im Komplement der 1.
- Ist $M\subset\mathbb{N}$ eine Teilmenge, die das Element 1 enthält und die mit jedem Element $m$ auch $f(m)$ enthält, so ist $M$ gleich $\mathbb{N}$.
Dann nennt man $\mathbb{N}$, zusammen mit dem Element 1 und der Abbildung $f$, Menge der natürlichen Zahlen.
Man sagt, die Abbildung $f$ ordne jedem Element $n\in\mathbb{N}$ seinen Nachfolger $f\left(n\right)$ zu. Dass die natürlichen Zahlen die beschriebenen Eigenschaften haben, das ist wohl jeder bereit, zuzugestehen. Interessant an diesen Axiomen ist, dass sie die natürlichen Zahlen mitsamt all ihren Eigenschaften vollständig charakterisieren. Wenn wir also künftig von den natürlichen Zahlen reden, so reden wir von einer Menge, die den beiden Axiomen genügt. Inwieweit eine solche Menge tatsächlich existiert, wie jeder Einzelne sie sich vorstellt oder wo sie vom Einzelnen verortet wird, das ist nicht weiter von Belang, solange wir uns auf die Gültigkeit dieser Axiome verständigen. Die Frage, inwieweit die natürlichen Zahlen durch die beiden Axiome eindeutig bestimmt sind, werden wir später zurückkommen. Die axiomatische Einführung der natürlichen Zahlen geht auf Dedekind und Peano zurück. Peano formulierte fünf Axiome, die in der obigen Definition nur anders gruppiert sind. Peanos fünftes Axiom stimmt überein mit dem obigen zweiten. Aus diesem folgt unmittelbar das Beweisprinzip der vollständigen Induktion. Weiterhin folgt auch, etwas weniger offensichtlich, das Konstruktionsprinzip der rekursiven Definition.
1.2.1. Prinzip der vollständigen Induktion. Es sei für jede natürliche Zahl $n\in\mathbb{N}$ eine Aussage $A(n)$ gegeben und es gelte:
- Die Aussage $A(1)$ ist wahr. (Induktionsverankerung)
- Setzen wir die Gültigkeit der Aussage $A(n)$ für ein beliebiges $n\in\mathbb{N}$ voraus, so folgt daraus die Gültigkeit der Aussage $A(f(n))$ für den Nachfolger $f(n)$ von $n$. (Induktionsschritt)
- Setzen wir die Gültigkeit der Aussage $A(n)$ für ein beliebiges $n\in\mathbb{N}$ voraus, so folgt daraus die Gültigkeit der Aussage $A(f(n))$ für den Nachfolger $f(n)$ von $n$. (Induktionsschritt)
Dann sind die Aussagen $A(n)$ für alle $n\in\mathbb{N}$ wahr.
Wie eingangs erwähnt, ist dieses Prinzip der vollständigen Induktion eine Folgerung aus den Axiomen von Peano. Also bedarf es eines Beweises:
Beweis. Die Menge $$M:=\{n\in\mathbb{N}\;|\; A(n)\text{ ist wahr }\}\subset\mathbb{N}$$ enthält wegen der Induktionsverankerung die 1. Wegen des Induktionsschritts gilt für alle $n\in M$, dass auch der Nachfolger $f(n)\in M$ ist. Aus dem zweiten Peano-Axiom folgt nun $M=\mathbb{N}$, d.h. die Aussage $A(n)$ gilt für alle $n\in\mathbb{N}$.
qed
Das Kürzel qed steht für quod erat demonstrandum, zu deutsch was zu beweisen war. Dies ist ein traditioneller, formaler Abschluss eines Beweises.
1.2.2. Rekursionssatz. Es sei $X$ eine Menge, $x\in X$ und $g\colon X\to X$ eine Abbildung. Dann gibt es eine eindeutig bestimmte Abbildung $\varphi\colon\mathbb{N}\to X$, für die gilt $\varphi(1)=x$ und $\varphi(f(n))=g(\varphi(n))$ für alle $n\in\mathbb{N}$.
Beweis. Der Beweis hat zwei Teile. Zu Beginn zeigen wir, dass es höchstens eine Abbildung mit den geforderten Eigenschaften gibt. Dazu nehmen wir an, wir hätten die behauptete Abbildung $\varphi$ schon konstruiert. Außerdem gäbe es da eine zweite Abbildung $\psi\colon\mathbb{N}\to X$, für die ebenso gilt $\psi(1)=x$, sowie $\psi(f(n))=g(\psi(n))$ für alle $n\in\mathbb{N}$. Nun müssen wir nachweisen, dass die Abbildungen $\varphi$ und $\psi$ notwendigerweise gleich sein müssen. Anders ausgedrückt, müssen wir für alle $n\in\mathbb{N}$ die Aussage $A(n)$, welche besagt $\varphi(n)=\psi(n),$ nachweisen. Wir zeigen dies durch vollständige Induktion (mit was auch sonst; es steht ja nichts anderes zur Verfügung).
- Induktionsverankerung: $A(1)$ besagt $\varphi(1)=\psi(1)$. Dies ist offensichtlich richtig, da beide Seiten gleich $x$ sind.
- Induktionsschritt: Es sei für $n\in\mathbb{N}$ die Aussage $A(n)$ wahr, welche besagt $\varphi(n)=\psi(n)$. Es ist zu zeigen, dass $A(f(n))$ gilt. Dazu betrachten wir die Geichungskette $$\varphi(f(n))=g(\varphi(n))=g(\psi(n))=\psi(f(n)).$$ Die erste Gleichung benutzt die definierende Gleichung von $\varphi$. In der zweiten Gleichung benutzen wir die Aussage $A(n)$. Die dritte Gleichung benutzt die definierende Gleichung von $\psi$. Vergleichen wir den ersten Ausdruck in der obigen Gleichungskette mit dem letzten Ausdruck, so erhalten wir die Aussage $A(f(n))$. Das war zu zeigen.
Nach Induktion ist $A(n)$ wahr für alle $n\in\mathbb{N}$, die Abbildungen $\varphi$ und $\psi$ stimmen also überein.
Der zweite Teil des Beweises behandelt die Existenz der Abbildung $\varphi$. Dazu betrachten wir Teilmengen $C\subset\mathbb{N}\times X$, die folgende zwei Eigenschaften erfüllen:
- Es gilt $\left(1,x\right)\in C$.
- Ist $\left(n,y\right)\in C$, so gilt auch $\left(f\left(n\right),g\left(y\right)\right)\in C$.
Derartige Teilmengen existieren. Zum Beispiel besitzt die Menge $\mathbb{N}\times X$ selbst die beiden geforderten Eigenschaften. Es bezeichne nun $D$ den Durchschnitt aller Teilmengen von $\mathbb{N}\times X$, für welche die Bedingungen 1 und 2 erfüllt sind. Die Menge $D$ erfüllt als Durchschnitt selbst wieder die Eigenschaften 1 und 2 und ist in allen derartigen Teilmenge von $\mathbb{N}\times X$ enthalten.
Wir zeigen induktiv die Aussage $B(n)$, welche besagt, dass es für jedes $n\in \mathbb N$ ein eindeutig bestimmtes Element $\varphi(n)\in X$ gibt mit $\left(n,\varphi(n)\right)\in D$.
- Induktionsverankerung: Das Element $(1,x)$ ist nach Definition in $D$. Gäbe es ein weiteres Element $(1,y)\in D$ mit $x\not= y$, so erfüllte auch $D\setminus \{(1,y)\}$ die Bedingungen 1 und 2 und wäre außerdem echt enthalten in $D$. Dies widerspricht der angenommenen Minimalität von $D$. Folglich gilt die Aussage $B(1)$ mit $\varphi(1):=x$.
- Induktionsschritt: Die Aussage $B(n)$ sei für $n\in\mathbb{N}$ wahr. Es gibt also ein eindeutig bestimmtes Element $\varphi(n)\in X$ mit $\left(n,\varphi(n)\right)\in D$. Wegen Bedingung 2 ist folglich auch $\left(f(n),g\left(\varphi(n)\right)\right)\in D$. Gäbe es ein weiteres Element $\left(f(n),z\right)\in D$ mit $z\not= g\left(\varphi(n)\right)$, so erfüllte auch $D\setminus
\left\{ \left( f(n) , z \right) \right\}$ die Bedingungen 1 und 2 und wäre außerdem echt enthalten in $D$. Dies widerspricht der angenommenen Minimalität von $D$. Folglich gilt die Aussage $B\left(f(n)\right)$ mit $\varphi\left(f(n)\right):=g\left(\varphi(n)\right)$. Das war zu zeigen.
Die durch $n\mapsto \varphi(n)$ definierte Abbildung $\varphi:{\mathbb N}\to X$ erfüllt die Rekursion.
qed
Bei rekursiven Definitionen verwenden wir die folgende Sprechweise:
,,Wir definieren die Abbildung $\varphi\colon\mathbb{N}\to X$ durch $\varphi(1)=x$ und $\varphi(f(n)):=g(\varphi(n))$ für alle $n\in\mathbb{N}$.”
Sobald wir ein Modell der natürlichen Zahlen (bestehend aus Menge, ausgezeichnetem Element und Nachfolger-Abbildung) haben, lassen sich sehr leicht viele andere Modelle finden, die den gleichen Axiomen genügen. Zum Beispiel erfüllt die Menge der ungeraden Zahlen $\{1,3,5,7, \ldots\}\subset\mathbb N$, zusammen mit dem ausgezeichnetem Element 1 und der Nachfolger-Abbildung $f^2 := f\circ f$, ebenfalls die Dedekind-Peano Axiome. Die beiden Mengen sind aber klar verschieden.
Es soll hier nicht weiter in das Dickicht von Logik und Philosopie vorgedrungen werden [1], um zu klären, in welchem Sinne man trotzdem von den natürlichen Zahlen reden kann. Der entscheidende Punkt ist, dass alle Modelle äquivalent sind insoweit je zwei sich eindeutig strukturerhaltend ineinander abbilden lassen:
1.2.3. Satz. Sind $\left({\mathbb N},1,f\right)$ und $\left({\mathbb N}',1',f'\right)$ jeweils Mengen der natürlichen Zahlen, so gibt es eine eindeutig bestimmte, bijektive Abbildung $\varphi \colon {\mathbb N}\to{\mathbb N}'$ mit $\varphi(1)=1'$ und $\varphi\circ f = f' \circ \varphi$.
Beweis. Existenz und Eindeutigkeit der Abbildung $\varphi$ folgt aus dem Rekursionssatz mit $X={\mathbb N}', x=1'$ und $g=f'$. Es bleibt zu zeigen, dass $\varphi$ bijektiv ist. Dazu konstruieren wir die Umkehrabbildung.
Wenden wir den Rekursionssatz mit vertauschten Rollen an, so erhalten wir eine eindeutige Abbildung $\varphi' \colon {\mathbb N}'\to{\mathbb N}$ mit $\varphi(1')=1$ und $\varphi'\circ f' = f \circ \varphi'$.
Für die Abbildung $\varphi'\circ\varphi$ gilt: $\varphi'\circ\varphi(1)=1$ und $$
(\varphi'\circ\varphi)\left( f(n)\right)
=\varphi'\left(\varphi\left( f(n)\right)\right)
=\varphi'\left(f'\left( \varphi(n)\right)\right)
=f\left(\varphi'\left( \varphi(n)\right)\right)
=f\left((\varphi'\circ\varphi)(n)\right).
$$ Sie erfüllt also die Bedingung des Rekursionssatzes mit $X=\mathbb N$ und $g=f$, genauso wie die identische Abbildung. Wegen der Eindeutigkeitsaussage des Rekursionssatzes muss also gelten $\varphi'\circ\varphi=id_{\mathbb N}$. Analog folgert man $\varphi\circ\varphi'=id_{{\mathbb N}'}$. Somit sind $\varphi$ und $\varphi'$ jeweils Umkehrabbildungen voneinander.
qed
-------
[1] Wen es danach drängt, mag anfangen mit B. Russel: Introduction to Mathematical Philosophy