The Ordinals package is a collection of commands for computing with ordinal numbers in Cantor normal form. Mathematically, an ordinal number, or ordinal for short, represents an isomorphism class of well-orderings. The Ordinals package can represent and handle all ordinals less than ${\mathrm{ϵ}}_0$, that is, ordinal numbers that can be obtained from non-negative integers and $\mathbf{\omega }$, the ordinal for the standard ordering of the natural numbers $\mathbb{N}$, in a finite number of steps by ordinal addition, multiplication and exponentiation.

Every non-negative integer $n$ is an ordinal, representing the finite well-ordered set $\left\{0<1<\cdots <n-1\right\}$ of numbers less than $n$. Infinite ordinals can be created using the Ordinal constructor. The constant omega represents the ordinal $\mathbf{\omega }$.

The ordinals themselves are well-ordered by the relation $a\preccurlyeq b$ meaning that the well-ordering represented by $a$ is order-isomorphic to an initial segment of the well-ordering represented by $b$. See LessThan for more details.

The data structure for an infinite ordinal is basically a list of pairs $\left[\left[e_1\&comma;c_1\right]\&comma;\mathrm{...}\&comma;\left[e_k\&comma;c_k\right]\right]$ encoding its Cantor normal form ${\mathbf{\omega }}^{e_1}\cdot c_1\&plus;\cdots \&plus;{\mathbf{\omega }}^{e_k}\cdot c_k$, where $k\ge 1$ is an integer, $e_1\succ \cdots \succ e_k$ are ordinals (that is, non-negative integers, or recursively, ordinal data structures) and $c_1,\mathrm{...},c_k$ are positive integers. See Ordinal for more details.

The access functions degree, lcoeff and lterm return $e_1$, $c_1$ and $\left[e_1\&comma;c_1\right]$, respectively. Similarly, the access functions tdegree, tcoeff and tterm return $e_k$, $c_k$ and $\left[e_k\&comma;c_k\right]$, respectively.

The basic arithmetic operations for ordinals are addition, multiplication, and exponentiation. Their corresponding inverse operations are left subtraction, left division, and logarithm, respectively. Other operations implemented include maximum and minimum, greatest common left divisors and least common right multiples, and factorization.

The arithmetic operators +, ., ^ and the relational operators < and <= are overloaded for ordinals, and they cause the corresponding commands Add, Mult, Power and LessThan, respectively, to be executed. Note that + is not a commutative operator for ordinals. In addition, the package also recognizes inactive or inert versions of these operators, namely, &+, &., &^, &-, &<, &>, &<=, and &>=. Such inactive operators do not result in any computations and are useful for display purposes. The value command turns these inert operators into their active forms.

The Ordinals package allows ordinals to be parametric. This means that the coefficients $c_1,\mathrm{...},c_k$ in the Cantor normal form may contain variables, such as $x$ or $y_1$, and depend on these polynomially with positive integer coefficients. For example, $x^2+2$ is a valid parametric coefficient, but $x^2-2$, $\sqrt{x}$, and $\sin \left(x\right)+\frac{1}{3}$ are not. Currently, only the coefficients $c_i$ can be parametric; the exponents $e_i$ cannot contain any parameters.

All parameters are implicitly assumed to represent non-negative integers. Each command in the Ordinals package guarantees that the results it returns are correct when arbitrary non-negative integers are substituted for some or all of the parameters. If such a universally valid result cannot be computed, an error will be raised. For example, if $x$ is a parameter, then ${\left(x\&plus;2\right)}^{\mathbf{\omega }}\&equals;\mathbf{\omega }$ is correct for all non-negative integer values of $x$, but neither $x^{\mathbf{\omega }}\&equals;\mathbf{\omega }$ nor ${\left(x\&plus;1\right)}^{\mathbf{\omega }}\&equals;\mathbf{\omega }$ are universally valid, since $0^{\mathbf{\omega }}\&equals;0$ and $1^{\mathbf{\omega }}\&equals;1$.

The Eval command can be used to substitute integer values or polynomial expressions for some or all of the parameters in a parametric ordinal.

Each command in the Ordinals package can be accessed by using either the long form or the short form of the command name in the command calling sequence.

The long form, Ordinals:-command, is always available. The short form can be used after loading the package.

The following is a list of commands available in the Ordinals package.

To display the help page for a particular Ordinals command, see Getting Help with a Command in a Package.

$\mathrm{with}\left(\mathrm{Ordinals}\right)$

$\left[\mathrm{`+`}\&comma;\mathrm{`.`}\&comma;\mathrm{`<`}\&comma;\mathrm{<=}\&comma;\mathrm{Add}\&comma;\mathrm{Base}\&comma;\mathrm{Dec}\&comma;\mathrm{Decompose}\&comma;\mathrm{Div}\&comma;\mathrm{Eval}\&comma;\mathrm{Factor}\&comma;\mathrm{Gcd}\&comma;\mathrm{Lcm}\&comma;\mathrm{LessThan}\&comma;\mathrm{Log}\&comma;\mathrm{Max}\&comma;\mathrm{Min}\&comma;\mathrm{Mult}\&comma;\mathrm{Ordinal}\&comma;\mathrm{Power}\&comma;\mathrm{Split}\&comma;\mathrm{Sub}\&comma;\mathrm{`^`}\&comma;\mathrm{degree}\&comma;\mathrm{lcoeff}\&comma;\log \&comma;\mathrm{lterm}\&comma;\mathrm{\omega }\&comma;\mathrm{quo}\&comma;\mathrm{rem}\&comma;\mathrm{tcoeff}\&comma;\mathrm{tdegree}\&comma;\mathrm{tterm}\right]$

$a≔2$

$a≔2$

$b≔\mathrm{\omega }$

$b≔\mathbf{\omega }$

$c≔\mathrm{Ordinal}\left(\left[\left[\mathrm{\omega }\&comma;1\right]\&comma;\left[2\&comma;3\right]\&comma;\left[0\&comma;5\right]\right]\right)$

$c≔{\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$\mathrm{type}\left(a\&comma;\mathrm{ordinal}\right),\mathrm{type}\left(b\&comma;\mathrm{ordinal}\right),\mathrm{type}\left(c\&comma;\mathrm{ordinal}\right)$

$\mathrm{false},\mathrm{true},\mathrm{true}$

$\mathrm{degree}\left(a\right),\mathrm{degree}\left(b\right),\mathrm{degree}\left(c\right)$

$0,1,\mathbf{\omega }$

$\mathrm{lcoeff}\left(a\right),\mathrm{lcoeff}\left(b\right),\mathrm{lcoeff}\left(c\right)$

$2,1,1$

$\mathrm{tterm}\left(a\right),\mathrm{tterm}\left(b\right),\mathrm{tterm}\left(c\right)$

$\left[0\&comma;2\right],\left[1\&comma;1\right],\left[0\&comma;5\right]$

$\mathrm{Add}\left(c\&comma;a\right)=c+a$

${\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;7={\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;7$

$a\&+c=a+c$

$2\mathbf{\&plus;}\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5\right)={\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$d≔a+c+b$

$d≔{\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;\mathbf{\omega }$

$\mathrm{LessThan}\left(c\&comma;d\right),c<d$

$\mathrm{true},\mathrm{true}$

$d\&-c=\mathrm{Sub}\left(d\&comma;c\right)$

$\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;\mathbf{\omega }\right)\mathbf{-}\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5\right)=\mathbf{\omega }$

$c\&+\mathrm{\omega }=c+\mathrm{\omega }$

$\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5\right)\mathbf{\&plus;}\mathbf{\omega }={\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;\mathbf{\omega }$

$\mathrm{Mult}\left(b\&comma;c\right)=b·c$

${\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^3\cdot 3\&plus;\mathbf{\omega }\cdot 5={\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^3\cdot 3\&plus;\mathbf{\omega }\cdot 5$

$c\&.b=c·b$

$\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5\right)\mathbf{\cdot }\mathbf{\omega }={\mathbf{\omega }}^{\mathbf{\omega }\&plus;1}$

$\left(c\&.b\right)\&.a=c·b·a$

$\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5\right)\mathbf{\cdot }\mathbf{\omega }\mathbf{\cdot }2={\mathbf{\omega }}^{\mathbf{\omega }\&plus;1}\cdot 2$

$\mathrm{Power}\left(c\&comma;a\right)=c^a$

${\mathbf{\omega }}^{\mathbf{\omega }\cdot 2}\&plus;{\mathbf{\omega }}^{\mathbf{\omega }\&plus;2}\cdot 3\&plus;{\mathbf{\omega }}^{\mathbf{\omega }}\cdot 5\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5={\mathbf{\omega }}^{\mathbf{\omega }\cdot 2}\&plus;{\mathbf{\omega }}^{\mathbf{\omega }\&plus;2}\cdot 3\&plus;{\mathbf{\omega }}^{\mathbf{\omega }}\cdot 5\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$a\&ˆc=a^c$

${\left(2\right)}^{{\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5}={\mathbf{\omega }}^{{\mathbf{\omega }}^{\mathbf{\omega }}\&plus;\mathbf{\omega }\cdot 3}\cdot 32$

$e≔\mathrm{Ordinal}\left(\left[\left[4\&comma;2\right]\&comma;\left[3\&comma;1\right]\&comma;\left[2\&comma;3\right]\&comma;\left[0\&comma;5\right]\right]\right)$

$e≔{\mathbf{\omega }}^4\cdot 2\&plus;{\mathbf{\omega }}^3\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$g≔\mathrm{Gcd}\left(c\&comma;e\right)$

$g≔{\mathbf{\omega }}^2\cdot 3\&plus;5$

$\mathrm{c1}≔\mathrm{quo}\left(c\&comma;g\right)$

$\mathrm{c1}≔{\mathbf{\omega }}^{\mathbf{\omega }}\&plus;1$

$\mathrm{e1}≔\mathrm{quo}\left(e\&comma;g\right)$

$\mathrm{e1}≔{\mathbf{\omega }}^2\cdot 2\&plus;\mathbf{\omega }\&plus;1$

$\mathrm{rem}\left(c\&comma;g\right),\mathrm{rem}\left(e\&comma;g\right)$

$0,0$

$g\&.\mathrm{c1}=g·\mathrm{c1}$

$\left({\mathbf{\omega }}^2\cdot 3\&plus;5\right)\mathbf{\cdot }\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;1\right)={\mathbf{\omega }}^{\mathbf{\omega }}\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$g\&.\mathrm{e1}=g·\mathrm{e1}$

$\left({\mathbf{\omega }}^2\cdot 3\&plus;5\right)\mathbf{\cdot }\left({\mathbf{\omega }}^2\cdot 2\&plus;\mathbf{\omega }\&plus;1\right)={\mathbf{\omega }}^4\cdot 2\&plus;{\mathbf{\omega }}^3\&plus;{\mathbf{\omega }}^2\cdot 3\&plus;5$

$\mathrm{Factor}\left(c\&comma;\mathrm{output}=\mathrm{inert}\right)$

$5\mathbf{\cdot }\left({\mathbf{\omega }}^2\&plus;1\right)\mathbf{\cdot }3\mathbf{\cdot }\left({\mathbf{\omega }}^{\mathbf{\omega }}\&plus;1\right)$

$\mathrm{Factor}\left(e\&comma;\mathrm{output}=\mathrm{inert}\right)$

$5\mathbf{\cdot }\left({\mathbf{\omega }}^2\&plus;1\right)\mathbf{\cdot }3\mathbf{\cdot }{\left(\mathbf{\omega }\&plus;1\right)}^2\mathbf{\cdot }2$

$\mathrm{Factor}\left(g\&comma;\mathrm{output}=\mathrm{inert}\right)$

$5\mathbf{\cdot }\left({\mathbf{\omega }}^2\&plus;1\right)\mathbf{\cdot }3$

$\mathrm{value}\left(\right)$

${\mathbf{\omega }}^2\cdot 3\&plus;5$

$\mathrm{Factor}\left(\mathrm{c1}\&comma;\mathrm{output}=\mathrm{inert}\right)$

${\mathbf{\omega }}^{\mathbf{\omega }}\&plus;1$

$\mathrm{Factor}\left(\mathrm{e1}\&comma;\mathrm{output}=\mathrm{inert}\right)$

${\left(\mathbf{\omega }\&plus;1\right)}^2\mathbf{\cdot }2$

$\mathrm{Gcd}\left(\mathrm{c1}\&comma;\mathrm{e1}\right)$

$1$

$r≔\left(\mathrm{\omega }+x\right)\&.\left(\mathrm{\omega }+1\right)\&colon;$

$r=\mathrm{value}\left(r\right)$

$\left(\mathbf{\omega }\&plus;x\right)\mathbf{\cdot }\left(\mathbf{\omega }\&plus;1\right)={\mathbf{\omega }}^2\&plus;\mathbf{\omega }\&plus;x$

$\mathrm{r1}≔\mathrm{Eval}\left(r\&comma;x=1000\right)\&colon;$

$\mathrm{r1}=\mathrm{value}\left(\mathrm{r1}\right)$

$\left(\mathbf{\omega }\&plus;1000\right)\mathbf{\cdot }\left(\mathbf{\omega }\&plus;1\right)={\mathbf{\omega }}^2\&plus;\mathbf{\omega }\&plus;1000$

$p≔{\mathrm{\omega }}^2·\left(x+1\right)+\mathrm{\omega }·y+z$

$p≔{\mathbf{\omega }}^2\cdot \left(x+1\right)\&plus;\mathbf{\omega }\cdot y\&plus;z$

$p^3$

Error, (in Ordinals:-Power) cannot determine if z is nonzero

${\left(\mathrm{Eval}\left(p\&comma;z=z+1\right)\right)}^3$

${\mathbf{\omega }}^6\cdot \left(x+1\right)\&plus;{\mathbf{\omega }}^5\cdot y\&plus;{\mathbf{\omega }}^4\cdot \left(xz+x+z+1\right)\&plus;{\mathbf{\omega }}^3\cdot y\&plus;{\mathbf{\omega }}^2\cdot \left(xz+x+z+1\right)\&plus;\mathbf{\omega }\cdot y\&plus;\left(z+1\right)$

${\left(\mathrm{Eval}\left(p\&comma;z=0\right)\right)}^3$

${\mathbf{\omega }}^6\cdot \left(x+1\right)\&plus;{\mathbf{\omega }}^5\cdot y$

The Ordinals package was introduced in Maple 2015.

For more information on Maple 2015 changes, see Updates in Maple 2015.