Theorem 5.1: (The Well Ordering Principle) Every nonempty set of natural numbers has a smallest element.

Proof: We proceed by induction on the number of elements in the set. If the set is nonempty, the smallest number of elements could be one. Let S be a set with one element. That one element would have to be the least element.

Assume that the theorem is true for sets with k elements and let S be a set with k + 1 elements. Since S has k + 1 elements it is not empty. Let

There are two cases. Either s₁ is the smallest element of S or it is not. If it is the smallest element, then S has a smallest element. If not, then there is a smaller element

Consider

By Theorem 4.9, the number of elements in S₁ will be the predecessor of k + 1 which, by Theorem 4.10, will be k. . By the induction hypothesis, there will be a smallest element of S₁. Call it s_o. Since s_o is the smallest element of S₁, s_o < s for all

In particular, s_o < s₂ < s₁ so s_o is the smallest element in S.