Ordinal Arithmetic - Exponentiation

Exponentiation

The definition of ordinal exponentiation for finite exponents is straightforward. If the exponent is a finite number, the power is the result of iterated multiplication. For instance, ω2 = ω·ω using the operation of ordinal multiplication. Note that ω·ω can be defined using the set of functions from 2 = {0,1} to ω = {0,1,2,...}, ordered lexicographically with the least significant position first:

(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...

Here for brevity, we have replaced the function {(0,k), (1,m)} by the ordered pair (k, m).

Similarly, for any finite exponent n, can be defined using the set of functions from n (the domain) to the natural numbers (the range). These functions can be abbreviated as n-tuples of natural numbers.

But for infinite exponents, the definition may not be obvious. A limit ordinal, such as ωω, is the supremum of all smaller ordinals. It might seem natural to define ωω using the set of all infinite sequences of natural numbers. However, we find that any absolutely defined ordering on this set is not well-ordered. To deal with this issue we can use the variant lexicographical ordering again. We restrict the set to sequences with are nonzero at only a finite number of arguments. This is naturally motivated as the limit of the finite powers of the base (similar to the concept of coproduct in algebra). This can also be thought of as the infinite union .

Each of those sequences corresponds to an ordinal less than such as and is the supremum of all those smaller ordinals.

The lexicographical order on this set is a well ordering that resembles the ordering of natural numbers written in decimal notation, except with digit positions reversed, and with arbitrary natural numbers instead of just the digits 0-9:

(0,0,0,...) < (1,0,0,0,...) < (2,0,0,0,...) < ... <

(0,1,0,0,0,...) < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... <

(0,2,0,0,0,...) < (1,2,0,0,0,...) < (2,2,0,0,0,...)

< ... <

(0,0,1,0,0,0,...) < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,...)

< ...

In general, any ordinal α can be raised to the power of another ordinal β in the same way to get αβ.

It is easiest to explain this using Von Neumann's definition of an ordinal as the set of all smaller ordinals. Then, to construct a set of order type αβ consider all functions from β to α such that only a finite number of elements of the domain β map to a non zero element of α (essentially, we consider the functions with finite support). The order is lexicographic with the least significant position first. We find

• 1ω = 1,
• 2ω = ω,
• 2ω+1 = ω·2 = ω+ω.

The definition of exponentiation can also be given inductively (the following induction is on β, the exponent):

• α0 = 1,
• αβ+1 = (αβ)·α, and
• if δ is limit, then αδ is the limit of the αβ for all β < δ.

Properties of ordinal exponentiation:

• α0 = 1.
• If 0 < α, then 0α = 0.
• 1α = 1.
• α1 = α.
• αβ·αγ = αβ + γ.
• (αβ)γ = αβ·γ.
• There are α, β, and γ for which (α·β)γ ≠ αγ·βγ. For instance, (ω·2)2 = ω2·2 ≠ ω2·4.
• Ordinal exponentiation is strictly increasing and continuous in the right argument: If γ > 1 and α < β, then γα < γβ.
• If α < β, then αγ ≤ βγ. Note, for instance, that 2 < 3 and yet 2ω = 3ω = ω.
• If α > 1 and αβ = αγ, then β = γ. If α = 1 or α = 0 this is not the case.
• For all α and β, if β > 1 and α > 0 then there exist unique γ, δ, and ρ such that α = βγ·δ + ρ such that 0 < δ < β and ρ < βγ.

Warning: Ordinal exponentiation is quite different from cardinal exponentiation. For example, the ordinal exponentiation 2ω = ω, but the cardinal exponentiation is the cardinality of the continuum which is larger than . To avoid confusing ordinal exponentiation with cardinal exponentiation, one can use symbols for ordinals (e.g. ω) in the former and symbols for cardinals (e.g. ) in the latter.