Weak induction is equivalent to strong induction

[wrldt]

Homework Statement

Prove that weak induction is equivalent to strong induction.

Homework Equations

To prove this...we assume weak induction. That is

(i) 1 $\in$ S
(ii) n$\in$ S $\Rightarrow$ n+1 $\in$ S for all n in N

The Attempt at a Solution

So to prove strong induction we need to prove the following:
(i) 1 $\in$ S
This is given by our assumption of weak induction.
(ii) {1...n} $\in$ is a subset of S.
SInce we know 1 is in S, we can make 2...n by 1+1, 1+1+1, 1+...+1 (n times)
(iii) if (ii) is true than n+1 is in S.
I think this is true because our assumption guaranteed this.

This is a rough sketch of what I wan to say. Am I on the right track.

 

[micromass]

So assume weak induction, that is:

If
(i) $1\in S$
(ii) $n\in S~\Rightarrow~n+1\in S$
then $S=\mathbb{N}$.

You need to prove that strong induction holds. That is, you assume that
(a) $1\in S$
(b) $\{1,...,n\}\in S~\Rightarrow~n+1\in S$.
You need to prove from (a) and (b) that $S=\mathbb{N}$. You don't need to prove (a) and (b), they are given.