[FOM] A New Ordinal Notation

[Lew Gordeew]

Thanks.

Now let x:=C(0,0,0)=1 and y:=C(0,C(0,0,0),0). Clearly x is in the standard
form. Furthermore, we have:

(I) x<y, since (0,0) < (0,C(0,0,0)) via 0<C(0,0,0)=1
     by (a,b) < (b, e) for a=b:=0 and e:=C(0,0,0)

(II) y is in the standard form, since 0 is clearly minimal and C(0,0,0)
maximal by (I).

(III) y<x, since 0<C(0,0,0) and (0,C(0,0,0)) < (C(0,0,0),0) via 0<C(0,0,0)
     by (a,b) < (b, e) for a=e:=0 and b:=C(0,0,0)  

Hence x<y<x and x, y are both in the standard form.

By the same token, X<Y<X is true of
X:= C(C(1,1,0),0) = "the proof-theoretical ordinal for Pi1_1-CA_0"
Y:= C(C(2,0,0),0) = "the ordinal for Pi1_1 Transfinite Recursion (with
induction limited to sets)"

What went wrong?

Regards,
LG 

> ---------------
> Dmytro Taranovsky <dmytro at MIT.EDU>
> fom at cs.nyu.edu
> Re: [FOM] A New Ordinal Notation
> Tue, 16 Aug 2005 13:59:45 -0400
> 
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 

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