Nachfolgerstruktur (Konstruktion von $\mathbb{N}$)

Eine Menge $N$ mit einer Abbildung $\sigma:N\rightarrow N$ ($\sigma$ heiße Nachfolgerabbildung) heißt Nachfolgerstruktur, falls sie die Peano-Axiome erfüllt:

1. $\left(P_{1}\right)$ Es gibt ein Element $o\in N$, so dass $\forall x\in N:\sigma\left(x\right)\neq o$
2. $\left(P_{2}\right)$ Aus $\sigma\left(x\right)=\sigma\left(y\right)$ folgt $x=y$ ($\sigma$ ist injektiv)
3. $\left(P_{3}\right)$ Ist $X\subseteq N$ eine Teilmenge, und gilt $o\in X$, und folgt aus $x\in X\Rightarrow\sigma\left(x\right)\in X$ (d.h. $X$ ist abgeschlossen unter der Nachfolgerfunktion) so gilt $X=N$.

• $\left(P_{3}\right)$ ist das Axiom der vollständigen Induktion.
• Es gibt genau eine Nachfolgerstruktur mit $\left(\mathbb{N},s\right)$ mit $o=\emptyset$ und $s\left(x\right)=x\cup\left\{ x\right\}$
• Ist $\left(N,\sigma\right)$ eine Nachfolgerstruktur, dann gibt es genau eine bijektive Abbildung $\varphi:\mathbb{N}\rightarrow N$ mit $\varphi\left(\emptyset\right)=o$, $s\left(x\right)=x\cup\left\{ x\right\}$ und $\varphi\left(s\left(x\right)\right)=\sigma\left(\varphi\left(x\right)\right)$
• Addition:
  $o+o=o$
  $o+x=x=x+o$
  $\sigma\left(x\right)+y=\sigma\left(x+y\right)$
• Multiplikation:
  $o*o=o$
  $o*x=o=x*o$
  $\sigma\left(x\right)*y=x*y+y$
• Bei dieser Kodierung der natürlichen Zahlen gilt:
  $n<m\Leftrightarrow n\in m$

Vollständige Induktion

Das Peano-Axiom $\left(P_{3}\right)$ sagt: ist $\varphi$ eine Aussage über natürliche Zahlen und gilt:

1. $\varphi\left(0\right)$ ist wahr
2. $\varphi\left(n\right)\Rightarrow\varphi\left(n+1\right)$

dann ist $\varphi\left(m\right)$ wahr für alle $m\in\mathbb{N}$.