Peano Arithmetic

Definition 5..46 (Language of Peano arithmetic)  

$\Omega = \{ 0, s, +, \times \}$ where $s$ is the successor function.

Definition 5..47 (Axioms of Peano Arithmetic)  

1. $(\forall x)(\neg(s(x) = 0))$
2. $(\forall x,y)((s(x) = s(y)) \Rightarrow (x=y))$
3. $(\forall y_1)\cdots(\forall y_n)((p[0/x] \wedge (\forall x)(p \Rightarrow p[s(x)/x])) \Rightarrow (\forall x)p)$, that is, induction with parameters $(\forall y_1)\cdots(\forall y_n)$ for free variables in $p$.
4. $(\forall x)(x + 0 = x)$
5. $(\forall x,y)(x + s(y) = s(x + y))$
6. $(\forall x)(x \times 0 = 0)$
7. $(\forall x,y)(x \times s(y) = (x \times y) + x)$

The first three axioms are sometimes called weak Peano Arithmetic.

Observation 5..48  

We might have first guessed that the induction axiom should have been $(p[0/x] \wedge (\forall x)(p \Rightarrow p[s(x)/x]))\Rightarrow (\forall x)p$. But this is not how we do induction in real life.

Definition 5..49 (Axiom scheme)  

The induction axiom is in fact a different axiom for each $p$. An axiom like this specifying an infinite set of axioms is sometimes called an axiom scheme.

Observation 5..50  

PA has an infinite model ( $\mathbb{N}$) so by the Upward-Löwenheim-Skolem theorem PA has an uncountable model which is therefore not $\mathbb{N}$. But we would like $\mathbb{N}$ to be characterized uniquely by these axioms. The problem is that the induction axiom is not powerful enough - it only refers to countably many subsets of $\mathbb{N}$ (those defined by a $p$) whereas normal induction refers to all subsets.

Therefore induction is not a first order property.