Complete induction in the Peano system 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$$
 A: 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)$.
