5.1: The Principle of Well-Ordering

Number theory studies the properties of integers. Some basic results in number theory rely on the existence of a certain number. The next theorem can be used to show that such a number exists.

Theorem \(\PageIndex{1}\label{thm:PWO}\)

Every nonempty subset of \(\mathbb{N}\) has a smallest element.

Proof

The idea is rather simple. Start with the integer 1. If it belongs to \(S\), we are done. If not, consider the next integer 2, and then 3, and so on, until we find the first element in \(S\). However, like the principle of mathematical induction, it is unclear why “and so on” is possible. In fact, we cannot prove the principle of well-ordering with just the familiar properties that the natural numbers satisfy under addition and multiplication. Hence, we shall regard the principle of well-ordering as an axiom. Interestingly though, it turns out that the principle of mathematical induction and the principle of well-ordering are logically equivalent.

Theorem \(\PageIndex{2}\label{thm:PMI-PWO}\)

The principle of mathematical induction holds if and only if the principle of well-ordering holds.

Proof

(\(\Rightarrow\)) Suppose \(S\) is a nonempty set of natural numbers that has no smallest element. Let \[R = \{ x\in\mathbb{N} \mid x\leq s \mbox{ for every } s\in S\}. \nonumber\] Since \(S\) does not have a smallest element, it is clear that \(R\cap S = \emptyset\). It is also obvious that \(1\in R\). Assume \(k\in R\). Then any natural number less than or equal to \(k\) must also be less than or equal to \(s\) for every \(s\in S\). Hence \(1,2,\ldots,k \in R\). Because \(R\cap S=\emptyset\), we find \(1,2,\ldots,k\notin S\). If \(k+1\in S\), then \(k+1\) would have been the smallest element of \(S\). This contradiction shows that \(k+1\in R\). Therefore, the principle of mathematical induction would have implied that \(R=\mathbb{N}\). That would make \(S\) an empty set, which contradicts the assumption that \(S\) is nonempty. Therefore, any nonempty set of natural numbers must have a smallest element.

(\(\Leftarrow\)) Let \(S\) be a set of natural numbers such that

1. \(1\in S\),
2. For any \(k\geq1\), if \(k\in S\), then \(k+1\in S\).

Suppose \(S\neq\mathbb{N}\). Then \(\overline{S}=\mathbb{N}-S\neq\emptyset\). The principle of well-ordering states that \(\overline{S}\) has a smallest element \(z\). Since \(1\in S\), we deduce that \(z\geq2\), which makes \(z-1\geq1\). The minimality of \(z\) implies that \(z-1\notin \overline{S}\). Hence, \(z-1\in S\). Condition (ii) implies that \(z\in S\), which is a contradiction. Therefore, \(S=\mathbb{N}\).

The principle of well-ordering is an existence theorem. It does not tell us which element is the smallest integer, nor does it tell us how to find the smallest element.

Example \(\PageIndex{1}\label{eg:PWO-01}\)

Consider the sets \[\begin{array}{r c l} A &=& \{ n\in\mathbb{N} \mid n \mbox{ is a multiple of 3} \}, \\ B &=& \{ n\in\mathbb{N} \mid n = -11+7m \mbox{ for some } m\in\mathbb{Z} \}, \\ C &=& \{ n\in\mathbb{N} \mid n = x^2-8x+12 \mbox{ for some } x\in\mathbb{Z} \}. \end{array} \nonumber\] It is easy to check that all three sets are nonempty, and since they contain only positive integers, the principle of well-ordering guarantees that each of them has a smallest element.

These smallest elements may not be easy to find. It is obvious that the smallest element in \(A\) is 3. To find the smallest element in \(B\), we need \(-11+7m>0\), which means \(m>11/7\approx1.57\). Since \(m\) has to be an integer, we need \(m\geq2\). Since \(-11+7m\) is an increasing function in \(m\), its smallest value occurs when \(m=2\). The smallest element in \(B\) is \(-11+7\cdot2=3\).

To determine the smallest element in \(C\), we need to solve the inequality \(x^2-8x+12>0\). Factorization leads to \(x^2-8x+12 = (x-2)(x-6)>0\), so we need \(x<2\) or \(x>6\). Because \(x\in\mathbb{Z}\), we determine that the minimum value of \(x^2-8x+12\) occurs at \(x=1\) or \(x=7\). Since \[1^2-8\cdot1+12 = 7^2-8\cdot7+12 = 5, \nonumber\] The smallest element in \(C\) is 5.

Example \(\PageIndex{2}\label{eg:PWO-02}\)

The principle of well-ordering may not be true over real numbers or negative integers. In general, not every set of integers or real numbers must have a smallest element. Here are two examples:

• The set \(\mathbb{Z}\).
• The open interval \((0,1)\).

The set \(\mathbb{Z}\) has no smallest element because given any integer \(x\), it is clear that \(x-1<x\), and this argument can be repeated indefinitely. Hence, \(\mathbb{Z}\) does not have a smallest element.

A similar problem occurs in the open interval \((0,1)\). If \(x\) lies between 0 and 1, then so is \(\frac{x}{2}\), and \(\frac{x}{2}\) lies between 0 and \(x\), such that \[0 < x < 1 \quad\Rightarrow\quad 0 < \frac{x}{2} < x < 1. \nonumber\] This process can be repeated indefinitely, yielding \[0 < \cdots < \frac{x}{2^n} < \cdots < \frac{x}{2^3} < \frac{x}{2^2} < \frac{x}{2} < x < 1. \nonumber\] We keep getting smaller and smaller numbers. All of them are positive and less than 1. There is no end in sight, hence the interval \((0,1)\) does not have a smallest element.

The idea behind the principle of well-ordering can be extended to cover numbers other than positive integers.

Definition

A set \(T\) of real numbers is said to be well-ordered if every nonempty subset of \(T\) has a smallest element.

Therefore, according to the principle of well-ordering, \(\mathbb{N}\) is well-ordered.

Example \(\PageIndex{3}\label{eg:PWO-03}\)

Show that \(\mathbb{Q}\) is not well-ordered.

Solution

Suppose \(x\) is the smallest element in \(\mathbb{Q}\). Then \(x-1\) is a rational number that is smaller than \(x\), which contradicts the minimality of \(x\). This shows that \(\mathbb{Q}\) does not have a smallest element. Therefore \(\mathbb{Q}\) is not well-ordered.

[eg:PWO-03]

hands-on exercise \(\PageIndex{1}\label{he:PWO-01}\)

Show that the interval \([0,1]\) is not well-ordered by finding a subset that does not have a smallest element

Summary and Review

• A set of real numbers (which could be decimal numbers) is said to be well-ordered if every nonempty subset in it has a smallest element.
• A well-ordered set must be nonempty and have a smallest element.
• Having a smallest element does not guarantee that a set of real numbers is well-ordered.
• A well-ordered set can be finite or infinite, but a finite set is always well-ordered.

Exercises 5.1

Exercise \(\PageIndex{1}\label{ex:PWO-01}\)

Find the smallest element in each of these subsets of \(\mathbb{N}\).

1. \(\{n\in\mathbb{N} \mid n=m^2-10m+28 \mbox{ for some integer}\) \(m\).
2. \(\{n\in\mathbb{N} \mid n=5q+3 \mbox{ for some integer} \) \(q\).
3. \(\{n\in\mathbb{N} \mid n=-150-17d \mbox{ for some integer} \) \(d\).
4. \(\{n\in\mathbb{N} \mid n=4s+9t \mbox{ for some integers}\) \(s\) and \(t\).

Exercise \(\PageIndex{2}\label{ex:PWO-02}\)

Determine which of the following subsets of \(\mathbb{R}\) are well-ordered:

1. \(\{\;\}\)
2. \(\{-9,-7,-3,5,11\}\)
3. \(\{0\}\cup\mathbb{Q}^+\)
4. \(2\mathbb{Z}\)
5. \(5\mathbb{N}\)
6. \(\{-6,-5,-4,\ldots\,\}\)

Exercise \(\PageIndex{3}\label{ex:PWO-03}\)

Show that the interval \([3,5]\) is not well-ordered.

Hint

Find a subset of \([3,5]\) that does not have a smallest element.

Exercise \(\PageIndex{4}\label{ex:PWO-04}\)

Assume \(\emptyset \neq T_1 \subseteq T_2 \subseteq \mathbb{R}\). Show that if \(T_2\) is well-ordered, then \(T_1\) is also well-ordered.

Hint

Let \(S\) be a nonempty subset of \(T_1\). We want to show that \(S\) has a smallest element. To achieve this goal, note that \(T_1\subseteq T_2\).

Exercise \(\PageIndex{5}\label{ex:PWO-05}\)

Prove that \(2\mathbb{N}\) is well-ordered.

Hint

Use the previous problem.

Exercise \(\PageIndex{6}\label{ex:PWO-06}\)

Assume \(\emptyset \neq T_1 \subseteq T_2 \subseteq \mathbb{R}\). Prove that if \(T_1\) does not have a smallest element, then \(T_2\) is not well-ordered.