Ordinals: transitive sets well-ordered by ∈, and the proofs they make possible¶

Level: 201 · for anyone at Cori and Lascar's Definition 7.12 or Jech's chapter 2 who can follow the definition and does not yet see what it is for

One line: An ordinal is a set that is transitive, every member is also a subset, and well-ordered by membership, and the only ordinals in a finite universe are the von Neumann numbers 0, 1, 2, 3; what ordinals buy is the right to say "this quantity goes down at every step, so the process stops" past the finite numbers, and Goodstein's theorem is a statement about ordinary integers whose only known proof says exactly that.

The definition, read aloud¶

Cori and Lascar, Definition 7.12: α is an ordinal when (1) α is transitive, meaning every member of a member of α is a member of α, so every member is a subset, and (2) the membership relation on α is a well-ordering: a strict total order in which every non-empty subset has a least member. Jech, chapter 2, defines it the same way. The two conditions say that α is a set of earlier ordinals arranged in a line, and the next ordinal after α is α ∪ {α}, the line with α itself appended (Corollary 7.19).

The program finds the transitive sets of V₄ in section 1: six of the sixteen. Four of them are ordinals, the numbers 0 to 3, each the set of the smaller ones. The other two are transitive and not totally ordered: V₃ = {∅, {∅}, {{∅}}, {∅, {∅}}} has the members {∅} and {{∅}}, and neither is a member of the other, so ∈ does not compare them. Section 3 checks the book's remarks 7.13 to 7.22 on the four ordinals: α ∉ α, every member of an ordinal is an ordinal, α ⊆ β exactly when α ≤ β, α ∪ {α} is an ordinal, and any two ordinals compare.

What they are for¶

Counting past the finite. ω = {0, 1, 2, …} is an ordinal, the first infinite one and the first limit ordinal, neither ∅ nor a successor; the axiom of infinity in Cori and Lascar's form says exactly that one exists. Then ω + 1 = ω ∪ {ω}, ω + 2, …, ω + ω, …, ω², …, ω^ω, and every well-ordered set is isomorphic to exactly one ordinal (Proposition 7.27). Ordinals are the measuring sticks for well-orderings as cardinals are for size.

Induction and recursion beyond ℕ. A proof by induction on the ordinals, or a definition by recursion along them (Theorem 7.20, and the stages V_α), covers transfinite constructions: the Borel sets of analysis are built in ω₁ steps, Cantor invented ordinals in 1872 to iterate the derived set of a set of real numbers past ω for a problem about Fourier series, and Gödel's constructible universe L is a recursion along all the ordinals.

Termination. The property that matters most outside set theory is the one the definition hides in "well-ordered": a strictly decreasing sequence of ordinals is finite. If each step of a process is labelled with an ordinal and the labels go down, the process stops, however fast the numbers inside it grow. This is how proof theory measures the strength of theories (Gentzen proved the consistency of arithmetic in 1936 by induction up to ε₀) and how programs are proved to terminate: a proof assistant such as Lean accepts a recursive definition when a measure decreases, and the measure may be an ordinal.

Goodstein's theorem: number theory that needs ordinals¶

Section 4 runs the example that shows the point. Write n in hereditary base 2: in base 2, with the exponents also in base 2, and so on down. Change every 2 to a 3 and subtract 1. Write the result in hereditary base 3, change 3 to 4, subtract 1. Continue. Goodstein (1944) proved that every such sequence reaches 0, and the program shows why: replace the base by ω and each step's expression is an ordinal in Cantor normal form, and it strictly decreases, because the subtraction of 1 always knocks down a term while the base change does not touch the ordinal. A decreasing sequence of ordinals is finite, so the sequence ends.

What the output shows is the gap between the two readings. G(3) is over in five steps. G(4) climbs 4, 26, 41, 60, 83, … and reaches 0 only after 3 · 2^402653211 − 2 steps, a number with over a hundred million digits, while its ordinal label drops from ω^ω through ω²·2 + ω·2 + 2 one unit at a time. Kirby and Paris (1982) proved that Goodstein's theorem, a statement purely about natural numbers, cannot be proved in Peano arithmetic: any proof must use something as strong as induction up to ε₀, which is to say ordinals. So the answer to "does number theory use this?" is: ordinarily no, the integers of Cori and Lascar's section 7.2.4 are built and then arithmetic forgets the construction; but there are true statements about the integers whose only road is through the ordinals, and this is the simplest one.

What the program prints¶

Verified output of ordinals.py — regenerated by tools/run_examples.py, never hand-typed.

1. TRANSITIVE SETS IN V_4: EVERY MEMBER IS ALSO A SUBSET
   6 of the 16 sets are transitive:
     ∅                                  ordinal: True
     {∅}                                ordinal: True
     {∅, {∅}}                           ordinal: True
     {∅, {∅}, {{∅}}}                    ordinal: False
     {∅, {∅}, {∅, {∅}}}                 ordinal: True
     {∅, {∅}, {{∅}}, {∅, {∅}}}          ordinal: False
   not transitive, e.g. {{∅}}: its member {∅} is not a subset.

2. ORDINALS: TRANSITIVE AND WELL-ORDERED BY ∈ (DEFINITION 7.12)
   the ordinals in V_4 are the von Neumann numbers [0, 1, 2, 3]:
   ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}
   {∅, {∅}, {{∅}}, {∅, {∅}}} is transitive but not an ordinal:
   {∅} and {{∅}} are members, and neither is a member of the other,
   so ∈ does not order it totally (Proposition 7.17 needs that).

3. THE BOOK'S REMARKS, CHECKED ON THESE ORDINALS
   7.13  α ∉ α for every ordinal: True
   7.14  every member of an ordinal is an ordinal: True
   7.16  α ⊆ β iff α ≤ β (α ∈ β or α = β): True
   7.19  α ∪ {α} is an ordinal: True
   7.22  for ordinals α, β exactly one of α ∈ β, β ∈ α, α = β: True

4. WHAT ORDINALS ARE FOR: A DECREASING SEQUENCE OF THEM MUST STOP
   Goodstein (1944): write n in hereditary base 2 (exponents in base 2 too),
   change every 2 to 3 and subtract 1; write that in hereditary base 3,
   change 3 to 4, subtract 1; and so on. Replace the base by ω and each
   step's ordinal is strictly smaller, though the numbers explode.
   G(3):
     step base  value   ordinal
        0    2      3   ω + 1
        1    3      3   ω
        2    4      3   3
        3    5      2   2
        4    6      1   1
        5    7      0   0
   G(4):
     step base  value   ordinal
        0    2      4   ω^ω
        1    3     26   ω^2·2 + ω·2 + 2
        2    4     41   ω^2·2 + ω·2 + 1
        3    5     60   ω^2·2 + ω·2
        4    6     83   ω^2·2 + ω + 5
        5    7    109   ω^2·2 + ω + 4
        6    8    139   ω^2·2 + ω + 3
        7    9    173   ω^2·2 + ω + 2
        8   10    211   ω^2·2 + ω + 1
   G(3) reaches 0 in 5 steps. G(4) grows for 3·2^402653211 − 2 steps and
   then reaches 0, and so does every G(n), because its ordinals decrease
   and a decreasing sequence of ordinals is finite: that is what 'well-
   ordered' means. Kirby and Paris (1982) proved this statement about
   natural numbers cannot be proved in Peano arithmetic at all: the
   ordinals are not decoration here, they are the only known road.

Po polsku, w skrócie¶

Liczba porządkowa (ordinal) to zbiór przechodni, czyli taki, którego każdy element jest też podzbiorem, dobrze uporządkowany przez relację należenia ∈. W skończonym uniwersum V₄ liczbami porządkowymi są tylko liczby von Neumanna 0, 1, 2, 3; zbiór V₃ jest przechodni, ale nie jest liczbą porządkową, bo jego elementów {∅} i {{∅}} relacja ∈ nie porównuje. Program sprawdza na tych liczbach uwagi 7.13–7.22 z książki Coriego i Lascara. Po co to wszystko: liczby porządkowe liczą dalej niż liczby naturalne (ω, ω + 1, …, ω^ω), pozwalają na indukcję i rekursję pozaskończoną, a przede wszystkim dają prawo powiedzieć „ta wielkość maleje w każdym kroku, więc proces się skończy". Ciągi Goodsteina pokazują to na liczbach naturalnych: zapis w bazie dziedzicznej, zamiana bazy na następną i odjęcie 1; liczby rosną astronomicznie, a przypisane im liczby porządkowe maleją, więc ciąg dochodzi do zera. G(4) potrzebuje na to 3 · 2^402653211 − 2 kroków. Kirby i Paris (1982) udowodnili, że tego twierdzenia o liczbach naturalnych nie da się udowodnić w arytmetyce Peana: jedyna znana droga wiedzie przez liczby porządkowe.

Auf Deutsch: Stichwörter¶

Ordinalzahlen sind transitive, durch ∈ wohlgeordnete Mengen; die Beweise, die sie ermöglichen, und was ω + 1 ≠ 1 + ω bedeutet.

Stichwörter: Ordinalzahl, transitive Menge, Wohlordnung, Nachfolgerordinalzahl, Limesordinalzahl, ω, transfinite Induktion, Ordinalarithmetik.

Run it yourself¶

From the root of your clone of this repository:

python3 13_Axioms_of_Set_Theory/ordinals/examples/ordinals.py