Arithmetik und Ordnung auf den natürlichen Zahlen
Bislang können wir nur Nachfolger bilden. Die Arithmetik auf den natürlichen Zahlen lässt sich mit Hilfe von Rekursion einführen. Bei dieser Definitionsform definieren wir zunächst ein Objekt F(0). Weiter definieren wir für alle n ein Objekt F(S(n)) unter Verwendung von F(n) (oder allgemeiner F(0), …, F(n)).
Rekursive Definition der Addition
Sei m ∈ ℕ. Wir definieren rekursiv:
m + 0 = m, m + S(n) = S(m + n) für alle n ∈ ℕ.
Beispiel
Es gilt 2 + 2 = 2 + S(1) = S(2 + 1) = S(3) = 4. Weiter gilt
n + 1 = n + S(0) = S(n + 0) = S(n) für alle n ∈ ℕ.
Rekursive Definition der Multiplikation
Für alle m ∈ ℕ setzen wir:
m · 0 = 0, m · S(n) = m · n + m für alle n ∈ ℕ.
Die Form ist durch m · S(n) = m · (n + 1) und das Distributivgesetz motiviert. Wir lassen Malpunkte oft weg und schreiben kurz m n statt m · n.
Mit Hilfe des Induktionsaxioms lassen sich alle Rechengesetze nachweisen:
∀n,m,k (n + m) + k = n + (m + k)(Assoziativgesetz für die Addition)
∀n,m n + m = m + n(Kommutativgesetz für die Addition)
∀n,m,k (n m) k = n (m k)(Assoziativgesetz für die Multiplikation)
∀n,m n m = m n(Kommutativgesetz für die Multiplikation)
∀n,m,k n (m + k) = nm + n k (Distributivgesetz)
Analog können wir die Exponentiation rekursiv durch m0 = 1, mn + 1 = mn · m einführen und die Potenzregeln zeigen.
Die Ordnung lässt sich vergleichsweise leicht definieren:
Definition der Ordnung
Wir setzen für alle natürlichen Zahlen n, m:
n ≤ m, falls ∃k n + k = m.
Die Relation ≤ ist reflexiv, antisymmetrisch und transitiv. Zudem gilt:
∀n, m (n ≤ m ∨ m ≤ n)(Vergleichbarkeit)