Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 38 · Ordinals and Well-Ordering

Well-Ordered Sets

Learn what a well-ordering is, why the naturals are well-ordered but the integers and reals are not, and test least elements in Python.

Cardinality asks "how many?". Ordinals ask "in what order?". To count past infinity we need to look at sets whose elements are arranged one after another, in a way that lets us always say what comes first. Such arrangements are called well-orderings, and they are the foundation for ordinal numbers and for transfinite induction.

Total orders

A total order on a set X is a relation ≤ such that for all a, b, c in X:

  • Reflexive: a ≤ a.
  • Antisymmetric: if a ≤ b and b ≤ a then a = b.
  • Transitive: if a ≤ b and b ≤ c then a ≤ c.
  • Total (comparable): a ≤ b or b ≤ a.

The usual orders on ℕ, ℤ, ℚ and ℝ are total orders. So is alphabetical (dictionary) order on words. A partially ordered set, such as subsets under inclusion, lacks the last property.

Well-orders

A total order is a well-order if every nonempty subset has a least element. A least (or minimum) element of S is some m ∈ S with m ≤ s for all s ∈ S.

Examples:

  • (ℕ, ≤) is a well-order. Any nonempty set of natural numbers has a smallest one. This statement is the well-ordering principle, equivalent to induction.
  • Any finite totally ordered set is well-ordered.
  • (ℤ, ≤) is not: the set ℤ itself has no least element.
  • (ℚ⁺, ≤) and ([0, 1], ≤): not well-ordered. (0, 1] has no least element (halving always gives something smaller), and ℚ⁺ has none either.
  • ℤ is also not well-ordered even if you restrict to the negatives, since -1, -2, -3, ... descends forever.

A quick test: a total order is a well-order exactly when there is no infinite strictly descending sequence x₀ > x₁ > x₂ > .... (The direction "no descending sequence implies every subset has a least element" uses a small amount of choice.)

Python Descending chains in Z versus N

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Same elements, different order

A set can have many orders. Take ℕ with a new order ≺ in which 0 is moved to the end: 1 ≺ 2 ≺ 3 ≺ ... ≺ 0. Is this a well-order? Any nonempty subset not containing 0 has an ordinary least element. A subset containing 0 along with other numbers has the same least element as before, and the set has least element 0. So yes: it is a well-order, with an unusual shape: an infinite list followed by one more element. You can test orders with a key function: a rule that gives each element a rank, and a ≺ b means key(a) < key(b), as long as ranks compare in a well-ordered set.

Python Two well-orders on the same set

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Order isomorphism: when two orders have the same shape

Two ordered sets (X, ≤) and (Y, ≤) have the same order type if there is an order isomorphism: a bijection f: X → Y with a ≤ b if and only if f(a) ≤ f(b). Unlike a plain bijection, it must preserve the order.

  • (ℕ, ≤) and the even numbers (2ℕ, ≤) are order-isomorphic via n ↦ 2n.
  • (ℕ, ≤) and (ℕ with 0 last, ≺) are not isomorphic. The second has a largest element (0), and the first does not.

Order type is the notion of "shape" we need. The order type of a well-ordered set is called an ordinal number, defined in the next lesson.

Initial segments

For a in a well-ordered set W, the initial segment below a is W_a = {x ∈ W : x < a}. It is itself well-ordered. In (ℕ, ≤), ℕ_5 = {0, 1, 2, 3, 4}.

A central fact is that two well-ordered sets can always be compared: either they are order-isomorphic, or one is isomorphic to an initial segment of the other (and exactly one of these holds). That is why ordinals are lined up one after another like points on a line.

When a problem asks you to prove something for all elements of a well-ordered set, look for a minimal counterexample: if the property fails somewhere, the set of failures has a least element, which you can examine.

The well-ordering theorem

A famous claim is that every set can be well-ordered. That includes ℝ! No one can describe such an order explicitly, because the statement is equivalent to the axiom of choice, as you will see later.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which ordered set is a well-order?

    Every nonempty set of natural numbers has a least element. ℤ and [0, 1] have nonempty subsets without a least element.
  2. 2. In the order 1 ≺ 2 ≺ 3 ≺ ... ≺ 0 on ℕ, what is the least element of {0, 7, 12}?

    0 comes after every positive number in this order, so the least element is 7.
  3. 3. A total order is a well-order exactly when...

    That is the definition. It is equivalent (with a little choice) to having no infinite strictly descending sequence.
  4. 4. Why are (ℕ, ≤) and (ℕ with 0 last) not order-isomorphic?

    An order isomorphism preserves greatest elements. The reordered set has 0 as the greatest element; ℕ with its usual order has none.

Summary

  • A well-order is a total order in which every nonempty subset has a least element; equivalently, there are no infinite descending chains.
  • ℕ is well-ordered; ℤ, ℚ, ℝ and (0, 1] are not with their usual orders.
  • A set can carry several well-orders of different shapes, for instance ℕ with 0 moved to the end.
  • Order isomorphisms preserve order; the order type of a well-ordered set is its ordinal.
  • Every set can be well-ordered if the axiom of choice holds.

Next: Ordinal Numbers