Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 · Ordinals and Well-Ordering

Ordinal Numbers

Build the ordinals 0, 1, 2, ω, ω+1 as sets, see successor and limit ordinals, and test the von Neumann definition with Python frozensets.

Natural numbers play two roles. They answer "how many?" (3 apples) and "which position?" (the 3rd in line). For finite sets the two roles coincide. For infinite sets they split: there is one cardinal ℵ₀ for the size of ℕ, but there are many different ordinals for the ways to arrange it in a line.

An ordinal number is the order type of a well-ordered set. This lesson builds ordinals concretely, as sets, using John von Neumann's idea: every ordinal is the set of all smaller ordinals.

Von Neumann's construction

Start with nothing and keep collecting:

Text
0 = ∅                      = { }
1 = {0}                    = { ∅ }
2 = {0, 1}                 = { ∅, {∅} }
3 = {0, 1, 2}              = { ∅, {∅}, {∅, {∅}} }
n + 1 = n ∪ {n}

The successor of an ordinal α is α + 1 = α ∪ {α}. Each number is built from earlier ones using only braces. The number n has exactly n elements, and m < n is the same as m ∈ n.

Python Build the finite von Neumann ordinals

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.

What makes a set an ordinal?

A set α is an ordinal (von Neumann) if:

  1. α is transitive: every element of an element of α is an element of α. (Equivalently x ∈ α implies x ⊆ α.)
  2. α is well-ordered by ∈: for elements x, y of α, exactly one of x ∈ y, x = y, y ∈ x holds, and ∈ has no infinite descending chains on α.

(The usual definition uses the axiom of foundation to simplify condition 2.)

Check 2 = {∅, {∅}}. Its elements are ∅ and {∅}. Every element of an element is an element: the only non-empty element is {∅}, whose element ∅ is in 2. Transitive. And ∅ ∈ {∅}, so ∈ orders the two elements. So 2 is an ordinal.

Python Test whether a set is transitive and ∈-ordered

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.

Past the finite: ω

Collect all finite ordinals into one set:

Text
ω = {0, 1, 2, 3, ...} = ℕ

It is transitive (each n is a subset of ω) and well-ordered by ∈. Its order type is ℕ's. It is the first infinite ordinal. Because ω contains every finite ordinal but is not itself the successor of any of them, it is a limit ordinal: there is no largest element below it.

  • A successor ordinal has the form α + 1; it has a greatest element α.
  • A limit ordinal is a nonzero ordinal that is not a successor, so it is the union of the ordinals below it. ω is the least one.

The ordinals go on

Keep applying the successor operation after ω:

Text
ω, ω + 1, ω + 2, ω + 3, ..., ω + ω = ω·2, ω·2 + 1, ..., ω·3, ..., ω², ..., ω^ω, ...

ω + 1 = ω ∪ {ω}: an infinite list followed by one extra element at the end. That is exactly the "zero moved last" order from the previous lesson.

flowchart LR
  Z["0"] --> O1["1"] --> O2["2"] --> D["..."] --> W["ω"] --> W1["ω+1"] --> W2["ω+2"] --> D2["..."] --> W2x["ω·2"] --> D3["..."]

The ordinals continue past all natural numbers. Each arrow means "next".

All of these ordinals are countable: ω + 1, ω·2 and ω² can each be matched with ℕ. Yet they are all different as order types. Cardinality forgets order; ordinals remember it.

Comparing ordinals

For ordinals, α < β means α ∈ β. This relation is a well-order on any collection of ordinals. Two facts are key:

  • Trichotomy: for any two ordinals α and β, exactly one of α < β, α = β, β < α holds.
  • Every well-ordered set is order-isomorphic to exactly one ordinal. This is the reason ordinals measure all well-orders.

The first uncountable ordinal is ω₁, the set of all countable ordinals. It is the order type of a well-order on a set of cardinality ℵ₁, which you will meet in the continuum hypothesis lesson.

There is no set of all ordinals. If there were, it would be itself an ordinal, hence an element of itself, which foundation forbids. This is the Burali-Forti paradox, an early cousin of Russell's paradox.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In von Neumann's construction, what is the ordinal 3?

    Each ordinal is the set of all smaller ordinals, so 3 = {0, 1, 2}.
  2. 2. Which of these is a limit ordinal?

    ω is not a successor of any ordinal; it is the union of all natural numbers. 5 and ω + 1 are successors.
  3. 3. Why is {0, 2} not an ordinal?

    Ordinals are transitive sets. The element 2 has the element 1, but 1 is missing from {0, 2}.
  4. 4. How are ω and ω + 1 related?

    Order types differ: ω + 1 has a greatest element, ω has none. Both are countable, so their cardinality is the same.

Summary

  • An ordinal is the order type of a well-ordered set; in von Neumann's version, each ordinal is the set of all smaller ordinals.
  • 0 = ∅, α + 1 = α ∪ {α}; α < β means α ∈ β.
  • An ordinal is a transitive set well-ordered by ∈.
  • ω = ℕ is the first limit ordinal; the sequence continues ω + 1, ω + 2, ..., ω·2, ..., ω².
  • Different countable ordinals have the same cardinality but different shapes; there is no set of all ordinals.

Next: Transfinite Induction