# Well Orders

A well order (also referred as well-ordering or well-order relation) is a special type of total order where every non-empty subset has a least element. A set with a well-order relation is called a well-ordered set.

For example, the set of natural numbers $$\mathbb{N}$$ under the usual order relation $$\le$$ forms a well-ordered set.

By definition, any well-ordered set is totally ordered. However, the converse is not true – the set of integers $$\mathbb{Z},$$ which is totally ordered, is not well-ordered under the standard ordering (since $$\mathbb{Z}$$ itself and some its subsets do not have least elements). Although, any finite totally ordered set is well-ordered.

In a well-ordered set, every element (except a possible greatest element) has a unique successor. However, not every element of a well-ordered set needs to have a predecessor.

The well-ordering theorem (also known as Zermelo’s theorem) states that every set may be well-ordered. If so, we can find an order on the set of integers $$\mathbb{Z}$$ which makes it well-ordered. For example, instead of the regular order relation $$\le,$$ we can define the following order:

$\require{AMSsymbols}{0 \preccurlyeq – 1 \preccurlyeq 1 \preccurlyeq – 2 \preccurlyeq 2 \preccurlyeq – 3 \preccurlyeq 3 \preccurlyeq \ldots}$

That’s a well order relation on $$\mathbb{Z},$$ in which $$0$$ is the least element.

The well-ordering theorem is equivalent to the axiom of choice.

Let $$A$$ and $$B$$ be two partially ordered sets. If there is a function $$f : A \to B$$ such that, for every $$x, y \in A,$$

$x \le y \Rightarrow f\left( x \right) \le f\left( y \right),$

then the sets $$A$$ and $$B$$ are said to be order-isomorphic. Isomorphic sets are denoted as $$A \cong B.$$

Order isomorphism preserves well-ordering.

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Determine which of the following subsets of $$\mathbb{R}$$ are well-ordered:
1. $$\varnothing$$
2. $$\left\{ {12,3, – 4, – 7,0,-2,-11,5,1} \right\}$$
3. $$\left\{ {- \sqrt{2} ,0,\sqrt{2} ,2\sqrt{2} ,3\sqrt{2}, \ldots } \right\}$$
4. $$2\mathbb{N}$$
5. $$\left\{ {\large{\frac{1}{{a – 1}}}\normalsize \,\bigg|\, a \in \mathbb{N}, a \gt 1} \right\}$$

### Example 2

Determine which of the following subsets of $$\mathbb{R}$$ are well-ordered:
1. $$\left\{ {\sqrt{3}, \sqrt{5}, \sqrt{2}, \sqrt{11}, \sqrt{7} } \right\}$$
2. $$3\mathbb{Z} – 5$$
3. $$\left\{ {\large{\frac{1}{a}}\normalsize \,\bigg|\, a \in \mathbb{N}, a \le 100} \right\}$$
4. $$\left\{ {a \mid a \in \mathbb{Q} ,a \gt 5} \right\}$$
5. $$\left\{ {a \mid a \in \mathbb{Z} ,a \ge 10} \right\}$$

### Example 3

Determine whether the set of positive rational numbers $$\mathbb{Q}^+$$ is well-ordered.

### Example 4

Show that the interval $$\left[ {2,5} \right]$$ is not well-ordered.

### Example 1.

Determine which of the following subsets of $$\mathbb{R}$$ are well-ordered:
1. $$\varnothing$$
2. $$\left\{ {12,3, – 4, – 7,0,-2,-11,5,1} \right\}$$
3. $$\left\{ {- \sqrt{2} ,0,\sqrt{2} ,2\sqrt{2} ,3\sqrt{2}, \ldots } \right\}$$
4. $$2\mathbb{N}$$
5. $$\left\{ {\large{\frac{1}{{a – 1}}}\normalsize \,\bigg|\, a \in \mathbb{N}, a \gt 1} \right\}$$

Solution.

1. By definition, a partially ordered set is a well order if it is a total order and every non-empty subset has a least element. For the empty set $$\varnothing,$$ both these conditions are vacuously true. (We cannot prove that they are false, so they are considered to be true.) Therefore, the empty set $$\varnothing$$ is a well order.
2. The set $$\left\{ {12,3, – 4, – 7,0,-2,-11,5,1} \right\}$$ is finite and totally ordered by the usual “less than” ($$\lt$$) relation: $-11 \lt -7 \lt -4 \lt -2 \lt 0 \lt 1 \lt 3 \lt 5 \lt 12.$ Hence, this is a well order.
3. The set $$\left\{ {- \sqrt{2} ,0,\sqrt{2} ,2\sqrt{2} ,3\sqrt{2}, \ldots } \right\}$$ is well-ordered since there is an order preserving one-to-one mapping (order isomorphism) between the given set and the well-ordered subset of $$\mathbb{Z}$$ with the least element $$-1:$$ $\left\{ { – 1,0,1,2,3, \ldots } \right\}$
4. The set $$2\mathbb{N}$$ is order isomorphic to $$\mathbb{N}.$$ Therefore it is well-ordered.
5. The first elements of the set $$\left\{ {\large{\frac{1}{{a – 1}}}\normalsize \,\bigg|\, a \in \mathbb{N}, a \gt 1} \right\}$$ are given by $1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5}, \ldots$ As it can be seen, $$a_n \to 0$$ as $$n \to \infty.$$ This set does not have a least element and is not a well-order under the standard ordering $$\le.$$

### Example 2.

Determine which of the following subsets of $$\mathbb{R}$$ are well-ordered:
1. $$\left\{ {\sqrt{3}, \sqrt{5}, \sqrt{2}, \sqrt{11}, \sqrt{7} } \right\}$$
2. $$3\mathbb{Z} – 5$$
3. $$\left\{ {\large{\frac{1}{a}}\normalsize \,\bigg|\, a \in \mathbb{N}, a \le 100} \right\}$$
4. $$\left\{ {a \mid a \in \mathbb{Q} ,a \gt 5} \right\}$$
5. $$\left\{ {a \mid a \in \mathbb{Z} ,a \ge 10} \right\}$$

Solution.

1. The given set is finite and totally ordered: ${\sqrt{2} \lt \sqrt{3} \lt \sqrt{5} \lt \sqrt{7} \lt \sqrt{11} }.$ Hence, it is well-ordered.
2. The set $$3\mathbb{Z} – 5$$ is order isomorphic to the set of integers $$\mathbb{Z}.$$ Both these sets are not well-ordered under the standard ordering relation.
3. The denominator $$a$$ of the fraction $${\large{\frac{1}{a}}\normalsize}$$ ranges from $$1$$ to $$100.$$ So this is a finite totally ordered set of rational numbers with the least element $${\large{\frac{1}{100}}\normalsize}.$$ It is a well order.
4. The set $$\left\{ {a \mid a \in \mathbb{Q} ,a \gt 5} \right\}$$ is not a well order under standard ordering. For example, the following subset of rational numbers does not have a least element: $\left\{ {5 + \frac{1}{2},5 + \frac{1}{3},5 + \frac{1}{4}, \ldots } \right\}$
5. The set $$\left\{ {a \mid a \in \mathbb{Z} ,a \ge 10} \right\}$$ is well-ordered, since every its non-empty subset contains positive integers and has a least element.

### Example 3.

Determine whether the set of positive rational numbers $$\mathbb{Q}^+$$ is well-ordered.

Solution.

If we consider the usual ordering, the set $$\mathbb{Q}^+$$ is not well-ordered, because there are subsets that have no least element. For example, the subset $$\left\{ {\large{\frac{1}{{{2^n}}}}\normalsize \,\bigg|\, n \in \mathbb{N}} \right\}$$ does not have a least element.

However, according to the well-ordering theorem, we can construct a well order on $$\mathbb{Q}^+$$. One of the algorithms looks as follows:

1. Reduce the rationals to lower terms (when the numerator and denominator have no common factors other than $$1$$).
2. Order the rationals $$\large{\frac{m}{n}}\normalsize$$ by ascending value of $$m + n.$$
3. Within a subset with the same value of $$m + n,$$ order the rationals by ascending value of $$m.$$

So the order is given by

$\underbrace {\frac{1}{1}}_{m + n = 2},\underbrace {\frac{1}{2},\frac{2}{1}}_{m + n = 3},\underbrace {\frac{1}{3},\frac{3}{1}}_{m + n = 4},\underbrace {\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1}}_{m + n = 5}, \ldots$

With this ordering, the set of positive integers $$\mathbb{Q}^+$$ becomes well-ordered.

### Example 4.

Show that the interval $$\left[ {2,5} \right]$$ is not well-ordered.

Solution.

Consider a non-empty subset of the interval $$\left[ {2,5} \right]$$ – for example, the open interval $$\left( {3,4} \right).$$ For any $$x \in \left( {3,4} \right),$$ we can find a number $$y$$ such that $$y \in \left( {3,4} \right)$$ and $$y \lt x.$$ This means that the subset $$\left( {3,4} \right)$$ has no least element. Hence, the original interval $$\left[ {2,5} \right]$$ is not well-ordered under the usual ordering relation.