[FOM] A New Ordinal Notation

Lew Gordeew legor at gmx.de
Tue Aug 16 04:26:23 EDT 2005

 Dmytro Taranovsky wrote:

> The description under the heading "Comparison Relation" in my paper
> http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
> leads naturally to a recursive algorithm that checks whether the
> ordinals are given in the standard form, and if so, compares them.

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)?

> To compare d and e check whether d<e and whether e<d.

Does the remaining option refer to literal term-eqiality of standard
forms, e=d?

> To check whether d<e, verify that 'd' is in the standard form and then
> use (1) (see the paper).
> Let d be given as C(a, b, c).  To verify that d is in the standard form,
> verify that b and c are in the standard form, and then verify that b is
> maximal and c is minimal. To verify that c is minimal, apply (3).  To
> verify that b is maximal,  apply (4) and (5).  
> Note that being in  the standard form guarantees the maximality and the
> minimality in (1), (3), and (5).  To avoid infinite regress, when asked
> to check for a strict inequality, check only for the strict inequality
> as opposed to doing the full comparison.
> 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).
>    Note: (a, b) < (c, d) iff a<c or a=c and b<d.
>    Note: g is also the least ordinal >= b that is in H(b, C(a, b, c)).
>    g exists iff some ordinal >= b has representation in terms of
>    ordinals less than C(a, b, c). If g does not exist, let
>    (a, g) < (c, d) be true iff a<c.

What else is known about "simple" g ?
Besides, (a, b) =< (d, e) used in (3) was not explained in the paper.


Lust, ein paar Euro nebenbei zu verdienen? Ohne Kosten, ohne Risiko!
Satte Provisionen für GMX Partner: http://www.gmx.net/de/go/partner

More information about the FOM mailing list