omega - Maple Help

Ordinals[Ordinal]

construct ordinal number data structure

Ordinals[omega]

ordinal for natural numbers

type/ordinal

check for an ordinal

 Calling Sequence Ordinal(c) Ordinal([[e1,c1], [e2,c2], ...]) omega type(a, ordinal)

Parameters

 c, c1, c2, ... - non-negative integers or polynomials with positive integer coefficients e1, e2, ... - ordinals or non-negative integers a - any expression

Returns

 • The Ordinal calling sequences return either a non-negative integer, a polynomial with positive integer coefficients, or an ordinal data structure.
 • The omega calling sequence returns the ordinal data structure ORDINAL([[1,1]]) representing the natural numbers.
 • The type(a, ordinal) calling sequence returns either true or false.

Description

 • A (non-parametric) ordinal number is represented either by a non-negative integer or by an ordinal data structure in Cantor normal form. The second option is of the form:

$\mathrm{ORDINAL}\left(\left[\left[{e}_{1},{c}_{1}\right],\left[{e}_{2},{c}_{2}\right],\mathrm{...}\right]\right)$

 where ORDINAL is a literal keyword, e1,e2,... are non-negative integers or themselves ordinal data structures, recursively, and c1,c2,... are positive integers. This represents the ordinal number:

${\mathbf{\omega }}^{{e}_{1}}\cdot {c}_{1}+{\mathbf{\omega }}^{{e}_{2}}\cdot {c}_{2}+\cdots$

 where $\mathbf{\omega }$ is the ordinal representing the natural numbers $ℕ$ equipped with their standard ordering.
 • Moreover, the exponents are sorted, that is, ${e}_{1}\succ {e}_{2}\succ \cdots$, where $\succ$ is the (strict) ordering of ordinals.
 • Finally, there must be at least one term [e1,c1], and e1 cannot be zero - an ordinal that is actually a non-negative integer is represented as such and not by an ordinal data structure.
 • The Ordinal command constructs such an ordinal data structure. It is recommended to always use this constructor and not form the data structure directly using the ORDINAL keyword. It is safer to use the Ordinal command because it ensures that the result is a valid ordinal data structure.
 • The omega calling sequence creates and returns an ordinal data structure, namely, ORDINAL([[1,1]]), for $\mathbf{\omega }$ itself.
 • The type(a, ordinal) calling sequence checks whether a is an ordinal data structure of the form described above, and if so, returns true, and otherwise false. In particular, the return value is false if a is a non-negative integer.
 • The Ordinals package can only handle (and the Ordinal constructor can only form) ordinal numbers smaller than ${\mathrm{ϵ}}_{0}$, that is, ordinal numbers that can be constructed from $\mathbf{\omega }$ and positive integers in a finite number of steps by ordinal addition, multiplication, and exponentiation.
 • In addition to the non-parametric ordinals described earlier, the Ordinals package can also handle parametric ordinals. These are ordinals where the coefficients ci may contain parameters, that is, names, such as $x$ or ${y}_{2}$, occurring polynomially and with positive integer coefficients. The Ordinal command allows the construction of a parametric ordinal.
 • All parameters are implicitly assumed to represent non-negative integers.
 • A parametric coefficient ci in an ordinal data structure is always in expanded form.
 • Currently the exponents ei cannot be parametric, and if they are themselves ordinals, their coefficients cannot contain parameters, either.
 • The type(a, ordinal) calling sequence checks if a is a valid (possibly parametric) ordinal data structure, and returns true if that is the case and false otherwise. If a is an integer or a polynomial with positive integer coefficients, the result is false.
 • If the argument to the Ordinal command represents an ordinal smaller than $\mathbf{\omega }$, that is, a non-negative integer, then the return value is not an ordinal data structure but either a non-negative integer, if there are no parameters, or a polynomial in the parameters with positive integer coefficients. In particular, when the Ordinal(c) calling sequence is used, where c is a non-negative integer or a polynomial with positive integer coefficients, then the return value is c.

Examples

 > $\mathrm{with}\left(\mathrm{Ordinals}\right)$
 $\left[{\mathrm{+}}{,}{\mathrm{.}}{,}{\mathrm{<}}{,}{\mathrm{<=}}{,}{\mathrm{Add}}{,}{\mathrm{Base}}{,}{\mathrm{Dec}}{,}{\mathrm{Decompose}}{,}{\mathrm{Div}}{,}{\mathrm{Eval}}{,}{\mathrm{Factor}}{,}{\mathrm{Gcd}}{,}{\mathrm{Lcm}}{,}{\mathrm{LessThan}}{,}{\mathrm{Log}}{,}{\mathrm{Max}}{,}{\mathrm{Min}}{,}{\mathrm{Mult}}{,}{\mathrm{Ordinal}}{,}{\mathrm{Power}}{,}{\mathrm{Split}}{,}{\mathrm{Sub}}{,}{\mathrm{^}}{,}{\mathrm{degree}}{,}{\mathrm{lcoeff}}{,}{\mathrm{log}}{,}{\mathrm{lterm}}{,}{\mathrm{\omega }}{,}{\mathrm{quo}}{,}{\mathrm{rem}}{,}{\mathrm{tcoeff}}{,}{\mathrm{tdegree}}{,}{\mathrm{tterm}}\right]$ (1)
 > $\mathrm{o0}≔\mathrm{Ordinal}\left(\left[\left[2,2\right],\left[1,3\right],\left[0,4\right]\right]\right)$
 ${\mathrm{o0}}{≔}{{\mathbf{\omega }}}^{{2}}{\cdot }{2}{+}{\mathbf{\omega }}{\cdot }{3}{+}{4}$ (2)
 > $\mathrm{lprint}\left(\mathrm{o0}\right):$
 ORDINAL([[2, 2], [1, 3], [0, 4]])
 > $\mathrm{Ordinal}\left(\left[\left[1,1\right]\right]\right)=\mathrm{\omega }$
 ${\mathbf{\omega }}{=}{\mathbf{\omega }}$ (3)

Coefficients that are $0$ are removed automatically.

 > $\mathrm{Ordinal}\left(\left[\left[3,0\right],\left[2,2\right],\left[1,0\right],\left[0,4\right]\right]\right)$
 ${{\mathbf{\omega }}}^{{2}}{\cdot }{2}{+}{4}$ (4)

Terms out of order are removed as well; smaller terms from the left are absorbed by larger terms from the right.

 > $\mathrm{Ordinal}\left(\left[\left[4,3\right],\left[2,2\right],\left[3,1\right],\left[0,5\right]\right]\right)$
 ${{\mathbf{\omega }}}^{{4}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{3}}{+}{5}$ (5)

After removal of out-of-order terms, the coefficients of neighboring terms with the same exponents are combined additively.

 > $\mathrm{o1}≔\mathrm{Ordinal}\left(\left[\left[4,3\right],\left[3,2\right],\left[2,2\right],\left[3,1\right],\left[3,4\right],\left[2,3\right],\left[0,5\right]\right]\right)$
 ${\mathrm{o1}}{≔}{{\mathbf{\omega }}}^{{4}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{3}}{\cdot }{7}{+}{{\mathbf{\omega }}}^{{2}}{\cdot }{3}{+}{5}$ (6)

If, after all of the above simplifications, what remains represents a non-negative integer, it will be converted into one.

 > $\mathrm{o2}≔\mathrm{Ordinal}\left(\left[\left[0,3\right],\left[2,0\right],\left[0,4\right]\right]\right)$
 ${\mathrm{o2}}{≔}{7}$ (7)
 > $\mathrm{type}\left(\mathrm{o1},\mathrm{ordinal}\right)$
 ${\mathrm{true}}$ (8)
 > $\mathrm{type}\left(\mathrm{o2},\mathrm{ordinal}\right)$
 ${\mathrm{false}}$ (9)
 > $\mathrm{Ordinal}\left(\left[\right]\right)$
 ${0}$ (10)

Exponents can be ordinals themselves.

 > $\mathrm{o3}≔\mathrm{Ordinal}\left(\left[\left[\mathrm{o1},3\right],\left[2,1\right],\left[1,4\right]\right]\right)$
 ${\mathrm{o3}}{≔}{{\mathbf{\omega }}}^{{{\mathbf{\omega }}}^{{4}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{3}}{\cdot }{7}{+}{{\mathbf{\omega }}}^{{2}}{\cdot }{3}{+}{5}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{2}}{+}{\mathbf{\omega }}{\cdot }{4}$ (11)
 > $\mathrm{o4}≔\mathrm{Ordinal}\left(\left[\left[\mathrm{o3},1\right],\left[\mathrm{o1},2\right],\left[1,3\right],\left[0,4\right]\right]\right)$
 ${\mathrm{o4}}{≔}{{\mathbf{\omega }}}^{{{\mathbf{\omega }}}^{{{\mathbf{\omega }}}^{{4}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{3}}{\cdot }{7}{+}{{\mathbf{\omega }}}^{{2}}{\cdot }{3}{+}{5}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{2}}{+}{\mathbf{\omega }}{\cdot }{4}}{+}{{\mathbf{\omega }}}^{{{\mathbf{\omega }}}^{{4}}{\cdot }{3}{+}{{\mathbf{\omega }}}^{{3}}{\cdot }{7}{+}{{\mathbf{\omega }}}^{{2}}{\cdot }{3}{+}{5}}{\cdot }{2}{+}{\mathbf{\omega }}{\cdot }{3}{+}{4}$ (12)
 > $\mathrm{type}\left(\mathrm{o3},\mathrm{ordinal}\right),\mathrm{type}\left(\mathrm{o4},\mathrm{ordinal}\right)$
 ${\mathrm{true}}{,}{\mathrm{true}}$ (13)
 > $\mathrm{lprint}\left(\mathrm{o4}\right):$
 ORDINAL([[ORDINAL([[ORDINAL([[4, 3], [3, 7], [2, 3], [0, 5]]), 3], [2, 1], [1, 4]]), 1], [ORDINAL([[4, 3], [3, 7], [2, 3], [0, 5]]), 2], [1, 3], [0, 4]])

An ordinal with two parameters.

 > $\mathrm{o5}≔\mathrm{Ordinal}\left(\left[\left[\mathrm{\omega },x\left(x+y\right)\right],\left[2,{y}^{2}+1\right],\left[0,4\right]\right]\right)$
 ${\mathrm{o5}}{≔}{{\mathbf{\omega }}}^{{\mathbf{\omega }}}{\cdot }\left({{x}}^{{2}}{+}{x}{}{y}\right){+}{{\mathbf{\omega }}}^{{2}}{\cdot }\left({{y}}^{{2}}{+}{1}\right){+}{4}$ (14)
 > $\mathrm{type}\left(\mathrm{o5},\mathrm{ordinal}\right)$
 ${\mathrm{true}}$ (15)

Neither coefficients nor exponents can be negative.

 > $\mathrm{Ordinal}\left(\left[\left[3,2\right],\left[1,-5\right]\right]\right)$
 > $\mathrm{Ordinal}\left(\left[\left[3,2\right],\left[1,x-5\right]\right]\right)$
 > $\mathrm{Ordinal}\left(\left[\left[3,2\right],\left[-1,5\right]\right]\right)$

Exponents cannot contain parameters.

 > $\mathrm{Ordinal}\left(\left[\left[\mathrm{o5},2\right],\left[3,1\right]\right]\right)$

Compatibility

 • The Ordinals[Ordinal], Ordinals[omega] and type/ordinal commands were introduced in Maple 2015.