Ordinal arithmetic

In themathematicalfield ofset theory,ordinal arithmeticdescribes the three usual operations onordinal numbers:addition,multiplication,andexponentiation.Each can be defined in essentially two different ways: either by constructing an explicitwell-ordered setthat represents the result of the operation or by usingtransfinite 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 ordinalsand thenimber operations.

Addition

The sum of two well-ordered setsSandTis the ordinal representing the variant oflexicographical orderwith least significant position first, on the union of theCartesian productsS× {0}andT× {1}.This way, every element ofSis smaller than every element ofT,comparisons withinSkeep the order they already have, and likewise for comparisons withinT.

The definition of additionα+βcan also be given bytransfinite recursiononβ.When the right addendβ= 0,ordinary addition givesα+ 0 =αfor anyα.Forβ> 0,the value ofα+βis the smallest ordinal strictly greater than the sum ofαandδfor allδ<β.Writing the successor and limit ordinals cases separately:

• α+ 0 =α
• α+S(β) =S(α+β),whereSdenotes thesuccessorfunction.
• $\alpha +\beta =\bigcup _{\delta <\beta }(\alpha +\delta )$whenβis alimit ordinal.

Ordinal addition on thenatural numbersis the same as standard addition. The first transfinite ordinal isω,the set of all natural numbers, followed byω+ 1,ω+ 2,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. Writing0' < 1' < 2' <...for the second copy,ω+ωlooks like

0 < 1 < 2 < 3 <... < 0' < 1' < 2' <...

This is different fromωbecause inωonly0does not have a direct predecessor while inω+ωthe two elements0and0'do not have direct predecessors.

Properties

Ordinal addition is, in general, notcommutative.For example,3 +ω=ωsince the order relation for3 +ωis0 < 1 < 2 < 0' < 1' < 2' <...,which can be relabeled toω.In contrastω+ 3is not equal toωsince the order relation0 < 1 < 2 <... < 0' < 1' < 2'has a largest element (namely,2') andωdoes not (ωandω+ 3areequipotent,but not order isomorphic).

Ordinal addition is stillassociative;one can see for example that(ω+ 4) +ω=ω+ (4 +ω) =ω+ω.

Addition isstrictly increasingandcontinuousin the right argument:

$\alpha <\beta \Rightarrow \gamma +\alpha <\gamma +\beta$

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

$\alpha <\beta \Rightarrow \alpha +\gamma \leq \beta +\gamma$

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

$3+\omega =0+\omega =\omega$but$3\neq 0$

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 (seeadditively indecomposable ordinal). These are exactly the ordinals of the formω^β.

Multiplication

The disjoint union{ (n,0):n∈N}∪{ (n,1):n∈N},using lexicographic order with least significant position first, has order typeω• 2.This is different fromω.

The set{(0,n),(1,n):n∈N},under lexicographic order with least significant position first, has order type2 •ω,which is equal toω.

TheCartesian product,S×T,of two well-ordered setsSandTcan be well-ordered by a variant oflexicographical orderthat puts the least significant position first. Effectively, each element ofTis replaced by a disjoint copy ofS.The order-type of the Cartesian product is the ordinal that results from multiplying the order-types ofSandT.

The definition of multiplication can also be given by transfinite recursion onβ.When the right factorβ= 0,ordinary multiplication givesα· 0 = 0for anyα.Forβ> 0,the value ofα·βis the smallest ordinal greater than or equal to(α·δ) +αfor allδ<β.Writing the successor and limit ordinals cases separately:

• α· 0 = 0.
• α·S(β) = (α·β) +α,for a successor ordinalS(β).
• $\alpha \cdot \beta =\bigcup _{\delta <\beta }(\alpha \cdot \delta )$,whenβis a limit ordinal.

As an example, here is the order relation forω· 2:

0₀< 1₀< 2₀< 3₀<... < 0₁< 1₁< 2₁< 3₁<...,

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

0₀< 1₀< 0₁< 1₁< 0₂< 1₂< 0₃< 1₃<...

and after relabeling, this looks just likeω. Thus,ω· 2 =ω+ω≠ω= 2 ·ω,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

α· 0 = 0 ·α= 0,and thezero-product propertyholds:α·β= 0 →α= 0orβ= 0.The ordinal 1 is a multiplicative identity,α· 1 = 1 ·α=α.Multiplication is associative,(α·β) ·γ=α· (β·γ).Multiplication is strictly increasing and continuous in the right argument: (α<βandγ> 0) →γ·α<γ·β.Multiplication isnotstrictly increasing in the left argument, for example, 1 < 2 but1 ·ω= 2 ·ω=ω.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α^m=βⁿfor some nonzero natural numbersmandn.The relation "αcommutes withβ"is an equivalence relation on the ordinals greater than 1, and all equivalence classes are countably infinite.

Distributivityholds, on the left:α(β+γ) =αβ+αγ.However, the distributive law on the right(β+γ)α=βα+γαisnotgenerally true:(1 + 1) ·ω= 2 ·ω=ωwhile1 ·ω+ 1 ·ω=ω+ω,which is different. There is aleft cancellationlaw: Ifα> 0andα·β=α·γ,thenβ=γ.Right cancellation does not work, e.g.1 ·ω= 2 ·ω=ω,but 1 and 2 are different. Aleft divisionwithremainderproperty holds: for allαandβ,ifβ> 0,then there are uniqueγandδsuch thatα=β·γ+δandδ<β.Right division does not work: there is noαsuch thatα·ω≤ω^ω≤ (α+ 1) ·ω.

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

Aδ-number (seeMultiplicatively indecomposable ordinal) is an ordinalβgreater than 1 such thatαβ=βwhenever0 <α<β.These consist of the ordinal 2 and the ordinals of the formβ=ω^ωγ.

Exponentiation

The definition ofexponentiationvia order types is most easily explained usingVon 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 functionsf:β→αsuch thatf(x) = 0for all but finitely many elementsx∈β(essentially, we consider the functions with finitesupport). This set isordered lexicographicallywith the least significant position first: we writef<gif and only if there existsx∈βwithf(x) <g(x)andf(y) =g(y)for ally∈βwithx<y.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β= 0,ordinary exponentiation givesα⁰= 1for anyα.Forβ> 0,the value ofα^βis the smallest ordinal greater than or equal toα^δ·αfor allδ<β.Writing the successor and limit ordinals cases separately:

• α⁰= 1.
• α^S(β)= (α^β) ·α,for a successor ordinalS(β).
• $\alpha ^{\beta }=\bigcup _{0<\delta <\beta }(\alpha ^{\delta })$,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 equation2^ω=ωexpresses the fact that finite sequences of zeros and ones can be identified with natural numbers, using thebinary numbersystem. 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$\omega ^{n_{1}}c_{1}+\omega ^{n_{2}}c_{2}+\cdots +\omega ^{n_{k}}c_{k}$wherek,n₁,...,n_kare natural numbers,c₁,...,c_kare nonzero natural numbers, andn₁>... >n_k.

The same is true in general: every element ofα^β(i.e. every ordinal smaller thanα^β) can be uniquely written in the form$\alpha ^{b_{1}}a_{1}+\alpha ^{b_{2}}a_{2}+\cdots +\alpha ^{b_{k}}a_{k}$wherekis a natural number,b₁,...,b_kare ordinals smaller thanβwithb₁>... >b_k,anda₁,...,a_kare nonzero ordinals smaller thanα.This expression corresponds to the functionf:β→αwhich sendsb_itoa_ifori= 1,...,kand sends all other elements ofβto 0.

While the same exponent-notation is used for ordinal exponentiation andcardinal exponentiation,the two operations are quite different and should not be confused. The cardinal exponentiationA^Bis defined to be the cardinal number of the set ofallfunctionsB→A,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.$\aleph _{0}$) in the latter.

Properties

• α⁰= 1.
• If0 <α,then0^α= 0.
• 1^α= 1.
• α¹=α.
• α^β·α^γ=α^β+γ.
• (α^β)^γ=α^β·γ.
• There areα,β,andγfor which(α·β)^γ≠α^γ·β^γ.For instance,(ω· 2)²=ω·2·ω·2 =ω²· 2 ≠ω²· 4.
• Ordinal exponentiation is strictly increasing and continuous in the right argument: Ifγ> 1andα<β,thenγ^α<γ^β.
• Ifα<β,thenα^γ≤β^γ.Note, for instance, that 2 < 3 and yet2^ω= 3^ω=ω.
• Ifα> 1andα^β=α^γ,thenβ=γ.Ifα= 1orα= 0this is not the case.
• For allαandβ,ifβ> 1andα> 0then there exist uniqueγ,δ,andρsuch thatα=β^γ·δ+ρsuch that0 <δ<βandρ<β^γ.

Jacobsthalshowed that the only solutions ofα^β=β^αwithα≤βare given byα=β,orα= 2andβ= 4,orαis any limit ordinal andβ=εαwhereεis anε-numberlarger thanα.

Beyond exponentiation

There are ordinal operations that continue the sequence begun by addition, multiplication, and exponentiation, including ordinal versions oftetration,pentation,andhexation.See alsoVeblen function.

Cantor normal form

Every ordinal numberαcan be uniquely written as$\omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}$,wherekis a natural number,$c_{1},c_{2},\ldots,c_{k}$are nonzero natural numbers, and$\beta _{1}>\beta _{2}>\ldots >\beta _{k}\geq 0$are ordinal numbers. The degenerate caseα= 0occurs whenk= 0and there are noβs norcs. This decomposition ofαis called theCantor normal formofα,and can be considered the base-ωpositional numeral system.The highest exponent$\beta _{1}$is called the degree of$\alpha$,and satisfies$\beta _{1}\leq \alpha$.The equality$\beta _{1}=\alpha$applies if and only if$\alpha =\omega ^{\alpha }$.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 numbersc_iequal to 1 and allow the exponents to be equal. In other words, every ordinal number α can be uniquely written as$\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k}}$,wherekis a natural number, and$\beta _{1}\geq \beta _{2}\geq \ldots \geq \beta _{k}\geq 0$are ordinal numbers.

Another variation of the Cantor normal form is the "baseδexpansion ", whereωis replaced by any ordinalδ> 1,and the numbersc_iare 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$:in other words, assuming$\beta _{1}<\alpha$in the Cantor normal form, we can also express the exponents$\beta _{i}$in Cantor normal form, and making the same assumption for the$\beta _{i}$as forαand so on recursively, we get a system of notation for these ordinals (for example,

$\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+65537$

denotes an ordinal).

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 0<α.It is the smallest ordinal that does not have a finite arithmetical expression in terms ofω,and the smallest ordinal such that$\varepsilon _{0}=\omega ^{\varepsilon _{0}}$,i.e. in Cantor normal form the exponent is not smaller than the ordinal itself. It is the limit of the sequence

$0,\,1=\omega ^{0},\,\omega =\omega ^{1},\,\omega ^{\omega },\,\omega ^{\omega ^{\omega }},\,\ldots \,.$

The ordinal ε₀is important for various reasons in arithmetic (essentially because it measures theproof-theoretic strengthof thefirst-orderPeano arithmetic:that is, Peano's axioms can show transfinite induction up to any ordinal less than ε₀but not up to ε₀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§ Additionand§ Multiplication) that

$\omega ^{\beta }c+\omega ^{\beta '}c'=\omega ^{\beta '}c'\,,$

if$\beta '>\beta$(if$\beta '=\beta$one can apply the distributive law on the left and rewrite this as$\omega ^{\beta }(c+c')$,and if$\beta '<\beta$the expression is already in Cantor normal form); and to compute products, the essential facts are that when$0<\alpha =\omega ^{\beta _{1}}c_{1}+\cdots +\omega ^{\beta _{k}}c_{k}$is in Cantor normal form and$0<\beta '$,then

$\alpha \omega ^{\beta '}=\omega ^{\beta _{1}+\beta '}\,$

and

$\alpha n=\omega ^{\beta _{1}}c_{1}n+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}\,,$

ifnis a non-zero natural number.

To compare two ordinals written in Cantor normal form, first compare$\beta _{1}$,then$c_{1}$,then$\beta _{2}$,then$c_{2}$,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.

Factorization into primes

Ernst Jacobsthalshowed 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,ω²+ 1,ω³+ 1,...,ω^ω,ω^ω+ 1,ω^{ω+ 1}+ 1,... There are three sorts of prime ordinals:

• The finite primes 2, 3, 5,...
• The ordinals of the formω^ωαfor any ordinalα.These are the prime ordinals that are limits, and are thedelta numbers,the transfinite ordinals that are closed under multiplication.
• The ordinals of the formω^α+ 1for any ordinalα> 0.These are the infinite successor primes, and are the successors ofgamma numbers,the additively indecomposable 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:

• 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αβwhereαis the smallest power ofωin the Cantor normal form andβis a successor.
• Ifα=ω^γthen writingγin Cantor normal form gives an expansion ofαas a product of limit primes.
• Now look at the Cantor normal form ofβ.Ifβ=ω^λm+ω^μn+ smaller terms, thenβ= (ω^μn+ smaller terms)(ω^λ−μ+ 1)mis a product of a smaller ordinal and a prime and a natural numberm.Repeating this and factorizing the natural numbers into primes gives the prime factorization ofβ.

So the factorization of the Cantor normal form ordinal

ω^α₁n₁+ ⋯ +ω^α_kn_k(withα₁> ⋯ >α_k)

into a minimal product of infinite primes and natural numbers is

(ω^ωβ₁⋯ω^ωβ_m)n_k(ω^{α_k−1−α_k}+ 1)n_k−1⋯ (ω^{α₁−α₂}+ 1)n₁

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

α_k=ω^β₁+ ⋯ +ω^β_mwithβ₁≥ ⋯ ≥β_m.

Large countable ordinals

As discussed above, the Cantor normal form of ordinals below ε₀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 anordinal notation:a system for naming ordinals over a finite alphabet. This particular system of ordinal notation is called the collection ofarithmeticalordinal expressions, and can express all ordinals below ε₀,but cannot express ε₀.There are other ordinal notations capable of capturing ordinals well past ε₀,but because there are only countably many finite-length strings over any finite alphabet, for any given ordinal notation there will be ordinals belowω₁(thefirst uncountable ordinal) that are not expressible. Such ordinals are known aslarge countable ordinals.

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

Natural operations

Thenatural sumandnatural productoperations on ordinals were defined in 1906 byGerhard Hessenberg,and are sometimes called theHessenberg sum(or product) (Sierpiński 1958). 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$\alpha =\omega ^{\alpha _{1}}+\cdots +\omega ^{\alpha _{k}}$and$\beta =\omega ^{\beta _{1}}+\cdots +\omega ^{\beta _{\ell }}$be in Cantor normal form (i.e.$\alpha _{1}\geq \cdots \geq \alpha _{k}$and$\beta _{1}\geq \cdots \geq \beta _{\ell }$). Let$\gamma _{1},\ldots,\gamma _{k+\ell }$be the exponents$\alpha _{1},\ldots,\alpha _{k},\beta _{1},\ldots,\beta _{\ell }$sorted in nonincreasing order. Then$\alpha \oplus \beta$is defined as$$\alpha \oplus \beta =\omega ^{\gamma _{1}}+\cdots +\omega ^{\gamma _{k+\ell }}.$$ The natural product of$\alpha$and$\beta$is defined as$$\alpha \otimes \beta =\bigoplus _{\begin{aligned}&1\leq i\leq k\\&1\leq j\leq \ell \end{aligned}}\omega ^{\alpha _{i}\oplus \beta _{j}}.$$ For example, suppose$\alpha =\omega ^{\omega ^{\omega }}+\omega$and$\beta =\omega ^{\omega }+\omega ^{5}$.Then$\alpha \oplus \beta =\omega ^{\omega ^{\omega }}+\omega ^{\omega }+\omega ^{5}+\omega$,whereas$\alpha +\beta =\omega ^{\omega ^{\omega }}+\omega ^{\omega }+\omega ^{5}$.And$\alpha \otimes \beta =\omega ^{\omega ^{\omega }+\omega }+\omega ^{\omega ^{\omega }+5}+\omega ^{\omega +1}+\omega ^{6}$,whereas$\alpha \beta =\omega ^{\omega ^{\omega }+\omega }+\omega ^{\omega ^{\omega }+5}$.

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$then$\alpha \oplus \gamma <\beta \oplus \gamma$;if$\alpha \leq \beta$then$\alpha \otimes \gamma \leq \beta \otimes \gamma$;and if$\alpha <\beta$and$\gamma >0$then$\alpha \otimes \gamma <\beta \otimes \gamma$.

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

We always have$\alpha +\beta \leq \alpha \oplus \beta$and$\alpha \beta \leq \alpha \otimes \beta$.If both$\alpha <\omega ^{\gamma }$and$\beta <\omega ^{\gamma }$then$\alpha \oplus \beta <\omega ^{\gamma }$.If both$\alpha <\omega ^{\omega ^{\gamma }}$and$\beta <\omega ^{\omega ^{\gamma }}$then$\alpha \otimes \beta <\omega ^{\omega ^{\gamma }}$.

Natural sum and product are not continuous in the right argument, since, for example$\lim _{n<\omega }\alpha \oplus n=\alpha +\omega$,and not$\alpha \oplus \omega$;and$\lim _{n<\omega }\alpha \otimes n=\alpha \omega$,and not$\alpha \otimes \omega$.

The natural sum and product are the same as the addition and multiplication (restricted to ordinals) ofJohn Conway'sfieldofsurreal numbers.

The natural operations come up in the theory ofwell partial orders;given two well partial orders$S$and$T$,oftypes(maximumlinearizations)$o(S)$and$o(T)$,the type of the disjoint union is$o(S)\oplus o(T)$,while the type of the direct product is$o(S)\otimes o(T)$.One may take this relation as a definition of the natural operations by choosingSandTto 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β.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 someordered abelian group,then their sum has order type at mostα⊗β.

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γsuch that(α⊗δ) ⊕ (ε⊗β) <γ⊕ (ε⊗δ)for allε<αandδ<β.Also, see the article onsurreal numbersfor 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ω+ 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ω.

Under natural addition, the ordinals can be identified with the elements of thefree commutative monoidgenerated by the gamma numbersω^α.Under natural addition and multiplication, the ordinals can be identified with the elements of thefree commutative semiringgenerated 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, ifxis any delta number, then

x⁵+x⁴+x³+x²+x+ 1 = (x+ 1) (x⁴+x²+ 1) = (x²+x+ 1) (x³+ 1)

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

Nimber arithmetic

Main article:Nimber

There are arithmetic operations on ordinals by virtue of the one-to-one correspondence between ordinals andnimbers.Three common operations on nimbers are nimber addition, nimber multiplication, andminimum excludance (mex).Nimber addition is a generalization of thebitwise exclusive oroperation on natural numbers. Themexof a set of ordinals is the smallest ordinalnotpresent in the set.

References

• Thomas Jech(21 March 2006).Set Theory: The Third Millennium Edition, revised and expanded.Springer Science & Business Media.ISBN978-3-540-44085-7.
• Kunen, Kenneth,1980.Set Theory: An Introduction to Independence Proofs.Elsevier.ISBN0-444-86839-9.
• Sierpiński, Wacław(1958),Cardinal and ordinal numbers,Polska Akademia Nauk Monografie Matematyczne, vol. 34, Warsaw: Państwowe Wydawnictwo Naukowe,MR0095787

External links

• ordCalc ordinal calculator