In the mathematical field of set theory, ordinal arithmetic includes binary operations on ordinal numbers such as addition, multiplication, and exponentiation. Each can be defined in two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. In addition to these standard operations for ordinals, there are also the "natural" arithmetic operations, which are usually described using the Cantor normal form for ordinals, and nimber operations.
Background Ordinal numbers are like the counting numbers {0, 1, 2, ...} but go to infinity ω and beyond ω+1, ω+2, ..., ω+ω, ω+ω+1, .... The standard arithmetic operations and natural arithmetic operations on the finite ordinals are the same as the corresponding operations on the counting numbers, but arithmetic operations on the infinite ordinals are more complicated.
Addition The sum of two well-ordered sets S and T is the ordinal representing the variant of lexicographical order with least significant position first, on the union of the Cartesian products S × {0} and T × {1}. 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. The definition of ordinal addition α + β can also be given by transfinite recursion on β. When the right addend β = 0, 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(α + β), where S denotes the successor function. α + β = ⋃ δ < β {\displaystyle \bigcup _{\delta <\beta }} (α + δ) when β is a limit ordinal. Ordinal addition on the natural numbers is the same as standard addition. The first transfinite ordinal is ω, the set of all natural numbers, followed by ω + 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. Writing 0′ < 1′ < 2′ < ... for the second copy, ω + ω 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.
Properties Ordinal addition is, in general, not commutative. For example, 3 + ω = ω since the order relation for 3 + ω is 0 < 1 < 2 < 0′ < 1′ < 2′ < ..., which can be relabeled to ω. In contrast ω + 3 is not equal to ω since the order relation 0 < 1 < 2 < ... < 0′ < 1′ < 2′ has a largest element (namely, 2′) and ω does not (ω and ω + 3 are equipotent, but not order-isomorphic). Ordinal addition is still associative; one can see for example that (ω + 4) + ω = ω + (4 + ω) = ω + ω. Addition is strictly increasing and continuous in the right argument:
α < β ⇒ γ + α < γ + β but the analogous relation does not hold for the left argument; instead we only have:
α < β ⇒ α + γ ≤ β + γ Ordinal addition is left-cancellative: if α + β = α + γ, then β = γ. Furthermore, one can define left subtraction for ordinals β ≤ α: there is a unique γ such that α = β + γ. On the other hand, right cancellation does not work:
3 + ω = 0 + ω = ω, but 3 ≠ 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 (see Additively indecomposable ordinal). These are exactly the ordinals of the form ωβ.
Multiplication
The Cartesian product, S × T, of two well-ordered sets S and T can be well-ordered by a variant of lexicographical order that 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 that results from multiplying the order-types of S and T. The definition of ordinal multiplication can also be given by transfinite recursion on β. When the right factor β = 0, multiplication gives α · 0 = 0 for 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 ordinal S(β). α · β = ⋃ δ < β {\displaystyle \bigcup _{\delta <\beta }} (α · δ), when β is a limit ordinal. As an example, here is the order relation for ω · 2:
00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ..., which has the same order type as ω + ω. In contrast, 2 · ω looks like this:
00 < 10 < 01 < 11 < 02 < 12 < 03 < 13 < ... 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.
… excerpt ends here. Continue reading the full article.
