Ordinals - Maple Help

All Products Maple MapleSim

Home : Support : Online Help : System : Information : Updates : Maple 2015 : Ordinals

Ordinals

Ordinals crash course, or: What is $ω$ ?

Constructing ordinals

Ordinal arithmetic

Multiplication

Powering

Subtraction and comparison

Inverse operations

Logarithms and base conversion

Gcd and factorization

Ordinals crash course, or: What is $ω$ ?

Short answer: $ω$ = $ℕ$ endowed with its natural ordering $0 < 1 < 2 < \dots$

What if you add a largest possible element?

$ω + 1 = ω \cup \{\infty\} = \{0 < 1 < 2 < \dots < \infty\}$

What if you add a new smallest element?

$1 + ω = \{- \infty\} \cup ω = \{- \infty < 0 < 1 < 2 < \dots\}$

$≅ ω$

So:

$1 + ω = ω < ω + 1$

(Read "is isomorphic to" for $=$ and "is (isomorphic to) an initial segment of" for $\leq$ ).

Note that $ω$ is not isomorphic to $ω + 1$ , since $ω + 1$ has a largest element, namely $\infty$ , while $ω$ does not.

Moving on:

$ω + 2 = \{0 < 1 < 2 < \dots < \infty < \infty + 1\}$

$2 + ω = \{- 1 - \infty < - \infty < 0 < 1 < 2 < \dots\} = ω$

and

$2 + ω = 1 + ω = ω < ω + 1 < ω + 2$

Keep going: for any positive integer $n$

$\begin{array}{c} n + ω = ω < ω + 1 < ω + 2 < \dots < ω + n < \dots < & &quest; \end{array}$

Answer:

$\begin{array}{c} &quest; & = ω + ω = ω \cdot 2 \end{array}$ (2 copies of $ω$ )

You can identify each natural number $n$ with the ordered set of integers smaller than $n$ :

$n = \{0 < 1 < 2 < \dots < n - 1\}$

(Note: in contrast to the $0 < 1 < 2 < \dots < \infty$ cases earlier, the $\dots$ in this "definition" is finite.)

Then:

$0 = \{\} = \emptyset$

$1 = \{0\} = \{\emptyset\}$

$2 = \{0 < 1\} = \{\emptyset < \{\emptyset\}\}$

$3 = \{0 < 1 < 2\} = \{\emptyset < \{\emptyset\} < \{\emptyset, \{\emptyset\}\}\}$

$4 = \{0 < 1 < 2 < 3\} = \{\emptyset < \{\emptyset\} < \{\emptyset, \{\emptyset\}\} < \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\}$

$⋮$

and, as ordered sets:

$0 < 1 < 2 < \dots < ω < ω + 1 < ω + 2 < \dots < ω + ω < ω + ω + 1 < ω + ω + 2 < \dots < ω + ω + ω < \dots$

In general, you can (isomorphically) identify each set above (ordinal) with the set of all smaller ordinals. E.g.:

$\{0 < 1 < 2 < \dots\} = ω$

$\{0 < 1 < 2 < \dots < ω\} = ω + 1$

$\{0 < 1 < 2 < \dots < ω < ω + 1\} = ω + 2$

$\{0 < 1 < 2 < \dots < ω < ω + 1 < ω + 2 < \dots\} = ω + ω$

$\{0 < 1 < 2 < \dots < ω < ω + 1 < ω + 2 < \dots < ω + ω\} = ω + ω + 1$

$⋮$

Beyond addition:

$ω + ω ≕ ω \cdot 2$ (2 copies of $ω$ )

$2 + 2 + \dots = 2 \cdot ω = ω$ ( $ω$ copies of 2)

$ω + ω + ω = ω \cdot 3$

$3 \cdot ω = ω$

$\underset{n times}{\underset{⏟}{ω + \dots + ω}} = ω \cdot n$ ( $n$ copies of $ω$ )

$n \cdot ω = ω$

$⋮$

So:

$\begin{array}{c} 0 < 1 < 2 < \dots < ω < ω + 1 < \dots < ω \cdot 2 < ω \cdot 2 + 1 < \dots < ω \cdot 3 < \dots < ω \cdot n < \dots < & &quest; \end{array}$

Answer:

$\begin{array}{c} &quest; & = ω \cdot ω = ω^{2} \end{array}$ ( $ω$ copies of $ω$ )

or, isomorphically equivalent: pairs of nonnegative integers with reverse lexicographic ordering

$(a_{0}, a_{1}) < (b_{0}, b_{1}) \Leftrightarrow a_{1} < b_{1} \lor (a_{1} = b_{1} \land a_{0} < b_{0})$

Similarly:

$ω \cdot ω \cdot ω = ω^{3}$ (3-tuples)

$ω \cdot ω \cdot ω \cdot ω = ω^{4}$ (4-tuples)

$⋮$

$\underset{n times}{\underset{⏟}{ω \cdot \dots \cdot ω}} = ω^{n}$ ( $n$ -tuples)

$⋮$

What is next?

$ω^{ω}$ ( $ω$ -tuples with finitely many nonzero entries)

Other interpretation: the union $ω^{ω} = 1 \subseteq ω \subseteq ω^{2} \subseteq \dots \subseteq ω^{n} \subseteq \dots$ of all $n$ -tuples for $n \in ω$ with reverse lexicographic ordering.

The picture so far:

$0 < 1 < 2 < \dots <$

$ω < ω + 1 < ω + 2 < \dots <$

$ω + ω = ω \cdot 2 < ω \cdot 2 + 1 < ω \cdot 2 + 2 < \dots <$

$ω \cdot 3 < ω \cdot 3 + 1 < \dots < ω \cdot 4 < ω \cdot 4 + 1 < \dots <$

$⋮$

$ω \cdot ω = ω^{2} < ω^{2} + 1 < \dots < ω^{2} + ω < ω^{2} + ω + 1 < \dots < ω^{2} + ω \cdot 2 < \dots$

$ω^{2} \cdot 2 < ω^{2} \cdot 2 + 1 < \dots < ω^{2} \cdot 2 + ω < ω^{2} \cdot 2 + ω + 1 < \dots < ω^{2} \cdot 2 + ω \cdot 2 < \dots$

$ω^{2} \cdot 3 < ω^{2} \cdot 3 + 1 < \dots < ω^{2} \cdot 3 + ω < \dots < ω^{2} \cdot 4 < ω^{2} \cdot 4 + 1 < \dots < ω^{2} \cdot 4 + ω < \dots$

$⋮$

$ω^{2} \cdot ω = ω^{3} < ω^{3} + 1 < \dots < ω^{3} + ω < \dots < ω^{3} + ω \cdot 2 < \dots < ω^{3} + ω^{2} < \dots <$

$ω^{3} \cdot 2 < ω^{3} \cdot 2 + 1 < \dots < ω^{3} \cdot 2 + ω < \dots < ω^{3} \cdot 2 + ω \cdot 2 < \dots < ω^{3} \cdot 2 + ω^{2} < \dots <$

$ω^{3} \cdot 3 < ω^{3} \cdot 3 + 1 < \dots < ω^{3} \cdot 3 + ω < \dots < ω^{3} \cdot 4 < ω^{3} \cdot 4 + 1 < \dots < ω^{3} \cdot 4 + ω < \dots <$

$⋮$

$ω^{3} \cdot ω = ω^{4} < ω^{4} + 1 < \dots < ω^{4} + ω < \dots < ω^{5} < ω^{5} + 1 < \dots < ω^{5} + ω < \dots <$

$ω^{ω} < ω^{ω} + 1 < \dots < ω^{ω} + ω < \dots < ω^{ω} \cdot 2 < \dots < ω^{ω} \cdot ω = ω^{ω + 1} < \dots < ω^{ω \cdot 2} < \dots <$

$ω^{ω^{2}} < \dots < ω^{ω^{3}} < \dots < ω^{ω^{ω}} < \dots < ω^{ω^{ω^{ω}}} < \dots < ϵ_{0} < \dots$

Cantor normal form (CNF):

$ω^{e_{1}} \cdot c_{1} + ω^{e_{2}} \cdot c_{2} + \dots + ω^{e_{k}} \cdot c_{k}$

where

$c_{1}, c_{2}, ..., c_{k}$ are positive integers,

$e_{1} > e_{2} > \dots > e_{k} \geq 0$ are themselves ordinals, recursively.

CNF is proper $\Leftrightarrow e_{1} < ω^{e_{1}}$ .

Side note about CNF: basically only exponentiation and addition; multiplication is redundant.

$ϵ_{0} =$ {all proper CNFs} is itself an ordinal, the smallest ordinal which cannot be defined explicitly using $+, \cdot, ˆ$ .

$ϵ_{0} = ω^{ω^{ω^{ω^{⋰}}}}$ is countable and the smallest ordinal $e$ such that $e = ω^{e}$ ; no $e$ in proper CNF satisfies this fixed point equation.

There are uncountably many ordinals larger than $ϵ_{0}$ , but the rest of this document focuses on a Maple package for ordinals in proper CNF, that is, ordinals that are smaller than $ϵ_{0}$ and their arithmetic.

Constructing ordinals

•	Load the Ordinals package to begin.

>	$with (Ordinals)$

$[`+`, `.`, `<`, <=, Add, Base, Dec, Decompose, Div, Eval, Factor, Gcd, Lcm, LessThan, Log, Max, Min, Mult, Ordinal, Power, Split, Sub, `^`, degree, lcoeff, \log, lterm, ω, quo, rem, tcoeff, tdegree, tterm]$

(1)

•	Use the Ordinal constructor to create the Cantor normal form of an ordinal.

>	$a := Ordinal ([[3, 1], [1, 2], [0, 3]])$

$a := ω^{3} + ω \cdot 2 + 3$

(2)

•	Every non-negative integer is an ordinal; no constructor call required.

$b := 2$

(3)

•	The export omega represents $ω$ . The following two assignments are equivalent.

$c := ω$

(4)

>	$c := Ordinal ([[1, 1]])$

$c := ω$

(5)

•	An ordinal with a non-integer exponent.

>	$d := Ordinal ([[ω, 3], [2, 5], [1, 1], [0, 4]])$

$d := ω^{ω} \cdot 3 + ω^{2} \cdot 5 + ω + 4$

(6)

•	The functions degree, (tdegree), and lcoeff, (tcoeff) return the leading (trailing) exponent and coefficient, respectively.

>	$degree (a), degree (b), degree (c), degree (d)$

$3, 0, 1, ω$

(7)

>	$tdegree (a), tdegree (b), tdegree (c), tdegree (d)$

$0, 0, 1, 0$

(8)

>	$lcoeff (a), lcoeff (b), lcoeff (c), lcoeff (d)$

$1, 2, 1, 3$

(9)

>	$tcoeff (a), tcoeff (b), tcoeff (c), tcoeff (d)$

$3, 2, 1, 4$

(10)

•	In Maple, the coefficients $c_{i}$ in the Cantor normal form of an ordinal can be parametric, which means, they may depend polynomially on variables, such as $x$ or $y_{2}$ , with positive integer coefficients. Each parameter like this is implicitly assumed to represent a non-negative integer.

>	$e := Ordinal ([[3, x], [2, x^{2} + x y + y^{2}], [0, z_{0}^{2} + 3]])$

$e := ω^{3} \cdot x + ω^{2} \cdot (x^{2} + x y + y^{2}) + (z_{0}^{2} + 3)$

(11)

•	The Eval command can be used to substitute integers or integer polynomials for some or all of the parameters.

>	$Eval (e, x = 0)$

$ω^{2} \cdot (y^{2}) + (z_{0}^{2} + 3)$

(12)

>	$Eval (e, [x = x + 1, y = 0, z_{0} = 0])$

$ω^{3} \cdot (x + 1) + ω^{2} \cdot (x^{2} + 2 x + 1) + 3$

(13)

Ordinal arithmetic

•	The functions Add, Mult, and Power implement addition, multiplication, and exponentiation of ordinals, respectively.

>	$Add (a, b), Mult (a, b), Power (a, b)$

$ω^{3} + ω \cdot 2 + 5, ω^{3} \cdot 2 + ω \cdot 2 + 3, ω^{6} + ω^{4} \cdot 2 + ω^{3} \cdot 3 + ω \cdot 2 + 3$

(14)

•	The operators +, . and ^ are overloaded for ordinals.

>	$b + a, b &period; a, b^{a}$

$ω^{3} + ω \cdot 2 + 3, ω^{3} + ω \cdot 2 + 6, ω^{ω^{2} + 2} \cdot 8$

(15)

•	There are inert versions of these operators, which are rendered in gray and are useful for display purposes.

>	$(a &+ b) &+ c = a + b + c$

$(ω^{3} + ω \cdot 2 + 3) + 2 + ω = ω^{3} + ω \cdot 3$

(16)

>	$(b &^c) &. a = b^{c} &period; a$

${(2)}^{ω} \cdot (ω^{3} + ω \cdot 2 + 3) = ω^{4} + ω^{2} \cdot 2 + ω \cdot 3$

(17)

•	Parametric ordinals can be used to illustrate the rules of ordinal arithmetic. All parameters are allowed to assume the value $0$ , you can add $1$ to the leading and trailing coefficients to ensure that they are nonzero for arbitrary non-negative integer values of the parameters.

>	$p := Ordinal ([[3, x_{3} + 1], [2, x_{2}], [1, x_{1}], [0, x_{0} + 1]])$

$p := ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(18)

>	$q := Ordinal ([[2, y_{2} + 1], [1, y_{1}], [0, y_{0} + 1]])$

$q := ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)$

(19)

•	For addition, terms of lower degree are absorbed from the left and appended from the right.

>	$p &+ q = p + q$

$(ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)) + (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) = ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot (x_{2} + y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)$

(20)

>	$q &+ p = q + p$

$(ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) + (ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)) = ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(21)

>	$q &+ z = q + z$

$(ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) + z = ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1 + z)$

(22)

Multiplication

•	For multiplication, if both arguments have a nonzero constant coefficient, the coefficients of the right factor appear on the left of the product, and vice versa.

>	$p := Ordinal ([[3, x_{3} + 1], [2, x_{2}], [1, x_{1}], [0, x_{0} + 1]])$

$p := ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(23)

>	$q := Ordinal ([[2, y_{2} + 1], [1, y_{1}], [0, y_{0} + 1]])$

$q := ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)$

(24)

>	$p &. q = p &period; q$

$(ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)) \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) = ω^{5} \cdot (y_{2} + 1) + ω^{4} \cdot y_{1} + ω^{3} \cdot (x_{3} y_{0} + x_{3} + y_{0} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(25)

>	$q &. p = q &period; p$

$(ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) \cdot (ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)) = ω^{5} \cdot (x_{3} + 1) + ω^{4} \cdot x_{2} + ω^{3} \cdot x_{1} + ω^{2} \cdot (y_{2} x_{0} + x_{0} + y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)$

(26)

•	In particular, multiplication of an ordinal with a nonzero constant coefficient by a positive constant $z + 1$ only affects the leading or constant coefficient, respectively, depending on the order.

>	$q &. (z + 1) = q &period; (z + 1)$

$(ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) \cdot (z + 1) = ω^{2} \cdot (y_{2} z + z + y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)$

(27)

>	$(z + 1) &. q = (z + 1) &period; q$

$(z + 1) \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) = ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} z + z + y_{0} + 1)$

(28)

•	Note that this is not universally valid for $z$ instead of $z + 1$ .

>	$z & &period; q = Eval (rhs (), z = z - 1)$

$z \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) = ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (z y_{0} + z)$

(29)

>	$0 &. q = 0 &period; q$

$0 \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1} + (y_{0} + 1)) = 0.$

(30)

•	If the factor on the right does not have a constant term, then it absorbs the factor on the left except for its leading power of $ω$ .

>	$p & &period; Eval (q, y_{0} = - 1) = p &period; Eval (q, y_{0} = - 1)$

$(ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)) \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1}) = ω^{5} \cdot (y_{2} + 1) + ω^{4} \cdot y_{1}$

(31)

>	$(z + 1) & &period; Eval (q, y_{0} = - 1) = (z + 1) &period; Eval (q, y_{0} = - 1)$

$(z + 1) \cdot (ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1}) = ω^{2} \cdot (y_{2} + 1) + ω \cdot y_{1}$

(32)

•	Some iterated products.

>	$b ≔ ω &period; 2 + 3$

$b := ω \cdot 2 + 3$

(33)

>	$b &^2 = b^{2}$

${(ω \cdot 2 + 3)}^{2} = ω^{2} \cdot 2 + ω \cdot 6 + 3$

(34)

>	$b &^3 = b^{3}$

${(ω \cdot 2 + 3)}^{3} = ω^{3} \cdot 2 + ω^{2} \cdot 6 + ω \cdot 6 + 3$

(35)

>	$b &^4 = b^{4}$

${(ω \cdot 2 + 3)}^{4} = ω^{4} \cdot 2 + ω^{3} \cdot 6 + ω^{2} \cdot 6 + ω \cdot 6 + 3$

(36)

>	$b &^10 = b^{10}$

${(ω \cdot 2 + 3)}^{10} = ω^{10} \cdot 2 + ω^{9} \cdot 6 + ω^{8} \cdot 6 + ω^{7} \cdot 6 + ω^{6} \cdot 6 + ω^{5} \cdot 6 + ω^{4} \cdot 6 + ω^{3} \cdot 6 + ω^{2} \cdot 6 + ω \cdot 6 + 3$

(37)

Powering

•	For exponentiation, only the base can be parametric but not the exponent.

>	$p := Ordinal ([[3, x_{3} + 1], [2, x_{2}], [1, x_{1}], [0, x_{0} + 1]])$

$p := ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(38)

>	$p &^3 = p^{3}$

${(ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1))}^{3} = ω^{9} \cdot (x_{3} + 1) + ω^{8} \cdot x_{2} + ω^{7} \cdot x_{1} + ω^{6} \cdot (x_{3} x_{0} + x_{0} + x_{3} + 1) + ω^{5} \cdot x_{2} + ω^{4} \cdot x_{1} + ω^{3} \cdot (x_{3} x_{0} + x_{0} + x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1)$

(39)

•	If the exponent does not have a constant term, then all coefficients of the base are ignored and so are all exponents except for the leading one, that is, the degree. (In the following example, the degree gets absorbed into the exponent as well, since $3 \cdot ω = ω$ .)

>	$p &^ω = p^{ω}$

${(ω^{3} \cdot (x_{3} + 1) + ω^{2} \cdot x_{2} + ω \cdot x_{1} + (x_{0} + 1))}^{ω} = ω^{ω}$

(40)

•	The only type of example for proper CNF ordinals where $e = b^{e}$ is when $b = z + 2$ is an integer $\geq 2$ and $e = ω$ .

>	$(z + 2) &^ω = {(z + 2)}^{ω}$

${((z + 2))}^{ω} = ω$

(41)

•	This equality is illustrated by writing non-negative integers in base $b$ representation, but in reverse order, with the least significant digit first. For example, if $z = 0$ and $b = 2$ :

$2^{ω} = 2^{0} \subseteq 2^{1} \subseteq 2^{2} \subseteq \dots$

$= \{(((\underset{0}{\underset{⏟}{0}} < \underset{1}{\underset{⏟}{2^{0}}}) < \underset{01}{\underset{⏟}{2^{1}}} < \underset{11}{\underset{⏟}{2^{0} + 2^{1}}}) < \underset{001}{\underset{⏟}{2^{2}}} < \underset{101}{\underset{⏟}{2^{0} + 2^{2}}} < \underset{011}{\underset{⏟}{2^{1} + 2^{2}}} < \underset{111}{\underset{⏟}{2^{0} + 2^{1} + 2^{2}}}) < \underset{0001}{\underset{⏟}{2^{3}}} < \dots\}$

•	Some iterated powers.

>	$Power (), Power (0), Power (0, 0), Power (0, 0, 0), Power (0, 0, 0, 0)$

$1, 0, 1, 0, 1$

(42)

>	$Power (), Power (2), Power (2, 2), Power (2, 2, 2), Power (2, 2, 2, 2)$

$1, 2, 4, 16, 65536$

(43)

>	$Power (2, 2, 2, 2, 2)$

$2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348[...19529 &DifferentialD;ⅈgⅈts...]5775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156736$

(44)

>	$b ≔ ω &period; 2 + 3$

$b := ω \cdot 2 + 3$

(45)

>	$b &^b = b^{b}$

${(ω \cdot 2 + 3)}^{ω \cdot 2 + 3} = ω^{ω \cdot 2 + 3} \cdot 2 + ω^{ω \cdot 2 + 2} \cdot 6 + ω^{ω \cdot 2 + 1} \cdot 6 + ω^{ω \cdot 2} \cdot 3$

(46)

>	$b &^(b &^b) = Power (b, b, b)$

${(ω \cdot 2 + 3)}^{{(ω \cdot 2 + 3)}^{ω \cdot 2 + 3}} = ω^{ω^{ω \cdot 2 + 3} \cdot 2 + ω^{ω \cdot 2 + 2} \cdot 6 + ω^{ω \cdot 2 + 1} \cdot 6 + ω^{ω \cdot 2} \cdot 3}$

(47)

>	$b &^(b &^(b &^b)) = Power (b, b, b, b)$

${(ω \cdot 2 + 3)}^{{(ω \cdot 2 + 3)}^{{(ω \cdot 2 + 3)}^{ω \cdot 2 + 3}}} = ω^{ω^{ω^{ω \cdot 2 + 3} \cdot 2 + ω^{ω \cdot 2 + 2} \cdot 6 + ω^{ω \cdot 2 + 1} \cdot 6 + ω^{ω \cdot 2} \cdot 3}}$

(48)

Subtraction and comparison

•	If $b \leq a$ , then there is a unique ordinal $c$ such that $b + c = a$ . This is computed using the Sub command.

>	$a := (ω^{2}) &period; 3 + ω &period; 2 + 1$

$a := ω^{2} \cdot 3 + ω \cdot 2 + 1$

(49)

>	$b := (ω^{2}) &period; 3 + ω + 3$

$b := ω^{2} \cdot 3 + ω + 3$

(50)

>	$a &- b = Sub (a, b)$

$(ω^{3} + ω \cdot 2 + 3) - (ω^{2} \cdot 3 + ω + 3) = ω^{3} + ω \cdot 2 + 3$

(51)

>	$a &- a = Sub (a, a)$

$(ω^{3} + ω \cdot 2 + 3) - (ω^{3} + ω \cdot 2 + 3) = 0$

(52)

•	If $a < b$ , then $Sub (a, b)$ returns $NULL$ .

>	$[Sub (b, a)]$

$[]$

(53)

•	The LessThan command and the < and <= operators compare two ordinals. $LessThan (a, b)$ and $a < b$ return false if and only if $Sub (a, b)$ returns $NULL$ .

>	$LessThan (a, b), LessThan (a, a), LessThan (b, a)$

$false, false, true$

(54)

>	$a < b, a < a, b < a$

$false, false, true$

(55)

>	$a \leq b, a \leq a, b \leq a$

$false, true, true$

(56)

•	The commands Max and Min return the largest and smallest element, respectively, in a sequence or list of ordinals.

>	$l := [a, ω, 2, b]$

$l := [ω^{3} + ω \cdot 2 + 3, ω, 2, ω^{2} \cdot 3 + ω + 3]$

(57)

>	$Max (l), Min (l)$

$ω^{3} + ω \cdot 2 + 3, 2$

(58)

>	$sort (l, LessThan)$

$[2, ω, ω^{2} \cdot 3 + ω + 3, ω^{3} + ω \cdot 2 + 3]$

(59)

Inverse operations

•	The Sub command performs subtraction on the left. It is a partial inverse of addition on the right: $Sub (b + c, b) = c$ for arbitrary ordinals $b$ and $c$ , and $b + Sub (a, b) = a$ if $b \leq a$ .

•	There is no inverse for addition on the left. The following example illustrates that a difference on the right is not unique in general.

>	$1 + ω = 2 + ω$

$ω = ω$

(60)

•	The following examples illustrate that even though $ω < ω + 1$ , there is no ordinal $c$ such that $c + ω = ω + 1$ .

>	$x &+ ω = x + ω$

$x + ω = ω$

(61)

>	$(ω &period; y + x) &+ ω = ω &period; y + x + ω$

$(ω \cdot y + x) + ω = ω \cdot (y + 1)$

(62)

>	$((ω^{2}) &period; z + ω &period; y + x) &+ ω = (ω^{2}) &period; z + ω &period; y + x + ω$

$(ω^{2} \cdot z + ω \cdot y + x) + ω = ω^{2} \cdot z + ω \cdot (y + 1)$

(63)

•	Another way to see this is that $c + ω$ does not have a largest element no matter what $c$ is, while $ω + 1$ does. Thus, a difference on the right does not exist in general.

•	The Div command performs division with remainder on the left, with a remainder that is smaller than the divisor.

>	$f := ω^{ω} &period; 2 + ω^{3} + (ω^{2}) &period; 3 + 5$

$f := ω^{ω} \cdot 2 + ω^{3} + ω^{2} \cdot 3 + 5$

(64)

>	$g := (ω^{2}) &period; 2 + ω + 3$

$g := ω^{2} \cdot 2 + ω + 3$

(65)

>	$q, r := Div (f, g)$

$q, r := ω^{ω} \cdot 2 + ω + 1, ω^{2} + 5$

(66)

>	$(g &. q) &+ r = g &period; q + r$

$(ω^{2} \cdot 2 + ω + 3) \cdot (ω^{ω} \cdot 2 + ω + 1) + (ω^{2} + 5) = ω^{ω} \cdot 2 + ω^{3} + ω^{2} \cdot 3 + 5$

(67)

$r < g$

$true$

(68)

•	The quotient and the remainder can be computed individually using the quo and rem commands, respectively.

>	$quo (f, g), rem (f, g)$

$ω^{ω} \cdot 2 + ω + 1, ω^{2} + 5$

(69)

•

Left division is a partial inverse of right multiplication: $quo (Mult (g, q), g) = q$ and $rem (Mult (g, q), g) = 0$ for arbitrary ordinals $g$ , $q$ , and if $rem (f, g) = 0$ , then $Mult (g, quo (f, g)) = f$ . Similar to addition, there is no unique inverse for left multiplication, that is, a right quotient, in general.

>	$2 &period; ω = 3 &period; ω$

$ω = ω$

(70)

Logarithms and base conversion

•	The $Log (f, g)$ command returns three ordinals: a logarithm $l$ , a quotient $0 < q < g$ and a remainder $r < g^{l}$ , such that $f = g^{l} \cdot q + r$ .

>	$f := ω^{ω} &period; 2 + ω^{3} + (ω^{2}) &period; 3 + 5$

$f := ω^{ω} \cdot 2 + ω^{3} + ω^{2} \cdot 3 + 5$

(71)

>	$g := (ω^{2}) &period; 2 + ω + 3$

$g := ω^{2} \cdot 2 + ω + 3$

(72)

>	$l, q, r := Log (f, g)$

$l, q, r := ω, 2, ω^{3} + ω^{2} \cdot 3 + 5$

(73)

>	$((g &^l) &. q) &+ r = g^{l} &period; q + r$

${(ω^{2} \cdot 2 + ω + 3)}^{ω} \cdot 2 + (ω^{3} + ω^{2} \cdot 3 + 5) = ω^{ω} \cdot 2 + ω^{3} + ω^{2} \cdot 3 + 5$

(74)

$q < g$

$true$

(75)

>	$r < g^{l}$

$true$

(76)

•	The logarithm is a partial inverse of exponentiation on the right:

$f = g^{l} \Leftrightarrow Log (f, g) = l, 1, 0,$ for arbitrary ordinals $f, g$ and $l$ .

Similar to addition and multiplication, there is in general no unique inverse for powering on the left.

>	$2^{ω} = 3^{ω}$

$ω = ω$

(77)

•

The Cantor normal form can be viewed as a base- $ω$ representation for ordinals. Repeated application of the Log command yields a base- $g$ representation for an arbitrary ordinal $g \geq 2$ . This is implemented in the Base command. If $g > ω$ , then the coefficients in that representation need not be integers.

>	$Base (f, g)$

$[[ω, 2], [1, ω + 1], [0, ω^{2} + 5]]$

(78)

>	$Base (f, g, output = inert)$

${(ω^{2} \cdot 2 + ω + 3)}^{ω} \cdot 2 + (ω^{2} \cdot 2 + ω + 3) \cdot (ω + 1) + (ω^{2} + 5)$

(79)

>	$value ()$

$ω^{ω} \cdot 2 + ω^{3} + ω^{2} \cdot 3 + 5$

(80)

>	$Base (f, ω, output = inert)$

${(ω)}^{ω} \cdot 2 + {(ω)}^{3} + {(ω)}^{2} \cdot 3 + 5$

(81)

•	In the binary representation, all nonzero coefficients are $1$ .

>	$Base (f, 2, output = inert)$

${(2)}^{ω^{2} + 1} + {(2)}^{ω \cdot 3} + {(2)}^{ω \cdot 2 + 1} + {(2)}^{ω \cdot 2} + {(2)}^{2} + 1$

(82)

>	$Base (f, 2)$

$[[ω^{2} + 1, 1], [ω \cdot 3, 1], [ω \cdot 2 + 1, 1], [ω \cdot 2, 1], [2, 1], [0, 1]]$

(83)

>	$map (z \to 2^{z_{1}},)$

$[ω^{ω} \cdot 2, ω^{3}, ω^{2} \cdot 2, ω^{2}, 4, 1]$

(84)

Gcd and factorization

•	The Div command implements left division with remainder, and therefore any two ordinals have a greatest common left divisor.

>	$u := ω^{ω} &period; (x + 1) + ω^{3} + (ω^{2}) &period; 3 + ω + 5$

$u := ω^{ω} \cdot (x + 1) + ω^{3} + ω^{2} \cdot 3 + ω + 5$

(85)

>	$v := (ω^{4}) &period; 2 + (ω^{2}) &period; 3 + ω + 5$

$v := ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5$

(86)

>	$g := Gcd (u, v)$

$g := ω^{2} \cdot 3 + ω + 5$

(87)

>	$rem (u, g), rem (v, g)$

$0, 0$

(88)

>	$u1, v1 := quo (u, g), quo (v, g)$

$u1, v1 := ω^{ω} \cdot (x + 1) + ω + 1, ω^{2} \cdot 2 + 1$

(89)

>	$g & &period; u1 = g &period; u1$

$(ω^{2} \cdot 3 + ω + 5) \cdot (ω^{ω} \cdot (x + 1) + ω + 1) = ω^{ω} \cdot (x + 1) + ω^{3} + ω^{2} \cdot 3 + ω + 5$

(90)

>	$g & &period; v1 = g &period; v1$

$(ω^{2} \cdot 3 + ω + 5) \cdot (ω^{2} \cdot 2 + 1) = ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5$

(91)

•

It is not a coincidence that the coefficients and exponents of the gcd and the last few coefficients of the two input polynomials agree. As discussed in the section Multiplication earlier, and as illustrated again by the last two examples, the coefficients and exponents of the left factor in a multiplication of two ordinals with nonzero constant coefficients reappear as the rightmost coefficients and exponents of the product. This is illustrated more clearly by factoring all the polynomials involved.

>	$Factor (u, output = inert)$

$5 \cdot {(ω + 1)}^{2} \cdot 3 \cdot (ω + 1) \cdot (ω^{ω} + 1) \cdot (x + 1)$

(92)

>	$Factor (v, output = inert)$

$5 \cdot {(ω + 1)}^{2} \cdot 3 \cdot (ω^{2} + 1) \cdot 2$

(93)

>	$Factor (g, output = inert)$

$5 \cdot {(ω + 1)}^{2} \cdot 3$

(94)

>	$Gcd (u1, v1)$

$1$

(95)

>	$Factor (u1, output = inert)$

$(ω + 1) \cdot (ω^{ω} + 1) \cdot (x + 1)$

(96)

>	$Factor (v1, output = inert)$

$(ω^{2} + 1) \cdot 2$

(97)

•	Any ordinal of the form $ω^{e} + 1$ with $e > 0$ is multiplicatively irreducible, since the product of two ordinals with nonzero constant coefficients and with at least two terms each has at least three terms.

•	For factoring an ordinal, first the trailing coefficient can be extracted on the left.

>	$q1, r1 := quo (v, 5), rem (v, 5)$

$q1, r1 := ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 1, 0$

(98)

•	For factoring an ordinal with the last two terms equal to $ω^{e} \cdot c + 1$ , where $e > 0$ and $c > 0$ , you can extract the irreducible factor $ω^{e} + 1$ on the right.

>	$q2, r2 := quo (q1, ω + 1), rem (q1, ω + 1)$

$q2, r2 := ω^{3} \cdot 2 + ω \cdot 3 + 1, 0$

(99)

•	If the trailing term $ω^{d}$ is not a constant (that is, if $d > 0$ ), it can be extracted as a left factor first, and the left quotient results by left subtracting $d$ from all exponents. So far, the partial factorization can be written as:

>	$v = (5 &. (ω + 1)) &. q2$

$ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5 = 5 \cdot (ω + 1) \cdot (ω^{3} \cdot 2 + ω \cdot 3 + 1)$

(100)

>	$value ()$

$ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5 = ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5$

(101)

•

Proceeding recursively with $q2$ gives the full factorization of $v$ below. In fact, the integer coefficients in the factored normal form are identical to the integer coefficients in the CNF, just in reverse order. The exponents in the factored normal form are the left differences (see section Subtraction and comparison earlier) of the exponents in the CNF, also in reverse order. In the following example, the coefficients in the CNF are $[2, 3, 1, 5]$ and the exponents are $[4, 2, 1, 0]$ :

$v$

$ω^{4} \cdot 2 + ω^{2} \cdot 3 + ω + 5$

(102)

>	$Factor (v)$

$[1, 5, ω + 1, 1, ω + 1, 3, ω^{2} + 1, 2]$

(103)

>	$Factor (v, output = inert)$

$5 \cdot {(ω + 1)}^{2} \cdot 3 \cdot (ω^{2} + 1) \cdot 2$

(104)

•	For ordinals without a constant term, factoring is not unique in general. As discussed in section Multiplication earlier, such an ordinal is left divisible by any ordinal of smaller degree, for example:

>	$inert := ((ω^{2}) &period; (x + 1) + ω &period; y + z) &. ω &colon;$ $inert = value (inert)$

$(ω^{2} \cdot (x + 1) + ω \cdot y + z) \cdot ω = ω^{3}$

(105)

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim