Ordinal arithmetic

Template:Short description Template:Too technical In the mathematical field of set theory, ordinal arithmetic includes binary operations on ordinal numbers such as addition, multiplication, and exponentiation. Each can be defined in two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. In addition to these standard operations for ordinals, there are also the "natural" arithmetic operations, which are usually described using the Cantor normal form for ordinals, and nimber operations.

Background

Ordinal numbers are like the counting numbers Template:Math but go to infinity Template:Mvar and beyond Template:Math. The standard arithmetic operations and natural arithmetic operations on the finite ordinals are the same as the corresponding operations on the counting numbers, but arithmetic operations on the infinite ordinals are more complicated.

Addition

The sum of two well-ordered sets Template:Mvar and Template:Mvar is the ordinal representing the variant of lexicographical order with least significant position first, on the union of the Cartesian products Template:Math and Template:Math. This way, every element of Template:Mvar is smaller than every element of Template:Mvar, comparisons within Template:Mvar keep the order they already have, and likewise for comparisons within Template:Mvar.

The definition of ordinal addition Template:Math can also be given by transfinite recursion on Template:Mvar. When the right addend Template:Math, addition gives Template:Math for any Template:Mvar. For Template:Math, the value of Template:Math is the smallest ordinal strictly greater than the sum of Template:Mvar and Template:Mvar for all Template:Math. Writing the successor and limit ordinals cases separately:

• Template:Math
• Template:Math, where Template:Mvar denotes the successor function.
• Template:Math when Template:Mvar is a limit ordinal.

Ordinal addition on the natural numbers is the same as standard addition. The first transfinite ordinal is Template:Mvar, the set of all natural numbers, followed by Template:Math, Template:Math, etc. The ordinal Template:Math 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 Template:Math for the second copy, Template:Math looks like

Template:Math

This is different from Template:Mvar because in Template:Mvar only Template:Math does not have a direct predecessor while in Template:Math the two elements Template:Math and Template:Math do not have direct predecessors.

Properties

Ordinal addition is, in general, not commutative. For example, Template:Math since the order relation for Template:Math is Template:Math, which can be relabeled to Template:Mvar. In contrast Template:Math is not equal to Template:Mvar since the order relation Template:Math has a largest element (namely, Template:Math) and Template:Mvar does not (Template:Mvar and Template:Math are equipotent, but not order-isomorphic).

Ordinal addition is still associative; one can see for example that Template:Math.

Addition is strictly increasing and continuous in the right argument:

Template:Math

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

Template:Math

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

Template:Math, but Template:Math

Nor does right subtraction, even when Template:Math: for example, there does not exist any Template:Mvar such that Template:Math.

If the ordinals less than Template:Mvar are closed under addition and contain Template:Math, then Template:Mvar is occasionally called a Template:Mvar-number (see Additively indecomposable ordinal). These are exactly the ordinals of the form Template:Math.

Multiplication

The disjoint union Template:Math, using lexicographic order with least significant position first, has order type Template:Math. This is different from Template:Mvar.

The set Template:Math, under lexicographic order with least significant position first, has order type Template:Math, which is equal to Template:Mvar.

The Cartesian product, Template:Math, of two well-ordered sets Template:Mvar and Template:Mvar can be well-ordered by a variant of lexicographical order that puts the least significant position first. Effectively, each element of Template:Mvar is replaced by a disjoint copy of Template:Mvar. The order-type of the Cartesian product is the ordinal that results from multiplying the order-types of Template:Mvar and Template:Mvar.

The definition of ordinal multiplication can also be given by transfinite recursion on Template:Mvar. When the right factor Template:Math, multiplication gives Template:Math for any Template:Mvar. For Template:Math, the value of Template:Math is the smallest ordinal greater than or equal to Template:Math for all Template:Math. Writing the successor and limit ordinals cases separately:

• Template:Math.
• Template:Math, for a successor ordinal Template:Math.
• Template:Math, when Template:Mvar is a limit ordinal.

As an example, here is the order relation for Template:Math:

Template:Math Template:Math,

which has the same order type as Template:Math. In contrast, Template:Math looks like this:

Template:Math

and after relabeling, this looks just like Template:Mvar. Thus, Template:Math, showing that multiplication of ordinals is not in general commutative, c.f. pictures.

As is the case with addition, ordinal multiplication on the natural numbers is the same as standard multiplication.

Properties

Template:Math, and the zero-product property holds: Template:Math implies Template:Math or Template:Math. The ordinal Template:Math is a multiplicative identity, Template:Math. Multiplication is associative, Template:Math. Multiplication is strictly increasing and continuous in the right argument: (Template:Math and Template:Math) implies Template:Math. Multiplication is not strictly increasing in the left argument, for example, Template:Math but Template:Math. However, it is (non-strictly) increasing, i.e. Template:Math implies Template:Math.

Multiplication of ordinals is not in general commutative. Specifically, a natural number greater than Template:Math never commutes with any infinite ordinal, and two infinite ordinals Template:Mvar and Template:Mvar commute if and only if Template:Math for some nonzero natural numbers Template:Mvar and Template:Mvar. The relation "Template:Mvar commutes with Template:MvarTemplate:-" is an equivalence relation on the ordinals greater than Template:Math, and all equivalence classes are countably infinite.

Distributivity holds, on the left: Template:Math. However, the distributive law on the right Template:Math is not generally true: Template:Math while Template:Math, which is different. There is a left cancellation law: If Template:Math and Template:Math, then Template:Math. Right cancellation does not apply, e.g. Template:Math, but Template:Math and Template:Math are different. A left division with remainder property holds: for all Template:Mvar and Template:Mvar, if Template:Math, then there are unique Template:Mvar and Template:Mvar such that Template:Math and Template:Math. Right division does not work: there is no Template:Mvar such that Template:Math.

The ordinal numbers form a left near-semiring, but do not form a ring. Hence the ordinals are not a Euclidean domain, since they are not even a ring; furthermore the Euclidean "norm" would be ordinal-valued using the left division here.

A Template:Mvar-number (see Template:Slink) is an ordinal Template:Mvar greater than Template:Math such that Template:Math whenever Template:Math. These consist of the ordinal Template:Math and the ordinals of the form Template:Math.

Exponentiation

The definition of exponentiation via order types is most easily explained using Von Neumann's definition of an ordinal as the set of all smaller ordinals. Then, to construct a set of order type Template:Math consider the set of all functions Template:Math such that Template:Math for all but finitely many elements Template:Math (essentially, we consider the functions with finite support). This set is ordered lexicographically with the least significant position first: that is, we write Template:Math if and only if Template:Math for the value Template:Math. This is a well-ordering and its order type is an ordinal number, Template:Math.

The definition of ordinal exponentiation can also be given by transfinite recursion on the exponent Template:Mvar. When the exponent Template:Math, exponentiation gives Template:Math for any Template:Mvar, including Template:Math. For Template:Math, the value of Template:Math is the smallest ordinal greater than or equal to Template:Math for all Template:Math. Writing the successor and limit ordinals cases separately:

• Template:Math.
• Template:Math, for a successor ordinal Template:Math.
• Template:Math, when Template:Mvar is a limit ordinal.

Both definitions simplify considerably if the exponent Template:Mvar is a finite number: Template:Math is then just the product of Template:Mvar copies of Template:Mvar; e.g. Template:Math, and the elements of Template:Math can be viewed as triples of natural numbers, ordered lexicographically with least significant position first. This agrees with the ordinary exponentiation of natural numbers.

But for infinite exponents, the definition may not be obvious. For example, Template:Math can be identified with a set of finite sequences of elements of Template:Mvar, properly ordered. The equation Template:Math expresses the fact that finite sequences of zeros and ones can be identified with natural numbers, using the binary number system. The ordinal Template:Math can be viewed as the order type of finite sequences of natural numbers; every element of Template:Math (i.e. every ordinal smaller than Template:Math) can be uniquely written in the form Template:Math, where Template:Mvar, Template:Math, ..., Template:Math are natural numbers, Template:Math, ..., Template:Math are nonzero natural numbers, and Template:Math.

The same is true in general: every element of Template:Math (i.e. every ordinal smaller than Template:Math) can be uniquely written in the form Template:Math where Template:Mvar is a natural number, Template:Math, ..., Template:Math are ordinals smaller than Template:Mvar with Template:Math, and Template:Math are nonzero ordinals smaller than Template:Mvar. This expression corresponds to the function Template:Math which sends Template:Math to Template:Math for Template:Math and sends all other elements of Template:Mvar to Template:Math.

While the same exponent notation is used for ordinal exponentiation and cardinal exponentiation, the two operations are quite different and should not be confused. The cardinal exponentiation Template:Math is defined to be the cardinal number of the set of all functions Template:Math, while the ordinal exponentiation Template:Math only contains the functions Template:Math with finite support, typically a set of much smaller cardinality. To avoid confusing ordinal exponentiation with cardinal exponentiation, one can use symbols for ordinals (e.g. Template:Mvar) in the former and symbols for cardinals (e.g. Template:Math) in the latter.

Properties

• Template:Math.
• If Template:Math, then Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• There are Template:Mvar, Template:Mvar, and Template:Mvar for which Template:Math. For instance, Template:Math.
• Ordinal exponentiation is strictly increasing and continuous in the right argument: If Template:Math and Template:Math, then Template:Math.
• If Template:Math, then Template:Math. Note, for instance, that Template:Math and yet Template:Math.
• If Template:Math and Template:Math, then Template:Math. If Template:Math or Template:Math this is not the case.
• For all Template:Mvar and Template:Mvar, if Template:Math and Template:Math then there exist unique Template:Mvar, Template:Mvar, and Template:Mvar such that Template:Math such that Template:Math and Template:Math.

Jacobsthal showed that the only solutions of Template:Math with Template:Math are given by Template:Math, or Template:Math and Template:Math, or Template:Mvar is any limit ordinal and Template:Math where Template:Mvar is an [[Epsilon numbers (mathematics)|Template:Mvar-number]] larger than Template:Mvar.

Beyond exponentiation

There are ordinal operations that continue the sequence begun by addition, multiplication, and exponentiation, including ordinal versions of tetration and other hyperoperations. See also Veblen function.

Cantor normal form

Every ordinal number Template:Math can be uniquely written as Template:Math, where Template:Mvar is a natural number, Template:Math, Template:Math, ..., Template:Math are nonzero natural numbers, and Template:Math are ordinal numbers. The degenerate case Template:Math occurs when Template:Math which requires there be no Template:Mvars nor Template:Mvars. This decomposition of Template:Mvar is called the Cantor normal form of Template:Mvar, and can be considered the base-Template:Mvar positional numeral system. The highest exponent Template:Math is called the degree of Template:Math, and satisfies Template:Math. The equality Template:Math applies if and only if Template:Math. In that case Cantor normal form fails to express the ordinal in terms of smaller ones; this can happen as explained below.

To compare two ordinals written in Cantor normal form, first compare Template:Math, then Template:Math, then Template:Math, then Template:Math, and so on. At the first occurrence of inequality, the ordinal that has the larger component is the larger ordinal. If they are the same until one terminates before the other, then the one that terminates first is smaller.

The Cantor normal form allows us to uniquely express—and order—the ordinals Template:Mvar that are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and exponentiation base-Template:Math: in other words, assuming Template:Math in the Cantor normal form, we can also express the exponents Template:Math in Cantor normal form, and making the same assumption for the Template:Math as for Template:Mvar and so on recursively, we get a system of notation for these ordinals (for example,

Template:Math

denotes an ordinal).

Fixed point

The ordinal Template:Math (epsilon nought) is the set of ordinal values Template:Math of the finite-length arithmetical expressions of Cantor normal form that are hereditarily non-trivial where non-trivial means Template:Math when Template:Math. It is the smallest ordinal such that Template:Math, i.e. in Cantor normal form the exponent is not smaller than the ordinal itself. It is the limit of the sequence

Template:Math.

The ordinal Template:Math 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 Template:Math but not up to Template:Math itself).

Sums

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 Template:Slink and Template:Slink) that

Template:Math,

if Template:Math. If Template:Math one can apply the distributive law on the left and rewrite this as Template:Math, and if Template:Math the expression is already in Cantor normal form). E.g.

$({\omega }^2\cdot 2+\omega \cdot 3+4)+(\omega \cdot 5+6)={\omega }^2\cdot 2+\omega \cdot 8+6.$

Products

To compute products, the essential facts are that when Template:Math is in Cantor normal form and Template:Math, then

Template:Math

and

Template:Math,

if Template:Mvar is a non-zero natural number. E.g.

$({\omega }^3\cdot 7+\omega +1)\cdot (\omega \cdot 8+9)={\omega }^4\cdot 8+{\omega }^3\cdot 63+\omega +1.$

Powers

If ω^α ≤ β < ω^α+1, then β^ω = ω^α·ω. For example,

$({\omega }^{\omega }\cdot 2+\omega \cdot 3+4{)}^{({\omega }^2\cdot 5+2)}=({\omega }^{{\omega }^3\cdot 5})\cdot ({\omega }^{\omega \cdot 2}\cdot 2+{\omega }^{\omega +1}\cdot 3+{\omega }^{\omega }\cdot 8+\omega \cdot 3+4)$

$={\omega }^{{\omega }^3\cdot 5+\omega \cdot 2}\cdot 2+{\omega }^{{\omega }^3\cdot 5+\omega +1}\cdot 3+{\omega }^{{\omega }^3\cdot 5+\omega }\cdot 8+{\omega }^{{\omega }^3\cdot 5+1}\cdot 3+{\omega }^{{\omega }^3\cdot 5}\cdot 4$

Variations

A variation of Cantor normal form is to set all the numbers Template:Math equal to Template:Math and allow the exponents to be equal. In other words, every ordinal number Template:Math can be uniquely written as Template:Math, where Template:Mvar is a natural number, and Template:Math are ordinal numbers.

Another variation of the Cantor normal form is the "base Template:Mvar expansion", where Template:Mvar is replaced by any ordinal Template:Math and the coefficients satisfy Template:Math.

Factorization into primes

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 Template:Harv.

A prime ordinal is an ordinal greater than Template:Math that cannot be written as a product of two smaller ordinals. Some of the first primes are Template:Math, Template:Math, Template:Math, ... , Template:Mvar, Template:Math, Template:Math, Template:Math, ..., Template:Math, Template:Math, Template:Math, ... There are three types of prime ordinals:

• The finite primes Template:Math, Template:Math, Template:Math, ...
• The ordinals of the form Template:Math for any ordinal Template:Mvar. These are the prime ordinals that are limits, and are the delta numbers, the transfinite ordinals that are closed under multiplication.
• The ordinals of the form Template:Math for any ordinal Template:Math. These are the infinite successor primes, and are the successors of gamma numbers, the additively indecomposable ordinals.

Factorization into primes is not unique: for example, Template:Math, Template:Math, Template:Math and Template:Math. However, there is a unique factorization into primes satisfying the following additional conditions:

• Every limit prime must occur before any successor prime
• If two consecutive primes of the prime factorization are both limits or both finite, the second one must be less than or equal to the first one.

This prime factorization can easily be read off using the Cantor normal form as follows:

• First write the ordinal as a product Template:Math, where Template:Mvar is the smallest power of Template:Mvar in the Cantor normal form and Template:Mvar is a successor.
• If Template:Math then writing Template:Mvar in Cantor normal form gives an expansion of Template:Mvar as a product of limit primes.
• Now look at the Cantor normal form of Template:Mvar. If Template:Math + smaller terms, then Template:Math is a product of a smaller ordinal and a prime and a natural number Template:Mvar. Repeating this and factorizing the natural numbers into primes gives the prime factorization of Template:Mvar.

So the factorization of the Cantor normal form ordinal

Template:Math (with Template:Math)

into a minimal product of infinite primes and natural numbers is

Template:Math

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

Template:Math with Template:Math.

Large countable ordinals

As discussed above, the Cantor normal form of ordinals below Template:Math 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 Template:Mvar. We can do away with the infinitely many numerals by using just the constant symbol Template:Math and the operation of successor, Template:Math (for example, the natural number Template:Math may be expressed as Template:Math. This describes an ordinal notation: a system for naming ordinals over a finite alphabet. This particular system of ordinal notation is called the collection of arithmetical ordinal expressions, and can express all ordinals below Template:Math, but cannot express Template:Math. There are other ordinal notations capable of capturing ordinals well past Template:Math, but because there are only countably many finite-length strings over any finite alphabet, for any given ordinal notation there will be ordinals below Template:Math (the first uncountable ordinal) that are not expressible. Such ordinals are known as large countable ordinals.

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.

Natural operations

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) Template:Harv. The natural sum of Template:Mvar and Template:Mvar is often denoted by Template:Math or Template:Math, and the natural product by Template:Math or Template:Math.

The natural sum and product are defined as follows. Let Template:Math and Template:Math be in Cantor normal form (i.e. Template:Math and Template:Math). Let Template:Math be the exponents Template:Math, ..., Template:Math, Template:Math, ..., Template:Math sorted in nonincreasing order. Then Template:Math is defined as

Template:Math.

The natural product of Template:Math and Template:Math is defined as

Template:Math.

For example, suppose Template:Math and Template:Math. Then Template:Math, whereas Template:Math. And Template:Math, whereas Template:Math.

The natural sum and product are commutative and associative, and natural product distributes over natural sum. The operations are also monotonic, in the sense that if Template:Math then Template:Math; if Template:Math then Template:Math; and if Template:Math and Template:Math then Template:Math.

We have $\underset{n}{\underbrace{\alpha \oplus \cdots \oplus \alpha }}=\alpha \otimes n$.

We always have Template:Math and Template:Math. If both Template:Math and Template:Math then Template:Math. If both Template:Math and Template:Math then Template:Math.

Natural sum and product are not continuous. For example, if natural sum were continuous then Template:Math, but the left-hand side equals Template:Mvar and the right-hand side equals Template:Math. Similarly, if natural product were continuous Template:Math, but the left-hand side equals Template:Mvar and the right-hand side equals Template:Math.

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

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

We can also define the natural sum Template:Math by simultaneous transfinite recursion on Template:Mvar and Template:Mvar, as the smallest ordinal strictly greater than the natural sum of Template:Mvar and Template:Mvar for all Template:Math and of Template:Mvar and Template:Mvar for all Template:Math. Similarly, we can define the natural product Template:Math by simultaneous transfinite recursion on Template:Mvar and Template:Mvar, as the smallest ordinal Template:Mvar such that Template:Math for all Template:Math and Template:Math. Also, see the article on surreal numbers for the definition of natural multiplication in that context; however, it uses surreal subtraction, which is not 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 Template:Mvar and Template:Math is Template:Math (the usual sum), but this is also the natural sum of Template:Math and Template:Mvar. 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 Template:Mvar and Template:Math is Template:Math (the usual product), but this is also the natural product of Template:Math and Template:Mvar.

Under natural addition, the ordinals can be identified with the elements of the free commutative monoid generated by the gamma numbers Template:Math. Under natural addition and multiplication, the ordinals can be identified with the elements of the free commutative semiring generated by the delta numbers Template:Math. 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 Template:Mvar is any delta number, then

Template:Math

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

Nimber arithmetic

Template:Main 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 excluded value (mex). Nimber addition is a generalization of the bitwise exclusive or operation on natural numbers. The Template:Math of a set of ordinals is the smallest ordinal not present in the set.

References

• Template:Cite book
• Template:Citation
• Template:Citation

External links

• Template:Webarchive