Zählen

Die natürlichen Zahlen aus nichts als einer Null und einem Nachfolger: die Axiome von Peano, Addition durch Rekursion, die vollständige Induktion, und der Gnomon der Pythagoreer, der die ungeraden Zahlen zu Quadraten fügt.

„Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk“, soll Leopold Kronecker 1886 gesagt haben. Ende des 19. Jahrhunderts wollten Mathematiker es genauer wissen. Was genau ist eine natürliche Zahl, und was muss man über sie annehmen, damit alles Übrige folgt? Die Antwort, die Richard Dedekind 1888 und Giuseppe Peano 1889 fanden, ist erstaunlich knapp: Man braucht eine erste Zahl und die Möglichkeit, immer eine weiterzuzählen.

Die Axiome von Peano

Wir beginnen wie Lean bei der Null und schreiben $S(n)$ für den Nachfolger von $n$ , die Zahl, die beim Zählen als nächste kommt.

Axiom 1 bis 5

Es gibt eine Menge $\mathbb{N}_0$ , ein Element $0 \in \mathbb{N}_0$ und eine Abbildung $S : \mathbb{N}_0 \to \mathbb{N}_0$ mit

$0 \in \mathbb{N}_0$ ,
$n \in \mathbb{N}_0 \Rightarrow S(n) \in \mathbb{N}_0$ ,
$S(n) \neq 0$ für alle $n$ ,
$S(m) = S(n) \Rightarrow m = n$ ,
Ist $A \subseteq \mathbb{N}_0$ mit $0 \in A$ und $n \in A \Rightarrow S(n) \in A$ , so ist $A = \mathbb{N}_0$ .

Was die fünf Sätze in Worten sagen:

Es gibt einen Anfang, die Null.
Nach jeder Zahl kommt eine weitere.
Die Kette läuft nie zur Null zurück. Eine Uhr, die nach 11 wieder bei 0 anfängt, erfüllt dieses Axiom nicht.
Zwei verschiedene Zahlen haben verschiedene Nachfolger. Die Kette verzweigt sich nicht und läuft nicht zusammen.
Wer bei der Null anfängt und immer weiterzählt, erreicht jede Zahl. Es gibt keine Zahlen außerhalb der Kette.

Das fünfte Axiom ist das Induktionsaxiom, die Dominokette aus Kapitel 1. Es ist der Grund, warum Beweise durch Induktion gültig sind: Die Menge $A$ der Zahlen, für die eine Aussage stimmt, enthält die Null und mit jeder Zahl ihren Nachfolger, also nach Axiom 5 alle Zahlen.

Die vertrauten Namen sind nur Abkürzungen: $1 := S(0)$ , $2 := S(1)$ , $3 := S(2)$ und so weiter. Die Tetraktys ist in dieser Sprache zehnmal weitergezählt:

10 = S(S(S(S(S(S(S(S(S(S(0)))))))))).

Rechnen aus dem Zählen

Auch die Addition muss man nicht voraussetzen. Man definiert sie durch Rekursion, indem man sagt, wie man mit 0 addiert und wie man einen Schritt weiter kommt.

Definition

Für $a, b \in \mathbb{N}_0$ sei

a + 0 := a, \qquad a + S(b) := S(a + b).

Ebenso für die Multiplikation:

a \cdot 0 := 0, \qquad a \cdot S(b) := a \cdot b + a.

Damit lässt sich jede Rechnung auf das Weiterzählen zurückführen, zum Beispiel

\begin{aligned} 2 + 2 &= 2 + S(1) = S(2 + 1) \\ &= S(2 + S(0)) = S(S(2 + 0)) \\ &= S(S(2)) = S(3) = 4. \end{aligned}

Das sieht umständlich aus, und das soll es auch. Es zeigt, dass in $2 + 2 = 4$ nichts steckt, was nicht aus den Axiomen folgt. Selbst Dinge, die jedes Kind weiß, müssen nun bewiesen werden, denn die Definition sagt nur etwas über $a + 0$ , nicht über $0 + a$ .

Satz 1

Für alle $a \in \mathbb{N}_0$ gilt $0 + a = a$ .

Beweis

Durch Induktion über $a$ . Anfang: $0 + 0 = 0$ nach Definition. Schritt: Gilt $0 + a = a$ , so ist $0 + S(a) = S(0 + a) = S(a)$ , die erste Gleichung nach Definition, die zweite nach Annahme.

∎

Satz 2

Die Addition ist kommutativ: $a + b = b + a$ für alle $a, b \in \mathbb{N}_0$ .

Beweis

Zuerst ein Hilfssatz: $S(a) + b = S(a + b)$ . Er folgt durch Induktion über $b$ : Für $b = 0$ sind beide Seiten $S(a)$ , und aus der Annahme für $b$ folgt

\begin{aligned} S(a) + S(b) &= S(S(a) + b) \\ &= S(S(a + b)) = S(a + S(b)). \end{aligned}

Nun Induktion über $b$ für den Satz selbst. Anfang: $a + 0 = a = 0 + a$ nach Definition und Satz 1. Schritt: Gilt $a + b = b + a$ , so ist

\begin{aligned} a + S(b) &= S(a + b) \\ &= S(b + a) = S(b) + a, \end{aligned}

die letzte Gleichung nach dem Hilfssatz.

∎

Nach demselben Muster beweist man, dass die Addition assoziativ ist, dass die Multiplikation kommutativ ist und dass das Distributivgesetz gilt. Alle Rechenregeln der Schule folgen aus den fünf Axiomen.

Vom Computer geprüft: der Beweis in Lean

Hier baut Lean die natürlichen Zahlen selbst, genau nach Peano: inductive Zahl sagt, eine Zahl ist entweder null oder nach einer Zahl, der Nachfolger. Lean folgert daraus von selbst die Axiome 3 bis 5. plus ist die Addition nach der Definition oben, null_plus ist Satz 1, plus_komm ist Satz 2 mit dem Hilfssatz nach_plus. Am Ende steht Satz 3 über die ungeraden Zahlen, diesmal mit Leans eingebauten Zahlen Nat. Wer das selbst üben will: Das Natural Number Game von Kevin Buzzard (Imperial College London), heute auf einem Server der Universität Düsseldorf, führt Schritt für Schritt durch genau diese Beweise.

/-! Kapitel 2: Die natürlichen Zahlen nach Peano, selbst gebaut -/

/-- Eine natürliche Zahl ist entweder null oder
    der Nachfolger einer natürlichen Zahl. -/
inductive Zahl where
  | null : Zahl
  | nach : Zahl → Zahl

open Zahl

/-- Addition, nur aus null und Nachfolger definiert:
    a + 0 = a und a + nach b = nach (a + b) -/
def plus : Zahl → Zahl → Zahl
  | a, null => a
  | a, nach b => nach (plus a b)

/-- Satz 1: 0 + a = a. Das steht nicht in der Definition
    und muss bewiesen werden. -/
theorem null_plus (a : Zahl) : plus null a = a := by
  induction a with
  | null => rfl
  | nach a ih => simp [plus, ih]

/-- Hilfssatz: nach a + b = nach (a + b) -/
theorem nach_plus (a b : Zahl) :
    plus (nach a) b = nach (plus a b) := by
  induction b with
  | null => rfl
  | nach b ih => simp [plus, ih]

/-- Satz 2: Die Addition ist kommutativ, a + b = b + a. -/
theorem plus_komm (a b : Zahl) : plus a b = plus b a := by
  induction b with
  | null => simp [plus, null_plus]
  | nach b ih => simp [plus, nach_plus, ih]

/-- Die Summe der ersten n ungeraden Zahlen
    1 + 3 + … + (2n − 1) -/
def ungerade : Nat → Nat
  | 0 => 0
  | n + 1 => ungerade n + (2 * n + 1)

/-- Satz 3: 1 + 3 + 5 + … + (2n − 1) = n² -/
theorem ungerade_quadrat (n : Nat) : ungerade n = n * n := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [ungerade, ih]
    grind

Im Browser ausprobieren auf live.lean-lang.org ↗Wie man Lean liest

Der Gnomon der Pythagoreer

Die Pythagoreer legten Zahlen mit Steinchen und sahen dabei Gesetze, die man heute durch Induktion beweist. Das berühmteste ist der Gnomon, der Winkelhaken. Legt man um ein Quadrat aus Steinchen einen Haken, entsteht das nächste Quadrat, und die Haken enthalten nacheinander 1, 3, 5, 7 … Steinchen, die ungeraden Zahlen. Aristoteles erwähnt in seiner Physik (III 4) knapp das Herumlegen der Gnomone um die Eins als Lehre der Pythagoreer, die Deutung mit den ungeraden Zahlen und den Quadraten stammt von späteren Kommentatoren.

Jeder Winkelhaken enthält zwei Steinchen mehr als der vorige. Zusammen bilden die ersten n ungeraden Zahlen das Quadrat n mal n.

Satz 3

Für alle $n \in \mathbb{N}$ gilt

\begin{gathered} 1 + 3 + 5 + \dots + (2n - 1) \\ = \sum_{i=1}^{n} (2i - 1) = n^2. \end{gathered}

Beweis

Durch Induktion über $n$ . Anfang: Für $n = 1$ ist $1 = 1^2$ . Schritt: Gilt die Formel für $n$ , so ist

\begin{aligned} \sum_{i=1}^{n+1} (2i - 1) &= n^2 + (2n + 1) \\ &= (n+1)^2. \end{aligned}

Das ist genau der Haken im Bild: Um das Quadrat $n \times n$ legt man $n$ Steinchen oben, $n$ rechts und eines in die Ecke, zusammen $2n + 1$ .

∎

Hier zeigt sich, warum man die pythagoreische Zahlenlehre gern einen Ursprung der Mathematik nennt, wie wir sie kennen, auch wenn Babylonier und Ägypter schon früher rechneten. Die Steinchen sind keine Spielerei. Wer sieht, dass der Haken bei jedem Quadrat gleich gebaut ist, hat den Induktionsschritt verstanden, auch wenn der Name dafür erst zweitausend Jahre später kam. Die geraden Zahlen geben auf dieselbe Weise die Rechteckzahlen $n(n+1)$ , und deren Hälften sind die Dreieckszahlen aus Kapitel 1.

Wo das auf dieser Website vorkommt

Dreieckszahlen, Tetraederzahlen und die Simplexe mit ihren $T(n-1)$ Kanten (siehe Das Punktedreieck und Vom Punkt zum Körper) sind alle durch solche Summen definiert, und ihre Formeln werden durch Induktion bewiesen. Wie man aus dem Zählen das Teilen gewinnt, zeigt das nächste Kapitel, Teilen.

Quellen und Literatur

Quellen

Richard Dedekind, Was sind und was sollen die Zahlen?, Braunschweig 1888
Giuseppe Peano, Arithmetices principia, nova methodo exposita, Turin 1889
Aristoteles, Physik III 4, 203a (der Gnomon)
Heinrich Weber, Leopold Kronecker, Jahresbericht der Deutschen Mathematiker-Vereinigung 2, 1893 (das Wort über die ganzen Zahlen)

Zum Weiterlesen

Kevin Buzzard und Mohammad Pedramfar, Natural Number Game, Lean-Lernspiel im Netz