Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle)WOP

Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle) WOP

To prove this we must define a subset of the natural numbers T, and show that T is nonempty, and has a smallest element.

We will use a combination of taking the contrapositive and proving it by induction. That sounds more complicated than it is, so hold on to your hat and see the proof before thinking all this is confusing!

The contrapositive is to suppose that T has no smallest element. If this is true then there must be another set S that is equal to the natural numbers(N) so that we can make the statement:

S = N - T , or that is to say that S will be equal to N only if T is empty.

To prove this using iduction we take the first case in the natural numbers which is 1. 1 is the smallest element in the natural numbers and as T has no smallest element, 1 must be in S by our statement S = N - T

Now, say that a number k is an element in S, then that number cannot be in T, because if it were, it would imply that there is a smallest element in T, and also, k cannot be in T since k is in S. Then k+1 cannot be in T, by the same implication of there being a smallest element in T, and so k+1 must be an element in S.

So by induction S = N, or the set S is equal to the natural numbers, and since T has no smallest element, T has to be an empty subset of the natural numbers.

However, by contraposition, if T had an element, then it would have to have a smallest element. Thus, any non-empty subset of the natural numbers (N) has a smallest element, and this is the Well Ordering Principle.