Peano-Arithmetik

Die Peano-Arithmetik erster Stufe ist ein Axiomensystem, das die Natürlichen Zahlen formal innerhalb der Prädikatenlogik erster Stufe definiert. Sie enthält alle Peano-Axiome außer das Induktionsaxiom, das in Prädikatenlogik zweiter Stufe formuliert ist, weil es eine Bedingung über Teilmengen natürlicher Zahlen enthält. Dieses Axiom kann nicht in der Prädikatenlogik erster Stufe ausgedrückt werden, weil die Teilmengenbedingung eine Quantifizierung über Mengen natürlicher Zahlen erfordert, die hier nicht möglich ist. Das Induktionsaxiom von Peano kann aber ersetzt werden durch ein Axiomenschema, das abzählbar unendlich viele Induktionsaxiome generiert:

Sei ${\bar {y}}$ eine Abkürzung für $\,y_{1},...,y_{k}$.

Für jede Formel $\phi (x,{\bar {y}})$ lautet dann das Induktionsaxiom erster Stufe:

$\forall {\bar {y}}(\phi (0,{\bar {y}})\land \forall x(\phi (x,{\bar {y}})\Rightarrow \phi (x+1,{\bar {y}}))\Rightarrow \forall x\phi (x,{\bar {y}}))$