Calculus

Set Theory

Set Theory Logo

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 \(\large{\frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}}\normalsize.\)

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


Solved Problems

Click or tap a problem to see the solution.

Example 1

Prove the formula for the sum of the first \(n\) odd natural numbers: \[{\sum\limits_{i = 1}^n {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2n – 1} \right) }={ {n^2}.}\]

Example 2

Prove the formula for the sum of the first \(n\) even natural numbers: \[{\sum\limits_{i = 1}^n {{2i}} }={ 2 + 4 + 6 + \ldots + 2n }={ n\left({n+1}\right).}\]

Example 3

Show that \(n^5 – n\) is divisible by \(5\) for any \(n \in \mathbb{N}.\)

Example 4

Show that \(4^n – 1\) is divisible by \(3\) for any \(n \in \mathbb{N}.\)

Example 5

Prove that for all natural numbers \[\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{n}{{n + 1}}.\]

Example 6

Prove by well ordering principle that \[\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{{n + 1}}{{2n}}\] for \(n \ge 2.\)

Example 1.

Prove the formula for the sum of the first \(n\) odd natural numbers: \[{\sum\limits_{i = 1}^n {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2n – 1} \right) }={ {n^2}.}\]

Solution.

By following the general pattern for well ordering proof, we suppose that the formula is false for certain \(n.\) We collect all such numbers in a set \(C:\)

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

By the well ordering principle, there is a least element \(m\) in set \(C.\) Notice that \(m \gt 1\) since the formula is true for \(n = 1:\)

\[{LHS = \sum\limits_{i = 1}^1 {\left( {2i – 1} \right)} = 1;\;\;}\kern0pt{ RHS = {1^2} = 1,}\;\; \Rightarrow {LHS = RHS.}\]

The summation formula is also true for all \(1\le i \lt m,\) so for \(i = m-1\) we get

\[{\sum\limits_{i = 1}^{m – 1} {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2m – 3} \right) }={ {\left( {m – 1} \right)^2}.}\]

Add the next term \(2m – 1\) to both sides of the equation. This yields

\[\require{cancel}{\sum\limits_{i = 1}^m {\left( {2i – 1} \right)} }={ {\left( {m – 1} \right)^2} + 2m – 1 }={ {m^2} – \cancel{2m} +\cancel{1} + \cancel{2m} – \cancel{1} }={ {m^2}}.\]

The last equation shows that the summation formula is also true for the number \(m,\) which contradicts the assumption. Hence, the set of counterexamples \(C\) is empty and the given formula holds for all \(n \in \mathbb{N}.\)

Example 2.

Prove the formula for the sum of the first \(n\) even natural numbers: \[{\sum\limits_{i = 1}^n {{2i}} }={ 2 + 4 + 6 + \ldots + 2n }={ n\left({n+1}\right).}\]

Solution.

We prove by well ordering. Let \(P\left( n \right)\) be the assertion that the summation formula is true for a number \(n\) where \(n \in \mathbb{N}\). By contradiction, we assume that there are some values of \(n\) for which this formula is false. We collect all such values of \(n\) in a set \(C,\) so

\[C = \left\{ {n \in \mathbb{N} \mid \sum\limits_{i = 1}^n {2i} \ne {n^2}} \right\}.\]

Assume that \(C\) is non-empty. Then, by the well ordering principle, there is a least element \(m \in C.\) Obviously, \(P\left( m \right)\) is false.

Given that \(P\left( 1 \right)\) is true:

\[{LHS = \sum\limits_{i = 1}^1 {2i} = 2;\;\;}\kern0pt{ RHS = 1\left( {1 + 1} \right) = 2,}\;\; \Rightarrow {LHS = RHS,}\]

we conclude that \(m \gt 1.\) Hence, we can take the number \(m – 1,\) for which the predicate \(P\left( {m – 1} \right)\) is true. It is given by the expression

\[\sum\limits_{i = 1}^{m – 1} {2i} = \left( {m – 1} \right)m.\]

Add the next term \(2m\) to both sides of the equation:

\[{\sum\limits_{i = 1}^m {2i} }={ \left( {m – 1} \right)m + 2m }={ {m^2} – m + 2m }={ {m^2} + m }={ m\left( {m + 1} \right).}\]

We have obtained the true formula for the number \(m,\) which contradicts our assumption. Consequently, the set of counterexamples \(C\) is empty and the summation formula holds for all \(n \in \mathbb{N}.\)

Example 3.

Show that \(n^5 – n\) is divisible by \(5\) for any \(n \in \mathbb{N}.\)

Solution.

Consider the predicate \(P\left( n \right)\) that means that \(n^5 – n\) is divisible by \(5\) where \(n\) is a natural number. It is easy to see that \(P\left( 1 \right)\) is true, since \({1^5} – 1 = 0\) is divisible by \(5.\)

By contradiction, suppose that \(P\left( n \right)\) is false for certain \(n.\) Let all such values of \(n\) be represented by a set \(C:\)

\[{C = \left\{ {n \in \mathbb{N} \mid {n^5} – n}\right.}\kern0pt{\left.{\text{is not divisible by }5} \right\}.}\]

The well ordering principle states that there is a least element \(m \in C\) assuming \(C\) is not an empty set. It follows from the above that \(m \gt 1\) and hence, \(m -1\) is also a natural number.

Thus, we have two facts: \(P\left( m \right)\) is false, that is, \(m^5 -m\) is not divisible by \(5,\) but \(P\left( {m – 1} \right)\) is true, so \({\left( {m – 1} \right)^5} – \left( {m – 1} \right)\) is divisible by \(5.\)

We then have:

\[{{\left( {m – 1} \right)^5} – \left( {m – 1} \right) }={ {m^5} – 5{m^4} }+{ 10{m^3} – 10{m^2} + 5m – \cancel{1} – m + \cancel{1} }={ \left( {{m^5} – m} \right) }+{ \left( { – 5{m^4} + 10{m^3} – 10{m^2} + 5m} \right) }={ \left( {{m^5} – m} \right) }-{ 5m\left( {{m^3} – 2{m^2} + 2m – 1} \right).}\]

In the last expression, the \(2\text{nd}\) term \(5m\left( {{m^3} – 2{m^2} + 2m – 1} \right)\) is divisible by \(5.\) Hence, the \(1\text{st}\) term \(\left( {{m^5} – m} \right)\) is also divisible by \(5.\) But this contradicts the statement that \(P\left( m \right)\) is false!

So, our assumption (the set \(C\) is not empty) is wrong, and consequently, \(P\left( n \right)\) is true for all natural numbers.

Example 4.

Show that \(4^n – 1\) is divisible by \(3\) for any \(n \in \mathbb{N}.\)

Solution.

We denote this divisibility property by \(P\left( n \right)\) and prove it using well ordering. Notice that \(P\left( 1 \right)\) is true since \({4^1} – 1 = 3\) is divisible by \(3.\)

By contradiction, suppose that \(P\left( n \right)\) is false for some \(n.\) Let \(C\) be the set that contains all such numbers \(n:\)

\[{C = \left\{ {n \in \mathbb{N} \mid {4^n – 1}}\right.}\kern0pt{\left.{\text{is not divisible by }3} \right\}.}\]

If \(C\) is not empty, then by the well ordering principle, it has a smallest element \(m \gt 1.\) It is obvious that \(P\left( m \right)\) is false.

From the other side, \(P\left( {m – 1} \right)\) is true, that is, \({4^{m – 1}} – 1\) is divisible by \(3.\)

After some algebra we get

\[{{4^m} – 1 = 4 \cdot {4^{m – 1}} – 1 }={ 4 \cdot {4^{m – 1}} – 4 + 3 }={ 4\left( {{4^{m – 1}} – 1} \right) + 3.}\]

Here the first term \(4\left( {{4^{m – 1}} – 1} \right)\) is divisible by \(3\) by the previous assertion. Hence, the initial expression \({4^m} – 1\) is also divisible by \(3.\) This is a contradiction!

We conclude that set of counterexamples \(C\) is empty and, hence, the property \(P\left( n \right)\) holds for all \(n \in \mathbb{N}.\)

Example 5.

Prove that for all natural numbers \[\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{n}{{n + 1}}.\]

Solution.

Let \(P\left( n \right)\) be the summation formula for a number \(n.\) Using well ordering proof techniques, we suppose by contradiction that \(P\left( n \right)\) is false for certain numbers \(n.\) Let all such values of \(n\) be collected in a set \(C:\)

\[{C \text{ = }}\kern0pt{\left\{ {n \in \mathbb{N} \,\Biggm|\,\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} \ne \frac{n}{{n + 1}}} \right\}.}\]

It is easy to see that \(P\left( 1 \right)\) is true:

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

Assume that the set \(C\) is not empty. Then, by the well ordering principle, there is a least element \(m \in C,\) such that \(P\left( m \right)\) is false. It follows from the above that \(m \gt 1.\)

From the other side, \(P\left( {m – 1} \right)\) must be true since \(m – 1 \not\in C.\)

The summation formula for \(n = m – 1\) is given by

\[\sum\limits_{i = 1}^{m – 1} {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{{m – 1}}{m}.\]

Add the term \({\large{\frac{m}{{m + 1}}}\normalsize}\) to both sides of the equation:

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

This implication shows that if \(P\left( {m – 1} \right)\) is true, then \(P\left( {m} \right)\) is also true, which contradicts the assumption. Hence, the set of counterexamples \(C\) is empty, and the given summation formula holds for all natural numbers.

Example 6.

Prove by well ordering principle that \[\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{{n + 1}}{{2n}}\] for \(n \ge 2.\)

Solution.

Let \(P\left( n \right)\) be the product formula for a number \(n.\) By contradiction, suppose that \(P\left( n \right)\) is false for some \(n.\) Let the set \(C\) represent all such counterexamples:

\[{C \text{ = }}\kern0pt{\left\{ {n \in \mathbb{N} \,\Biggm|\,\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} \ne \frac{{n + 1}}{{2n}}} \right\}.}\]

The property \(P\left( n \right)\) is valid for \(n = 2:\)

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

Suppose that \(C\) is not empty. Then, by \(WOP,\) it contains a least number \(m.\) Since \(m \ge 2,\) then \(m – 1\) is also a natural number.

We have two facts: \(P\left( m \right)\) is false and \(P\left( {m – 1} \right)\) is true. Let’s show that there is the implication \(P\left( {m – 1} \right) \Rightarrow P\left( m \right).\) For \(n = m – 1\) we have:

\[\prod\limits_{i = 2}^{m – 1} {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{m}{{2\left( {m – 1} \right)}}.\]

Multiply both sides of this equation by \({\left( {1 – \large{\frac{1}{{{m^2}}}}\normalsize} \right)}.\) This yields:

\[{\prod\limits_{i = 2}^m {\left( {1 – \frac{1}{{{i^2}}}} \right)} }={ \frac{m}{{2\left( {m – 1} \right)}} \cdot \left( {1 – \frac{1}{{{m^2}}}} \right) }={ \frac{m}{{2\left( {m – 1} \right)}} \cdot \frac{{{m^2} – 1}}{{{m^2}}} }={ \frac{{\cancel{m}\cancel{\left( {m – 1} \right)}\left( {m + 1} \right)}}{{2{m^{\cancel{2}}}\cancel{\left( {m – 1} \right)}}} }={ \frac{{m + 1}}{{2m}}.}\]

Thus, the true assertion \(P\left( {m – 1} \right)\) implies that \(P\left( {m} \right)\) is also true. This is a contradiction! Hence, our assumption (the set of counterexamples \(C\) is not empty) is wrong and the property \(P\left( {n} \right)\) holds for all \(n \ge 2.\)