# 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 mn 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.