Well Ordering Principle

Home → Well Ordering Principle

The well ordering principle relies on the fact that the set \(\mathbb{Z^{+}}\) is well-ordered and states that every non-empty subset of positive integers has a least element.

More formally, let \(S \subseteq \mathbb{Z^{+}}.\) Then \(S\) has a least element, i.e. there is an \(m \in S\) such that \(m \le n\) for all \(n \in S.\)

The well ordering principle is often used in proofs by contradiction to show that a predicate \(P\left( n \right)\) is true for all \(n \in \mathbb{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}.\)