Thread: Induction

Hi there,
I need help with proving "weak induction--->string induction" using weak induction
Where to start?

Weak induction for natural numbers: P(0) -> ∀x (P(x) -> P(x+1)) -> ∀x P(x).
Strong induction for natural numbers: ∀x ((∀y < x Q(y)) -> Q(x)) -> ∀x Q(x).

To prove strong induction for a given property Q, apply weak induction where P(x) is ∀y < x Q(y).

We want to prove that
P(0) and
(forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
implies
forall n. P(n)

The proof of this by mathematical induction won't go through unless
we strengthen what we're trying to prove to the following

P(0) and
(forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
implies
forall n. forall i. i < n implies P(i)

Now for the proof by mathematical induction on n.
Base case, n=0:
We need to show that forall i. i < 0 implies P(0).
This is vacuosly true because there is no natural number i such that i < 0.

Induction step:
The induction hypothesis is forall i. i < n implies P(i).
We need to show that forall i. i < n+1 implies P(i).
So we pick an arbitrary i where i < n+1 and need to prove P(i).
We consider the following two cases.
Case i < n:
Then by the induction hypothesis we have P(i).
Case i = n:
We consider two further subcases:
Case n = 0:
We have P(i) from the assumption P(0).
Case n > 0:
There is some k such that n = k + 1.
With this and the induction hypothesis we have forall i<k+1. P(i).
We can then apply the step assumption to get P(k+1), which is P(i).