Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 37 · Cardinality and Orders

Well-Orders, Induction and Ordinals

Understand well-orders, well-founded induction, ordinal numbers beyond infinity, ordinal arithmetic and the axiom of choice, with runnable Python examples of termination orders.

A well-order is a total order in which every nonempty subset has a least element. (ℕ, ≤) is the model: any nonempty set of natural numbers has a smallest member. The integers (ℤ, ≤) are not well-ordered (the set of negative numbers has no least), and neither are the positive rationals ({1/n} has no least element).

Well-orders are the exact setting in which induction works. They also give the clearest way to count past infinity, which is what ordinals are for.

Why induction works

Take a statement P(n). The well-ordering principle says any nonempty set of naturals has a least element. Suppose P(0) holds and P(n) implies P(n+1), yet P fails somewhere. The set of failures has a least element m; m ≠ 0, and P(m−1) holds, so P(m) holds, a contradiction. Induction and well-ordering are equivalent.

Strong induction assumes P(k) for all k < n and proves P(n). It is more convenient for recursion that refers to many earlier cases, like unique prime factorization.

Python Strong induction as a recursive check: every n > 1 is a product of primes

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.

Well-founded relations

A relation < is well-founded if there is no infinite descending chain a₀ > a₁ > a₂ > …. This generalizes well-orders to partial orders (see partial orders) and gives you well-founded induction: to prove P(x) for all x, show that P(x) follows whenever P(y) holds for all y < x.

In programming this is termination. A loop or recursion terminates if you can find a measure that strictly decreases in a well-founded order. Euclid's algorithm terminates because the second argument decreases in ℕ. The Ackermann function terminates because pairs (m, n) decrease in the lexicographic order on ℕ × ℕ, a well-order even though no single natural number measure suffices.

Python Lexicographic measure for the Ackermann function

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.

Ordinal numbers

Ordinals are the order types of well-orders. The finite ordinals are 0, 1, 2, …; the first infinite one is ω, the order type of ℕ. After that comes ω + 1 (ℕ followed by one extra element on top), ω + 2, …, ω · 2 (two copies of ℕ), ω², ω^ω, and on and on far beyond any list. Each ordinal is either 0, a successor α + 1, or a limit (like ω) which is the supremum of smaller ordinals.

Ordinal arithmetic is not commutative: 1 + ω = ω (a new first element can be absorbed) but ω + 1 > ω. In the standard von Neumann construction each ordinal is the set of all smaller ordinals: 0 = ∅, 1 = {0}, 2 = {0, 1}, and so on.

Python Von Neumann naturals and the order 1 + w versus w + 1

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.

Transfinite induction and recursion

Induction on ordinals needs three cases: prove P(0); prove P(α) ⇒ P(α + 1); and for a limit λ, show that if P(β) holds for all β < λ then P(λ). Transfinite recursion defines objects the same way. It builds the cumulative hierarchy of sets V₀ = ∅, V_{α+1} = P(V_α), V_λ = ⋃_{α<λ} V_α, which models the universe of sets described in the ZFC lesson.

The axiom of choice

The axiom of choice (AC) says that for any family of nonempty sets there is a function choosing one element from each. It is equivalent to two other famous statements:

  • Well-ordering theorem: every set can be well-ordered.
  • Zorn's lemma: if every chain in a nonempty poset has an upper bound, the poset has a maximal element.

AC proves that every vector space has a basis, and that a countable union of countable sets is countable. It also implies counterintuitive results such as the Banach–Tarski paradox. Mathematicians typically accept it; computer scientists often prefer constructive arguments where the choice can be computed.

For finite families, or when you can specify a rule (for example "pick the smallest element of each set of naturals"), choice is automatic. The axiom matters only for infinite families without a rule, such as choosing one sock from each of infinitely many pairs of indistinguishable socks.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

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

    Every nonempty set of natural numbers has a least element. The others have subsets, like the negative integers, with no least element.
  2. 2. What does well-founded mean?

    A relation is well-founded exactly when no infinite strictly descending sequence exists, which is why recursion over it terminates.
  3. 3. Which equation is true for ordinal arithmetic?

    A new first element is absorbed into ω, but adding an element on top, ω + 1, gives a strictly larger ordinal. Ordinal addition and multiplication are not commutative.
  4. 4. Zorn's lemma is equivalent to

    Over ZF, Zorn's lemma, the well-ordering theorem and the axiom of choice are equivalent.

Summary

  • A well-order gives every nonempty subset a least element; induction and well-ordering are equivalent.
  • Well-founded relations have no infinite descending chains and justify termination proofs.
  • Ordinals measure well-orders and continue counting past ω; ordinal arithmetic is not commutative.
  • The axiom of choice is equivalent to the well-ordering theorem and Zorn's lemma.

Next: ZFC Axioms and Russell's Paradox