Ordinal Arithmetic - Cantor Normal Form

Cantor Normal Form

Ordinal numbers present a rich arithmetic. Every ordinal number α can be uniquely written as, where k is a natural number, are positive integers, and are ordinal numbers (we allow ). This decomposition of α is called the Cantor normal form of α, and can be considered the base-ω positional numeral system. The highest exponent is called the degree of, and satisfies . The equality applies if and only if . In that case Cantor normal form does not express the ordinal in terms of smaller ones; this can happen as explained below.

A minor variation of Cantor normal form, which is usually slightly easier to work with, is to set all the numbers c_i equal to 1 and allow the exponents to be equal. In other words, every ordinal number α can be uniquely written as, where k is a natural number, and are ordinal numbers.

The Cantor normal form allows us to uniquely express—and order—the ordinals α which are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and “raising ω to the power of”: in other words, assuming in the Cantor normal form, we can also express the exponents in Cantor normal form, and making the same assumption for the as for α and so on recursively, we get a system of notation for these ordinals (for example,

denotes an ordinal).

The ordinal ε₀ (epsilon nought) is the set of ordinal values of the finite arithmetical expressions of this form. It is the smallest ordinal that does not have a finite arithmetical expression, and the smallest ordinal such that, i.e. in Cantor normal form the exponent is not smaller than the ordinal itself. It is the limit of the sequence

The ordinal ε₀ is important for various reasons in arithmetic (essentially because it measures the proof-theoretic strength of the first-order Peano arithmetic: that is, Peano's axioms can show transfinite induction up to any ordinal less than ε₀ but not up to ε₀ itself).

The Cantor normal form also allows us to compute sums and products of ordinals: to compute the sum, for example, one need merely know that

if (if one can obviously rewrite this as, and if the expression is already in Cantor normal form); and to compute products, the essential facts are that when is in Cantor normal form (and α>0) then

and

if n is a non-zero natural number.

To compare two ordinals written in Cantor normal form, first compare, then, then, then, etc.. At the first difference, the ordinal which has the larger component is the larger ordinal. If they are the same until one terminates before the other, then the one which terminates first is smaller.