Ordinals and axioms · Definition

Well-ordering

set theoryordinals and axioms

Before you start you need to know

The natural numbers can be traversed from the first one onward without ever going backward. Well-ordering formalizes that intuition and extends it to any set.

Definition

A set \(A\) is well-ordered by \(<\) if \(<\) is a total order on \(A\) and every nonempty subset of \(A\) has a least element.

\[\forall S\subseteq A(S\ne\varnothing\Rightarrow\exists m\in S\forall s\in S\,m\le s)\]

Every well-ordered set is also totally ordered, so any two elements are comparable. The key property is that every nonempty subset has a least element, which rules out any infinite strictly decreasing sequence. That is why \(\mathbb{N}\) with its usual order is well-ordered, while \(\mathbb{Z}\) is not.

Take \(A=\{\frac{1}{n} : n\in\mathbb{N},\ n\ge 1\}\) with the usual order of \(\mathbb{R}\). The set \(A\) has no least element, because for each \(\frac{1}{n}\) there is a smaller \(\frac{1}{n+1}\). With the reverse order \(\ge\), however, its first element is \(1\), and the set is well-ordered.

A common mistake is to think every total order is a well-order. The interval \((0,1)\) with its usual order is totally ordered, but it has no least element, so it is not well-ordered. Having a largest element is not enough either: the set \(\{\dots,-2,-1,0\}\) has maximum \(0\) but no least element.

Think about it

Why is \(\mathbb{N}\) well-ordered but \(\mathbb{Z}\) is not?

Because every nonempty subset of \(\mathbb{N}\) has a least element, while the negative integers in \(\mathbb{Z}\) do not.

Exercises 10

  1. Which of the following statements describes a well-ordered set?
  2. Is \(\mathbb{Z}\) well-ordered by its usual order?
  3. Which of these sets is well-ordered by the usual order of \(\mathbb{R}\)?
  4. If \(A\) is well-ordered and \(B\subseteq A\) is nonempty, what holds?
  5. Let \(A=\{2,5,7\}\) with the usual order. What is its least element, and why is \(A\) well-ordered?
  6. Is the set \(\{x\in\mathbb{Q} : x>0\}\) well-ordered by its usual order?
  7. Let \(B=\{n\in\mathbb{N} : n^2>20\}\) with the usual order. What is its least element?
  8. Which of these subsets of \(\mathbb{Z}\) has a least element?
  9. Let \(A\) be a well-ordered set and \(f:A\to A\) such that \(f(a)<a\) for all \(a\in A\). What follows?
  10. Is \(\mathbb{N}\) well-ordered by the reverse order \(\ge\)? Choose the correct statement.

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.