Mittels Rekursion lassen sich die Rechenoperationen Addition und Multiplikation definieren:
Definition. Die Zahl $m\in\mathbb{N}$ sei gegeben. Wir definieren die Additionsabbildung $\mathbb{N}\to\mathbb{N},n\mapsto m+n$, rekursiv durch $m+1:=f(m)$ und $m+f(n):=f(m+n)$ für alle $n\in\mathbb{N}$.
So erhält man:
1.3.1. Proposition. $$2+2=4.$$
Beweis. $$2+2=2+f(1)=f(2+1)=f(f(2))=f(3)=4.$$ qed
Definition. Die Zahl $m\in\mathbb{N}$ sei gegeben. Wir definieren die Multiplikationsabbildung $\mathbb{N}\to\mathbb{N},n\mapsto m\cdot n$, rekursiv durch $m\cdot1:=m$ und $m\cdot f(n):=(m\cdot n)+m$ für alle $n\in\mathbb{N}$.
Für die so definierten Rechenoperationen können wir die bekannten Rechenregeln beweisen. Hier ein Beispiel:
1.3.2. Proposition (Assoziativität der Addition). Für alle $m,n,p\in\mathbb{N}$ gilt: $$m+(n+p)=(m+n)+p.$$
Beweis. Die Aussage $A(p)$ besage, dass für alle $m,n\in\mathbb{N}$ gilt $m+(n+p)=(m+n)+p$. Wir beweisen $A(p)$ für alle $p\in\mathbb{N}$ durch Induktion nach $p$.
- Induktionsverankerung: Aussage $A(1)$ besagt: $m+(n+1)=(m+n)+1$ für alle $m,n\in\mathbb{N}$. Diese Aussage ist richtig nach Definition der Addition.
- Induktionsschritt: Die Aussage $A(p)$ sei wahr. Es ist zu zeigen, dass dann auch $A(p+1)$ wahr ist. In der Tat gilt: $$\begin{align*} m+(n+(p+1)) & =m+((n+p)+1) & & \text{nach Definition der Addition}\\ & =(m+(n+p))+1 & & \text{nach Definition der Addition}\\ & =((m+n)+p)+1 & & \text{weil nach Annahme A(p) wahr ist}\\ & =(m+n)+(p+1) & & \text{nach Definition der Addition.} \end{align*}$$
qed
Die restlichen Eigenschaften von Addition und Multiplikation lassen sich alle auf ähnliche Weise beweisen. Wichtige Rechenregeln sind im folgenden Satz gelistet.
1.3.3. Satz. Für natürliche Zahlen $m,n,p\in\mathbb{N}$ gelten die Rechenregeln
- Kommutativität der Addition $$m+n=n+m,$$
- Distributivität $$\begin{align*} m\cdot(n+p)&=(m\cdot n)+(m\cdot p)\\ (m+n)\cdot p&=(m\cdot p)+(n\cdot p)\end{align*}$$
- Assoziativität der Multiplikation $$m\cdot(n\cdot p)=(m\cdot n)\cdot p,$$
- Kommutativität der Multiplikation $$m\cdot n=n\cdot m.$$
Beweis.
Wir beweisen die Kommutativität der Addition und hier zuerst den Spezialfall $n=1$. Zu beweisen ist die Gültigkeit der Aussage $A(m)$ für alle $m\in \mathbb{N}$. Die Aussage $A(m)$ postuliert die Gültigkeit der Gleichung $1+m=m+1$.
- Induktionsverankerung: Aussage $A(1)$ ist die Tautologie $1+1=1+1$.
- Induktionsschritt: Die Aussage $A(m)$ sei wahr. Dass dann auch $A(m+1)$ wahr ist, folgt aus der Gleichungskette: $$\begin{align*} 1+(m+1) & =(1+m)+1 & & \text{wegen Assoziativität der Addition}\\ & =(m+1)+1 & & \text{weil nach Annahme A(m) wahr ist}\end{align*}$$
Nun nehmen wir uns der Aussage $B(n)$ an, welche besagt: Für alle $m\in\mathbb{N}$ gilt $m+ n=n+m$.
- Induktionsverankerung: Die Aussage $B(1)$ ist die soeben bewiesene Aussage $A$.
- Induktionsschritt: Wir nehmen an, $B(n)$ sei wahr. Die Aussage $B(n+1)$ folgt aus der Gleichungskette: $$\begin{align*} m+(n+1) & =(m+n)+1 & & \text{wegen Assoziativität der Addition}\\ & =(n+m)+1 & & \text{weil nach Annahme B(n) wahr ist}\\ & =n+(m+1) & & \text{wegen Assoziativität der Addition}\\ & =n+(1+m) & & \text{weil B(1) wahr ist}\\ & =(n+1)+m & & \text{wegen Assoziativität der Addition}
\end{align*}$$
Der Beweis der übrigen Rechenregeln ist für die Übungen vorgesehen. Es empfiehlt sich, die angegebene Reihenfolge einzuhalten.
qed