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.

John Fremlin 2010-02-17