Vollständige Induktion

Mit Hilfe seiner Axiome hat Giuseppe Peano (1858 - 1932) die grundlegenden Eigenschaften der Menge der natürlichen Zahlen beschrieben:

(1) 0 ist eine natürliche Zahl.
(2) Jede natürliche Zahl hat einen Nachfolger und dieser ist wieder eine natürliche Zahl.
(3) Enthält eine Menge S die Zahl 0 und mit jeder natürlichen Zahl auch stets deren Nachfolger, so enthält S alle natürlichen Zahlen.
(4) Sind die Nachfolger zweier natürlicher Zahlen a und b einander gleich, so gilt a = b.
(5) Kein Nachfolger einer natürlichen Zahl ist gleich der Zahl 0.

Die Formulierung dieser Axiome ist nicht ganz unproblematisch, denn die Begriffe "Zahl", "0" und "Nachfolger" werden in (1) bis (5) im mathematischen Sinne nicht definiert.

Es gibt zu dem Axiomensystem (1) bis (5) von Peano folgende äquivalente Alternative unter Benutzung des Begriffs der Abbildung:

Mit dieser Beschreibung von ℕ handelt man sich ein anderes Problem ein: Die Axiome (II) und (III) zur Definition der Abbildung succ auf der Menge ℕ setzt die Existenz von ℕ bereits voraus, obwohl ja erst mit Hilfe des Axiomensystems (I) bis (IV) die Menge ℕ definiert werden soll.

Man kann es drehen und wenden wie man will, im Grunde wird gefordert, dass ℕ eine wohlgeordnete und unendliche Menge ist mit 0 ∈ ℕ als kleinstem Element, und man setzt axiomatisch fest, dass die Wohlgeordnetheit von ℕ mit der injektiven Abbildung succ gewährleistet ist.

Mit anderen Worten: Das elementare Tun des Hintereinanderreihens von wohlunterschiedenen Objekten, das heißt der Prozess des Zählens, scheint auf mathematischem Wege nicht begründbar und nicht hinterfragbar zu sein. Von Leopold Kronecker (1823 - 1891) ist der berühmte Ausspruch überliefert: "Die natürlichen Zahlen hat der liebe Gott erschaffen, alles andere ist Menschenwerk".

Sei M eine nichtleere Menge gleichartiger Objekte und

R ⊂ M x M = { (x;y): x ∈ M und y ∈ M }

eine Relation auf M. Dann heißt R genau dann Halbordnung, wenn für alle x, y, z ∈ M Folgendes gilt:

x R y und y R z ⇒ x R z (Transitivität)
x R y und y R x ⇒ x = y (Identitivität)
x R x (Reflexivität)

Existiert für eine Menge eine solche Halbordnung, so sagt man: "M ist teilweise geordnet".

Gilt außerdem noch

x, y ∈ M ⇒ x R y oder y R x

dann heißt M total geordnet (oder linear geordnet).

Alle Gesetze der natürlichen Zahlen (inklusive aller vertrauten Rechenregeln in ℕ) beruhen im Wesentlichen auf der Tatsache, dass man die natürlichen Zahlen abzählen kann. Für die Herleitung der Gesetze in ℕ nur unter Voraussetzung der Axiome (I) bis (IV) formuliert man zweckmässigerweise auf Grundlage des Axioms (IV) das sogenannte Prinzip der vollständigen Induktion:

Wenn für irgendeine Aussage E, die in Abhängigkeit von n ∈ ℕ formuliert werden kann, gilt:
(i) E(0) ist wahr;
(ii) E(m) ist wahr für ein m ∈ ℕ ⇒ E(succ(m)) ist wahr,
dann folgt: E(n) ist wahr für alle n ∈ ℕ.

(i) heißt Induktionsanfang und (ii) heißt Induktionsschluss.

"E(m) ist wahr für ein m ∈ ℕ" heißt Induktionsvoraussetzung (oder Induktionsannahme).

Oftmals führt man einen Induktionsbeweis nur über einer (natürlich nach oben nicht beschränkten) Teilmenge von ℕ aus. Dann kann man auf Grundlage des Induktionsprinzips wie folgt argumentieren:

Wenn für irgendeine Aussage E, die in Abhängigkeit von n ∈ ℕ mit n ≥ k formuliert werden kann, gilt:
(i) E(k) ist wahr;
(ii) E(m) ist wahr für ein m ≥ k ⇒ E(succ(m)) ist wahr,
dann folgt: E(n) ist wahr für alle n ≥ k.

Richard Dedekind (1831–1916) hat in seiner Schrift "Was sind und was sollen Zahlen?" 1887 das Induktionsprinzip nicht als Axion, sondern als beweisbaren Satz präsentiert. Dies liegt daran, dass Dedekind auf (nach heutigem Sprachgebrauch) mengentheoretischem Wege zu einer Charakterisierung der natürlichen Zahlen gelangt und dann hieraus den Satz der vollständigen Induktion ableitet. Der wesentliche Begriff hierbei ist der der "Kette". Im Folgenden soll die Dedekind'sche Argumentation in heutiger Terminologie (→ Definitionen) vorgestellt werden.

Sei K eine nichtleere Menge und φ: M → M eine injektive Abbildung,
das heißt es gilt a ǂ b⇒ φ(a) ǂ φ(b) für alle a, b ∈ M.
Dann heißt K eine φ-Kette (oder kurz Kette), wenn φ(K) ⊆ K ist.

Sei A irgendeine nichtleere Teilmenge einer gegebenen Menge S und
φ: S → S eine injektive Abbildung.
Dann heißt die Schnittmenge all derjenigen φ-Ketten K, für welche A ⊆ K gilt, die Kette von A.
Die Kette von A soll mit K_A bezeichnet werden.
Besteht die Menge A nur aus einem einzigen Element a, so soll K_a geschrieben werden.

Da S eine Kette ist, ist K_A nie leer.
K_A ist die Schnittmenge von φ-Ketten, also ist K_A ebenfalls eine φ-Kette.
Damit ist die Bezeichnung "Kette von A" für K_A gerechtfertigt.

A und B seien nichtleere Teilmengen von S, φ: S → S sei eine injektive Abbildung und es gelte A ⊆ B.
Dann gilt auch φ(A) ⊆ φ(B) und mit (K1) folgt φ(A) ⊆ φ(K_A). Wegen (K2) hat man dann φ(A) ⊆ K_A.

Beweis:
"⇒": Aus M ⊆ K_A folgt unter Verwendung von (K3): K_M ⊆ K_A, denn K_A ist eine Kette.
"⇐": Zusammen mit M ⊆ K_M folgt aus K_M ⊆ K_A: M ⊆ K_A.

Beweis:
Aus M ⊆ K_A folgt aus dem vorherigen Satz K_M ⊆ K_A.
Zusammen mit φ(M) ⊆ K_M (wegen K2) folgt die Behauptung.

Sei A irgendeine nichtleere Teilmenge einer Menge S und φ: S → S eine injektive Abbildung.
Sei P irgendeine weitere Menge. Wenn gezeigt werden kann, dass

Beweis:
Die Schnittmenge K_A∩P wird im Folgenden mit G bezeichnet.
Es ist A ⊆ K_A und wegen (K1) A ⊂ P folgt A ⊆ G. G ist also eine nichtleere Menge.
G ⊆ K_A und K_A ⊆ S (wegen K3). Also folgt G ⊆ S.
Ferner folgt aus G ⊆ K_A wegen des zuletzt bewiesenen Satzes: φ(G) ⊆ K_A.

Aufgrund der Bedingung (2) gilt φ(G) ⊆ P.
Zusammen mit φ(G) ⊆ K_A folgt somit: φ(G) ⊆ G, also ist G eine Kette.
Aus A ⊆ G folgt hieraus wegen (K3) K_A ⊆ G.

Es gilt also gleichzeitig G ⊆ K_A und K_A ⊆ G. Also ist K_A = K_A∩P.
Hieraus folgt die Behauptung.

Wenn man P interpretiert als Menge von Objekten, die allesamt eine bestimmte Eigenschaft E besitzen und zeigen kann, dass (1) alle Elemente aus A diese Eigenschaft besitzen und (2) das Bild φ(s) jedes Elements s ∈ K_A, das diese Eigenschaft besitzt, diese Eigenschaft ebenfalls hat, dann folgt mit dem Induktionssatz, dass alle Elemente der Kette K_A die Eigenschaft E haben.

Eine Menge N mit dem Grundelement e heißt abzählbar unendlich, wenn folgende Bedingungen erfüllt sind:

(a) Es gibt eine Abbildung φ: N → N mit φ(N) ⊆ N.
(b) N = K_e.
(c) e ist nicht in φ(N) enthalten.
(d) Die Abbildung φ ist injektiv.

φ(n) mit n ∈ N wird das auf n folgende Element genannt.

Dies ist im Wesentlichen die Dedekind'sche Charakterisierung einer abzählbar unendlichen Menge (von ihm damals einfach unendliche Menge genannt) und er sagt:

„Wenn man bei der Betrachtung eines einfach unendlichen, durch eine Abbildung φ geordneten Systems N von der besonderen Beschaffenheit der Elemente gänzlich absieht, lediglich ihre Unterscheidbarkeit festhält und nur die Beziehungen auffaßt, in die sie durch die ordnende Abbildung φ zueinander gesetzt sind, so heißen diese Elemente natürliche Zahlen oder Ordinalzahlen...“
(R. Dedekind: Was sind und was sollen Zahlen?, Braunschweig 1911³, S. 17)

Beweis:
Sei n irgendeine natürliche Zahl und φ(n) Teil einer φ-Kette L.
Setzt man K = {n} ∪ L, so ist φ(K) = {φ(n)} ∪ φ(L).
φ(L) ⊆ L, weil L eine Kette ist, {φ(n)} ⊆ L nach Voraussetzung, also folgt φ(K) ⊆ L.
Da L ⊆ K folgt φ(K) ⊆ K und damit ist bewiesen, dass K = {n} ∪ L eine Kette ist.

Nun soll gezeigt werden, dass das Bild der Kette von n gleich der Kette des Bildes von n ist,
das heißt:

φ(K_n) = K_φ(n).

K_φ(n) ist eine φ-Kette, also gilt (wegen K1) φ(n) ∈ K_φ(n).
Nach dem Vorhergehenden gibt es dann eine Kette K mit n ∈ K und φ(K) ⊆ K_φ(n).
Mit (K3) folgt K_n ⊆ K und hiermit gilt auch φ(K_n) ⊆ φ(K).
Aus φ(K_n) ⊆ φ(K) und φ(K) ⊆ K_φ(n) folgt φ(K_n) ⊆ K_φ(n).

Andererseits ist wegen (K1) n ∈ K_n und damit auch φ(n) ∈ φ(K_n).
φ(K_n) ist als Bild der Kette K_n wieder eine Kette. Also folgt mit (K3): K_φ(n) ⊆ φ(K_n).

Aus φ(K_n) ⊆ K_φ(n) und K_φ(n) ⊆ φ(K_n) folgt φ(K_n) = K_φ(n).

Sei nun K = {n} ∪ φ(K_n).
Weil φ(K_n) eine Kette ist, ist auch K eine Kette (siehe oben).
Nach Definition ist n ∈ K, also folgt mit (K3) K_n ⊆ K.

Nach (K1) ist n ∈ K_n und nach (K2) K_φ(n) = φ(K_n) ⊆ K_n.
Aus {n} ⊆ K_n und φ(K_n) ⊆ K_n folgt K ⊆ K_n.

Aus K_n ⊆ K und K ⊆ K_n folgt die Behauptung.

Dies bedeutet, dass jede von der Grundzahl e verschiedene Zahl Element von φ(N) ist, das heißt, jede natürliche Zahl n mit n ǂ e ist das Bild einer anderen natürlichen Zahl. Insbesondere ist die auf e folgende Zahl auch Element von φ(N).

Wenn mit der abzählbar unendlichen Menge N die Menge der natürlichen Zahlen gemeint ist, soll nun statt "N" "ℕ" und statt "e" "0" geschrieben werden. (Dedekind bezeichnet das Grundelement der natürlichen Zahlen mit "1", aber das ist im Hinblick auf die hier vorgestellten Gedankengänge ohne Belang.)

Sei nun E = E(n) eine Aussage, die in Abhängigkeit von n ∈ ℕ hingeschrieben werden kann und sei ferner P diejenige Menge von Zahlen z, für die E(z) eine wahre Aussage darstellt. (Die Verwendung der Bezeichnung "z" soll hier keine Verwirrung stiften, sondern nur andeuten, dass E(z) durchaus wahr sein kann, wenn z keine natürliche Zahl ist.)

Wenn man nun den Dedekind'schen Induktionssatz auf die natürlichen Zahlen anwendet und A durch {0}, S durch ℕ und φ durch succ ersetzt, dann erhält man genau das oben bereits formulierte Prinzip der vollständigen Induktion.

Es sollen jetzt alle Gesetze, die innerhalb der Menge der natürlichen Zahlen gelten, auf Grundlage des Axiomensystems (I) bis (IV) hergeleitet werden.

Die Abbildung add_j: ℕ → ℕ sei auf induktive Weise für jedes j ∈ ℕ wie folgt definiert:

Beweis:
Sei k ∈ ℕ beliebig, aber fest gewählt.
Induktionsanfang:
Mit (A1) folgt succ(add_k(0)) = succ(k) = add_succ(k)(0).
Das bedeutet, dass die behauptete Aussage für n = 0 wahr ist.
Induktionsvoraussetzung:
Es gelte succ(add_k(m)) = add_succ_(k)(m) für ein m ∈ ℕ.
Induktionsschluss:
succ(add_k(succ(m)))
= succ(succ(add_k(m))) wegen (A2)
= succ(add_succ_(k)(m)) nach Induktionsvoraussetzung
= add_succ_(k)(succ(m)) wegen (A2)
Hieraus folgt die Behauptung.

Mit succ(add_k(n)) = add_succ_(k)(n) folgt, dass für alle k, n ∈ ℕ gilt:

Beweis:
Zunächst wird gezeigt, dass für alle n ∈ ℕ die Aussage add₀(n) = n wahr ist.
Induktionsanfang:
Nach (A1) gilt add₀(0) = 0.
Induktionsvoraussetzung:
Angenommen, die Aussage add₀(m) = m sei bereits für ein m ∈ ℕ bewiesen.
Induktionsschluss:
add₀(succ(m))
= succ(add₀(m)) wegen (A2)
= succ(m) nach Induktionsvoraussetzung.

Es ist nun zu zeigen, dass die Aussage add_k(n) = add_n(k) wahr ist für alle n, k ∈ ℕ.

Sei k im Folgenden eine beliebige, aber fest gewählte natürliche Zahl.
Induktionsanfang:
add_k(0)
= k wegen (A1)
= add₀(k) weil add₀(n) = n für alle n ∈ ℕ.
Induktionsvoraussetzung:
Es gelte bereits add_k(m) = add_m(k) für ein m ∈ ℕ.
Induktionsschluss:
add_k(succ(m))
= succ(add_k(m)) wegen (A2)
= succ(add_m(k)) nach Induktionsvoraussetzung
= add_succ_(m)(k)

Da hiernach die Aussage add_k(n) = add_n(k) für alle n ∈ ℕ und für jedes beliebige k ∈ ℕ wahr ist, ist damit die Behauptung bewiesen.

Mit der für jedes j ∈ ℕ induktiv definierten Abbildung mul_j: ℕ → ℕ, gegeben durch

Beweis:
(i) Als erstes wird gezeigt, dass add_k(mul_m(k)) = mul_succ_(m)(k) für alle m, k ∈ ℕ.
Sei hierfür m ∈ ℕ beliebig, aber fest gewählt.
Induktionsanfang:
add₀(mul_m(0)) = add₀(0) = 0 = mul_succ_(m)(0)
Induktionsvoraussetzung:
Es gelte add_K(mul_m(K)) = mul_succ_(m)(K) für ein K ∈ ℕ.
Induktionsschluss:
add_succ(K)(mul_m(succ(K)))
= add_succ(K)(add_m(mul_m(K))) wegen (M2)
= succ(add_K(add_m(mul_m(K)))) wegen add_succ_(k)(n) = succ(add_k(n)) für alle n, k ∈ ℕ.
= succ(add_m(add_K(mul_m(K))))
= add_succ(m)(add_K(mul_m(K)))
= add_succ_(m)(mul_succ_(m)(K)) nach Induktionsvoraussetzung
= mul_succ_(m)(succ(K)) wegen (M2)

(ii) Im zweiten Schritt wird gezeigt, dass für alle n ∈ ℕ die Aussage mul₀(n) = 0 wahr ist.
Induktionsanfang:
Nach (M1) gilt mul₀(0) = 0.
Induktionsvoraussetzung:
Angenommen, die Aussage mul₀(m) = 0 sei bereits für ein m ∈ ℕ bewiesen.
Induktionsschluss:
mul₀(succ(m))
= add₀(mul₀(m)) wegen (M2)
= add₀(0) nach Induktionsvoraussetzung
= 0

(iii) Es ist nun zu zeigen, dass die Aussage mul_k(n) = mul_n(k) wahr ist für alle n, k ∈ ℕ.
Sei k im Folgenden eine beliebige, aber fest gewählte natürliche Zahl.
Induktionsanfang:
mul_k(0)
= 0 wegen (M1)
= mul₀(k)
Induktionsvoraussetzung:
Es gelte bereits mul_k(m) = mul_m(k) für ein m ∈ ℕ.
Induktionsschluss:
mul_k(succ(m))
= add_k(mul_k(m)) wegen (M2)
= add_k(mul_m(k)) nach Induktionsvoraussetzung
= mul_succ_(m)(k) aufgrund der unter (i) bewiesenen Regel.

Da hiernach die Aussage mul_k(n) = mul_n(k) für alle n ∈ ℕ und für jedes beliebige k ∈ ℕ wahr ist, ist damit die Behauptung bewiesen.

Nun werden die Addition und die Multiplikation als zweistellige Operationen auf ℕ definiert:

Eine 2-stellige Operation (oder eine Verknüpfung) auf einer Menge M ist eine Abbildung

"@": M x M → M ,

das heißt, jedem geordneten Paar (x;y) mit x ∈ M und y ∈ M wird durch eine Zuordnungsvorschrift in eindeutiger Weise ein Bild @(x;y) ∈ M zugeordnet.

Sei auf einer Menge M eine Verknüpfung "@" definiert.
Seien x, y ∈ M und z ∈ M das Bild von (x;y) ∈ M² unter "@".
Dann sind folgende Schreibweisen gleichbedeutend: @((x;y)) = z @(x;y) = z x @ y = z

Die Verknüpfungen "+" (Addition) und "·" (Multiplikation) werden auf ℕ für alle k, n ∈ ℕ wie folgt definiert:

k + n =_def add_k(n)

k · n =_def mul_k(n)

Die Multiplikation hat gegenüber der Addition die höhere Prioriät, das heißt, für alle k, m, n ∈ ℕ gilt:

k + m · n =_def k + (m · n)
k · m + n =_def (k · m) + n

Anschaulich gesprochen: "Punktrechnung geht vor Strichrechnung".

Wegen add_k(n) = add_n(k) bzw. mul_k(n) = mul_n(k) für alle k, n ∈ ℕ sind die Verknüpfungen "+" und "·" kommutativ, das heißt, für alle k, n ∈ ℕ gilt:

Außerdem gelten nach dem oben Gesagten für alle k, n ∈ ℕ folgende Rechenregeln:

Hiermit kann man zeigen, dass die Verknüpfungen "+" und "·" auch assoziativ sind, das heißt, für alle k, m, n ∈ ℕ gilt

Beweis:
Assoziativgesetz bezüglich der Addition.
Induktionsanfang:
m + (n + 0) = m + n = (m + n) + 0
Das bedeutet, dass die behauptete Aussage für k = 0 wahr ist.
Induktionsvoraussetzung:
Es gelte m + (n + K) = (m + n) + K für ein K ∈ ℕ.
Induktionsschluss:
m + (n + succ(K))
= m + succ(n + K)
= succ(m + (n + K))
= succ((m + n) + K)
= (m + n) + succ(K)

Distributivgesetz.
Induktionsanfang:
k·(m + 0) = k·m = k·m + 0 = k·m + k·0
Induktionsvoraussetzung:
Es gelte k·(m + N) = k·m + k·N für ein N ∈ ℕ.
Induktionsschluss:
k·(m + succ(N))
= k·succ(m + N)
= k + k·(m + N)
= k·(m + N) + k
= (k·m + k·N) + k
= k·m + (k·N + k)
= k·m + (k + k·N)
= k·m + k·succ(N)

Assoziativgesetz bezüglich der Multiplikation.
Induktionsanfang:
m·(n·0) = m·n = (m·n)·0
Induktionsvoraussetzung:
Es gelte m·(n·K) = (m·n)·K für ein K ∈ ℕ.
Induktionsschluss:
m·(n·succ(K))
= m·(n + (n·K))
= (m·n) + m·(n·K)
= (m·n) + ((m·n)·K)
= (m·n)·succ(K)

Beweis:
(N1):
Seien x und y irgendwelche natürliche Zahlen.
Induktionsanfang:
x + 0 = y + 0  ⇔ x = y wegen (A1)
Induktionsvoraussetzung:
Es gelte x + m = y + m  ⇔ x = y für ein m ∈ ℕ.
Induktionsschluss:
Es ist zu zeigen, dass x + succ(m) = y + succ(m)  ⇔ x = y

"⇐":
x = y
⇒ x + m = y + m nach Induktionsvoraussetzung
⇒ succ(x + m) = succ(y + m), denn succ ist eine Abbildung
⇒ x + succ(m) = y + succ(m)

"⇒":
x + succ(m) = y + succ(m)
⇒ succ(x + m) = succ(y + m)
⇒ x + m = y + m, denn die Abbildung succ ist injektiv
⇒ x = y nach Induktionsvoraussetzung

(N2) lässt sich auf analoge Art beweisen.

Die Regeln (N1) und (N2) spielen zum Beispiel eine wesentliche Rolle, wenn es darum geht zu zeigen, dass die Gleichungen von der Form m + x = n bzw. m · x = n mit vorgegebenen Zahlen m und n im Falle der Lösbarkeit eindeutig lösbar sind (siehe: Gleichungen (G1) und (G2) im Kapitel Zahlenmengen).

Seien m, n ∈ ℕ. Dann wird gesetzt:

m ≤ n ⇔_def ∃p ∈ ℕ: m + p = n

Mit anderen Worten:
m ist genau dann kleiner oder gleich n, wenn eine natürliche Zahl p existiert mit der Eigenschaft, dass m + p = n.

Wenn für zwei natürliche Zahlen m und n m ≤ n und m ǂ n gilt, dann schreibt man: m < n.

Beweis:
Induktionsanfang:
Es gilt 0 + 0 = 0, also ist 0 ≤ 0.
Induktionsvoraussetzung:
Es gelte 0 ≤ m für ein m ∈ ℕ.
Induktionsschluss:
0 ≤ m
⇒ 0 + p = m mit passend gewähltem p ∈ ℕ
⇒ (0 + p) + succ(0) = m + succ(0)
⇒ 0 + (p + succ(0)) = m + succ(0)
⇒ 0 ≤ m + succ(0)
Mit (m + succ(0)) = succ(m + 0) = succ(m) folgt die Behauptung.

Mit der oben bewiesenen Rechenregel k + succ(n) = succ(k + n) für alle k, n ∈ ℕ folgt insbesondere
k + succ(0) = succ(k + 0) und damit

Aufgrund dieser Regel ist es jetzt in Verbindung mit der Ordnungsrelation < möglich, alle natürlichen Zahlen "der Reihe nach aufzuschreiben", vornehmer ausgedrückt: "linear zu ordnen":

Beweis:
Seien im Folgenden k, m, n ∈ ℕ beliebig gewählt.

(i) Transitivität:
k ≤ n und n ≤ m
⇒ k + p₁ = n und n + p₂ = m mit passend gewählten p₁, p₂ ∈ ℕ
⇒ (k + p₁) + (n + p₂) = m + n
⇒ (k + (p₁ + p₂)) + n = m + n
⇒ k + (p₁ + p₂) = m
⇒ k ≤ m

(ii) Reflexivität:
n + 0 = n
⇒ n ≤ n denn 0 ∈ ℕ.

(iii) Jede nichtleere Teilmenge von ℕ hat ein kleinstes Element.
ℕ selbst hat ein kleinstes Element, nämlich 0.

Sei nun T ⊂ ℕ irgendeine nichtleere Teilmenge von ℕ.
Induktionsanfang:
Angenommen, T hat nur ein einziges Element t.
Dann ist t ≤ t und t ist trivialerweise kleinstes Element von T.
Induktionsvoraussetzung:
Sei T ⊂ ℕ eine Menge natürlicher Zahlen mit m Elementen und einem kleinsten Element,
es gibt also ein n_min ∈ T: n_min ≤ x für alle x ∈ T.
Induktionsschluss:
Sei nun p irgendeine natürliche Zahl mit p ∉ T.
Dann gilt entweder p < n_min oder n_min< p, weil die natürlichen Zahlen linear geordnet sind.
In der (m+1)-elementigen Menge T* = T ∪ { p } ist demzufolge unter Beachtung der Induktionsvoraussetzung entweder n_min oder p kleinstes Element.

(iv) Identitivität:
m ≤ n und n ≤ m
⇒ m + p₁ = n und n + p₂ = m mit passend gewählten p₁, p₂ ∈ ℕ
⇒ (m + p₁) + (n + p₂) = m + n
⇒ (m + n) + (p₁+ p₂) = m + n
⇒ (m + n) + (p₁+ p₂) = (m + n) + 0
⇒ p₁+ p₂ = 0
⇒ p₁ ≤ 0
⇒ p₁ = 0, denn 0 ist das kleinste Element in ℕ
⇒ m = n

Jeder, der die Menge der natürlichen Zahlen gut kennt, wird über die Resultate der vorstehenden Beweise nicht wirklich überrascht sein: Man kann die Elemente der Menge ℕ der Reihe nach abzählen und mit 0 geht es los. (Der Name der ersten natürlichen Zahl ist im Hinblick auf die Natur der natürlichen Zahlen völlig belanglos; man könnte diese Zahl auch Null nennen, oder zero oder egal-wie.) Es gibt zwei Operationen auf ℕ, die Addition und die Multiplikation, und beide sind kommutativ und assoziativ. Außerdem gelten das Distributivgesetz k(m + n) = km + kn für alle k, m, n ∈ ℕ sowie ein paar andere nützliche Rechenregeln . Es gibt ferner eine Relation ≤ auf ℕ, mit der die natürlichen Zahlen wohlgeordnet sind.

Das alles ist nicht erstaunlich. Erstaunlich ist vielmehr, das alle diese Eigenschaften von ℕ tatsächlich allein mit den wenigen Axiomen (I) bis (IV) zusammenfassend und vollständig beschreibbar sind. Man erschließt sich diese Eigenschaften der Reihe nach im Wesentlichen mit einem Beweisprinzip, und dies ist das Prinzip der vollständigen Induktion.

Bemerkenswert ist auch, dass sich alle Gesetze in ℕ samt ihrer Beweise formulieren lassen, ohne die natürlichen Zahlen in irgendeiner Weise bezeichnen zu müssen, mit Ausnahme der kleinsten natürlichen Zahl. Um in ℕ unter Benutzung dieser Gesetze praktisch rechnen zu können, muss man natürlich Namen für die natürlichen Zahlen erfinden.

Die Idee, die natürlichen Zahlen mit Hilfe von dezimalen Zahlzeichen zu bezeichnen, stammt ursprünglich aus Indien. Der persische Mathematiker Abu Ja'far Muhammad ibn Musa al-Chwarizmi (etwa 780 - 850) hat das Dezimalsystem in seinem berühmten Werk hisab al-jabr wal-muqabalah verwendet. Danach hat es noch viele Jahrhunderte gedauert, bis das indische Dezimalsystem auch in Europa genutzt wurde.

Man benötigt zur Darstellung der natürlichen Zahlen im Dezimalsystem zehn Zahlzeichen, die je nach Sprache bzw. Schrift ganz unterschiedlich aussehen können. Beispiele:

2 =_def 1 + 1; 3 =_def 2 + 1; 4 =_def 3 + 1; 5 =_def 4 + 1;
6 =_def 5 + 1; 7 =_def 6 + 1; 8 =_def 7 + 1; 9 =_def 8 + 1;

Im Dezimalsystem haben die zehn Zahlzeichen zwei unterschiedliche Bedeutungen: zum einen dienen sie dazu, die ersten zehn natürlichen Zahlen zu bezeichnen, zum anderen benutzt man sie zur Bezeichnung aller weiteren natürlichen Zahlen, wobei sie als Ziffern abhängig von ihrer Stelle innerhalb der die natürlichen Zahlen beschreibenden Ziffernfolgen verschieden interpretiert werden.

Mit Hilfe der Zehnerpotenzen kann jede natürliche Zahl z ∈ ℕ wie folgt dargestellt werden:

Hierbei ist jedes der z_ieine der Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
(n-1) ist die natürliche Zahl, für die gilt: (n-1) + 1 = n.

Beweis:
Induktionsanfang:
Es gilt 0 = 0·1 = 0·10⁰.
Induktionsvoraussetzung:
Sei z ∈ ℕ dargestellt als n-stellige Dezimalzahl, das heißt,
es gelte z = z₀·10⁰ + z₁·10¹ + z₂·10² + ... + z_n-1·10^n-1 mit n ∈ ℕ;
z₀, z₁, z₂, ..., z_n-1 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} und
z_n-1 ǂ 0.
Induktionsschluss:
Es ist zu zeigen, dass (z + 1) auf die gleiche Art wie z dargestellt werden kann.

Fall 1: z₀ ǂ 9.
Dann gilt
z + 1
= 1 + (z₀·10⁰ + z₁·10¹ + ... + z_n-1·10^n-1) wegen der Kommutativität bezüglich "+"
= (1·10⁰+ z₀·10⁰) + z₁·10¹ + ... + z_n-1·10^n-1 wegen der Assoziativität bezüglich "+"
= (z₀+ 1)·10⁰ + z₁·10¹ + ... + z_n-1·10^n-1 wegen des Distributivgesetzes in ℕ
= Z₀·10⁰ + z₁·10¹ + z₂·10² + ... + z_n-1·10^n-1 mit Z₀ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 2: z₀= 9 und z₁ ǂ 9.
Dann gilt
z + 1
= 1 + (9·10⁰ + z₁·10¹ + ... + z_n-1·10^n-1)
= 10·10⁰ + z₁·10¹ + ... + z_n-1·10^n-1
= 10¹ + z₁·10¹ + ... + z_n-1·10^n-1
= 0·10⁰ + (z₁+ 1)·10¹ + z₂·10² + ... + z_n-1·10^n-1
= z₀·10⁰ + Z₁·10¹ + ... + z_n-1·10^n-1 mit Z₁ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 3: z₀= z₁= ... = z_i= 9 und z_i+1 ǂ 9 mit 0 < i < n-1
Dann gilt
z + 1
= 1 + (9·10⁰ + 9·10¹ + ... + z_i+1·10ⁱ⁺¹ + ... + z_n-1·10^n-1)
= 0·10⁰ + 0·10¹ + ... + 0·10ⁱ + (z_i+1+ 1)·10ⁱ⁺¹ + ... + z_n-1·10^n-1
= 0·10⁰ + 0·10¹ + ... + 0·10ⁱ + Z_i+1·10ⁱ⁺¹ + ... + z_n-1·10^n-1 mit Z_i+1 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 4: z₀= z₁= ... = z_n-1= 9
Dann gilt
z + 1
= 0·10⁰ + 0·10¹ + ... + 0·10^n-1 + 1·10ⁿ.

Für z = z₀·10⁰ + z₁·10¹ + z₂·10² + ... + z_n-1·10^n-1 schreibt man abkürzend:

In dem Ausdruck z_n-1...z₂z₁z₀sind die z_i keine Zahlen, sondern Ziffern, also Dezimalzeichen!
Beispielsweise ist 97132 = 2·10⁰ + 3·10¹ + 1·10² + 7·10³ + 9·10⁴.

Für succ(0), den Nachfolger der kleinsten natürlichen Zahl 0, haben wir die Bezeichnung "1" hingeschrieben.
Es gilt