$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.7: The Well-Ordering Principle

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.

## The Well-Ordering Principle

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

Proof

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.  This means if you accept one as an axiom, you can use that to prove the other.

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

## The Principle of Mathematical Induction holds if and only if the Well-Ordering Principle 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\}.$ 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\in S$$,

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{aligned} 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{aligned} 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,$ 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.$ 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.$ 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 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

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

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

a) $$\{n\in\mathbb{N} \mid n=m^2-10m+28 \mbox{ for some integer}$$ $$m\}$$.

b) $$\{n\in\mathbb{N} \mid n=5q+3 \mbox{ for some integer}$$ $$q\}$$.

c) $$\{n\in\mathbb{N} \mid n=-150-17d \mbox{ for some integer}$$ $$d\}$$.

d) $$\{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

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.