Ordinal arithmetic

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. 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. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

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

The first transfinite ordinal is ω, the set of all natural numbers. For example, the ordinal ω + ω is obtained by two copies of the natural numbers ordered in the usual fashion and the second copy completely to the right of the first. Writing 0' < 1' < 2' < ... for the second copy, ω + ω looks like

This is different from ω because in ω only 0 does not have a direct predecessor while in ω + ω the two elements 0 and 0' do not have direct predecessors. As another example, here are 3 + ω and ω + 3:

After relabeling, the former just looks like ω itself, i.e. 3 + ω = ω, while the latter does not: ω + 3 is not equal to ω since ω + 3 has a largest element (namely, 2') and ω does not (even if ω and ω + 3 are equipotent, they are not isomorphic). Hence, this addition is not commutative. In fact it is quite rare for α+β to be equal to β+α: this happens if and only if α=γm, β=γn for some ordinal γ and natural numbers m and n. From this it follows that "α commutes with β" is an equivalence relation on the class of nonzero ordinals, and all the equivalence classes are countably infinite. However, addition is still associative; one can see for example that (ω + 4) + ω = ω + (4 + ω) = ω + ω.

but the analogous relation does not hold for the left argument; instead we only have:

Ordinal addition is left-cancellative: if α + β = α + γ, then β = γ. Furthermore, one can define left subtraction for ordinals βα: there is a unique γ such that α = β + γ. On the other hand, right cancellation does not work:

Nor does right subtraction, even when βα: for example, there does not exist any γ such that γ + 42 = ω.

If the ordinals less than α are closed under addition and contain 0 then α is occasionally called a γ-number (see additively indecomposable ordinal). These are exactly the ordinals of the form ωβ.

The Cartesian product, S×T, of two well-ordered sets S and T can be well-ordered by a variant of lexicographical order that puts the least significant position first. 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. Again, this operation is associative and generalizes the multiplication of natural numbers.

which has the same order type as ω + ω. In contrast, 2·ω looks like this:

and after relabeling, this looks just like ω. Thus, ω·2 = ω+ω ≠ ω = 2·ω, showing that multiplication of ordinals is not commutative. More generally, a natural number greater than 1 never commutes with any infinite ordinal, and two infinite ordinals α, β commute if and only if αm = βn for some positive 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 partially holds for ordinal arithmetic: α(β+γ) = αβ+αγ. However, the other distributive law (β+γ)α = βα+γα is not generally true: (1+1)·ω = 2·ω = ω while 1·ω+1·ω = ω+ω, which is different. Therefore, the ordinal numbers form a left near-semiring, but do not form a ring.

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

A δ-number (see Multiplicatively indecomposable) is an ordinal greater than 1 such that αβ=β whenever 0<α<β. These consist of the ordinal 2 and the ordinals of the form ωωβ.

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

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:

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 . 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

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

Jacobsthal showed that the only solutions of αβ = βα with α ≤ β are given by α = β, or α = 2 and β = 4, or α is any limit ordinal and β = εα where ε is an ε-number larger than α.[2]

Another variation of the Cantor normal form is the "base δ expansion", where ω is replaced by any ordinal δ>1, and the numbers ci are positive ordinals less than δ.

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 Cantor normal form also allows us to compute sums and products of ordinals: to compute the sum, for example, one need merely know (see the properties listed in § Addition and § Multiplication) that

Ernst Jacobsthal showed that the ordinals satisfy a form of the unique factorization theorem: every nonzero ordinal can be written as a product of a finite number of prime ordinals. This factorization into prime ordinals is in general not unique, but there is a "minimal" factorization into primes that is unique up to changing the order of finite prime factors (Sierpiński 1958).

A prime ordinal is an ordinal greater than 1 that cannot be written as a product of two smaller ordinals. Some of the first primes are 2, 3, 5, ... , ω, ω+1, ω2+1, ω3+1, ..., ωω, ωω+1, ωω+1+1, ... There are three sorts of prime ordinals:

Factorization into primes is not unique: for example, 2×3=3×2, 2×ω=ω, (ω+1)×ω=ω×ω and ω×ωω = ωω. 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:

where each ni should be replaced by its factorization into a non-increasing sequence of finite primes and

The operations of addition, multiplication and exponentiation are all examples of primitive recursive ordinal functions, and more general primitive recursive ordinal functions can be used to describe larger ordinals.

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) (Sierpinski 1958). These are the same as the addition and multiplication (restricted to ordinals) of John Conway's field of surreal numbers. They have the advantage that they are associative and commutative, and natural product distributes over natural sum. The cost of making these operations commutative is that they lose the continuity in the right argument, which is a property of the ordinary sum and product. The natural sum of α and β is often denoted by αβ or α#β, and the natural product by αβ or αβ.

The natural operations come up in the theory of well partial orders; given two well partial orders S and T, of types (maximum linearizations) o(S) and o(T), the type of the disjoint union is o(S)⊕o(T), while the type of the direct product is o(S)⊗o(T).[3] One may take this relation as a definition of the natural operations by choosing S and T to be ordinals α and β; so αβ is the maximum order type of a total order extending the disjoint union (as a partial order) of α and β; while αβ is the maximum order type of a total order extending the direct product (as a partial order) of α and β.[4] A useful application of this is when α and β are both subsets of some larger total order; then their union has order type at most αβ. If they are both subsets of some ordered abelian group, then their sum has order type at most αβ.

We can also define the natural sum of α and β inductively (by simultaneous induction on α and β) as the smallest ordinal greater than the natural sum of α and γ for all γ < β and of γ and β for all γ < α. There is also an inductive definition of the natural product (by mutual induction), but it is somewhat tedious to write down and we shall not do so (see the article on surreal numbers for the definition in that context, which, however, uses surreal subtraction, something that obviously cannot be defined on ordinals).

The natural sum is associative and commutative. It is always greater or equal to the usual sum, but it may be strictly greater. For example, the natural sum of ω and 1 is ω+1 (the usual sum), but this is also the natural sum of 1 and ω. The natural product is associative and commutative and distributes over the natural sum. The natural product is always greater or equal to the usual product, but it may be strictly greater. For example, the natural product of ω and 2 is ω·2 (the usual product), but this is also the natural product of 2 and ω.

Yet another way to define the natural sum and product of two ordinals α and β is to use the Cantor normal form: one can find a sequence of ordinals γ1 > … > γn and two sequences (k1, …, kn) and (j1, …, jn) of natural numbers (including zero, but satisfying ki + ji > 0 for all i) such that

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. While the full polynomial ring does have unique factorization, the subset of polynomials with non-negative coefficients does not: for example, if x is any delta number, then

has two incompatible expressions as a natural product of polynomials with non-negative coefficients that cannot be decomposed further.

There are arithmetic operations on ordinals by virtue of the one-to-one correspondence between ordinals and nimbers. Three common operations on nimbers are nimber addition, nimber multiplication, and minimum excludance (mex). Nimber addition is a generalization of the bitwise exclusive or operation on natural numbers. The mex of a set of ordinals is the smallest ordinal not present in the set.