Nachfolger und Induktion
Das Zählen ist bestimmt durch die Nachfolgerbildung, die einer Zahl n ihren direkten Nachfolger S(n) zuordnet:
0, 1, 2, 3, …, n, S(n), …, …, …, m, S(m), …
Die Elemente dieser Reihe − wie auch immer wir sie konstruieren und benennen wollen − heißen natürliche Zahlen. Die Menge aller natürlichen Zahlen bezeichnen wir mit ℕ.
Die Zählreihe beginnt mit einer ausgezeichneten Zahl, dem Anfangselement der Zählreihe. Wir nennen dieses Anfangselement die Null der Zählreihe. Bei der Einführung der Arithmetik wird die Null auch die übliche Rolle einer Null übernehmen. Hier wollen wir nur das Zählen selbst betrachten, der Name für das Anfangselement ist prinzipiell beliebig.
Die Null ist kein Nachfolger einer Zahl, jede von Null verschiedene Zahl ist dagegen der Nachfolger genau einer anderen Zahl. Es werden immer neue Zahlen gebildet, die Nachfolgerfunktion ist injektiv: Haben zwei Zahlen denselben Nachfolger, so sind sie gleich. Weiter wird die Zählreihe durch die bei Null beginnende Nachfolgerbildung vollkommen bestimmt und ausgeschöpft. Diese komplexe und keineswegs unproblematische Intuition versuchen wir durch ein Induktionsschema auszudrücken:
Gilt eine Eigenschaft ℰ für die Null, und gilt ℰ mit n stets auch für S(n),
so gilt ℰ für alle n.
(Induktionsschema für Eigenschaften)
Formal:
ℰ(0) ∧ ∀n(ℰ(n) → ℰ(S(n))) → ∀n ℰ(n).
Statt von einer Eigenschaft ℰ(n) können wir auch von der Menge aller natürlichen Zahlen reden, auf die die Eigenschaft ℰ zutrifft. Wir setzen dann
X = { n ∈ ℕ | ℰ(n) }.
Ist umgekehrt X eine Teilmenge von ℕ, so ist „n ∈ X“ eine Eigenschaft für natürliche Zahlen. Das Induktionsschema lautet bei dieser Sicht der Dinge dann wie folgt:
Ist X eine Teilmenge von ℕ, die die Null enthält und die unter der Nachfolgerfunktion abgeschlossen ist, so ist X = ℕ. (mengentheoretisches Induktionsaxiom)
Formal:
∀X ⊆ ℕ (0 ∈ X ∧ ∀n (n ∈ X → S(n) ∈ X) → X = ℕ).
Im Gegensatz zum Induktionsschema für Eigenschaften, wo wir ein Induktions-Axiom pro Eigenschaft und damit unendlich viele Axiome fordern, können wir also in einer mengentheoretischen Umgebung das Induktionsprinzip durch ein einziges Axiom ausdrücken.
Diese intuitive Beschreibung des Zählens übersetzen wir nun in eine mathematische Begriffsbildung.