Die Arithmetik der natürlichen Zahlen
Mit Hilfe von Rekursion können wir die gesamte Arithmetik auf ℕ einführen:
Definition (Addition auf ℕ)
Wir definieren für alle m ∈ ℕ durch Rekursion über n ∈ ℕ:
m + 0 = m,
m + S(n) = S(m + n) für alle n ∈ ℕ.
Die Funktion + : ℕ2 → ℕ heißt die Addition auf ℕ. Für alle m, n ∈ ℕ heißt m + n die Summe von m und n, und m und n heißen die Summanden des Terms m + n.
Speziell gilt dann also:
m + 1 = m + S(0) = S(m + 0) = S(m) für alle m ∈ ℕ.
Mit Hilfe der Addition können wir nun auch die Multiplikation rekursiv definieren:
Definition (Multiplikation auf ℕ)
Wir definieren für alle m ∈ ℕ durch Rekursion über n ∈ ℕ:
m · 0 = 0,
m · S(n) = (m · n) + m für alle n ∈ ℕ.
Die Funktion · : ℕ2 → ℕ heißt die Multiplikation auf ℕ. Für alle m, n ∈ ℕ heißt m · n das Produkt von m und n, und m und n heißen die Faktoren des Terms m · n.
Wir schreiben wie üblich oft auch m n anstelle von m · n. Weiter vereinbaren wir, dass die Multiplikation stärker bindet als die Addition, d. h. m n + k ist die Summe (m n) + k und nicht etwa das Produkt m (n + k).
Mit Hilfe der Multiplikation wird schließlich auch noch die Exponentiation auf ℕ rekursiv eingeführt:
Definition (Exponentiation auf ℕ)
Für alle m ∈ ℕ definieren wir durch Rekursion über n ∈ ℕ:
m0 = 1,
mS(n) = mn · m für alle n ∈ ℕ.
Die Funktion (·)(·) : ℕ2 → ℕ heißt die Exponentiation auf ℕ. Für alle m ∈ ℕ heißt weiter die Funktion m(·) : ℕ → ℕ die Exponentiation zur Basis m.
Für alle m, n ∈ ℕ heißt mn die Potenz von m und n, und m heißt die Basis und n der Exponent des Terms mn.
Aus diesen Definitionen kann man alle vertrauten Eigenschaften der arithmetischen Operationen auf den natürlichen Zahlen ableiten. So gelten universell, d. h. für alle natürlichen Zahlen n, m, k, … die Gesetze:
n + (m + k) = (n + m) + k, n · (m · k) = (n · m) · k, (Assoziativität)
n + m = m + n, n · m = m · n, (Kommutativität)
n · (m + k) = n · m + n · k, (Distributivität)
nm · nk = nm + k, (nm)k = nm · k, nk · mk = (n · m)k. (Exponentiationsregeln)
Aus der Assoziativität und Kommutativität der Addition folgen viele weitere einfache Dinge, wie zum Beispiel
n + S(m) = n + (m + 1) = n + (1 + m) = (n + 1) + m = S(n) + m.