Question

Prove that the Well Ordering Principle implies the Principle of Induction.

please show step by step solution with clear explanation!

Answer 1

Principle of induction:

Let S be a subset of N with the properties -
(i) 1 belongs to S, and
(ii) whenever a natural number k belongs to S, then k +1 belongs
to S.
Then S = N.

Proof. Let T be the set of all those natural numbers which are not in S.
The theorem will be proved if we can prove that T is an empty set.
Let us assume that T is a non-empty set. Then by the well ordering
property T possesses a least element, say m. Since 1€S, m > 1 and so
m-1 is a natural number. Again since m is the least element in T, m-1
is not in T and so m - 1 is in S.
Since m - 1 is in S, by (ii) (m - 1) + 1 is in S, i.e., m is in S which
is a contradiction.
Therefore our assumption is wrong and T is empty and the theorem
is proved.