7.4

## Lathe Ordinals

Lathe Ordinals for Racket provides data structures and utilities for managing ordinal numbers. Ordinal numbers are good for representing things that go on forever, and then some, and then keep going on forever again... and then a little more....

For instance, if you have some relational data with two numeric columns in it, then you might want to consider that pair of numbers to be ordered on those columns according to the progression (0, 0), (0, 1), (0, 2), and so on, then (1, 0), (1, 1), (1, 2), and so on, then (2, 0), (2, 1), (2, 2), and so on, and so on. (A lexicographic ordering.) If that sounds familiar, omega squared may be the ordinal for you.

Here’s how to count all the ordinals less than omega-squared: 0, 1, 2, and so on, then omega, (omega + 1), (omega + 2), and so on, then (omega * 2), ((omega * 2) + 1), ((omega * 2) + 2), and so on, and so on. This progression corresponds to all those number pairs. The first ordinal that doesn’t correspond to any of them is the next one, (omega ^ 2) itself.

The larger the ordinals get, the more challenging they are to completely model. In fact, one of the ways people study the relative strengh of mathematical foundations is by how large an ordinal each of those foundations can deal with (ordinal analysis). This library will never be able to explore all of them, and at the moment, this library reaches its limit at epsilon zero.

There are some slight variations on ordinals that make sense in slight variations of set theory, such as the constructive ordinals of constructive set theory. This library might never explore all of those either, and for now it’s concerned exclusively with the standard notion of ordinal familiar from ZFC set theory.

That’s a lot of talk about set theory and mathematical foundations, but this library is primarily intended for use as a number system for programmers to use, like libraries for floating point numbers or matrices.

### 1Ordinal numerals

 (require lathe-ordinals) package: lathe-ordinals-lib

This module provides data structures to represent the ordinal numbers of ZFC set theory that are less than or equal to epsilon zero. The ordinals less than epsilon zero are the earliest set of ordinals that contains omega and has full support for ordinal addition, multiplication, and exponentiation.

All the ordinals of this library can be compared using ‘equal?‘. Finite ordinals are represented using natural numbers (natural?).

 procedure v : any/c
Returns whether the given value is an ordinal number constructed by this library. All such ordinals are less than or equal to epsilon zero.

 procedure(onum
Returns whether the given value is an ordinal number strictly less than epsilon zero. These are the ordinal numbers that most of the arithmetic operations of this library are restricted to.

 procedure(onum->cnf n) → (listof (list/c onum
Given an ordinal less than epsilon zero, returns a list of the powers and coefficients of the ordinal in Cantor normal form.

Examples:
> (define omega-plus-four (onum-plus (onum-omega) 4))
> omega-plus-four

(onum-cnf "omega + 4")

> (onum->cnf omega-plus-four)

'((1 1) (0 4))

 > (define square-of-that (onum-times omega-plus-four omega-plus-four))
> square-of-that

(onum-cnf "omega^2 + omega * 4 + 4")

> (onum->cnf square-of-that)

'((2 1) (1 4) (0 4))

 procedure(onum-compare a b) → (or/c '< '= '>) a : onum<=e0? b : onum<=e0?
Returns the symbol '< if the numbers are provided in ascending order, '= if they’re equal, and '> if they’re in descending order.

 procedure n : onum<=e0?
Returns a flat contract that requires the input to be an ordinal number strictly less than n.

 procedure
Returns the ordinal number omega. Every ordinal less than omega is a natural number.

 procedure
Returns the ordinal number epsilon zero, the first infinite ordinal that can’t be arrived at by exponentiation, multiplication, and addition.

 procedure(nat->onum n) → onum? n : natural?
Returns an ordinal number corresponding to the given natural number.

 procedure ns : (or/c (list/c) (*list/c onum
Adds up the given ordered list of ordinal numbers.

 procedure ns : (or/c (list/c) (*list/c onum
Multiplies the given ordered list of ordinal numbers.

### 2Ordinal-indexed lists

 (require lathe-ordinals/olist) package: lathe-ordinals-lib

This module provides a lazy list data structure that can have length less than or equal to epsilon zero. Most of what you can do with these lazy lists, you can do just by writing a function that takes an ordinal number as its argument. The difference has to do with garbage collection: These lists are designed so that if you append and remove an element, you can be sure that the diminished list no longer contains a reference to it.

 procedure v : any/c
Returns whether the given value is an ordinal-indexed list constructed by this library. Every such list has a length no greater than epsilon zero.

 procedure v : any/c
Returns whether the given value is an ordinal-indexed list with length strictly less than epsilon zero.

 procedure
Returns an empty ordinal-indexed list.

 procedure(olist-build len index->element) → olist<=e0? len : onum<=e0? index->element : (-> (onum
Returns an ordinal-indexed list of the given length, which computes each element by passing the element’s index to the given procedure.