{"history":[],"article":{"id":"e8434695-e6ce-4a88-b179-9d71eaab8d5f","title":"Ordinal arithmetic","slug":"ordinal-arithmetic","content":":::summary\n:::\n\n# \nIn the [mathematical](https://bliptext.com/articles/mathematics) field of [set theory](https://bliptext.com/articles/set-theory), **ordinal arithmetic** describes the three usual operations on [ordinal numbers](https://bliptext.com/articles/ordinal-number): [addition](https://bliptext.com/articles/addition), [multiplication](https://bliptext.com/articles/multiplication), and [exponentiation](https://bliptext.com/articles/exponentiation).\nEach can be defined in essentially two different ways: either by constructing an explicit [well-ordered set](https://bliptext.com/articles/well-order) that represents the result of the operation or by using [transfinite recursion](https://bliptext.com/articles/transfinite-recursion).\nCantor normal form provides a standardized way of writing ordinals.\nIn addition to these usual ordinal operations, there are also the [\"natural\" arithmetic of ordinals](https://bliptext.com/articles/) and the [nimber operations](https://bliptext.com/articles/).\n\n# Addition\nThe sum of two well-ordered sets S and T is the ordinal representing the variant of [lexicographical order](https://bliptext.com/articles/lexicographical-order) with least significant position first, on the union of the [Cartesian products](https://bliptext.com/articles/cartesian-product)\nS ×\nand\nT ×\n. This way, every element of S is smaller than every element of T, comparisons within S keep the order they already have, and likewise for comparisons within T.\nThe definition of addition\nα + β\ncan also be given by [transfinite recursion](https://bliptext.com/articles/transfinite-recursion) on β.\nWhen the right addend\nβ = 0\n, ordinary addition gives\nα + 0 = α\nfor any α.\nFor\nβ > 0\n, the value of\nα + β\nis the smallest ordinal strictly greater than the sum of α and δ for all\nδ < β\n. Writing the successor and limit ordinals cases separately:\nα + 0 = α\nα + S(β) = S(α + β)\n, where S denotes the [successor](https://bliptext.com/articles/successor-ordinal) function.\nOrdinal addition on the [natural numbers](https://bliptext.com/articles/natural-numbers) is the same as standard addition.\nThe first transfinite ordinal is ω, the set of all natural numbers, followed by\nω + 1\n,\nω + 2\n, etc. The ordinal\nω + ω\nis obtained by two copies of the natural numbers ordered in the usual fashion and the second copy completely to the right of the first.\nWriting\n0' < 1' < 2' < ...\nfor the second copy,\nω + ω\nlooks like\n0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...\nThis is different from ω because in ω only\n0\ndoes not have a direct predecessor while in\nω + ω\nthe two elements\n0\nand\n0'\ndo not have direct predecessors.\n\n## Properties\nOrdinal addition is, in general, not [commutative](https://bliptext.com/articles/commutative).\nFor example,\n3 + ω = ω\nsince the order relation for\n3 + ω\nis\n0 < 1 < 2 < 0' < 1' < 2' < ...\n, which can be relabeled to ω.\nIn contrast\nω + 3\nis not equal to ω since the order relation\n0 < 1 < 2 < ... < 0' < 1' < 2'\nhas a largest element (namely,\n2'\n) and ω does not (ω and\nω + 3\nare [equipotent](https://bliptext.com/articles/equipotent), but not order isomorphic).\nOrdinal addition is still [associative](https://bliptext.com/articles/associative); one can see for example that\n(ω + 4) + ω = ω + (4 + ω) = ω + ω\n.\nAddition is [strictly increasing](https://bliptext.com/articles/strictly-increasing) and [continuous](https://bliptext.com/articles/continuous-function-set-theory) in the right argument:\nbut the analogous relation does not hold for the left argument; instead we only have:\nOrdinal addition is [left-cancellative](https://bliptext.com/articles/left-cancellative): if\nα + β = α + γ\n, then\nβ = γ\n. Furthermore, one can define [left subtraction](https://bliptext.com/articles/left-division) for ordinals\nβ ≤ α\nα = β + γ\n. On the other hand, right cancellation does not work:\nNor does right subtraction, even when\nβ ≤ α\nγ + 42 = ω\n.\nIf the ordinals less than α are closed under addition and contain 0, then α is occasionally called a γ-number (see [additively indecomposable ordinal](https://bliptext.com/articles/additively-indecomposable-ordinal)).\nThese are exactly the ordinals of the form\nωβ\n.\n\n# Multiplication\n[[File:OmegaPlusOmega svg.svg|thumb|600px|The disjoint union\n{ (n,0) : n ∈ N } ∪ { (n,1) : n ∈ N }\n, using lexicographic order with least significant position first, has order type\nω • 2\n. This is different from ω.]]\n[[File:TwoTimesOmega svg.svg|thumb|600px|The set\n{ (0,n), (1,n) : n ∈ N }\n, under lexicographic order with least significant position first, has order type\n2 • ω\n, which is equal to ω.]]\nThe [Cartesian product](https://bliptext.com/articles/cartesian-product),\nS × T\n, of two well-ordered sets S and T can be well-ordered by a variant of [lexicographical order](https://bliptext.com/articles/lexicographical-order) that puts the least significant position first.\nEffectively, each element of T is replaced by a disjoint copy of S. The order-type of the Cartesian product is the ordinal that results from multiplying the order-types of S and T.\nThe definition of multiplication can also be given by transfinite recursion on β.\nWhen the right factor\nβ = 0\n, ordinary multiplication gives\nα · 0 = 0\nfor any α.\nFor\nβ > 0\n, the value of\nα · β\nis the smallest ordinal greater than or equal to\n(α · δ) + α\nfor all\nδ < β\n. Writing the successor and limit ordinals cases separately:\nα · S(β) = (α · β) + α\n, for a successor ordinal\nS(β)\n.\nAs an example, here is the order relation for\nω · 2\nwhich has the same order type as\nω + ω\n. In contrast,\n2 · ω\nlooks like this:\nand after relabeling, this looks just like ω.\nThus,\nω · 2 = ω+ω ≠ ω = 2 · ω\n, showing that multiplication of ordinals is not in general commutative, c.f. pictures.\nAs is the case with addition, ordinal multiplication on the natural numbers is the same as standard multiplication.\n\n## Properties\nα · 0 = 0 · α = 0\n, and the [zero-product property](https://bliptext.com/articles/zero-product-property) holds:\nα · β = 0 → α = 0\nor\nβ = 0\n. The ordinal 1 is a multiplicative identity,\nα · 1 = 1 · α = α\n. Multiplication is associative,\n(α · β) · γ = α · (β · γ)\n. Multiplication is strictly increasing and continuous in the right argument: (\nα < β\nand\nγ > 0\n) →\nγ·α < γ·β\n. Multiplication is not strictly increasing in the left argument, for example, 1 < 2 but\n1 · ω = 2 · ω = ω\n. However, it is (non-strictly) increasing, i.e.\nα ≤ β\n→\nα·γ ≤ β·γ\n.\nMultiplication of ordinals is not in general commutative.\nSpecifically, a natural number greater than 1 never commutes with any infinite ordinal, and two infinite ordinals α and β commute if and only if\nαm = βn\nfor some nonzero natural numbers m and n. The relation \"α commutes with β\" is an equivalence relation on the ordinals greater than 1, and all equivalence classes are countably infinite.\n[Distributivity](https://bliptext.com/articles/distributivity) holds, on the left:\nα(β + γ) = αβ + αγ\n. However, the distributive law on the right\n(β + γ)α = βα+γα\nis not generally true:\n(1 + 1) · ω = 2 · ω = ω\nwhile\n1 · ω + 1 · ω = ω + ω\n, which is different.\nThere is a [left cancellation](https://bliptext.com/articles/left-cancellative) law: If\nα > 0\nand\nα · β = α · γ\n, then\nβ = γ\n. Right cancellation does not work, e.g.\n1 · ω = 2 · ω = ω\n, but 1 and 2 are different.\nA [left division](https://bliptext.com/articles/left-division) with [remainder](https://bliptext.com/articles/remainder) property holds: for all α and β, if\nβ > 0\n, then there are unique γ and δ such that\nα = β · γ + δ\nand\nδ < β\n. Right division does not work: there is no α such that\nα · ω ≤ ωω ≤ (α + 1) · ω\n.\nThe ordinal numbers form a left [near-semiring](https://bliptext.com/articles/near-semi[ring](https://bliptext.com/articles/ring-algebra)), but do not form a [ring](https://bliptext.com/articles/ring-algebra).\nHence the ordinals are not a [Euclidean domain](https://bliptext.com/articles/euclidean-domain), since they are not even a ring; furthermore the Euclidean \"norm\" would be ordinal-valued using the left division here.\nA δ-number (see [Multiplicatively indecomposable ordinal](https://bliptext.com/articles/additively-indecomposable-ordinal)) is an ordinal β greater than 1 such that\nαβ = β\nwhenever\n0 < α < β\n. These consist of the ordinal 2 and the ordinals of the form\nβ = ωω γ\n.\n\n# Exponentiation\nThe definition of [exponentiation](https://bliptext.com/articles/exponentiation) via order types is most easily explained using [Von Neumann's definition of an ordinal as the set of all smaller ordinals](https://bliptext.com/articles/ordinal-number).\nThen, to construct a set of order type\nαβ\nconsider the set of all functions\nf : β → α\nsuch that\nf(x) = 0\nfor all but finitely many elements\nx ∈ β\n(essentially, we consider the functions with finite [support](https://bliptext.com/articles/support-mathematics)).\nThis set is [ordered lexicographically](https://bliptext.com/articles/lexicographic-order) with the least significant position first: we write\nf < g\nif and only if there exists\nx ∈ β\nwith\nf(x) < g(x)\nand\nf(y) = g(y)\nfor all\ny ∈ β\nwith\nx < y\n. This is a well-ordering and hence gives an ordinal number.\nThe definition of exponentiation can also be given by transfinite recursion on the exponent β.\nWhen the exponent\nβ = 0\n, ordinary exponentiation gives\nα0 = 1\nfor any α.\nFor\nβ > 0\n, the value of\nαβ\nis the smallest ordinal greater than or equal to\nαδ · α\nfor all\nδ < β\n. Writing the successor and limit ordinals cases separately:\nα0 = 1\n.\nαS(β) = (αβ) · α\n, for a successor ordinal\nS(β)\n.\nBoth definitions simplify considerably if the exponent β is a finite number:\nαβ\nis then just the product of β copies of α; e.g.\nω3 = ω·ω·ω\n, and the elements of\nω3\ncan be viewed as triples of natural numbers, ordered lexicographically with least significant position first.\nThis agrees with the ordinary exponentiation of natural numbers.\nBut for infinite exponents, the definition may not be obvious.\nFor example,\nαω\ncan be identified with a set of finite sequences of elements of α, properly ordered.\nThe equation\n2ω = ω\nexpresses the fact that finite sequences of zeros and ones can be identified with natural numbers, using the [binary number](https://bliptext.com/articles/binary-number) system.\nThe ordinal\nωω\ncan be viewed as the order type of finite sequences of natural numbers; every element of\nωω\n(i.e. every ordinal smaller than\nωω\n) can be uniquely written in the form where k,\nn1\n, ...,\nnk\nare natural numbers,\nc1\n, ...,\nck\nare nonzero natural numbers, and\nn1 > ...\n> nk\n.\nThe same is true in general: every element of\nαβ\n(i.e. every ordinal smaller than\nαβ\n) can be uniquely written in the form where k is a natural number,\nb1\n, ...,\nbk\nare ordinals smaller than β with\nb1 > ...\n> bk\n, and\na1, ..., ak\nare nonzero ordinals smaller than α.\nThis expression corresponds to the function\nf : β → α\nwhich sends\nbi\nto\nai\nfor\ni = 1, ..., k\nand sends all other elements of β to 0.\nWhile the same exponent-notation is used for ordinal exponentiation and [cardinal exponentiation](https://bliptext.com/articles/cardinal-exponentiation), the two operations are quite different and should not be confused.\nThe cardinal exponentiation\nAB\nis defined to be the cardinal number of the set of all functions\nB → A\n, while the ordinal exponentiation\nαβ\nonly contains the functions\nβ → α\nwith finite support, typically a set of much smaller cardinality.\nTo 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.\n\n## Properties\nα0 = 1\n.\n0 < α\n, then\n0α = 0\n.\n1α = 1\n.\nα1 = α\n.\nαβ·αγ = αβ + γ\n.\n(αβ)γ = αβ·γ\n.\n(α · β)γ ≠ αγ · βγ\n. For instance,\n(ω · 2)2 = ω·2·ω·2 = ω2 · 2 ≠ ω2 · 4\n.\nγ > 1\nand\nα < β\n, then\nγα < γβ\n.\nα < β\n, then\nαγ ≤ βγ\n. Note, for instance, that 2 < 3 and yet\n2ω = 3ω = ω\n.\nα > 1\nand\nαβ = αγ\n, then\nβ = γ\n. If\nα = 1\nor\nα = 0\nthis is not the case.\nβ > 1\nand\nα > 0\nthen there exist unique γ, δ, and ρ such that\nα = βγ · δ + ρ\nsuch that\n0 < δ < β\nand\nρ < βγ\n.\n[Jacobsthal](https://bliptext.com/articles/ernst-jacobsthal) showed that the only solutions of\nαβ = βα\nwith\nα ≤ β\nare given by\nα = β\n, or\nα = 2\nand\nβ = 4\n, or α is any limit ordinal and\nβ = εα\nwhere ε is an [ε-number](https://bliptext.com/articles/epsilon-numbers-mathematics) larger than α.\n\n# Beyond exponentiation\nThere are ordinal operations that continue the sequence begun by addition, multiplication, and exponentiation, including ordinal versions of [tetration](https://bliptext.com/articles/tetration), [pentation](https://bliptext.com/articles/pentation), and [hexation](https://bliptext.com/articles/hexation).\nSee also [Veblen function](https://bliptext.com/articles/veblen-function).\n\n# Cantor normal form\nEvery ordinal number α can be uniquely written as, where k is a natural number, are nonzero natural numbers, and are ordinal numbers.\nThe degenerate case\nα = 0\noccurs when\nk = 0\nand there are no βs nor cs.\nThis decomposition of α is called the **Cantor normal form** of α, and can be considered the base-ω [positional numeral system](https://bliptext.com/articles/positional-numeral-system).\nThe highest exponent \\beta_1 is called the degree of \\alpha, and satisfies.\nThe equality applies if and only if.\nIn that case Cantor normal form does not express the ordinal in terms of smaller ones; this can happen as explained below.\nA minor variation of Cantor normal form, which is usually slightly easier to work with, is to set all the numbers\nci\nequal to 1 and allow the exponents to be equal.\nIn other words, every ordinal number α can be uniquely written as, where k is a natural number, and are ordinal numbers.\nAnother variation of the Cantor normal form is the \"base δ expansion\", where ω is replaced by any ordinal\nδ > 1\n, and the numbers\nci\nare nonzero ordinals less than δ.\nThe 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 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,\ndenotes an ordinal).\nThe ordinal ε0 ([epsilon nought](https://bliptext.com/articles/epsilon-numbers-mathematics)) 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<α.\nIt is the smallest ordinal that does not have a finite arithmetical expression in terms of ω, and the smallest ordinal such that, i.e. in Cantor normal form the exponent is not smaller than the ordinal itself.\nIt is the limit of the sequence\nThe ordinal ε0 is important for various reasons in arithmetic (essentially because it measures the [proof-theoretic strength](https://bliptext.com/articles/proof-theoretic-strength) of the [first-order](https://bliptext.com/articles/first-order-logic) [Peano arithmetic](https://bliptext.com/articles/peano-axioms): that is, Peano's axioms can show transfinite induction up to any ordinal less than ε0 but not up to ε0 itself).\nThe 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\nif (if one can apply the distributive law on the left and 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 < \\beta', then\nand\nif n is a non-zero natural number.\nTo compare two ordinals written in Cantor normal form, first compare \\beta_1, then c_1, then \\beta_2, then c_2, and so on.\nAt the first occurrence of inequality, the ordinal that has the larger component is the larger ordinal.\nIf they are the same until one terminates before the other, then the one that terminates first is smaller.\n\n# Factorization into primes\n[Ernst Jacobsthal](https://bliptext.com/articles/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.\nThis 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.\nA prime ordinal is an ordinal greater than 1 that cannot be written as a product of two smaller ordinals.\nSome of the first primes are 2, 3, 5, ...\n, ω,\nω + 1\n,\nω2 + 1\n,\nω3 + 1\n, ...,\nωω\n,\nωω + 1\n,\nωω + 1 + 1\n, ... There are three sorts of prime ordinals:\nωω α\nfor any ordinal α.\nThese are the prime ordinals that are limits, and are the [delta numbers](https://bliptext.com/articles/additively-indecomposable-ordinal), the transfinite ordinals that are closed under multiplication.\nωα + 1\nfor any ordinal\nα > 0\n. These are the infinite successor primes, and are the successors of [gamma numbers](https://bliptext.com/articles/additively-indecomposable-ordinal), the additively indecomposable ordinals.\nFactorization into primes is not unique: for example,\n2×3 = 3×2\n,\n2×ω = ω\n,\n(ω+1)×ω = ω×ω\nand\nω×ωω = ωω\n. However, there is a unique factorization into primes satisfying the following additional conditions:\nThis prime factorization can easily be read off using the Cantor normal form as follows:\nαβ\nwhere α is the smallest power of ω in the Cantor normal form and β is a successor.\nα = ωγ\nthen writing γ in Cantor normal form gives an expansion of α as a product of limit primes.\nβ = ωλm + ωμn\n+ smaller terms, then\nβ = (ωμn + smaller terms)(ωλ−μ + 1)m\nis a product of a smaller ordinal and a prime and a natural number m. Repeating this and factorizing the natural numbers into primes gives the prime factorization of β.\nSo the factorization of the Cantor normal form ordinal\nωα1n1 + ⋯ + ωαknk\n(with\nα1 > ⋯ > αk\n) into a minimal product of infinite primes and natural numbers is\n(ωω β1 ⋯ ωω βm )nk (ωαk−1−αk + 1)nk−1 ⋯ (ωα1−α2 + 1)n1\nwhere each\nni\nshould be replaced by its factorization into a non-increasing sequence of finite primes and\nαk = ωβ1 + ⋯ + ωβm\nwith\nβ1 ≥ ⋯ ≥ βm\n.\n\n# Large countable ordinals\nAs 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 ω.\nWe 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))))).\nThis describes an [ordinal notation](https://bliptext.com/articles/ordinal-notation): a system for naming ordinals over a finite alphabet.\nThis particular system of ordinal notation is called the collection of arithmetical ordinal expressions, and can express all ordinals below ε0, but cannot express ε0.\nThere 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\nω1\n(the [first uncountable ordinal](https://bliptext.com/articles/first-uncountable-ordinal)) that are not expressible.\nSuch ordinals are known as [large countable ordinals](https://bliptext.com/articles/large-countable-ordinal).\nThe operations of addition, multiplication and exponentiation are all examples of [primitive recursive ordinal functions](https://bliptext.com/articles/primitive-recursive-ordinal-function), and more general [primitive recursive ordinal functions](https://bliptext.com/articles/primitive-recursive-ordinal-function) can be used to describe larger ordinals.\n\n# Natural operations\nThe **natural sum** and **natural product** operations on ordinals were defined in 1906 by [Gerhard Hessenberg](https://bliptext.com/articles/gerhard-hessenberg), and are sometimes called the **Hessenberg sum** (or product).\nThe natural sum of α and β is often denoted by\nα ⊕ β\nor\nα # β\n, and the natural product by\nα ⊗ β\nor\nα ⨳ β\n.\nThe natural sum and product are defined as follows.\nLet and be in Cantor normal form (i.e. and ).\nLet be the exponents sorted in nonincreasing order.\nThen is defined as The natural product of \\alpha and \\beta is defined as For example, suppose and.\nThen, whereas.\nAnd, whereas.\nThe natural sum and product are commutative and associative, and natural product distributes over natural sum.\nThe operations are also monotonic, in the sense that if then ; if then ; and if and \\gamma>0 then.\nWe have.\nWe always have and.\nIf both and then.\nIf both and then.\nNatural sum and product are not continuous in the right argument, since, for example, and not ; and , and not.\nThe natural sum and product are the same as the addition and multiplication (restricted to ordinals) of [John Conway](https://bliptext.com/articles/john-conway)'s [field](https://bliptext.com/articles/field-mathematics) of [surreal numbers](https://bliptext.com/articles/surreal-numbers).\nThe natural operations come up in the theory of [well partial orders](https://bliptext.com/articles/well-quasi-ordering); given two [well partial orders](https://bliptext.com/articles/well-quasi-ordering) S and T, of [types](https://bliptext.com/articles/order-type) (maximum [linearizations](https://bliptext.com/articles/linear-order)) o(S) and o(T), the type of the disjoint union is, while the type of the direct product is.\nOne may take this relation as a definition of the natural operations by choosing S and T to be ordinals α and β; so\nα ⊕ β\nis the maximum order type of a total order extending the disjoint union (as a partial order) of α and β; while\nα ⊗ β\nis the maximum order type of a total order extending the direct product (as a partial order) of α and β.\nA useful application of this is when α and β are both subsets of some larger total order; then their union has order type at most\nα ⊕ β\n. If they are both subsets of some [ordered abelian group](https://bliptext.com/articles/ordered-group), then their sum has order type at most\nα ⊗ β\n.\nWe can also define the natural sum\nα ⊕ β\nby simultaneous transfinite recursion on α and β, as the smallest ordinal strictly greater than the natural sum of α and γ for all\nγ < β\nand of γ and β for all\nγ < α\n. Similarly, we can define the natural product\nα ⊗ β\nby simultaneous transfinite recursion on α and β, as the smallest ordinal γ such that\n(α ⊗ δ) ⊕ (ε ⊗ β) < γ ⊕ (ε ⊗ δ)\nfor all\nε < α\nand\nδ < β\n. Also, see the article on [surreal numbers](https://bliptext.com/articles/surreal-numbers) for the definition of natural multiplication in that context; however, it uses surreal subtraction, which is not defined on ordinals.\nThe natural sum is associative and commutative.\nIt is always greater or equal to the usual sum, but it may be strictly greater.\nFor example, the natural sum of ω and 1 is\nω + 1\n(the usual sum), but this is also the natural sum of 1 and ω.\nThe natural product is associative and commutative and distributes over the natural sum.\nThe natural product is always greater or equal to the usual product, but it may be strictly greater.\nFor example, the natural product of ω and 2 is\nω · 2\n(the usual product), but this is also the natural product of 2 and ω.\nUnder natural addition, the ordinals can be identified with the elements of the [free commutative monoid](https://bliptext.com/articles/free-commutative-monoid) generated by the gamma numbers\nωα\n. Under natural addition and multiplication, the ordinals can be identified with the elements of the [free commutative semiring](https://bliptext.com/articles/semiring) generated by the delta numbers\nωω α\n. The ordinals do not have unique factorization into primes under the natural product.\nWhile the full polynomial ring does have unique factorization, the subset of polynomials with non-negative coefficients does not: for example, if x is any delta number, then\nx5 + x4 + x3 + x2 + x + 1 = (x + 1) (x4 + x2 + 1) = (x2 + x + 1) (x3 + 1)\nhas two incompatible expressions as a natural product of polynomials with non-negative coefficients that cannot be decomposed further.\n\n# Nimber arithmetic\nThere are arithmetic operations on ordinals by virtue of the one-to-one correspondence between ordinals and [nimbers](https://bliptext.com/articles/nimber).\nThree common operations on nimbers are nimber addition, nimber multiplication, and [minimum excludance (mex)](https://bliptext.com/articles/mex-mathematics).\nNimber addition is a generalization of the [bitwise exclusive or](https://bliptext.com/articles/bitwise-operation) operation on natural numbers.\nThe\nmex\nof a set of ordinals is the smallest ordinal not present in the set.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:44:19.876Z","updated_at":"2025-01-25T21:44:19.876Z","search_vector":"'arithmet':2 'ordin':1","search_content":" \n \n\n# \nIn the [mathematical](https://bliptext.com/articles/mathematics) field of [set theory](https://bliptext.com/articles/set-theory), **ordinal arithmetic** describes the three usual operations on [ordinal numbers](https://bliptext.com/articles/ordinal-number): [addition](https://bliptext.com/articles/addition), [multiplication](https://bliptext.com/articles/multiplication), and [exponentiation](https://bliptext.com/articles/exponentiation).\nEach can be defined in essentially two different ways: either by constructing an explicit [well-ordered set](https://bliptext.com/articles/well-order) that represents the result of the operation or by using [transfinite recursion](https://bliptext.com/articles/transfinite-recursion).\nCantor normal form provides a standardized way of writing ordinals.\nIn addition to these usual ordinal operations, there are also the [\"natural\" arithmetic of ordinals](https://bliptext.com/articles/) and the [nimber operations](https://bliptext.com/articles/).\n\n# Addition\nThe sum of two well-ordered sets S and T is the ordinal representing the variant of [lexicographical order](https://bliptext.com/articles/lexicographical-order) with least significant position first, on the union of the [Cartesian products](https://bliptext.com/articles/cartesian-product)\nS ×\nand\nT ×\n. This way, every element of S is smaller than every element of T, comparisons within S keep the order they already have, and likewise for comparisons within T.\nThe definition of addition\nα + β\ncan also be given by [transfinite recursion](https://bliptext.com/articles/transfinite-recursion) on β.\nWhen the right addend\nβ = 0\n, ordinary addition gives\nα + 0 = α\nfor any α.\nFor\nβ > 0\n, the value of\nα + β\nis the smallest ordinal strictly greater than the sum of α and δ for all\nδ 0\n, the value of\nα · β\nis the smallest ordinal greater than or equal to\n(α · δ) + α\nfor all\nδ 0\n) →\nγ·α 0\nand\nα · β = α · γ\n, then\nβ = γ\n. Right cancellation does not work, e.g.\n1 · ω = 2 · ω = ω\n, but 1 and 2 are different.\nA [left division](https://bliptext.com/articles/left-division) with [remainder](https://bliptext.com/articles/remainder) property holds: for all α and β, if\nβ > 0\n, then there are unique γ and δ such that\nα = β · γ + δ\nand\nδ 0\n, the value of\nαβ\nis the smallest ordinal greater than or equal to\nαδ · α\nfor all\nδ ...\n> nk\n.\nThe same is true in general: every element of\nαβ\n(i.e. every ordinal smaller than\nαβ\n) can be uniquely written in the form where k is a natural number,\nb1\n, ...,\nbk\nare ordinals smaller than β with\nb1 > ...\n> bk\n, and\na1, ..., ak\nare nonzero ordinals smaller than α.\nThis expression corresponds to the function\nf : β → α\nwhich sends\nbi\nto\nai\nfor\ni = 1, ..., k\nand sends all other elements of β to 0.\nWhile the same exponent-notation is used for ordinal exponentiation and [cardinal exponentiation](https://bliptext.com/articles/cardinal-exponentiation), the two operations are quite different and should not be confused.\nThe cardinal exponentiation\nAB\nis defined to be the cardinal number of the set of all functions\nB → A\n, while the ordinal exponentiation\nαβ\nonly contains the functions\nβ → α\nwith finite support, typically a set of much smaller cardinality.\nTo 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.\n\n## Properties\nα0 = 1\n.\n0 1\nand\nα 1\nand\nαβ = αγ\n, then\nβ = γ\n. If\nα = 1\nor\nα = 0\nthis is not the case.\nβ > 1\nand\nα > 0\nthen there exist unique γ, δ, and ρ such that\nα = βγ · δ + ρ\nsuch that\n0 1\n, and the numbers\nci\nare nonzero ordinals less than δ.\nThe 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 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,\ndenotes an ordinal).\nThe ordinal ε0 ([epsilon nought](https://bliptext.com/articles/epsilon-numbers-mathematics)) 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 0\n. These are the infinite successor primes, and are the successors of [gamma numbers](https://bliptext.com/articles/additively-indecomposable-ordinal), the additively indecomposable ordinals.\nFactorization into primes is not unique: for example,\n2×3 = 3×2\n,\n2×ω = ω\n,\n(ω+1)×ω = ω×ω\nand\nω×ωω = ωω\n. However, there is a unique factorization into primes satisfying the following additional conditions:\nThis prime factorization can easily be read off using the Cantor normal form as follows:\nαβ\nwhere α is the smallest power of ω in the Cantor normal form and β is a successor.\nα = ωγ\nthen writing γ in Cantor normal form gives an expansion of α as a product of limit primes.\nβ = ωλm + ωμn\n+ smaller terms, then\nβ = (ωμn + smaller terms)(ωλ−μ + 1)m\nis a product of a smaller ordinal and a prime and a natural number m. Repeating this and factorizing the natural numbers into primes gives the prime factorization of β.\nSo the factorization of the Cantor normal form ordinal\nωα1n1 + ⋯ + ωαknk\n(with\nα1 > ⋯ > αk\n) into a minimal product of infinite primes and natural numbers is\n(ωω β1 ⋯ ωω βm )nk (ωαk−1−αk + 1)nk−1 ⋯ (ωα1−α2 + 1)n1\nwhere each\nni\nshould be replaced by its factorization into a non-increasing sequence of finite primes and\nαk = ωβ1 + ⋯ + ωβm\nwith\nβ1 ≥ ⋯ ≥ βm\n.\n\n# Large countable ordinals\nAs 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 ω.\nWe 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))))).\nThis describes an [ordinal notation](https://bliptext.com/articles/ordinal-notation): a system for naming ordinals over a finite alphabet.\nThis particular system of ordinal notation is called the collection of arithmetical ordinal expressions, and can express all ordinals below ε0, but cannot express ε0.\nThere 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\nω1\n(the [first uncountable ordinal](https://bliptext.com/articles/first-uncountable-ordinal)) that are not expressible.\nSuch ordinals are known as [large countable ordinals](https://bliptext.com/articles/large-countable-ordinal).\nThe operations of addition, multiplication and exponentiation are all examples of [primitive recursive ordinal functions](https://bliptext.com/articles/primitive-recursive-ordinal-function), and more general [primitive recursive ordinal functions](https://bliptext.com/articles/primitive-recursive-ordinal-function) can be used to describe larger ordinals.\n\n# Natural operations\nThe **natural sum** and **natural product** operations on ordinals were defined in 1906 by [Gerhard Hessenberg](https://bliptext.com/articles/gerhard-hessenberg), and are sometimes called the **Hessenberg sum** (or product).\nThe natural sum of α and β is often denoted by\nα ⊕ β\nor\nα # β\n, and the natural product by\nα ⊗ β\nor\nα ⨳ β\n.\nThe natural sum and product are defined as follows.\nLet and be in Cantor normal form (i.e. and ).\nLet be the exponents sorted in nonincreasing order.\nThen is defined as The natural product of \\alpha and \\beta is defined as For example, suppose and.\nThen, whereas.\nAnd, whereas.\nThe natural sum and product are commutative and associative, and natural product distributes over natural sum.\nThe operations are also monotonic, in the sense that if then ; if then ; and if and \\gamma>0 then.\nWe have.\nWe always have and.\nIf both and then.\nIf both and then.\nNatural sum and product are not continuous in the right argument, since, for example, and not ; and , and not.\nThe natural sum and product are the same as the addition and multiplication (restricted to ordinals) of [John Conway](https://bliptext.com/articles/john-conway)'s [field](https://bliptext.com/articles/field-mathematics) of [surreal numbers](https://bliptext.com/articles/surreal-numbers).\nThe natural operations come up in the theory of [well partial orders](https://bliptext.com/articles/well-quasi-ordering); given two [well partial orders](https://bliptext.com/articles/well-quasi-ordering) S and T, of [types](https://bliptext.com/articles/order-type) (maximum [linearizations](https://bliptext.com/articles/linear-order)) o(S) and o(T), the type of the disjoint union is, while the type of the direct product is.\nOne may take this relation as a definition of the natural operations by choosing S and T to be ordinals α and β; so\nα ⊕ β\nis the maximum order type of a total order extending the disjoint union (as a partial order) of α and β; while\nα ⊗ β\nis the maximum order type of a total order extending the direct product (as a partial order) of α and β.\nA useful application of this is when α and β are both subsets of some larger total order; then their union has order type at most\nα ⊕ β\n. If they are both subsets of some [ordered abelian group](https://bliptext.com/articles/ordered-group), then their sum has order type at most\nα ⊗ β\n.\nWe can also define the natural sum\nα ⊕ β\nby simultaneous transfinite recursion on α and β, as the smallest ordinal strictly greater than the natural sum of α and γ for all\nγ < β\nand of γ and β for all\nγ < α\n. Similarly, we can define the natural product\nα ⊗ β\nby simultaneous transfinite recursion on α and β, as the smallest ordinal γ such that\n(α ⊗ δ) ⊕ (ε ⊗ β) < γ ⊕ (ε ⊗ δ)\nfor all\nε < α\nand\nδ < β\n. Also, see the article on [surreal numbers](https://bliptext.com/articles/surreal-numbers) for the definition of natural multiplication in that context; however, it uses surreal subtraction, which is not defined on ordinals.\nThe natural sum is associative and commutative.\nIt is always greater or equal to the usual sum, but it may be strictly greater.\nFor example, the natural sum of ω and 1 is\nω + 1\n(the usual sum), but this is also the natural sum of 1 and ω.\nThe natural product is associative and commutative and distributes over the natural sum.\nThe natural product is always greater or equal to the usual product, but it may be strictly greater.\nFor example, the natural product of ω and 2 is\nω · 2\n(the usual product), but this is also the natural product of 2 and ω.\nUnder natural addition, the ordinals can be identified with the elements of the [free commutative monoid](https://bliptext.com/articles/free-commutative-monoid) generated by the gamma numbers\nωα\n. Under natural addition and multiplication, the ordinals can be identified with the elements of the [free commutative semiring](https://bliptext.com/articles/semiring) generated by the delta numbers\nωω α\n. The ordinals do not have unique factorization into primes under the natural product.\nWhile the full polynomial ring does have unique factorization, the subset of polynomials with non-negative coefficients does not: for example, if x is any delta number, then\nx5 + x4 + x3 + x2 + x + 1 = (x + 1) (x4 + x2 + 1) = (x2 + x + 1) (x3 + 1)\nhas two incompatible expressions as a natural product of polynomials with non-negative coefficients that cannot be decomposed further.\n\n# Nimber arithmetic\nThere are arithmetic operations on ordinals by virtue of the one-to-one correspondence between ordinals and [nimbers](https://bliptext.com/articles/nimber).\nThree common operations on nimbers are nimber addition, nimber multiplication, and [minimum excludance (mex)](https://bliptext.com/articles/mex-mathematics).\nNimber addition is a generalization of the [bitwise exclusive or](https://bliptext.com/articles/bitwise-operation) operation on natural numbers.\nThe\nmex\nof a set of ordinals is the smallest ordinal not present in the set.","revisionCount":0},"hasMore":false,"nextCursor":null}

History