Set Theory

Set Theory Logo

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:

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.

Page 1 Page 2