Monthly Archives: May 2025

Prev TOC Next

Suppose β>1, and let ζ>0 be arbitrary. Then ζ has a unique representation in so-called Cantor normal form:

ζ =βα1 χ1+···+βαk χk α1>···>αk, 1≤χi<β for all i

(1)

Stillwell gives an illustration, close to a proof, in §2.6 (pp.46–47)¹, for the most important special case: β=ω and ζ<ε₀. (The Cantor normal form for ε₀ is just ω^ε₀, not helpful.)

Here’s a more formal proof of the full theorem. First generalize division to all ordinals. If β>1, then any ζ has a unique representation in the form

ζ= βχ+ρ,   ρ<β

Proof: since β>1, β(ζ+1)≥ζ+1, and so there is a least χ′ such that βχ′>ζ. Furthermore χ′ cannot be a limit ordinal: if βξ≤ζ for all ξ<λ, then βλ≤ζ by continuity of multiplication. Set χ=χ′−1, so

βχ≤ζ<β(χ+1)

Now write (by equation (7) of post 8)

ζ=βχ+(−βχ+ζ)=βχ+ρ

setting ρ=−βχ+ζ. We cannot have ρ≥β, otherwise

ζ=βχ+ρ≥βχ+β=β(χ+1)>ζ

Uniqueness needs to be done just right, since ordinal addition has cancellation on the left but not on the right. Suppose

βχ₁+ρ₁=βχ₂+ρ₂,    ρ₁,ρ₂<β

If χ₁<χ₂ then χ₂=χ₁+γ for some γ>0. So

βχ₁+ρ₁=β(χ₁+γ)+ρ₂=βχ₁+βγ+ρ₂

Cancelling on the left,

ρ₁=βγ+ρ₂≥βγ≥β

contradicting the definition of ρ₁. So χ₁=χ₂=χ (say), and we can cancel βχ on the left to get ρ₁=ρ₂.

The proof of Cantor normal form starts out in a similar fashion. First prove by induction that β^α≥α for all α. Since β^ζ+1>ζ, it follows that there is a least α with β^α>ζ. Furthermore α cannot be a limit ordinal by continuity of exponentiation (in the exponent). Set α₁=α−1. So

β^α₁≤ζ<β^α₁+1

Now we divide ζ by β^α₁:

ζ=β^α₁χ₁+ρ₁,    ρ₁<β^α₁

We cannot have χ₁≥β, otherwise

ζ=β^α₁χ₁+ρ₁≥β^α₁β=β^α₁+1>ζ

Repeat with ρ₁:

ρ₁=β^α₂χ₂+ρ₂,   χ₂<β,   ρ₂<β^α₂

We must have α₂<α₁ because β^α₂≤ρ₁<β^α₁. Continuing we get a descending sequence of α_i’s which must terminate in finitely many steps, because ordinals. This establishes (1).

The proof of uniqueness provides a bonus: a criterion for which of two normal forms is larger. It’s what you’d expect from decimal notation. Suppose

ζ	=βα1 χ1+···+βαk χk
ζ′	= βα1′ χ1′+···+ βαm′ χm′

are two unequal normal forms. Because cancellation on the left holds for addition, we can remove any equal terms on the left, and assume either α₁<α₁′ or α₁=α₁′ and χ₁<χ₁′ (for the reverse inequalities, just flip things around). Then ζ<ζ′. I will call this the first difference criterion for the ordering of Cantor normal forms.

The proof resembles a decimal computation. To show that 999<1000 (for example), we add 1 and do the carries. Here, we begin by combining the last two terms of ζ, using the facts that χ_k<β and α_k−1>α_k:

βαk-1 χk-1+βαk χk	<βαk-1 χk-1+βαk+1
	≤βαk-1 χk-1+βαk-1
	=βαk-1(χk-1+1)

Next we combine with the previous term, using the fact that χ_k−1+1≤β and α_k−2>α_k−1:

βαk-2 χk-2+βαk-1(χk-1+1)	≤βαk-2 χk-2+βαk-1+1
	≤βαk-2(χk-2+1)

We keep going, until eventually we have

ζ<β^α₁(χ₁+1)

If α₁=α₁′ and χ₁<χ₁′, then we have β^α₁(χ₁+1)≤β^α₁′ χ₁′. Thus ζ is less than the first term of ζ′. If α₁<α₁′ then we use the fact that χ₁+1≤β, concluding that β^α₁(χ₁+1)≤β^α₁+1≤β^α₁′, and hence ζ is again less than the first term of ζ′. A fortiori, ζ<ζ′.

Uniqueness follows. These ordering criteria are needed for the Goodstein and Hydra theorems.

[1] However, Stillwell messes up at the end of the example. In the last bullet he says, “This means that α is a term in the following sequence with limit ω^{ω2·7+ω·4+11}+ω= ω^{ω2·7+ω·4+12}.” This equation is incorrect; the last “+ω’’ should be “·ω’’. The sequence on the next line should have “·1’’, “·2’’, etc., instead of “+1’’, “+2’’, etc. So he has many more steps to go.

Another point. When he says that α “falls between” two terms in a sequence, he’s not entitled to assume it falls strictly between. He should say instead that there are two consecutive terms with α greater than or equal to the first and less than the second.

Prev TOC Next

Prev TOC Next

Usually one defines the ordinal operations via transfinite induction:

Continue reading →