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 but go to infinity and beyond . 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 and is the ordinal representing the variant of lexicographical order with least significant position first, on the union of the Cartesian products and . This way, every element of is smaller than every element of , comparisons within keep the order they already have, and likewise for comparisons within .
The definition of ordinal addition can also be given by transfinite recursion on . When the right addend , addition gives for any . For , the value of is the smallest ordinal strictly greater than the sum of and for all . Writing the successor and limit ordinals cases separately:
, where denotes the successor function. when is a limit ordinal.
Ordinal addition on the natural numbers is the same as standard addition. The first transfinite ordinal is , the set of all natural numbers, followed by , , etc. 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 for the second copy, looks like
This is different from because in only does not have a direct predecessor while in the two elements and do not have direct predecessors.
Properties
Ordinal addition is, in general, not commutative. For example, since the order relation for is , which can be relabeled to . In contrast is not equal to since the order relation has a largest element (namely, ) and does not ( and are equipotent, but not order-isomorphic).
Ordinal addition is still associative; one can see for example that .
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 . Furthermore, one can define left subtraction for ordinals : there is a unique such that . On the other hand, right cancellation does not work: , but Nor does right subtraction, even when : for example, there does not exist any such that .
If the ordinals less than are closed under addition and contain , then is occasionally called a -number (see Additively indecomposable ordinal). These are exactly the ordinals of the form .
Multiplication
The Cartesian product, , of two well-ordered sets and can be well-ordered by a variant of lexicographical order that puts the least significant position first. Effectively, each element of is replaced by a disjoint copy of . The order-type of the Cartesian product is the ordinal that results from multiplying the order-types of and .
The definition of ordinal multiplication can also be given by transfinite recursion on . When the right factor , multiplication gives for any . For , the value of is the smallest ordinal greater than or equal to for all . Writing the successor and limit ordinals cases separately: . , for a successor ordinal . , when is a limit ordinal.
As an example, here is the order relation for : , which has the same order type as . In contrast, looks like this:
and after relabeling, this looks just like . Thus, , 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
, and the zero-product property holds: implies or . The ordinal is a multiplicative identity, . Multiplication is associative, . Multiplication is strictly increasing and continuous in the right argument: for , implies . Multiplication is not strictly increasing in the left argument, for example, but . However, it is (non-strictly) increasing, i.e. implies .
Multiplication of ordinals is not in general commutative. Specifically, a natural number greater than never commutes with any infinite ordinal, and two infinite ordinals and commute if and only if for some nonzero natural numbers and . The relation " commutes with is an equivalence relation on the ordinals greater than , and all equivalence classes are countably infinite.
Distributivity holds, on the left: . However, the distributive law on the right is not generally true: while , which is different. There is a left cancellation law: If and , then . Right cancellation does not apply, e.g. , but . A left division with remainder property holds: for all and , if , then there are unique and such that and . Right division does not work: there is no such that .
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 -number (see ) is an ordinal greater than such that whenever . These consist of the ordinal and the ordinals of the form .
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 consider the set of all functions such that for all but finitely many elements (essentially, we consider the functions with finite support). This set is ordered lexicographically with the least significant position first: that is, we write if and only if for the value . This is a well-ordering and its order type is an ordinal number, .
The definition of ordinal exponentiation can also be given by transfinite recursion on the exponent . When the exponent , exponentiation gives for any , including . For , the value of is the smallest ordinal greater than or equal to for all . Writing the successor and limit ordinals cases separately: . , for a successor ordinal . , when is a limit ordinal.
Both definitions simplify considerably if the exponent is a finite number: is then just the product of copies of ; e.g. , and the elements of 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, can be identified with a set of finite sequences of elements of , properly ordered. The equation expresses the fact that finite sequences of zeros and ones can be identified with natural numbers, using the binary number system. The ordinal can be viewed as the order type of finite sequences of natural numbers; every element of (i.e. every ordinal smaller than ) can be uniquely written in the form , where , , ..., are natural numbers, , ..., are nonzero natural numbers, and .
The same is true in general: every element of (i.e. every ordinal smaller than ) can be uniquely written in the form where is a natural number, , ..., are ordinals smaller than with , and are nonzero ordinals smaller than . This expression corresponds to the function which sends to for and sends all other elements of to .
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 is defined to be the cardinal number of the set of all functions , while the ordinal exponentiation only contains the functions 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. ) in the former and symbols for cardinals (e.g. ) in the latter.
Properties
. If , then . . . . . There are , , and for which . For instance, . Ordinal exponentiation is strictly increasing and continuous in the right argument: If and , then . If , then . Note, for instance, that and yet . If and , then . If or this is not the case. For all and , if and then there exist unique , , and such that such that and .
Jacobsthal showed that the only solutions of with are given by , or and , or is any limit ordinal and where is an -number larger than .Ernst Jacobsthal, Vertauschbarkeit transfiniter Ordnungszahlen, Mathematische Annalen, Bd 64 (1907), 475–488. Available here
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 can be uniquely written as , where is a natural number, , , ..., are nonzero natural numbers, and are ordinal numbers. The degenerate case occurs when which requires there be no s nor s. 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 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 , then , then , then , 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 that are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and exponentiation base-: 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).
Fixed point
The ordinal (epsilon nought) is the set of ordinal values of the finite-length arithmetical expressions of Cantor normal form that are hereditarily non-trivial where non-trivial means when . It is 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).
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 and ) that , if . If one can apply the distributive law on the left and rewrite this as , and if the expression is already in Cantor normal form). E.g.
Products
To compute products, the essential facts are that when is in Cantor normal form and , then
and , if is a non-zero natural number. E.g.
Powers
If ωα ≤ β < ωα+1, then βω = ωα·ω. For example,
Variations
A variation of Cantor normal form is to set all the numbers equal to and allow the exponents to be equal. In other words, every ordinal number can be uniquely written as , where is a natural number, and are ordinal numbers.