[FOM] Ordinal notations]

[doner@math.ucsb.edu]

Yes, there is a notation system that should do what you want.  See the
paper of myself and Tarski "An extended arithmetic of ordinal numbers",
Fund. Math. v.65:p95-127.  There the basics of a hierarchy of ordinal
functions are developed.  The whole thing is worked out in much more
detail in my paper "Definability in the extended arithmetic of ordinal
numbers",
Dissertationes Math. 96 (1972).  More on the metamathematics of the system
was included in my Ph.D. dissertation, unpublished.  There are no gaps of
the type you refer to in this hierarchy, although it's reach for
definibility does end somewhere, at gamma_0 I think.

John Doner

---------------------------- Original Message ----------------------------
Subject: [FOM] Ordinal notations
From:    "Bill Taylor" <W.Taylor at math.canterbury.ac.nz>
Date:    Fri, May 19, 2006 2:08 am
To:      fom at cs.nyu.edu
--------------------------------------------------------------------------

I've been looking closely at notations for ordinals up to gamma_0.


I think I understand the definition of phi( - , - ) well enough,
and see how it gets to gamma_0.

However, I feel that to really understand an ordinal fully, it is
also a good idea to know what "all" the ordinals below it look like, and
how to order them easily from some suitable notation for them.

Now it seems easy enough to do this up to epsilon_0.
e.g. a "typical" element of  w^w  is  (w^i + w^j + ... + w^n)
for natural numbers  i >= j >= ... >= n >= 0.

(Allowing >= rather than > means we don't have to bother putting
the other natural numbers on the right of each term).
Ordering these is trivial.

Next, w^w^w  has a "typical element" like

            w^(term_1) + w^(term_2) + ... + w^(term_n)

where each term is an expression of the first-mentioned sort.

And so on for higher towers of omegas.  Until finally we see that
a "typical element" of eps_0 is just a sum of tower-terms like
the above, with no restriction on the height of the towers,
(all heights finite OC).
Again, determining the ordering between any two elements is simple.


So now I am wondering if the same sort of thing can be done for
the ordinals up to gamma_0?

It was suggested to me that a scheme like the following might do it:

0 is a term;
if x is a term then so is omega^x;
if x and y are terms then so are (x+y) and phi(x,y);
(together with a simple set of rules for ordering terms).

But will this do, in fact?  It seems to me that there are perhaps
a huge number of ordinals somehow missing "between the crevices"
of this notation system.    So can anyone please answer for me:-

Is the scheme above sufficient for all ordinals up to gamma_0 ?
If not, can it be augmented easily?

Thanks in advance for any help.

W Taylor

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom