Paul
Posts:
401
Registered:
7/12/10


Re: A canonical form for small ordinals
Posted:
Jan 17, 2014 5:13 PM


On Friday, January 17, 2014 11:27:44 AM UTC, quasi wrote: > quasi wrote: > > >quasi wrote: > > >>William Elliot wrote: > > >>>Paul wrote: > > >>>> > > >>>>I saw it asserted without proof that all ordinals, alpha, > > >>>>less than epsilon_0, can be uniquely expressed as > > >>>> > > >>>> (omega^beta)*(gamma + 1) > > >>>> > > >>>>for some gamma and some beta such that beta < alpha, > > >>>>where omega is the smallest infinite ordinal. This isn't > > >>>>clear to me. Could anyone help or give a reference? > > >> > > >>Note that alpha = 0 must be excluded since the ordinal 0 has > > >>no such representation. > > >> > > >>>Cantor's normal form. > > >> > > >>Assuming 0 < alpha < epsilon_0, then as suggested by > > >>William Elliot, Cantor's normal form clinches it. > > >> > > >>Proposition: > > >> > > >>For all ordinals alpha > 0 there are exist unique ordinals > > >>beta and gamma such that (omega^beta)*(gamma + 1). > > > > > >I meant: such that alpha = (omega^beta)*(gamma + 1). > > > > > >>Existence: > > >> > > >>Let beta be the least exponent in the Cantor normal form for > > >>alpha. Then the normal form factors as > > >> > > >> (omega^beta)*(gamma + 1) > > >> > > >>for some gamma. > > > > Clarifying remark: > > > > The least exponent beta may occur more than once in the normal > > form, but since the normal form has only finitely many terms, > > it will still be the case that once omega^beta is factored out > > (on the left) the remaining factor will not be a limit ordinal, > > and hence can be expressed in the form gamma + 1, for some > > ordinal gamma. > > > > >>Uniqueness: > > >> > > >>Suppose alpha has two representations: > > >> > > >> alpha = (omega^beta1)*(gamma1 + 1) > > >> > > >> alpha = (omega^beta2)*(gamma2 + 1) > > >> > > >>From the uniqueness of the normal form for alpha, together with > > >>the uniqueness of the normal form for gamma1 + 1 and gamma2 + 1, > > >>it follows that beta1 = beta2, and based on that, the uniqueness > > >>of the normal form for alpha then yields gamma1 = gamma2. > > >> > > >>This completes the proof of the proposition. > > >> > > >>Now suppose 0 < alpha < epsilon_0. > > >> > > >>Applying the proposition, there are unique ordinals beta and > > >>gamma such that alpha = (omega^beta)*(gamma + 1). > > >> > > >>Then > > >> > > >> alpha = (omega^beta)*(gamma + 1) > > >> > > >> => omega^beta <= alpha > > >> > > >>But the above, together with alpha < epsilon_0, yields > > >> > > >> beta < alpha > > >> > > >>as required. > > >> > > >>Bottom line: > > >> > > >>Sometimes William Elliot is right on target, and this was > > >>one of those times. > > > > quasi
Yes, Cantor Normal Form is enough. Thanks to quasi and William Elliot. The trick of dividing by the lowest term didn't occur to me. I'm not very familiar with ordinal division but I learned recently that the division algorithm applies generally to all ordinals, not just finite ones.
Paul Epstein

