Complete induction in the Peano system

Question

Is complete induction valid in the Peano model of the naturals and why. In more detail if $L$ is the first order language $\{ +, \cdot, 0, <,S\}$ and $T$ is the theory with non-logical axioms

$$PA0.\qquad 0\not= SX_0$$ $$PA1.\qquad SX_0 = SX_1 \to X_0=X_1$$ $$PA2.\qquad X_0\cdot 0=0$$ $$PA3.\qquad X_0+SX_1=S(X_0+X_1)$$ $$PA4.\qquad X_0+0=X_0$$ $$PA5.\qquad X_0\cdot SX_1=X_0\cdot X_1+X_0$$ $$PA6.\qquad X_0 \not\lt X_0$$ $$PA7.\qquad X_0 \lt SX_1\equiv X_0=X_1 \lor X_0\lt X_1$$ $$PA8.\qquad X_0 \lt X_1 \lor X_0=X_1 \lor X_1 \lt X_0$$ $$PA9.\qquad X_0 \lt X_1 \to X_1 \lt X_0 \to X_0 \lt X_2$$

In addition, the induction scheme: if A is a formula from L than for each variable X $$PA10.\qquad A_X[0]\to\forall _X(A\to A_X[SX])\to\forall _XA$$

Than show that for all formulas A, for all variables X $$\vdash \forall _X(\forall _Y(Y\lt X\to A_X[Y])\to A)\to A$$

Answer 1

Set $P(x) := \forall y, y < x \Rightarrow Q(y)$.

Given (H0) $\forall x, (\forall y, y < x \Rightarrow Q(y)) \Rightarrow Q(x)$ we use induction on $P$:

• $\forall y, y < 0 \Rightarrow Q(0)$ trivial
• $[\forall y, y < x \Rightarrow Q(y)] \Rightarrow [\forall y, y < Sx \Rightarrow Q(y)]$ just split the conseqent into cases (A) $y < x$ trivial by induction hypothesis (B) $y=x$ immediate from H0.

Thus we have $$[\forall x, (\forall y, y < x \Rightarrow Q(y)) \Rightarrow Q(x)] \Rightarrow \forall x, \forall y, (y < x \Rightarrow Q(y))$$ as a theorem of PA which you can now weaken to get the theorem you wanted.

---

We strengthened $\forall x, Q(x)$ to $\forall x, \forall y, (y < x \Rightarrow Q(y))$ to make the induction go through (this is a general technique called strengthening the induction hypothesis).

This gave us a proof of

$$(T0)\,\, [\forall x, (\forall y, y < x \Rightarrow Q(y)) \Rightarrow Q(x)] \Rightarrow \forall x, \forall y, (y < x \Rightarrow Q(y))$$

but all we really wanted was

$$(T1)\,\, [\forall x, (\forall y, y < x \Rightarrow Q(y)) \Rightarrow Q(x)] \Rightarrow \forall z, Q(z)$$

thus we use the fact that $$[\forall x, \forall y, (y < x \Rightarrow Q(y))] \Rightarrow \forall z, Q(z)$$ (to see this, set $x=Sz$, $y=z$ and use a proof of $z<Sz$) to "weaken" $(T0)$ to $(T1)$.