Ordinal arithmetic
Encyclopedia
In the mathematical field of set theory
, ordinal arithmetic describes the three usual operations on ordinal number
s: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set
which represents the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. The so-called "natural" arithmetical operations retain commutativity at the expense of continuity
.
T in which every element of S is smaller than every element of T. The sets S and T themselves keep the ordering they already have. This addition is associative and generalizes the addition of natural numbers.
The first transfinite ordinal is ω, the set of all natural numbers.
Let's try to visualize the ordinal ω + ω: two copies
of the natural numbers ordered in the normal fashion and the second copy completely to the right of the first. If we write the second copy as {0' < 1' < 2', ...} then ω + ω 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.
Here are 3 + ω and ω + 3:
After relabeling, the former just looks like ω itself while the latter does not: we have 3 + ω = ω. But is not equal to ω since has a largest element (namely, 2') and ω does not. So our addition is not commutative.
One can see for example that (ω + 4) + ω = ω + (4 + ω) = ω + ω.
The definition of addition can also be given inductively (the following induction is on β):
Using this definition, we also see that ω + 3 is a successor ordinal
(it is the successor of ω + 2) whereas 3 + ω is the limit of 3 + 0 = 3, 3 + 1 = 4, 3 + 2 = 5, etc., which is just ω.
Zero is an additive identity α + 0 = 0 + α = α.
Addition is associative (α + β) + γ = α + (β + γ).
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 β = γ. Furthemore, 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 γ + 42 = ω.
, S×T, of two well-ordered sets S and T can be well-ordered by a variant of lexicographical order
which 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 which results from multiplying the order-types of S and T. Again, this operation is associative and generalizes the multiplication of natural numbers.
Here is ω·2:
and we see: ω·2 = ω + ω. But 2·ω looks like this:
and after relabeling, this looks just like ω and so we get 2·ω = ω ≠ ω·2.
Hence multiplication of ordinals is not commutative.
Distributivity
partially holds for ordinal arithmetic: R(S + T) = RS + RT. However, the other distributive law (T + U)R = TR + UR is not generally true: (1 + 1) ·ω = 2·ω = ω while 1·ω + 1·ω = ω + ω which is different. Therefore, the ordinal numbers do not form a ring.
The definition of multiplication can also be given inductively (the following induction is on β):
The main properties of the product are:
of well ordered sets is defined as follows. If the exponent is a finite set, the power is the product of iterated multiplication. For instance, ω2 = ω·ω using the operation of ordinal multiplication.
To generalize this to the case when the exponent is an infinite ordinal requires a different viewpoint. Note that ω·ω can be visualized as the set of functions from 2 = {0,1} to ω = {0,1,2,...}, ordered lexicographically
with the least significant position first: < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...
Here for brevity, we have replaced the function {(0,k), (1,m)} by the ordered pair
(k, m).
Similarly, for any finite exponent n,
can be visualized as the set of functions from n (the domain) to the natural numbers (the range). These functions can be abbreviated as n-tuples
of natural numbers.
For
, we might try to visualize the set of infinite sequences of natural numbers. However, if we try to use any absolutely
defined ordering on this set, we find it is not well-ordered. Using the variant lexicographical ordering again, we restrict the set of sequences to those for which only a finite number of elements of the sequence are different from zero. This is naturally motivated as the limit of the finite powers of the base (similar to the concept of coproduct
in algebra). This can also be thought of as the infinite union
.
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:
< (1,0,0,0,...) < (2,0,0,0,...) < ... < < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... < < (1,2,0,0,0,...) < (2,2,0,0,0,...)
In general, any well ordered set B can be raised to the power of another well ordered set E, resulting in another well ordered set, the power BE. Each element of BE is a function from E to B such that only a finite number of elements of the domain E map to an element larger than the least element of the range B (essentially, we consider the functions with finite support
). The order is lexicographic with the least significant position first.
The order type of the power BE is the ordinal which results from applying ordinal exponentiation to the order type of the base B and the order type of the exponent E.
The definition of exponentiation can also be given inductively (the following induction is on β, the exponent):
Properties of ordinal exponentiation:
Warning: Ordinal exponentiation is quite different from cardinal exponentiation. For example, the ordinal exponentiation 2ω = ω, but the cardinal exponentiation
is the cardinality of the continuum
which is larger than
. 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.
, where k is a natural number, 
are positive integers, and 
are ordinal numbers (we allow 
). 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 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
, where k is a natural number, and 
are ordinal numbers.
The Cantor normal form allows us to uniquely express—and order—the ordinals α which are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and “raising ω to the power of”: 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).
The ordinal ε0 (epsilon nought
) is the set of ordinal values of the finite arithmetical expressions of this form. It is the smallest ordinal that does not have a finite arithmetical expression, and 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 ε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 that
if
(if 
one can obviously rewrite this as 
, and if 
the expression is already in Cantor normal form); and to compute products, the essential facts are that when 
is in Cantor normal form (and α>0) then
and
if n is a non-zero natural number.
To compare two ordinals written in Cantor normal form, first compare
, then 
, then 
, then 
, etc.. At the first difference, the ordinal which has the larger component is the larger ordinal. If they are the same until one terminates before the other, then the one which terminates first is smaller.
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). (Jacobsthal defined a natural power operation in 1907, which is very rarely used.) They are also sometimes called the Conway
operations, as they are just the addition and multiplication (restricted to ordinals) of 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 sometimes denoted by α # β, and the natural product by a sort of doubled × sign: α ⨳ β.
To define the natural sum of two ordinals, consider once again the disjoint union
of two well-ordered sets having these order types. Start by putting a partial order on this disjoint union by taking the orders on S and T separately but imposing no relation between S and T. Now consider the order types of all well-orders on 
which extend this partial order: the least upper bound of all these ordinals (which is, actually, not merely a least upper bound but actually a greatest element) is the natural sum. Alternatively, we can 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 γ < α.
The natural sum is associative and commutative: it is always greater or equal to the usual sum, but it may be greater. For example, the natural sum of ω and 1 is ω+1 (the usual sum), but this is also the natural sum of 1 and ω.
To define the natural product of two ordinals, consider once again the cartesian product S × T of two well-ordered sets having these order types. Start by putting a partial order on this cartesian product by using just the product order (compare two pairs if and only if each of the two coordinates is comparable). Now consider the order types of all well-orders on S × T which extend this partial order: the least upper bound of all these ordinals (which is, actually, not merely a least upper bound but actually a greatest element) is the natural product. There is also an inductive definition of the natural product (by mutual induction), but it is somewhat tedious to write down and we will not do so (see the article on surreal numbers for the definition in that context, which, however, uses Conway subtraction, something which obviously cannot be defined on ordinals).
The natural product is associative and commutative and distributes over the natural sum: it is always greater or equal to the usual product, but it may be 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
and defines
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, ordinal arithmetic describes the three usual operations on ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
s: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
which represents the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. The so-called "natural" arithmetical operations retain commutativity at the expense of continuity
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
.
Addition
The union of two disjoint well-ordered sets S and T can be well-ordered. The order-type of that union is the ordinal which results from adding the order-types of S and T. If two well-ordered sets are not already disjoint, then they can be replaced by order-isomorphic disjoint sets, e.g. replace S by S × {0} and T by T × {1}. Thus the well-ordered set S is written "to the left" of the well-ordered set T, meaning one defines an order on S T in which every element of S is smaller than every element of T. The sets S and T themselves keep the ordering they already have. This addition is associative and generalizes the addition of natural numbers.The first transfinite ordinal is ω, the set of all natural numbers.
Let's try to visualize the ordinal ω + ω: two copies
of the natural numbers ordered in the normal fashion and the second copy completely to the right of the first. If we write the second copy as {0' < 1' < 2', ...} then ω + ω looks like
- 0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...
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.
Here are 3 + ω and ω + 3:
- 0 < 1 < 2 < 0' < 1' < 2' < ...
- 0 < 1 < 2 < ... < 0' < 1' < 2'
After relabeling, the former just looks like ω itself while the latter does not: we have 3 + ω = ω. But is not equal to ω since has a largest element (namely, 2') and ω does not. So our addition is not commutative.
One can see for example that (ω + 4) + ω = ω + (4 + ω) = ω + ω.
The definition of addition can also be given inductively (the following induction is on β):
- α + 0 = α,
- α + (β + 1) = (α + β) + 1 (here, "+ 1" denotes the successor of an ordinal),
- and if δ is a limit ordinal then α + δ is the limit of the α + β for all β < δ.
Using this definition, we also see that ω + 3 is a successor ordinal
Successor ordinal
In set theory, the successor of an ordinal number α is the smallest ordinal number greater than α. An ordinal number that is a successor is called a successor ordinal...
(it is the successor of ω + 2) whereas 3 + ω is the limit of 3 + 0 = 3, 3 + 1 = 4, 3 + 2 = 5, etc., which is just ω.
Zero is an additive identity α + 0 = 0 + α = α.
Addition is associative (α + β) + γ = α + (β + γ).
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 β = γ. Furthemore, 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 γ + 42 = ω.
Multiplication
The Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
, S×T, of two well-ordered sets S and T can be well-ordered by a variant of lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
which 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 which results from multiplying the order-types of S and T. Again, this operation is associative and generalizes the multiplication of natural numbers.
Here is ω·2:
- 00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ...
and we see: ω·2 = ω + ω. But 2·ω looks like this:
- 00 < 10 < 01 < 11 < 02 < 12 < 03 < 13 < ...
and after relabeling, this looks just like ω and so we get 2·ω = ω ≠ ω·2.
Hence multiplication of ordinals is not commutative.
Distributivity
Distributivity
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
partially holds for ordinal arithmetic: R(S + T) = RS + RT. However, the other distributive law (T + U)R = TR + UR is not generally true: (1 + 1) ·ω = 2·ω = ω while 1·ω + 1·ω = ω + ω which is different. Therefore, the ordinal numbers do not form a ring.
The definition of multiplication can also be given inductively (the following induction is on β):
- α·0 = 0,
- α·(β + 1) = (α·β) + α,
- and if δ is limit then α·δ is the limit of the α·β for all β < δ.
The main properties of the product are:
- α·0 = 0·α = 0.
- One is a multiplicative identity α·1 = 1·α = α.
- Multiplication is associative (α·β)·γ = α·(β·γ).
- Multiplication is strictly increasing and continuous in the right argument: (α < β and γ > 0)
γ·α < γ·β
- In the left argument, do not have the same as in the right argument. For example, 1 < 2 but 1·ω = 2·ω = ω. Instead one gets α ≤ β
α·γ ≤ β·γ.
- There is a left cancellation law: If α > 0 and α·β = α·γ, then β = γ.
- Right cancellation does not work e.g. 1·ω = 2·ω = ω but 1 and 2 are different
- α·β = 0
α = 0 or β = 0.
- Distributive law on the left: α·(β + γ) = α·β + α·γ
- No distributive law on the right: e.g. (ω + 1)·2 = ω + 1 + ω + 1 = ω + ω + 1 = ω·2 + 1 which is not ω·2 + 2.
- Left division with remainderRemainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
: for all α and β, if β > 0, then there are unique γ and δ such that α = β·γ + δ and δ < β. (This does not however mean the ordinals are a Euclidean domainEuclidean domainIn mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
, since they are not even a ring, and the Euclidean "norm" is ordinal-valued.)
- Right division does not work: there is no α such that α·ω ≤ ωω ≤ (α + 1)·ω.
Exponentiation
ExponentiationExponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
of well ordered sets is defined as follows. If the exponent is a finite set, the power is the product of iterated multiplication. For instance, ω2 = ω·ω using the operation of ordinal multiplication.
To generalize this to the case when the exponent is an infinite ordinal requires a different viewpoint. Note that ω·ω can be visualized as the set of functions from 2 = {0,1} to ω = {0,1,2,...}, ordered lexicographically
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
with the least significant position first: < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...
Here for brevity, we have replaced the function {(0,k), (1,m)} by the ordered pair
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
(k, m).
Similarly, for any finite exponent n,
can be visualized as the set of functions from n (the domain) to the natural numbers (the range). These functions can be abbreviated as n-tuplesTuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
of natural numbers.
For
, we might try to visualize the set of infinite sequences of natural numbers. However, if we try to use any absolutelyAbsoluteness (mathematical logic)
In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures . Theorems about absoluteness typically establish relationships between the absoluteness of formulas and their syntactic form.There are two weaker forms of partial absoluteness...
defined ordering on this set, we find it is not well-ordered. Using the variant lexicographical ordering again, we restrict the set of sequences to those for which only a finite number of elements of the sequence are different from zero. This is naturally motivated as the limit of the finite powers of the base (similar to the concept of coproduct
Coproduct
In category theory, the coproduct, or categorical sum, is the category-theoretic construction which includes the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coproduct of a family of objects is essentially the...
in algebra). This can also be thought of as the infinite union
.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:
< (1,0,0,0,...) < (2,0,0,0,...) < ... < < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... < < (1,2,0,0,0,...) < (2,2,0,0,0,...)
-
- < ... < < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,...)
- < ...
In general, any well ordered set B can be raised to the power of another well ordered set E, resulting in another well ordered set, the power BE. Each element of BE is a function from E to B such that only a finite number of elements of the domain E map to an element larger than the least element of the range B (essentially, we consider the functions with finite support
Support (mathematics)
In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set . This concept is used very widely in mathematical analysis...
). The order is lexicographic with the least significant position first.
- We find
, 
, 
.
The order type of the power BE is the ordinal which results from applying ordinal exponentiation to the order type of the base B and the order type of the exponent E.
The definition of exponentiation can also be given inductively (the following induction is on β, the exponent):
- α0 = 1,
- αβ+1 = (αβ)·α, and
- if δ is limit, then αδ is the limit of the αβ for all β < δ.
Properties of ordinal exponentiation:
- α0 = 1.
- If 0 < α, then 0α = 0.
- 1α = 1.
- α1 = α.
- αβ·αγ = αβ + γ.
- (αβ)γ = αβ·γ.
- There are α, β, and γ for which (α·β)γ ≠ αγ·βγ. For instance, (ω·2)2 = ω2·2 ≠ ω2·4.
- Ordinal exponentiation is strictly increasing and continuous in the right argument: If γ > 1 and α < β, then γα < γβ.
- If α < β, then αγ ≤ βγ. Note, for instance, that 2 < 3 and yet 2ω = 3ω = ω.
- If α > 1 and αβ = αγ, then β = γ. If α = 1 or α = 0 this is not the case.
- For all α and β, if β > 1 and α > 0 then there exist unique γ, δ, and ρ such that α = βγ·δ + ρ such that 0 < δ < β and ρ < βγ.
Warning: Ordinal exponentiation is quite different from cardinal exponentiation. For example, the ordinal exponentiation 2ω = ω, but the cardinal exponentiation
is the cardinality of the continuumCardinality of the continuum
In set theory, the cardinality of the continuum is the cardinality or “size” of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by |\mathbb R| or \mathfrak c ....
which is larger than
. 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.Cantor normal form
Ordinal numbers present a rich arithmetic. Every ordinal number α can be uniquely written as, where k is a natural number, are positive integers, and are ordinal numbers (we allow ). 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 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
, where k is a natural number, and are ordinal numbers.The Cantor normal form allows us to uniquely express—and order—the ordinals α which are built from the natural numbers by a finite number of arithmetical operations of addition, multiplication and “raising ω to the power of”: 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).
The ordinal ε0 (epsilon nought
Epsilon nought
In mathematics, the epsilon numbers are a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map. Consequently, they are not reachable from 0 via a finite series of applications of the chosen exponential map and of "weaker" operations like...
) is the set of ordinal values of the finite arithmetical expressions of this form. It is the smallest ordinal that does not have a finite arithmetical expression, and 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 sequenceThe ordinal ε0 is important for various reasons in arithmetic (essentially because it measures the proof-theoretic strength of the first-order
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
Peano arithmetic
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
: 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 that
if
(if one can obviously rewrite this as , and if the expression is already in Cantor normal form); and to compute products, the essential facts are that when is in Cantor normal form (and α>0) thenand
if n is a non-zero natural number.
To compare two ordinals written in Cantor normal form, first compare
, then , then , then , etc.. At the first difference, the ordinal which has the larger component is the larger ordinal. If they are the same until one terminates before the other, then the one which terminates first is smaller.Natural operations
The natural sum and natural product operations on ordinals were defined in 1906 by Gerhard Hessenberg
Gerhard Hessenberg
Gerhard Hessenberg was a German mathematician. He received his Ph.D from the University of Berlin in 1899 under the guidance of Hermann Schwarz and Lazarus Fuchs...
, and are sometimes called the Hessenberg sum (or product). (Jacobsthal defined a natural power operation in 1907, which is very rarely used.) They are also sometimes called the Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
operations, as they are just the addition and multiplication (restricted to ordinals) of Conway's field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
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 sometimes denoted by α # β, and the natural product by a sort of doubled × sign: α ⨳ β.
To define the natural sum of two ordinals, consider once again the disjoint union
of two well-ordered sets having these order types. Start by putting a partial order on this disjoint union by taking the orders on S and T separately but imposing no relation between S and T. Now consider the order types of all well-orders on which extend this partial order: the least upper bound of all these ordinals (which is, actually, not merely a least upper bound but actually a greatest element) is the natural sum. Alternatively, we can 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 γ < α.The natural sum is associative and commutative: it is always greater or equal to the usual sum, but it may be greater. For example, the natural sum of ω and 1 is ω+1 (the usual sum), but this is also the natural sum of 1 and ω.
To define the natural product of two ordinals, consider once again the cartesian product S × T of two well-ordered sets having these order types. Start by putting a partial order on this cartesian product by using just the product order (compare two pairs if and only if each of the two coordinates is comparable). Now consider the order types of all well-orders on S × T which extend this partial order: the least upper bound of all these ordinals (which is, actually, not merely a least upper bound but actually a greatest element) is the natural product. There is also an inductive definition of the natural product (by mutual induction), but it is somewhat tedious to write down and we will not do so (see the article on surreal numbers for the definition in that context, which, however, uses Conway subtraction, something which obviously cannot be defined on ordinals).
The natural product is associative and commutative and distributes over the natural sum: it is always greater or equal to the usual product, but it may be 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
and defines
External links
- Ordinal calculator for download (MS-DOS executable or Borland C++ source)