Suppose β>1, and let ζ>0 be arbitrary. Then ζ has a unique representation in so-called Cantor normal form:
|
(1) |
Stillwell gives an illustration, close to a proof, in §2.6 (pp.46–47)1, for the most important special case: β=ω and ζ<ε0. (The Cantor normal form for ε0 is just ωε0, 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
βχ1+ρ1=βχ2+ρ2, ρ1,ρ2<β
If χ1<χ2 then χ2=χ1+γ for some γ>0. So
βχ1+ρ1=β(χ1+γ)+ρ2=βχ1+βγ+ρ2
Cancelling on the left,
ρ1=βγ+ρ2≥βγ≥β
contradicting the definition of ρ1. So χ1=χ2=χ (say), and we can cancel βχ on the left to get ρ1=ρ2.
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=α−1. So
βα1≤ζ<βα1+1
Now we divide ζ by βα1:
ζ=βα1χ1+ρ1, ρ1<βα1
We cannot have χ1≥β, otherwise
ζ=βα1χ1+ρ1≥βα1β=βα1+1>ζ
Repeat with ρ1:
ρ1=βα2χ2+ρ2, χ2<β, ρ2<βα2
We must have α2<α1 because βα2≤ρ1<βα1. 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 α1<α1′ or α1=α1′ and χ1<χ1′ (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(χ1+1)
If α1=α1′ and χ1<χ1′, then we have βα1(χ1+1)≤βα1′ χ1′. Thus ζ is less than the first term of ζ′. If α1<α1′ then we use the fact that χ1+1≤β, concluding that βα1(χ1+1)≤βα1+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.
