Hi there,

I need help with proving "weak induction--->string induction" using weak induction

Where to start? :D

Printable View

- May 19th 2011, 01:53 PMbeno1310Induction
Hi there,

I need help with proving "weak induction--->string induction" using weak induction

Where to start? :D - May 19th 2011, 02:08 PMemakarov
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). - May 22nd 2011, 02:27 PMbeno1310
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).