Ordinal arithmetic

Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion.

Cantor normal form provides a standardized way of writing ordinals.

The sum of two well-ordered sets S and T is the ordinal representing the variant of lexicographical order with least significant position first, on the union of the Cartesian products S × {0} and T × {1}.

This way, every element of S is smaller than every element of T, comparisons within S keep the order they already have, and likewise for comparisons within T. The definition of addition α + β can also be given by transfinite recursion on β.

Addition is strictly increasing and continuous in the right argument: but the analogous relation does not hold for the left argument; instead we only have: Ordinal addition is left-cancellative: if α + β = α + γ, then β = γ.

Effectively, each element of T is replaced by a disjoint copy of S. The order-type of the Cartesian product is the ordinal that results from multiplying the order-types of S and T. The definition of multiplication can also be given by transfinite recursion on β.

Multiplication is strictly increasing and continuous in the right argument: (α < β and γ > 0) → γ·α < γ·β.

Specifically, a natural number greater than 1 never commutes with any infinite ordinal, and two infinite ordinals α and β commute if and only if αm = βn for some nonzero natural numbers m and n. The relation "α commutes with β" is an equivalence relation on the ordinals greater than 1, and all equivalence classes are countably infinite.

Distributivity holds, on the left: α(β + γ) = αβ + αγ.

Then, to construct a set of order type αβ consider the set of all functions f : β → α such that f(x) = 0 for all but finitely many elements x ∈ β (essentially, we consider the functions with finite support).

The definition of exponentiation can also be given by transfinite recursion on the exponent β.

Writing the successor and limit ordinals cases separately: Both definitions simplify considerably if the exponent β is a finite number: αβ is then just the product of β copies of α; e.g. ω3 = ω·ω·ω, and the elements of ω3 can be viewed as triples of natural numbers, ordered lexicographically with least significant position first.

For example, αω can be identified with a set of finite sequences of elements of α, properly ordered.

The degenerate case α = 0 occurs when k = 0 and there are no βs nor cs.

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 ci equal to 1 and allow the exponents to be equal.

In other words, every ordinal number α can be uniquely written as

The Cantor normal form allows us to uniquely express—and order—the ordinals α that are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and exponentiation base-

, i.e. in Cantor normal form the exponent is not smaller than the ordinal itself.

It is the limit of the sequence The ordinal ε0 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 ε0 but not up to ε0 itself).

the expression is already in Cantor normal form); and to compute products, the essential facts are that when

However, there is a unique factorization into primes satisfying the following additional conditions: This prime factorization can easily be read off using the Cantor normal form as follows: So the factorization of the Cantor normal form ordinal into a minimal product of infinite primes and natural numbers is where each ni should be replaced by its factorization into a non-increasing sequence of finite primes and As discussed above, the Cantor normal form of ordinals below ε0 can be expressed in an alphabet containing only the function symbols for addition, multiplication and exponentiation, as well as constant symbols for each natural number and for ω.

We can do away with the infinitely many numerals by using just the constant symbol 0 and the operation of successor, S (for example, the natural number 4 may be expressed as S(S(S(S(0))))).

The natural sum and natural product operations on ordinals were defined in 1906 by Gerhard Hessenberg, and are sometimes called the Hessenberg sum (or product) (Sierpiński 1958).

Natural sum and product are not continuous in the right argument, since, for example

The natural sum and product are the same as the addition and multiplication (restricted to ordinals) of John Conway's field of surreal numbers.

Under natural addition, the ordinals can be identified with the elements of the free commutative monoid generated by the gamma numbers ωα.

Under natural addition and multiplication, the ordinals can be identified with the elements of the free commutative semiring generated by the delta numbers ωωα.

The ordinals do not have unique factorization into primes under the natural product.

Nimber addition is a generalization of the bitwise exclusive or operation on natural numbers.