Equivalence of strong and weak induction

Question

What is a simple way of proving strong induction implies weak induction and vice versa using simple predicate logic and quantifiers?

Answer 1

Weak induction: $$\Phi(0), \forall n\colon \Phi(n)\to\Phi(n+1)\vdash\forall n\colon \Phi(n).$$ Strong induction: $$\forall n\colon (\forall m<n\colon \Psi(m))\to\Psi(n)\vdash\forall n\colon \Psi(n)$$ (All vars implied to be in $\mathbb N_0$ for brevity).

To show that weak induction implies strong induction, one lets $\Phi(n)\equiv \forall m<n\colon \Psi(m)$ for given $\Psi$: We have $\Phi(0)$ because $\forall m<0\colon\Psi(m)$ is vacuously true. Using $m<n+1\to m<n\lor m=n$, we find that $$\forall m<n\colon \Psi(m)\implies\Psi(n)\land\forall m<n\colon \Psi(m)\implies \forall m<n+1\colon \Psi(m)$$ and thus $\forall n\colon \Phi(n)\to\Phi(n+1)$. By weak induction, $\forall n\colon \Phi(n)$. Especially, for arbitrary $n$ we find $\forall m<n\colon \Phi(m)$, i.e. $\forall n\colon\Psi(n)$.