Set Theory Jottings 8. Ordinal Arithmetic

Prev TOC Next

Usually one defines the ordinal operations via transfinite induction:

α+(β+1)	=	(α+β)+1	(1.1)
α+λ	=	supβ<λ (α+β)	(1.2)
α(β+1)	=	αβ+α	(1.3)
αλ	=	supβ<λ (αβ)	(1.4)
αβ+1	=	αβ α	(1.5)
αλ	=	supβ<λ (αβ)	(1.6)

But we can also define the operations directly:

• α+β is the order type of α⊔β, where ⊔ is disjoint union, i.e., the set (α×{1})∪(β×{2}), ordered with all the pairs in α×{1} less than all the pairs in β×{2}.
• αβ is the order type of α×β, with reverse lexicographic order, i.e., 〈x,y〉<〈x′,y′〉 iff y<y′ or (y=y′ and x<x′). (One says, ordered by last difference.)
• α^β is the order type of a set we’ll denote Fin(β→α). These are the functions from β to α with finite support, i.e., f(x)=0 for all but finitely many x∈β. (We call {x:f(x)≠0} the support of f.) We order Fin(β→α) by last difference, i.e., f<g iff f(x)<g(x) where x is the largest element of β such that f(x)≠g(x). We know there is such an x, unless f=g, because of the assumption of finite support. We’ll show that Fin(β→α) is well-ordered below.

We demonstrate agreement with the inductive definitions by proving three stronger facts (plus two more that I’ve thrown in just for kicks):

α+(β+γ)	=	(α+β)+γ	(2.1)
α(β+γ)	=	αβ+αγ	(2.2)
αβ+γ	=	αβ αγ	(2.3)
α(βγ)	=	(αβ)γ	(2.4)
(αβ)γ	=	αβγ	(2.5)

plus continuity in the second argument (the equations with λ). For the first equation in (2), note that both sides are order-isomorphic to α⊔β⊔γ, i.e.,

(α×{1}) ∪ (β×{2}) ∪ (γ×{3})

ordered by last difference (i.e., the tag 1, 2, or 3 counts most heavily, followed by the ordering within the ordinals α, β, and γ.) For the second, note that

α×(β⊔γ) ≅ (α×β)⊔(α×γ)

both sides being order-isomorphic to the set (α×β×{1})∪(α×γ×{2}) ordered by last difference. For the third, suppose f∈Fin(β+γ→α). Map f to 〈f↾β, f↾γ〉. (I trust you can tell what I mean by f↾β and f↾γ; this isn’t quite the usual kind of restriction, since β+γ is the order-type of β⊔γ and not β∪γ.) Verify that this is an order-isomorphism from Fin(β+γ→α) to Fin(β→α)×Fin(γ→α). The associativity of multiplication is trivial. The rule for stacked exponentials can be proved via induction, or via “currying” with the direct definition.

The continuity equations follow from the fact that λ=⋃_β<λβ plus the equations

α⊔⋃β<λβ	=	⋃β<λα⊔β
α×⋃β<λβ	=	⋃β<λα×β
Fin(λ→α)	≅	⋃β<λFin(β→α)

all routinely verified. (For the last, we have to extend functions of finite support on β to the domain λ, by assigning the value 0 to all arguments ≥β. On the other hand, any function of finite support with domain λ has its support contained in some β<λ.)

The three operations enjoy continuity in the second argument; how about the first? This fails for both addition and multiplication:

ω+ω = (sup_n∈ωn)+ω ≠ sup_n∈ω(n+ω) = ω
ωω = (sup_n∈ωn)ω ≠ sup_n∈ω(nω) = ω

But it does hold for exponentiation:

λ^β=(sup_α<λα)^β = sup_α<λ(α^β)

The proof resembles the proof of continuity in the exponent:

Fin(β→λ)=⋃_α<λFin(β→α)

since any function of finite support from β to λ has its range contained in some α<λ.

One can illustrate many of these equations with pictures, amounting to “proofs without words”. I won’t bother, but I do recommend it as an exercise.

We need to show that Fin(β→α) is well-ordered. We use transfinite induction on β. Let S be a nonempty subset of Fin(β→α). Pick an s∈S, and set S′={f∈S:f≤s}. A smallest element of S′ is obviously smallest in S. Let ρ be the largest element in the support of s (so ρ<β). For any f≤s and any σ with ρ<σ<β, we must have f(σ)=0. So we can restrict the domains of all the functions in S′ to ρ+1 without affecting the order relations. Consider all the values f(ρ) for f∈S′. Since α is well-ordered, there is a least such value; let it be m=f(ρ) with f∈S′. We now let S″={g∈S′:g≤f}. It is again obvious that a smallest element of S″ is smallest in S′ and hence in S. For any g≤f, we must have g(ρ)=m: if g(ρ)>m then g>f, and if g(ρ)<m then m would not be the least value at ρ for the functions in S′. Since all the functions in S″ have the same value at ρ, we can restrict their domains to ρ without affecting the order relations. But S″ (with domains thus restricted) is a nonempty subset of Fin(ρ→α), and so by inductive assumption has a least element.

Here are some facts about ordinal inequalities needed for the Goodstein and Hydra (Kirby-Paris) theorems. (I may or may not get to those.)

α≤α′	⇒	α+β≤α′+β	(3.1)
β<β′	⇒	α+β<α+β′	(3.2)
α≤α′	⇒	αβ≤α′β	(3.3)
β<β′ & α>0	⇒	αβ<αβ′	(3.4)
β≤β′	⇒	αβ≤αβ′	(3.5)
α≤α′	⇒	αβ≤(α′)β	(3.6)

Summarizing, addition on the left preserves strict inequalities, on the right just nonstrict ones. Likewise for multiplication by a nonzero ordinal. Exponentiation preserves nonstrict inequalities, in both the base and the exponent.

Note that from (3.1) and (3.2) we get

∀i α_i≤α_i′ ⇒ α₁+····+α_m ≤ α₁′+···+α_m′        (4)

thus: α₁+α₂≤α₁′+α₂≤α₁′+α₂′, etc. Likewise, from (3.3) and (3.4) we get

∀i α_i≤α_i′ ⇒α₁····α_m≤α₁′····α_m′            (5)

OK, proofs. First note that

α<β ⇔ (∃γ>0) α+γ=β            (6)

Visually this is obvious. More formally, let γ be the order-type of β∖α (since α⊂β when α<β). The other direction is also easy. Note that by (3.2) (once we prove it), γ is unique. One defines this unique γ to be −α+β, so

β=α+(−α+β)           (7)

For example, −1+ω=ω, and 1+(−1+ω)=ω. This suggests why the notation β−α is not used, as you’d expect ω−1 to be the (non-existent) predecessor of ω. Indeed, we write α−1 for the predecessor of a successor ordinal α.

From (6) we immediately have (3.2): β<β′ implies β+γ=β′ implies α+β+γ=α+β′.

In (3.1), observe that strict inequalities are not preserved: 0<1 but 0+ω=1+ω. Transfinite induction is the easiest approach. First note that if γ>0, then γ=1+δ with δ the order-type of γ∖{0}. Suppose α<α′ so α+γ=α′ with γ>0. Then α+γ+1=α′+1, i.e., α+1+δ+1=α′+1, so α+1≤α′+1. (Indeed, α+1<α′+1.) I leave the limit ordinal case as an exercise.

(6) also immediately yields (3.4): if β<β′ so β+γ=β′ with γ>0, then α(β+γ)=αβ+αγ=αβ′, so if α>0, then αβ<αβ′.

Multiplication on the right does not preserve strict inequalities: 1<2 but 1ω=2ω. Also, multiplication is not distributive on the right: (1+1)ω≠ω+ω.

We prove (3.3) inductively. If α≤α′, then α(β+1)=αβ+α≤α′β+α≤α′β+α′=α′(β+1). As usual, the limit ordinal case is straightforward.

(3.4) plus (2.3) yields (3.5), once we note that α^γ≥1 for α>0. If β+γ=β′, then α^β≤α^β α^γ=α^β+γ= α^β′.

Finally, for (3.6) we go back to our definition of α^β. (An inductive proof is also not hard.) Fin(β→α)⊆Fin(β→α′); moreover, the inclusion map is order-preserving, simply because the definition of f<g doesn’t depend on the codomain of f and g. Transfinite induction easily shows that if we have an order-preserving map from one well-ordered set into another, then the order-type of the first is less than or equal to the order-type of the second.

Prev TOC Next