From: renfrod@central.edu (Dave L. Renfro)
Subject: Re: Ordinal arithmetic: effective procedures and examples
Date: 30 Dec 2000 00:17:56 -0500
Newsgroups: sci.math
Summary: [missing]

<lemma_one@my-deja.com>
[sci.math Wed, 20 Dec 2000 10:12:05 GMT]
<http://forum.swarthmore.edu/epigone/sci.math/flingnalsmul>

wrote

> I have a set theory final real soon now and could use some more
> practice and understanding of ordinal arithmetic. (Ordinal
> arithmetic is interesting in that everything doesn't just collapse
> to a single point like with cardinal arithmetic, so that things
> like cantor normal form exist.)
> 
> In particular, to do ordinal arithmetic I find myself having to
> draw pictures to intuitively compute the order type, and some of
> the computations and pictures get really complicated, so that I
> have a lot of anxiety that I have made an error somewhere.
> 
> Here's an example computation [w = omega]:
> 
>    (w+1)^4 = (w+1)^3 * (w+1) = ... = (w+1)(w+1)(w+1)(w+1)
>    = [(w+1)*w + (w+1)] * [(w+1)*w + (w+1)]
> 
> Now I have to do (w+1)*w before I can go on. Drawing a picture, it
> pretty much looks like w^2, so
> 
>    = (w^2 + w + 1)(w^2 + w + 1)
>    =   (w^2 + w + 1)*(w^2)
>      + (w^2 + w + 1)*w
>      + (w^2 + w + 1)
> 
> Now things start to get really difficult, and I don't want to type
> anymore, but I think I can at least finish computing (w+1)^4. But
> how would I do something like
> 
>   (w^8 + w^2*9 + 5)^{(w^4)*5 + w^3 + 3}
> 
> ? I don't think drawing little pictures will do the trick. How do I
> more effectively compute these things?

I suppose this is too late (I've been real busy lately and haven't
looked at sci.math posts for several weeks), but here are some
suggestions in case you are (or anyone else is) still interested.

Ordinal addition is associative, not commutative, and is continuous
on the right:

   If L is a nonzero limit ordinal, then 
      SUP{a + b : b < L} = a + L for any ordinal a.

Ordinal multiplication is associative, not commutative, and
multiplication on the left is distributive over addition (but not
multiplication on the right), and is continuous on the right:

   a*(b1 + b2) = a*b1 + a*b2

   (1+1)*w NOT= 1*w + 1*w

   If L is a nonzero limit ordinal, then 
      SUP{a*b : b < L} = a*L for any ordinal a.

Ordinal exponentiation is not associative, not commutative, and
is continuous in the exponent:

   (a^b1)*(a^b2) = a^(b1 + b2)  [Hence, a^2 = a*a (use b1 = b2 = 1),
                                        a^3 = a*a*a, etc.]
   (a^b1)^b2 = a^(b1*b2)

   (2*2)^w = w NOT= (2^w)*(2^w) = w*w

   If L is a nonzero limit ordinal, then 
      SUP{a^b : b < L} = a^L for any ordinal a.

TWO EXAMPLES:

1. n+w = n*w = n^w = w for each ordinal n such that 1 < n < w.

   Proof: Use the right continuity laws. For example, 
          n^w = SUP{n^m : m < w} = w.

2. w*5 = w*4 + w = (2^w)*(2^2) + 2^w = 2^(w+2) + 2^w
      [An example of converting to "base 2" normal form.]

YOUR SIMPLER EXAMPLE:

(w+1)^4 = [(w+1)^2]*[(w+1)^2]

Before continuing, let's stop to see what (w+1)^2 is.

(w+1)^2 = (w+1)*(w+1) = (w+1)*w + (w+1)*1 = w^2 + w + 1,

since (w+1)*w = w^2.

[ Proof: w*w \leq (w+1)*w = SUP{ (w+1)*n : n < w}
              =  SUP{ w*n + 1 : n < w} \leq SUP{ w*(n+1) : n < w}
              =  w*w 

     (Note that (w+1)^n = (w+1) + (w+1) + ... + (w+1)
                       = w + (1+w) + (1+w) + ... + (1+w) + 1
                       = w + w + w + ... + w + 1
                       = w*n + 1.) ]

Hence, (w+1)^4 = (w^2 + w + 1)*(w^2 + w + 1)

      = (w^2 + w + 1)*w^2 + (w^2 + w + 1)*w + (w^2 + w + 1)*1.

Since we don't have right distributivity of multiplication over
addition, we have to simplify by other means.

(w^2)*(w^2) \leq (w^2 + w + 1)*(w^2) \leq (w^2 + w^2)*(w^2)

             =  [(w^2)*2)]*(w^2) = (w^2)*[2*(w^2)]

             =  (w^2)*(w^2) [since 2*(w^2) = w^2, the verification
                             of which is just like #1 above]

             =  w^4.

Therefore, (w^2 + w + 1)*(w^2) = w^4.

Similarly, (w^2 + w + 1)*w = w^3. Hence,

(w+1)^4 = w^4 + w^3 + w^2 + w + 1.

Your more complicated example seems a bit beyond anything I think
you need to worry about.

Two books that give a lot of ordinal arithmetic examples are
Sierpinski's "Cardinal and Ordinal Numbers" and Jean Rubin's
"Set Theory for the Mathematician". I don't have a copy of either
book with me now, but I believe (w^2 + w + 1)^2 is worked out
somewhere in Sierpinski's book using the properties of transfinite
sums (i.e. in a different way than what I did).

Dave L. Renfro