[FOM] A New Ordinal Notation

[Dmytro Taranovsky]

Lew Gordeew wrote:
> What about ordinal notations which are not in the standard form? Does the
> system of ordinal notation include all terms of the algebra {0, C(-,-,-)} or
> only some of them (standard forms, say)?

Every term denotes an ordinal, but if unique representation is required,
then the standard form is chosen.  To convert C(a, b, c) to the standard
form, convert a, b, and c to the standard form.  Then, minimize c by
repeatedly replacing c given as C(d, e, f) with f whenever (d, e)<(a,
b).  
The only way I know to maximize b (if it is not already maximal) is to
go through every h=C(a, g, c) in the standard form with g simpler than
b, and find the least h for which the inequality h < C(a, b, c) fails. 
There should be a more efficient way.

> 
> > To compare d and e check whether d<e and whether e<d.
> 
> Does the remaining option refer to literal term-equality of standard
> forms, e=d?

If neither d<e nor e<d, then e and d denote the same ordinal.  Term
equality follows if e and d are in the standard form.

> > The algorithm terminates since the expressions will simplify at each
> > stage of the recursion.
> 
> How does this simplification work in (1) ?
> 
> > 1. C(a, b, c) < C(d, e, f) iff C(a, b, c) =< f or c < C(d, e, f)
> >    and (a,g) < (b, e) where g is the largest ordinal such that
> >    C(a, g, c) = C(a, b, c).

g = b whenever C(a, b, c) is in the standard form.

Also, pairs of ordinals are compared lexicographically.  For example,
(a, b) <= (d, e) iff a<=d or a=d and b<=e.  ("And" takes precedence over
"or".)

Although mathematical papers tend to omit the comparison algorithm for
ordinal notations, its inclusion adds understandability, clarity, and
certainty to the representation system and hence is important.

For reference, the ordinal notation is defined and described in
http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm

Sincerely,
Dmytro Taranovsky