Calculus

Set Theory

Set Theory Logo

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.