Well ordering principle

Well-ordering principle: Every nonempty subset T of N has a least element. Thatis,thereisanm∈T suchthatm≤nforalln∈T.

Intutively clear as it may seem at the first glance, this principle turns out to be logically equivalent to the mathematical induction, the fifth axiom of Peano, which is quite surprising.

Theorem 1. The mathematical induction is logically equivalent to the well-ordering principle.

Proof. Part I. We show the well-ordering principle implies the math- ematical induction.

LetS⊂Nbesuchthat1∈Sandk∈Simpliesk′∈S. Wewant to establish that S = N by the well-ordering principle.

Suppose N\S is not empty. Then by the well-ordering principle there is a least element m ∈ N\S. Since 1 ∈ S we know 1 ∈/ N\S. Therefore m ̸= 1 and so by one of the homework 2 problems there is some q ∈ N such that m = q′ = q+1, which implies q < m by the definition of <. Weconcludethatq∈S;orelsewewouldhaveq∈N\Sandso m would not be the least element of N \ S, which is absurd. However, since S has the property that k ∈ S implies k′ ∈ S, we conclude that m = q′ ∈ S because q ∈ S. This contradicts m ∈ N \ S.

The contradiction establishes that N \ S is empty. Hence S = N. Part II. We show the mathematical induction implies the well-ordering principle.

Let S(n) be the statement: Any set of natural numbers containing a natural number ≤ n has a least element. Consider the set

E ={m∈N:S(m) is true}.

1 ∈ E because 1 is the least element of N (why?).

Wenextshowm∈Eimpliesm′∈E. Nowm∈EmeansifXis a subset of N containing a natural number ≤ m, then X has a least element. From this we want to establish m′ ∈ E.

So let C be any subset of N containing a natural number ≤ m′. If C has no element < m′, then m′ is the least element of C and we are done. Otherwise, we can now suppose there is a natural number y ∈ C such that y < m′. In particular, y ≤ m because by one of the homework 3 problems we know there is no natural number strictly between m and m′. Therefore, C now has an element y ≤ m, so that the induction hypothesis given in the preceding paragraph implies that C has a least element. In any event, we have proven C has a least element, so that

m′ ∈ E. Hence, the mathematical induction implies E = N.

 In summary, the mathematical induction implies that the statement S(n) is true for all n ∈ N.

To establish the well-ordering principle, let T ⊂ N be a nonempty set. There is some m ∈ T because T is nonempty, so that T contains a natural number ≤ m, which is just m itself. Then T has a least element because the statement S(m) is true by the preceding paragraph