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 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 addition can also be given by transfinite recursion on . When the right addend, ordinary 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:
\alpha+\beta=cup\delta<\beta(\alpha+\delta)
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.
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:
\alpha<\beta ⇒ \gamma+\alpha<\gamma+\beta
\alpha<\beta ⇒ \alpha+\gamma\le\beta+\gamma
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:
3+\omega=0+\omega=\omega
3 ≠ 0
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,, 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 multiplication can also be given by transfinite recursion on . When the right factor, ordinary 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:
\alpha ⋅ \beta=cup\delta<\beta(\alpha ⋅ \delta)
As an example, here is the order relation for :
00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ...,which has the same order type as . In contrast, looks like this:
00 < 10 < 01 < 11 < 02 < 12 < 03 < 13 < ...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.
, and the zero-product property holds: or . The ordinal 1 is a multiplicative identity, . Multiplication is associative, . Multiplication is strictly increasing and continuous in the right argument: (and) → . Multiplication is not strictly increasing in the left argument, for example, 1 < 2 but . However, it is (non-strictly) increasing, i.e. → .
Multiplication of ordinals is not in general commutative. Specifically, a natural number greater than 1 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 1, 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 work, e.g., but 1 and 2 are different. 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 Multiplicatively indecomposable ordinal) is an ordinal greater than 1 such that whenever . These consist of the ordinal 2 and the ordinals of the form .
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: we write if and only if there exists with and for all with . This is a well-ordering and hence gives an ordinal number.
The definition of exponentiation can also be given by transfinite recursion on the exponent . When the exponent, ordinary exponentiation 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:
\beta=cup | |
\alpha | |
0<\delta<\beta |
(\alpha\delta)
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
n1 | |
\omega |
c1+
n2 | |
\omega |
c2+ … +
nk | |
\omega |
ck
The same is true in general: every element of (i.e. every ordinal smaller than) can be uniquely written in the form
b1 | |
\alpha |
a1+
b2 | |
\alpha |
a2+ … +
bk | |
\alpha |
ak
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.
\aleph0
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 .[1]
There are ordinal operations that continue the sequence begun by addition, multiplication, and exponentiation, including ordinal versions of tetration, pentation, and hexation. See also Veblen function.
Every ordinal number can be uniquely written as
\beta1 | |
\omega |
c1+
\beta2 | |
\omega |
c2+ … +
\betak | |
\omega |
ck
c1,c2,\ldots,ck
\beta1>\beta2>\ldots>\betak\geq0
\beta1
\alpha
\beta1\le\alpha
\beta1=\alpha
\alpha=\omega\alpha
A minor variation of Cantor normal form, which is usually slightly easier to work with, is to set all the numbers equal to 1 and allow the exponents to be equal. In other words, every ordinal number α can be uniquely written as
\beta1 | |
\omega |
+
\beta2 | |
\omega |
+ … +
\betak | |
\omega |
\beta1\ge\beta2\ge\ldots\ge\betak\ge0
Another variation of the Cantor normal form is the "base expansion", where is replaced by any ordinal, and the numbers are nonzero ordinals less than .
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-
\omega
\beta1<\alpha
\betai
\betai
| |||||||
\omega |
\omega\omega | |
⋅ 3+\omega |
⋅ 5+65537
denotes an ordinal).
The ordinal ε0 (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 β1<α when 0<α. It is the smallest ordinal that does not have a finite arithmetical expression in terms of, and the smallest ordinal such that
\varepsilon0=
\varepsilon0 | |
\omega |
0,1=\omega0,\omega=\omega1,\omega\omega,
\omega\omega | |
\omega |
,\ldots.
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 and) that
\omega\betac+\omega\beta'c'=\omega\beta'c',
if
\beta'>\beta
\beta'=\beta
\omega\beta(c+c')
\beta'<\beta
0<\alpha=
\beta1 | |
\omega |
c1+ … +
\betak | |
\omega |
ck
0<\beta'
\alpha\omega\beta'=
\beta1+\beta' | |
\omega |
and
\alphan=
\beta1 | |
\omega |
c1n+
\beta2 | |
\omega |
c2+ … +
\betak | |
\omega |
ck,
if is a non-zero natural number.
To compare two ordinals written in Cantor normal form, first compare
\beta1
c1
\beta2
c2
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 .
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, ...,,,,, ...,,,, ... There are three sorts of prime ordinals:
Factorization into primes is not unique: for example,,, 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:
So the factorization of the Cantor normal form ordinal
(with)into a minimal product of infinite primes and natural numbers is
where each should be replaced by its factorization into a non-increasing sequence of finite primes and
with .
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))))). 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 ε0, but cannot express ε0. There are other ordinal notations capable of capturing ordinals well past ε0, but because there are only countably many finite-length strings over any finite alphabet, for any given ordinal notation there will be ordinals below (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.
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) . The natural sum of and is often denoted by or, and the natural product by or .
The natural sum and product are defined as follows. Let
\alpha1 | |
\alpha=\omega |
+ … +
\alphak | |
\omega |
\beta1 | |
\beta=\omega |
+ … +
\beta\ell | |
\omega |
\alpha1\ge … \ge\alphak
\beta1\ge … \ge\beta\ell
\gamma1,\ldots,\gammak+\ell
\alpha1,\ldots,\alphak,\beta1,\ldots,\beta\ell
\alpha ⊕ \beta
\alpha
\beta
\omega\omega | |
\alpha=\omega |
+\omega
\beta=\omega\omega+\omega5
\alpha ⊕ \beta=
\omega\omega | |
\omega |
+\omega\omega+\omega5+\omega
\omega\omega | |
\alpha+\beta=\omega |
+\omega\omega+\omega5
\omega\omega+\omega | |
\alpha ⊗ \beta=\omega |
\omega\omega+5 | |
+\omega |
+\omega\omega+1+\omega6
\omega\omega+\omega | |
\alpha\beta=\omega |
\omega\omega+5 | |
+\omega |
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
\alpha<\beta
\alpha ⊕ \gamma<\beta ⊕ \gamma
\alpha\le\beta
\alpha ⊗ \gamma\le\beta ⊗ \gamma
\alpha<\beta
\gamma>0
\alpha ⊗ \gamma<\beta ⊗ \gamma
We have
\underbrace{\alpha ⊕ … ⊕ \alpha}n=\alpha ⊗ n
We always have
\alpha+\beta\le\alpha ⊕ \beta
\alpha\beta\le\alpha ⊗ \beta
\alpha<\omega\gamma
\beta<\omega\gamma
\alpha ⊕ \beta<\omega\gamma
\omega\gamma | |
\alpha<\omega |
\omega\gamma | |
\beta<\omega |
\omega\gamma | |
\alpha ⊗ \beta<\omega |
Natural sum and product are not continuous in the right argument, since, for example
\limn<\omega\alpha ⊕ n=\alpha+\omega
\alpha ⊕ \omega
\limn<\omega\alpha ⊗ n=\alpha\omega
\alpha ⊗ \omega
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
S
T
o(S)
o(T)
o(S) ⊕ o(T)
o(S) ⊗ o(T)
We can also define the natural sum by simultaneous transfinite recursion on and, as the smallest ordinal strictly greater than the natural sum of and for all and of and for all . Similarly, we can define the natural product by simultaneous transfinite recursion on and, as the smallest ordinal that is both greater than or equal to for all and greater than or equal to for all . 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 and 1 is (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 (the usual product), but this is also the natural product of 2 and .
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 is any delta number, then
has two incompatible expressions as a natural product of polynomials with non-negative coefficients that cannot be decomposed further.
See main article: Nimber. 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 of a set of ordinals is the smallest ordinal not present in the set.