Well Ordering Principle

The well ordering principle relies on the fact that the set ℤ⁺ is well-ordered and states that every non-empty subset of positive integers has a least element.

More formally, S ⊆ ℤ⁺. Then S has a least element, i.e. there is an m ∈ S such that m ≤ n for all n ∈ S.

The well ordering principle is often used in proofs by contradiction to show that a predicate P(n) is true for all n ∈ ℕ.

A standard way of such proof looks as follows:

Suppose \(P\left( n \right)\) is false, that is, \(\exists n,\) \(\neg P\left( n \right).\)
Define the set of counterexamples \(C = \left\{ {n \in N:\neg P\left( n \right)} \right\}.\)
Assume \(C\) is non-empty to derive a contradiction.
By the well ordering principle, there exists a least element \(m \in C.\)
Derive a contradiction either by proving
\[\forall i \lt m,P\left( i \right) \Rightarrow P\left( m \right),\]
which contradicts to \(\neg P\left( m \right),\) or by proving
\[\neg P\left( m \right) \Rightarrow \exists i \lt m,\neg P\left( i \right),\]
which contradicts the fact that \(P\left( i \right)\) is true for all \(i \lt m.\)
Conclude that \(C\) must be empty, that is, no counterexamples exist, and hence, \(P\left( n \right)\) is true for all \(n \in \mathbb{N}.\)

The well ordering principle and the principle of mathematical induction are logically equivalent.

Consider an example of a proof using the well ordering principle. Let's prove the following finite series formula

\[\sum\limits_{i = 1}^n {{i^3}} = {1^3} + {2^3} + {3^3} + \ldots + {n^3} = \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}.\]

The predicate \(P\left( n \right)\) here means that the sum of the cubes of the first \(n\) natural numbers is \(\frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}.\)

Suppose by contradiction that \(P\left( n \right)\) is false. The set \(C\) of counterexamples is defined as

\[C = \left\{ {n \in \mathbb{N} \mid \sum\limits_{i = 0}^n {{i^3}} \ne \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}} \right\}.\]

We assume that \(C\) is non-empty. Then, according to the well ordering principle, there must exist a least element \(m\) in \(C.\) The predicate \(P\left( m \right)\) for the number \(m\) is false, that is

\[\sum\limits_{i = 1}^m {{i^3}} \ne \frac{{{m^2}{{\left( {m + 1} \right)}^2}}}{4}.\]

Note that \(m \gt 1\) since \(P\left( 1 \right)\) is true:

\[LHS = \sum\limits_{i = 1}^1 {{i^3}} = {1^3} = 1;\;\;RHS = \frac{{{1^2}{{\left( {1 + 1} \right)}^2}}}{4} = \frac{4}{4} = 1.\;\;\Rightarrow LHS = RHS.\]

For all \(1 \le i \lt m,\) the predicate \(P\left( i \right)\) is true. So, for \(i = m-1\) we have

\[\sum\limits_{i = 1}^{m - 1} {{i^3}} = \frac{{{{\left( {m - 1} \right)}^2}{m^2}}}{4}.\]

By adding \(m^3\) to both sides of the last equation we obtain

\[\sum\limits_{i = 1}^m {{i^3}} = \frac{{{{\left( {m - 1} \right)}^2}{m^2}}}{4} + {m^3} = \frac{{\left( {{m^2} - 2m + 1} \right){m^2}}}{4} + {m^3} = \frac{{{m^4} - 2{m^3} + {m^2} + 4{m^3}}}{4} = \frac{{{m^4} + 2{m^3} + {m^2}}}{4} = \frac{{{m^2}\left( {{m^2} + 2m + 1} \right)}}{4} = \frac{{{m^2}{{\left( {m + 1} \right)}^2}}}{4}.\]

which means that \(P\left( m \right)\) is true. But this contradicts the fact that \(m\) is the least element in \(C.\) Hence, our assumption that the set \(C\) is non-empty is wrong. Thus, the finite series formula holds for all \(n \in \mathbb{N}.\)

See solved problems on Page 2.

Calculus

Set Theory

Well Ordering Principle