A package for ordinal numbers and their arithmetic
Accessing Ordinals Package Commands
List of Ordinals Package Commands
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 ϵ0, that is, ordinal numbers that can be obtained from non-negative integers and ω, the ordinal for the standard ordering of the natural numbers ℕ, 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 0<1<⋯<n−1 of numbers less than n. Infinite ordinals can be created using the Ordinal constructor. The constant omega represents the ordinal ω.
The ordinals themselves are well-ordered by the relation a≼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 e1,c1,...,ek,ck encoding its Cantor normal form ωe1⋅c1+⋯+ωek⋅ck, where k≥1 is an integer, e1≻⋯≻ek are ordinals (that is, non-negative integers, or recursively, ordinal data structures) and c1,...,ck are positive integers. See Ordinal for more details.
The access functions degree, lcoeff and lterm return e1, c1 and e1,c1, respectively. Similarly, the access functions tdegree, tcoeff and tterm return ek, ck and ek,ck, 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 c1,...,ck in the Cantor normal form may contain variables, such as x or y1, and depend on these polynomially with positive integer coefficients. For example, x2+2 is a valid parametric coefficient, but x2−2, x, and sin⁡x+13 are not. Currently, only the coefficients ci can be parametric; the exponents ei 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 x+2ω=ω is correct for all non-negative integer values of x, but neither xω=ω nor x+1ω=ω are universally valid, since 0ω=0 and 1ω=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.
a ≔ 2
b ≔ ω
c ≔ Ordinal⁡ω,1,2,3,0,5
Using inert operators for display. The inert addition operator &+ is rendered as a regular + but in grey. Also note that addition is non-commutative.
a &+ c=a+c
Adding more than two ordinals.
d ≔ a+c+b
Comparing and subtracting ordinals.
d &- c=Sub⁡d,c
Verify the result.
c &+ ω=c+ω
Multiplication and exponentiation.
c &. b=`.`⁡c,b
c &. b &. a=`.`⁡c,b,a
a &^ c=ac
Division, greatest common divisors.
e ≔ Ordinal⁡4,2,3,1,2,3,0,5
g ≔ Gcd⁡c,e
c1 ≔ quo⁡c,g
e1 ≔ quo⁡e,g
Verify the divisibility.
g &. c1=`.`⁡g,c1
g &. e1=`.`⁡g,e1
Verify the gcd property by factorization.
Parametric ordinals. The variables x,y,z below are parameters implicitly assumed to represent non-negative integers. Unless there is an error, the results below remain correct for arbitrary non-negative integer values of the parameters.
r ≔ ω+x &. ω+1:
Substitute a value for x.
r1 ≔ rx=1000|rx=1000:
p ≔ `.`⁡ω2,x+1+`.`⁡ω,y+z
Error, (in Ordinals:-Power) cannot determine if z is nonzero
Indeed, the result when z=0 looks very different:
The Ordinals package was introduced in Maple 2015.
For more information on Maple 2015 changes, see Updates in Maple 2015.
Download Help Document