© 1999 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.


3.10 Die natürlichen Zahlen und das Induktionsaxiom

In diesem Abschnitt betrachten wir die Menge der natürlichen Zahlen mit der Zahl 0 und der Nachfolgerfunktion 1+ :→ , n→1+(n) := 1+n und folgenden Eigenschaften:

  1. Kein Wert der Nachfolgerfunktion 1+ ist 0.
  2. Die Nachfolgerfunktion 1+ ist injektiv.
  3. Für jede Teilmenge X der Menge der natürlichen Zahlen gilt: Enthält X die Null und mit jedem Element auch dessen Nachfolger, dann ist X die gesamte Menge der natürlichen Zahlen.

Ob die intuitiven natürlichen Zahlen diese drei Eigenschaften tatsächlich besitzen, insbesondere die dritte, kann selbstverständlich hinterfragt werden. Diese philosophische Frage soll uns aber hier nicht weiter beschäftigen. Aus mathematischer Sicht werden sie einfach postuliert und sogar zur Grundlage einer Formalisierung der natürlichen Zahlen in der Prädikatenlogik gemacht. Für eine solche Formalisierung benutzen wir folgende Hilfsmittel.

Definition 3.10.1.   Sei o,s die Sprache der Prädikatenlogik erster bzw. zweiter Stufe mit Gleichheit, die aus einer Konstanten o und einem einstelligen Funktionssymbol s besteht.

Es bezeichne (,0,1+) die normale o,s-Interpretation mit und und U(x)=0 für jede Variable x.

In der Sprache o,s soll also die Konstante o für die natürliche Zahl 0 stehen und das Funktionssymbol s für die Nachfolgerfunktion 1+. Damit können die obigen drei Eigenschaften durch drei geschlossene o,s-Formeln formalisiert werden.

Definition 3.10.2 (Das Peano'sches Axiomensystem).  
P1: ∀x ¬(s(x)o)
P2: ∀x∀y (s(x)s(y) ⇒ xy)
P3: ∀X[(X(o) ∧ ∀y [X(s(y))]) ⇒ ∀z X(z)]
(Induktionsaxiom)

Da wir postulieren, dass die natürlichen Zahlen die genannten drei Eigenschaften besitzen, ist die o,s-Interpretation (,0,1+) ein Modell der Formelmenge {P1, P2, P3}. Wir werden sehen, dass alle anderen normalen Modelle des Peano'schen Axiomensystems zu diesem Modell isomorph sind, das heißt, im wesentlichen identisch.

Definition 3.10.3 (Isomorphe Interpretationen).   Sei eine Sprache der Prädikatenlogik erster oder zweiter Stufe und seien M1=(D1,Ab1,U1) und M2=(D2,Ab2,U2) zwei -Interpretationen.

Eine Funktion μ:D1→D2 heißt ein Isomorphismus von M1 auf M2, wenn:

  1. μ:D1→D2 ist eine Bijektion.
  2. Für jede Konstante c gilt μ(cM1)=cM2.
  3. Für jedes n-stellige (n≥1) Funktionssymbol f und alle d1,...,dn∈D1 gilt μ(fM1(d1,...,dn))= fM2(μ(d1),...,μ(dn)).
  4. Für jedes nullstellige Relationssymbol p gilt pM1=pM2.
  5. Für jedes n-stellige (n≥1) Relationssymbol p und alle d1,...,dn∈D1 gilt (d1,...,dn)∈pM1 gdw. (μ(d1),...,μ(dn))∈pM2.
Gibt es einen Isomorphismus von M1 auf M2, dann heißen M1 und M2 isomorph.

Genaugenommen müsste die Definition auch Bedingungen für die Umgebungen enthalten. Wir betrachten aber nur geschlossene Formeln, so dass die Umgebungen keine Rolle spielen.

Satz 3.10.4 (Isomorphiesatz).   Sind M1 und M2 isomorphe -Interpretationen, so gilt für jede geschlossene -Formel F: M1F gdw. M2F.

Beweis:  strukturelle Induktion.

Bevor wir die Modelle des Peano'schen Axiomensystems untersuchen, betrachten wir die Formel P3 genauer. Sie ist eine Formel der Prädikatenlogik zweiter Stufe. Diese Formel wird als Induktionsaxiom bezeichnet, weil sie die Grundlage für Induktionsbeweise liefert.

Satz 3.10.5 (Beweisprinzip der vollständigen Induktion).   Sei M=(D,Ab,U) eine o,s-Interpretation, die das Induktionsaxiom P3 erfüllt. Um zu zeigen, dass jedes Element von D eine Eigenschaft ε besitzt, genügt es, zu zeigen:
  1. Induktionsbasis: Ab(o) besitzt die Eigenschaft ε.
  2. Induktionsschritt: Für jedes d∈D, das die Eigenschaft ε besitzt, besitzt auch Ab(s)(d) die Eigenschaft ε.

Beweis:   Sei Dε die Relation (das heißt, Teilmenge) derjenigen Elemente von D, die die Eigenschaft ε besitzen. M erfüllt P3 insbesondere auch für den Fall, dass X mit Dε interpretiert wird, mit anderen Worten:

M[Dε/X] [X(o)∧∀y[X(y)⇒X(s(y))]) ⇒ ∀z X(z)]   (*)

Wegen der Induktionsbasis gilt Ab(o)∈Dε, also M[Dε/X]X(o). Wegen des Induktionsschritts gilt für jedes d∈D: wenn d∈Dε so Ab(s)(d)∈Dε, das heißt, für jedes d∈D gilt M[Dε/X][d/y] [X(y)⇒X(s(y))], also M[Dε/X]∀y [X(y)⇒X(s(y))]. Mit diesen beiden Ergebnissen gilt wegen (*) auch M[Dε/X]∀z X(z), für jedes d∈D gilt damit d∈Dε, also besitzt jedes d∈D die Eigenschaft ε.

Dieses Beweisprinzip ist für jede o,s-Interpretation anwendbar, die P3 erfüllt, also insbesondere auch für (,0,1+). Spezialisiert für diese Interpretation lautet die Induktionsbasis, dass 0 die Eigenschaft ε hat und der Induktionsschritt, dass für jedes n∈ mit Eigenschaft ε auch 1+n die Eigenschaft ε hat. Das ist genau das übliche Beweisprinzip der vollständigen Induktion für die natürlichen Zahlen, das wir schon mehrfach benutzt haben.

Man kann aus der Tatsache, dass (,0,1+) ein normales Modell der Formelmenge {P1, P2, P3} ist, weitere bekannte Eigenschaften der natürlichen Zahlen ableiten, die wir bisher schon benutzt haben. Dazu gehört zum Beispiel ein Prinzip der rekursiven Definition von Funktionen auf oder auch, dass es zu jedem n∈ mit n≠0 ein k∈ gibt mit n=1+k.

Das soll aber hier nicht im einzelnen durchgeführt werden. Wir werden derartige Eigenschaften der natürlichen Zahlen weiterhin, wie bisher, einfach voraussetzen und benutzen, ohne sie formal daraus abzuleiten, dass (,0,1+) das Peano'sche Axiomensystem erfüllt.

Satz 3.10.6 (Satz von Dedekind)   Jedes normale Modell der Formelmenge {P1, P2, P3} ist mit (,0,1+) isomorph.

Beweis:   Sei M=(D,Ab,U) ein normales Modell von {P1, P2, P3}. Wir definieren eine Funktion μ:→D rekursiv für alle natürlichen Zahlen:
μ(0) := Ab(o)
μ(1+(n)) := Ab(s)(μ(n)) für alle n∈

Diese Funktion erfüllt nach Konstruktion die Forderungen 2. und 3. von Definition 3.10.3. Da das einzige Relationssymbol in o,s ist, gilt trivialerweise auch Forderung 4. Forderung 5. reduziert sich wegen der Normalität beider Modelle darauf, dass für alle m,n∈ gilt m=n gdw. μ(m)=μ(n). Das folgt unmittelbar, wenn die Funktion auch Forderung 1. erfüllt, also eine Bijektion ist, was noch zu zeigen bleibt.

Für die Injektivität von μ zeigen wir durch vollständige Induktion, dass jede natürliche Zahl n folgende Eigenschaft besitzt:

E(n): Für alle m∈ gilt, wenn m≠n, dann μ(m)≠μ(n).

Induktionsbasis n=0: Sei m≠0. Dann ist m=1+k für ein k∈. Also ist μ(m)=μ(1+(k))=Ab(s)(μ(k)). Da M das Axiom P1 erfüllt, gilt Ab(s)(μ(k))≠Ab(o). Wegen Ab(o)=μ(0) gilt also μ(m)≠μ(0).

Induktionsschritt n→1+n: Es gelte E(n). Sei m≠1+n. Falls m=0, wird wie im Basisfall gezeigt, dass μ(m)≠μ(1+(n)). Andernfalls ist m=1+(k) für ein k∈, also 1+(k)≠1+(n) und damit k≠n. Nach Induktionsannahme gilt dann μ(k)≠μ(n). Da M das Axiom P2 erfüllt, ist Ab(s) injektiv, so dass auch Ab(s)(μ(k))≠Ab(s)(μ(n)) gilt. Anwendung der Definition von μ auf beiden Seiten ergibt μ(1+(k))≠μ(1+(n)), das heißt, μ(m)≠μ(1+(n)).

Für die Surjektivität von μ nutzen wir aus, dass M das Induktionsaxiom P3 erfüllt. Wir zeigen durch vollständige Induktion die Surjektivität von μ, dass also jedes Element von D zum Bild von μ gehört.

Induktionsbasis Ab(o): Da μ(0)=Ab(o), gehört Ab(o) zum Bild von μ.

Induktionsschritt d→Ab(s)(d): Sei d im Bild von μ, das heißt, es gibt ein n∈ mit μ(n)=d. Nach Definition ist μ(1+(n))=Ab(s)(μ(n)), also μ(1+(n))=Ab(s)(d), das heißt, Ab(s)(d) gehört zum Bild von μ.

Das Peano'sche Axiomensystem hat also die Eigenschaft, dass alle seine normalen Modelle isomorph zu (,0,1+) sind. Unter Anwendung des Endlichkeitssatzes kann gezeigt werden, dass keine Menge von geschlossenen o,s-Formeln der Prädikatenlogik erster Stufe diese Eigenschaft hat. Das bedeutet, dass das Induktionsaxiom P3 nicht in der Prädikatenlogik erster Stufe ausdrückbar ist.

Da der Endlichkeitssatz für die Prädikatenlogik erster Stufe erst in Kapitel 4 bewiesen wird, wird auch die Nichtausdrückbarkeit des Induktionsaxioms erst dort behandelt.

Validierung