Well Ordering Principle: Statement, Proof, Application

The well ordering principle of natural numbers states that every non-empty subset of natural numbers has a least element. Here we state and prove the well-ordering principle with applications.

ℕ: = The set of natural numbers.

Statement of Well Ordering Principle

Every non-empty subset of natural numbers has a least element.

That is, if S is a non-empty subset of ℕ, then there exists a number m in S such that m≤s for all s ∈ S.

Proof of Well Ordering Principle

Let S be a non-empty subset of ℕ.

As S is non-empty, take k ∈ S.

Consider the subset T defined by

T = {x∈ S : x≤k}.

See that T ⊆ {1, 2, …, k}.

Thus, T is a finite set of natural numbers, so it has a least element, say m. That is,

m≤x for all x ∈ T.

Claim: We claim that m is the least element of S.

Let s ∈ S be any element. First suppose s ≤ k. So s ∈ T. As m is the least element of T, we have m ≤ s. Next suppose s > k. As m ∈ T, the inequality m≤k implies that m<s.

Thus, we have shown that m ≤ s for all s ∈ S. Therefore, m is the least element of S. So our claim is proved. That is, S has a least element. This completes the proof of the well-ordering principle.

Application

As an application of the well-ordering principle, one can prove the principle of induction.

Principle of Induction

Let S be a subset of ℕ such that

1. 1 ∈ S
2. if k ∈ S, then k+1 ∈ S.

Then S=ℕ.

Proof:

Let T=ℕ-S.

To prove S=ℕ, we need to show that T=∅ (null set).

Suppose T ≠ ∅ is non-empty.

So by the above well-ordering principle, T has a least element, say m.

As m ∈ T = ℕ-S, it follows that m ∉ S.

By assumption (1), we have 1 ∈ S. So m ∉ S implies that m≠1, hence m>1.

Therefore, m-1 ∈ ℕ.

As m is the least element of T, it follows that

m-1 ∉ T = ℕ-S .

Thus, m-1 ∈ S.

By assumption (2), (m-1)+1 ∈ S ⇒ m ∈ S.

This contradicts the fact that m ∉ S.

So our assumption T ≠ ∅ is wrong. Hence, T=∅. This completes the proof of the theorem.

Mathematical Analysis

FAQs