Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 38 · Ordinals and Well-Ordering

Ordinal Arithmetic

Add and multiply ordinals, see why 1 + ω = ω but ω + 1 ≠ ω, and compute with Cantor normal form for ordinals below ω^ω in Python.

Ordinals can be added, multiplied and raised to powers, just like numbers. But now the order of the operands matters. For ordinals, 1 + ω and ω + 1 are different, and 2 · ω and ω · 2 are different. This lesson explains why, using pictures of well-ordered sets, and gives you a small calculator for ordinals below ω^ω.

Addition: put one order after another

For ordinals α and β, the sum α + β is the order type of a copy of α followed by a copy of β. Place everything of the first order before everything of the second.

  • 2 + 3: two points, then three points: five points in a row. So 2 + 3 = 5.
  • ω + 1: an infinite list 0, 1, 2, ... followed by one more point at the end. This has a greatest element, so it is not the same as ω.
  • 1 + ω: one point followed by an infinite list. Relabel: *, 0, 1, 2, ... is order-isomorphic to 0, 1, 2, 3, ... by shifting. So 1 + ω = ω.
Text
ω + 1 : 0  1  2  3 ...   ★
1 + ω : ★  0  1  2  3 ...   =  ω

So ordinal addition is not commutative: 1 + ω = ω ≠ ω + 1. It is associative, and α < β implies γ + α < γ + β (strictly increasing in the right argument), but not in the left: 1 < 2 and yet 1 + ω = 2 + ω.

Formally (transfinite recursion on β): α + 0 = α, α + (β + 1) = (α + β) + 1, and α + λ = sup{α + β : β < λ} for limit λ.

Multiplication: repeat copies

α · β is the order type of β copies of α placed one after another. (Careful with the convention: α · β means "β copies of α", so ω · 2 = ω + ω while 2 · ω = 2 + 2 + 2 + ... = ω.)

  • ω · 2 = ω + ω: two infinite lists, one after the other. This is the ordinal following all ω + n.
  • 2 · ω: infinitely many copies of a two-point set: a b a b a b .... That is just an infinite list, so 2 · ω = ω.

So multiplication is not commutative either: 2 · ω = ω ≠ ω · 2.

Exponentiation α^β and the ordinal ω^2 = ω · ω (a copy of ω for each natural number) keep climbing: ω², ω³, ..., ω^ω, ..., ε₀.

Cantor normal form

Every ordinal α > 0 can be written uniquely as

Text
α = ω^(e₁)·c₁ + ω^(e₂)·c₂ + ... + ω^(eₖ)·cₖ

with ordinals e₁ > e₂ > ... > eₖ and positive natural numbers cᵢ. For ordinals below ω^ω, the exponents are natural numbers, so α looks like a polynomial in ω with natural-number coefficients written from the highest power down, for example ω² · 3 + ω · 5 + 7.

The rules:

  • Adding β on the right to α: terms of α with an exponent smaller than the leading exponent of β disappear (they are "absorbed"); then combine.
  • Multiplying by a finite n on the right: (ω^d · c + rest) · n = ω^d · (c·n) + rest; the lower terms survive only once.
  • Multiplying by ω^e (with e ≥ 1) on the right: α · ω^e = ω^(d+e), where d is the leading exponent of α.

A calculator

Represent an ordinal below ω^ω as a list of (exponent, coefficient) pairs, highest exponent first.

Python An ordinal calculator for ordinals below ω^ω

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.

Look at the output for (ω + 1) · 2. It is ω · 2 + 1, not ω · 2 + 2: the ordering is ω + 1 followed by ω + 1, and the first + 1 is absorbed into the second copy of ω. Similarly ω² + ω + ω simplifies to ω² + ω · 2.

Comparing ordinals in Cantor form

To compare two ordinals in Cantor normal form, compare them like words in a dictionary: compare the leading exponent first, then its coefficient, then the next term, and so on. A missing term counts as lower than a present term.

Python Compare ordinals in Cantor normal form

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.

Python's list comparison happens to be exactly the right rule here, because a shorter list that is a prefix of a longer one is smaller, which matches "a missing term is lower than a present term".

Why it matters

Ordinal arithmetic is the language of Goodstein's proof and of termination arguments for programs. It also shows that countable ordinals form a huge, rich collection: every ordinal below ε₀ has a Cantor normal form, yet all of them are countable.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is 1 + ω as an ordinal?

    A single point followed by ω has the same shape as ω itself: shift every element down one place. So 1 + ω = ω.
  2. 2. Which pair of ordinals is different?

    ω + 1 has a greatest element and 1 + ω does not, so they are different. Ordinal addition is not commutative.
  3. 3. What does ω · 2 mean?

    α · β means β copies of α. So ω · 2 = ω + ω, while 2 · ω = ω.
  4. 4. In Cantor normal form, ω² + ω + ω equals...

    The two copies of ω combine into ω · 2. The ω² stays in front.

Summary

  • α + β puts β after α; α · β is β copies of α.
  • Ordinal addition and multiplication are associative but not commutative: 1 + ω = ω ≠ ω + 1, 2 · ω = ω ≠ ω · 2.
  • Every ordinal has a unique Cantor normal form; below ω^ω it is a polynomial in ω with natural coefficients.
  • Adding on the right absorbs smaller terms; comparison is lexicographic.
  • Ordinal arithmetic is defined by transfinite recursion.

Next: Russell's Paradox