# 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

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

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

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

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

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

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}.\)