Proving the principle of weak induction, using strong induction I am struggling to figure out what exactly the claim that I am proving should be. I want to use the principle of strong induction to show that weak induction holds, where weak induction is the principle that for some predicate $P$, if $P(0)$ and $\forall n, P(n) \implies P(n+1)$, then $\forall n, P(n)$ and strong induction is where if $P(0)$ and if $\forall n, \forall k \space s.t \space k < n, P(k)$, then $P(n)$. What is the predicate that I should be using in my proof by strong induction? How do I proceed?
 A: The goal is to prove $P(0) \land (\forall x : P(x) \to P(x+1)) \to \forall n : P(n)$ by using the induction principle $I'$ :

$(\forall x : (\forall y <x : P (y)) \to P (x)) \to \forall n : P(n) $

So to prove the implication we assume that $P(0)$ and $IH :=\forall x : P(x) \to P(x+1)$ are true and we are left to prove $\forall n : P(n)$. By $I'$ it now suffices to show $\forall x : (\forall y <x : P (y)) \to P (x)$.
For this, assume we have some $x$ and $\forall y < x : P (y)$ and try to prove $P(x)$.

*

*If $x = 0$ then $P(x)$ is $P(0)$ and therefore true.

*If $x > 0$ then we have $x -1 <x$ which gives us $P(x-1)$ by $\forall y < x : P (y)$. Using $IH$ this proves $P(x-1+1)$ which is of course $P(x)$.

So in every case we were able to prove $P(x)$ as desired. $~\Box$

Some bit of extra information: The case distinction is quite necessary, and one can see this by looking at the proof in first-order $\mathsf{PA}$. If we let $\mathsf{PA}^-$ designate the usual Peano axioms without the normal induction scheme $I$ and let $A:= \forall x : (x = 0 \lor \exists z : x = z + 1)$ then we have
$$
  (\mathsf{PA}^- + I) \, \vdash I' \land A  
  \hspace{2em} \text{and} \hspace{2em}  
  (\mathsf{PA}^- + I' + A) \,\vdash I  
$$
where $A$ is enabling the same kind of case distinction that was done in the above.
It is not possible to show $(\mathsf{PA}^- + I') \vdash I$ as $PA^- + I'$ has models which falsify $I$. We can get one such model by taking $\mathbb{N}$ and interpreting the symbol for the successor $S$ as the function $n \mapsto n + 2$. In a sense this creates two disjoint copies of $\mathbb{N}$, one starting with $0$ and containing all even numbers, and one starting with $1$ and containing all odd numbers. The usual induction can then only show that a predicate is true on all even numbers of the model and is therefore false.
