Higher-order operations on transfinite ordinals

Higher-order operations on transfinite ordinals - Printable Version

+- Eretrandre Mathematics Forum (https://math.eretrandre.org/mybb)
+-- Forum: Mathematics (https://math.eretrandre.org/mybb/forumdisplay.php?fid=3)
+--- Forum: Questions (https://math.eretrandre.org/mybb/forumdisplay.php?fid=11)
+--- Thread: Higher-order operations on transfinite ordinals (/showthread.php?tid=31)

Higher-order operations on transfinite ordinals - quickfur - 2008-01-28

Recently I've been studying the correspondence between large (countable) ordinals and what I call "large number functions" over the natural numbers. It seems that when Cantor studied the ordinals, he wasn't aware of higher-order operations like tetration (or perhaps he chose not to use them for some reason?), so starting with w, w+1, w+2, ... w+w, w*3, w*4, ... w^2, w^3, w^4, ... w^w, w^w^w, w^w^w^w, ... he eventually stopped at $\epsilon_0 = w^{w^{w^{\ldots}}}$ . But really, this is simply w tetrated to itself, which is w pentated to 2. One can easily envision continuing the sequence: w pentated to 3, w pentated to 4, ... w pentated to w, and then w hexated to 2, w hexated to 3, w hexated to 4, ....

Now, my question, Cantor did define subsequent epsilon ordinals, but where exactly do they lie in the hierarchy of higher ordinal operations? For example, $\epsilon_1$ is defined to be the second ordinal satisfying $\epsilon_1 = w^{\epsilon_1}$ . Does that mean it is equal to w pentated to 3? Or perhaps w pentated to w?

Also, what about the Ackermann function as applied to the ordinals? Does A(w,w) correspond with some ordinal in the Veblen hierarchy?

I wonder what operation the Feferman-Schütte ordinal corresponds with---if we map it back to functions over the natural numbers, it would seem to me that this would correspond with an extremely fast-growing function. I suspect this function would still be computable, since it is still below the Church-Kleene ordinal. I also wonder if the Church-Kleene ordinal corresponds with the Busy Beaver function. (These considerations are part of my attempt to see how close I can get to the Busy Beaver function while still staying within the realm of computability.)

RE: Higher-order operations on transfinite ordinals - bo198214 - 2008-01-31

quickfur Wrote:Now, my question, Cantor did define subsequent epsilon ordinals, but where exactly do they lie in the hierarchy of higher ordinal operations? For example, $\epsilon_1$ is defined to be the second ordinal satisfying $\epsilon_1 = w^{\epsilon_1}$ . Does that mean it is equal to w pentated to 3? Or perhaps w pentated to w?

According to wikipedia $\epsilon_1$ is just the limit of the sequence $\epsilon_0+1,\omega^{\epsilon_0+1},\omega^{\omega^{\epsilon_0+1}},\dots$ .

RE: Higher-order operations on transfinite ordinals - quickfur - 2008-02-01

bo198214 Wrote:According to wikipedia $\epsilon_1$ is just the limit of the sequence $\epsilon_0+1,\omega^{\epsilon_0+1},\omega^{\omega^{\epsilon_0+1}},\dots$ .

Yes, I know that. $Smile$ But I was just wondering how exactly $\epsilon_1$ corresponds to the hierarchy of operations. Specifically, does it represent the equivalent of transfinite tetration, or pentation, or maybe something in between?

RE: Higher-order operations on transfinite ordinals - GFR - 2008-02-06

quickfur Wrote:... when Cantor studied the ordinals, he wasn't aware of higher-order operations like tetration ... so starting with w, w+1, w+2, ... w+w, w*3, w*4, ... w^2, w^3, w^4, ... w^w, w^w^w, w^w^w^w, ... he eventually stopped at $\epsilon_0 = w^{w^{w^{\ldots}}}$ . But really, this is simply w tetrated to itself, which is w pentated to 2. One can easily envision continuing the sequence: w pentated to 3, w pentated to 4, ... w pentated to w, and then w hexated to 2, w hexated to 3, w hexated to 4, ....

It is clear that Cantor's infinite ordinal $\epsilon_0 = w^{w^{w^{\ldots}}}$ is: w#w = w[4]w (omega-tetra-omega) and, perhaps, Cantor didn't pay enough attention to that.

Particularly, we indeed have: epsilon-0 = w[4]w = w[5]2 (omega-penta-2).

This notation is very clear and unambiguous and should be officially proposed to the international mathematical authorities (to the ICM, the International Congress of Mathematicians or to other bodies), because it is the shortest and clearest way of writing epsilon-0.

This fact, together with the existence of an infinite hyperoperation hierarchy, suggests that, perhaps, it is time now for a new analysis of the existing notation of the infinite countable ordinals.

I think, in this respect, that a special role should be plaid by the limit infinite ordinal, to be defined as:
W = w[w]w (omega-omega-omega).

GFR

RE: Higher-order operations on transfinite ordinals - quickfur - 2008-02-21

After studying Cantor's epsilon numbers more, I've come to realize that things aren't as simple as they seemed at first. On the surface, it seems that it should be easy to define transfinite tetration: after all, following the pattern of how a+w, a*w, and $a^{\omega}$ are defined, it's just a matter of taking the union of all the elements in the sequence of exponential towers, right? And then the ordinals following that union are just a matter of taking that union, and then repeating the exponential tower operation on it.

However, after trying to rigorously define tetration via transfinite recursion, I ran into a seemingly impassable roadblock. The root of the problem is that exponentiation is non-associative. This in itself does not make things too hard when we're defining exponentiation, because exponentiation is based on iterating multiplication, and multiplication is associative. Because multiplication is associative, the "tail end" of the transfinite product w*w*w*... is still "accessible": we can define w^(w+1) to be (w*w*w*...)*w. So transfinite recursion works past limit ordinals because of this property.

Now, when defining tetration, we run into a problem: in an exponential tower w^(w^(w^x))), the "top" of the tower is inaccessible: once it is formed, we have no way of reaching into the x and stacking more exponentials onto it. The most we can do is to "push" the tower from below by raising the tower into the exponent of more w's. This is OK for towers of finite height, because in constructing w[4]w, we don't need to change anything at the top of the tower. However, once the height of the tower reaches w, we have a problem: it is now w^(w^(w^(w^...))), and adding more w's to the bottom of the tower does not make it any higher. What we want is to add more exponents to the top of the tower. However, there is no way to access the top part of the tower to add more exponents to it! There is no straightforward way to define what w[4](w+1) means, because the non-associativity of exponentiation means that w[4](w+1) ≠ (w[4]w)^w. No matter how we try, there's no way to reach into the second argument of the tetration to make it bigger (no way to do this rigorously, anyway).

So we have a problem. Intuitively, we know what w[4](w+1) is: it's just an exponential tower of height w+1. But I can see no way of defining this via transfinite recursion.

Because of these problems, it seems that there is no other way but to use Cantor's fixed point definition of the epsilon numbers. (So it seems that Cantor wasn't just ignorant of higher operations... there are technical problems with the naive construction of higher operations via transfinite recursion.) Here is one way I've found:

First, given that we intuitively understand w[4](w+1) to be a tower of height w+1, we may imagine laying it out each element in the tower in a sequence: w, w, w, ... w (where the last w lies past the end of a stretch of w occurrences of w). Now, if we add one more w to the base of the tower, this does not change the resulting sequence. In other words, this means that w^(w[4](w+1)) = w[4](w+1). So it must be an epsilon number! (Since the epsilon numbers are defined as ordinals x that satisfy x=w^x.) The question is then, which epsilon number is it?

To answer this question, we look at the behaviour of epsilon_0, which is w[4]w. Suppose we add 1 to it to get w[4]w+1. Obviously, this no longer satisfies the property x=w^x. Moreover, we can continue to add things to w[4]w, and all of them do not satisfy this property. After that, we may try multiplying w[4]w by 2, 3, 4, and so forth, and we see that all those ordinals don't satisfy the property either. We may even raise w[4]w to some ordinal exponent, such as (w[4]w)^w = w^(w*(w[4]w)), and so forth, but none of those satisfies the property either. In fact, we shall soon realize that none of the ordinals less than w[4](w+1) satisfy this property!

Which means that w[4](w+1) is the next smallest ordinal satisfying x=w^x. This means that w[4](w+1) must be equal to epsilon_1. A similar line of argument will quickly show that w[4](w+2) must equal to epsilon_2, and so forth. In other words, w[4](w+x)=epsilon_x, for any ordinal x.

Hooray! So finally, we have found a way to define ordinal tetration. At least, we've defined it where the base of the tetration is w. I'm not sure if the fixed point trick will still work correctly for ordinals greater than w (this needs further research).

Now that we have a working definition, we can examine some of the properties of ordinal tetration. We have already seen that w[4](w+x) = epsilon_x. More specifically, w[4](w+w) = w[4](w*2) = epsilon_w, w[4](w+w+w) = epsilon_(w+w), w[4](w+w+w+w) = epsilon_(w+w+w), and so forth. Here, we notice something interesting: as we take the limit of this sequence, we see that even though the epsilon subscript has 1 less term than the argument to the tetration operation, when we reach epsilon_(w*w), the tetration argument also collapses: w[4](w*w). In other words, for x≥w*w, epsilon_x = w[4]x.

As we move to larger and larger x, we eventually reach epsilon_(w^w^w^...) = epsilon_epsilon_0 = w[4](w[4]w) = w[5]3. So now we see a new pattern: w[5]n = epsilon_epsilon_epsilon_..._epsilon_0, where there are n epsilon's. This lets us define w[5]w as the smallest ordinal x satisfying x=epsilon_x.

Now, the epsilons can no longer help us to go much farther; so pentation cannot in fact be defined in terms of the epsilon numbers. In order to do this, we will need to go full-scale into the Veblen hierarchy. Happily, using the method I described above, it is possible to rigorously define at least all the hyper operators of finite order with the help of the Veblen hierarchy. I'm a bit less certain about bigger things like the Ackermann function, but I suspect it would also work. The Veblen hierarchy is extremely powerful, and goes way past most well-known large number functions.

I might post about the Veblen hierarchy sometime in another thread, it's a very interesting subject that has profound implications for how to construct computable functions that make the Ackermann function look pathetic.

RE: Higher-order operations on transfinite ordinals - quickfur - 2008-02-21

GFR Wrote:[...]
This notation is very clear and unambiguous and should be officially proposed to the international mathematical authorities (to the ICM, the International Congress of Mathematicians or to other bodies), because it is the shortest and clearest way of writing epsilon-0.

Well, this isn't quite so simple, as I discovered. $Smile$ Currently I can't seem to get around defining tetration of w in terms of Cantor's epsilon numbers.

Quote:[...]
I think, in this respect, that a special role should be plaid by the limit infinite ordinal, to be defined as:
W = w[w]w (omega-omega-omega).

Actually, there's nothing particularly special about this ordinal, except perhaps the fact that it corresponds with the Ackermann function applied to ordinals. $Smile$ I have been studying how the Veblen hierarchy corresponds to higher-order operations, and, let's just say that the Ackermann function is less than a wimp when compared with some of the ultra heavyweights produced by the Veblen hierarchy. (Not to mention that almost incomprehensible---yet still countable!!!---ordinal known as the Feferman-Schütte ordinal, often denoted $\Gamma_0$ .

RE: Higher-order operations on transfinite ordinals - GFR - 2008-02-26

Feferman-Schuette(... Gamma-0 ...), , Busy Beaver and Church-Kleene. I see .... $Smile$ !!

It's a long, long way ... !

GFR