[FOM] A New Ordinal Notation System

[Dmytro Taranovsky]

I discovered a very strong yet relatively simple ordinal notation 
system.  The notation system consists of 0, W (a large ordinal), and a 
binary function C.  For ordinals in the standard representation written 
in the postfix form, the comparison is done in the lexicographical order 
where 'C' < '0' < 'W':  For example, C(C(0,0),0) < C(W, 0) because 000CC 
< 0WC. (Note: This does not hold for non-standard representations of 
ordinals.)  Of course, the real logic lies in deciding which 
representations are standard.

Here is a recursive definition. In this definition, '<' denotes the 
above-described lexicographical order.
"0" and "W" are standard.
"C(a, b)" is standard iff these three conditions are met:
1. "a" and "b" are standard.
2. If "b" is "C(c, d)", then "a" <= "c".
3. Let T_a be the parse tree of "a": T_a is the set of subterms of "a" 
(including their position in "a"). Let '<<' be the tree order on T_a 
with the root node ("a") being the '<<'-least element.  x<<=y means that 
x<<y or x is y.  For "C(a, b)" to be standard, the following must hold:
forall x in T_a forall y>>x (y<x or y>=W or thereis z<<x z<W or thereis 
z<<=y z<"C(a, b)")

Note:  In the parse tree, we distinguish identical strings occuring at 
different positions.  For example, the parse tree of "C(0, 0)" consists 
of the root node "C(0, 0)" and two child nodes: the left "0" and the 
right "0". We have "C(0, 0)" << 'left "0"', and "C(0, 0)" << 'right 
"0"', but not 'left "0"' <<= 'right "0"'.

The intuitive meaning of condition 3 is that "a" must be built from 
below in a certain sense: For every ordinal x in the representation of 
"a" in terms of ordinals below W, the representation of x can only use 
ordinals that are below x except in the scope of an ordinal below C(a, 
b), and not counting ordinals >=W.

I conjecture that its exact strength is that of
KP + {there is kappa such that L_kappa is a Sigma_1 elementary 
substructure of L_{omega(n, kappa^+ + 1)}}_n
where kappa^+ is the least admissible ordinal above kappa and "omega(n" 
refers to n iterations of x->omega^x.
(This is above KP + {Pi_n reflection}_n but below Pi^1_2-CA_0.)
Ordinals below C(W, 0) correspond to provably recursive ordinals, 
ordinals between C(W, 0) and W correspond to non-recursive ordinals 
having a provable canonical representation in the theory, and W and 
above can be viewed as syntactic sugar for constructing ordinals.

The advantage of this notation system is its simplicity compared to 
previously known ordinal notation systems at this strength.
An addition to the definition, we mention some properties of C:

* If a is below the least fixpoint of x->omega^x above b, then C(a, b) = 
b + omega^a
Consequently, above W, this notation system is essentially Cantor normal 
form.

Let S_a be the closure of {y: y = C(a, x) for some x}.
* C(a, b) is the least ordinal above b that is in S_a
* S_0 consists of all non-zero ordinals in the notation system.
* For limit a, S_a is the intersection of all S_b for b<a
* For every ordinal a, there is an ordinal b<=a such that
S_{a+1} = lim(S_a) union (S_a intersect b)  (here lim(S_a) is the set of 
limit points of S_a).

For results about this and related notation systems, the reader is 
referred to my paper:
http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm

I wrote a script to compare ordinals in the notation system, and to 
convert non-standard representations to the standard form:
http://web.mit.edu/dmytro/www/other/CompareOrdinals.py

A software implementation gives a sense of concreteness to the system 
that would otherwise be missing -- in a psychological if not in a formal 
sense.

Sincerely,
Dmytro Taranovsky