Show that the Principle of WellOrdering for the natural numb

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if S N such that 1 S and n + 1 S whenever n S, then S = N .

Please explain in the simplest way so I can understand

Solution

Suppose S IN is such that 1 S and whenever n S then also (n + 1) S.

Show : S = N .

Consider the complement T = IN \\ S and assume that T has a smallest element, say n.

The number n can’t be equal to 1 since 1 S.

Thus n 2 and n 1 is a natural number.

Since n is assumed to be the smallest element of T, and (n 1) < n, (n 1) cannot be in T, i.e. it is in S.

But by hypothesis, if (n 1) S then also n = ((n 1) + 1) S which contradicts n T.

Thus T cannot have a smallest element and by the well ordering principle T is empty or S = IN.