02/21/2008, 08:16 PM
(I migrated here 'cos the other eretrandre forum is too quiet 
)
Recently, in the course of trying to find extremely fast-growing computable functions, I stumbled upon a curious connection between Cantor's transfinite ordinals and functions on the natural numbers.
I won't repeat the definition of an ordinal number here, it's easily found on Wikipedia or other online sources. Cantor really only developed ordinal arithmetic up to exponentiation: he got as far as the limit of the sequence \( \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots \), calling it epsilon_0. This ordinal satisfies the fixed point property x=w^x. After that, he defined other epsilon numbers as subsequent ordinals with the same property.
In the course of researching higher-order operations such as tetration on the natural numbers, I noticed that epsilon_0 is the ideal candidate for w tetrated to w. Once you accept this, it's not too hard to imagine w[4](w+1), w[4](w+2), .... (I shall use the notation x[4]y to denote x tetrated to y, for the obvious reason that we want to also consider higher-order operations later.) This is very obvious---at least intuitively. However, it's not so simple to define rigorously, as I discovered recently when trying to formalize what I'm dealing with. The main problem is that exponentiation is non-associative, and because of this, one cannot easily define what is meant by w[4]x for x greater than w. (I'm leaving out the details 'cos it's not very interesting.)
So I proceeded along this line of reasoning: we intuitively understand w[4](w+1) to be a tower of exponents containing a stretch of w instances of w, followed by another w in the w'th position. We can lay out each element of the tower in a sequence: w, w, w, ... (w times), w. If we add another w to the base of the tower, we see that this sequence doesn't change. So what that means is that w^(w[4](w+1)) = w[4](w+1). In other words, it must be an epsilon number.
If we then start with w[4]w=epsilon_0, and construct larger ordinals from it, we see that epsilon_0+1, epsilon_0+2, ... all do not satisfy the fixed point property x=w^x. Multiplying epsilon_0 by 2, 3, 4, ... w, etc., all don't satisfy this property either. Neither does epsilon_0^2, epsilon_0^3, ... epsilon_0^w, .... In fact, one quickly realizes that any ordinal between w[4]w and w[4](w+1) does not satisfy this property. Therefore, we must conclude that w[4](w+1) = epsilon_1.
A similar line of reasoning shows that w[4](w+x) = epsilon_x. In other words, even though we don't know how to define ordinal tetration using transfinite recursion on lower-order operations, we can define it in terms of the epsilon numbers.
Now, we move on. Consider the ordinal w[4](w[4]w), which I shall denote as w[4]w[4]w (from now on, we'll assume right-to-left associativity, just to reduce the number of parentheses we need to write). By our definition of tetration, this ordinal is epsilon_epsilon_0. Similarly, w[4]w[4]w[4]w = epsilon_epsilon_epsilon_0. In other words, w[5](n+1) = epsilon_epsilon_...epsilon_0, where there are n epsilon's.
This defines pentation on ordinals up to w[5]w, which is the smallest ordinal satisfying x=epsilon_x. To define pentation for bigger right arguments, we need to go beyond the epsilon numbers.
Fortunately, a system for producing larger ordinals already exists: the Veblen hierarchy. It is defined in terms of a class of functions phi_y:
For y=0, phi_y(x) = w^x (base case)
For y=z+1, phi_y(x) = the x'th fixed point of phi_z
For limit ordinals y, phi_{y}(x) = union of all fixed points of phi_z, where z is less than y
Note that for our construction to be valid, x must be either an ordinal smaller than w or an ordinal we have already constructed with previous applications of the phi function.
So phi_0(0) = w^0 = 1, phi_0(1)=w, phi_0(2)=w^2, etc.. Now that we've constructed w^n for finite n, we can pass these ordinals to phi_0: phi_0(w)=w^w, phi_0(w^w)=w^w^w, and so forth. The limit (fixed point) of phi_0 is phi_0(phi_0(phi_0(...)))=w^w^w^...=epsilon_0. This is, by definition, phi_1(0).
Then again, by definition, phi_1(1) is the next fixed point of phi_0: that is, the next ordinal satisfying x=w^x. In other words, phi_1(1)=epsilon_1=w[4](w+1). So phi_1 is just the epsilon numbers.
Now we come to the interesting part: phi_2(0) is defined to be the first fixed point of phi_1, or, in other words, the fixed point of the epsilon numbers, epsilon_epsilon_epsilon_... = w[4]w[4]w[4]... = w[5]w. So we see that phi_2(0)=w[5]w. What is phi_2(1)? It is the next fixed point of the epsilon function: i.e., the next ordinal satisfying w[4]x = x. Using a parallel argument as we used above to determine that w[4](w+1)=epsilon_1, we can see that phi_2(1) must equal w[5](w+1). In other words, we can now define pentation: w[5]x = phi_2(x).
With this definition, we see that phi_2(phi_2(w)) = w[5]w[5]x, phi_2(phi_2(phi_2(w))) = w[5]w[5]w[5]w, and so forth. The fixed point of phi_2, then, must be w[5]w[5]w[5]... = w[6]w. By the definition of phi, it must be the case that w[6]w = phi_3(0).
The pattern is now clear: w[n]w = phi_{n-3}(0), and w[n](w+x) = phi_{n-3}(x). This gives us a rigorous definition of tetration, pentation, hexation, ... for the ordinals.
The next interesting ordinal is phi_w(0): this is the limit of all the nth order operations. So, it must be the ordinal equivalent of the Ackermann function!
But we have only barely begun. If we let A^i(x) to be the i'th iterate of the Ackermann function (i.e., A^2(x) = A(A(x)), A^3(x) = A(A(A(x))), ...). Then A^w(w) = phi_{w+1}(0). Call this function B. Now let B^i(x) be the i'th iterate of B. Then B^w(w) = phi_{w+2}(0). Call this function C. Then C^w(w) = phi_{w+3}(0). And so on, until we reach the w'th step of creating more iterates. That function then corresponds with phi_{w+w}(0).
As you can see, it's not so much that the ordinals themselves are all that interesting; it is the fact that they let us create larger and larger computable functions on the natural numbers.
As it stands, we've hardly begun to scratch the surface of the Veblen hierarchy. Keep in mind that phi_0(2)=w^2, so we have hardly begun to reach phi_{phi_0(2)}(0) = phi_{w^2}(0). Once we reach that, then we can go further to get to phi_{phi_0(3)}(0), phi_{phi_0(4)}(0), ... and so on, and eventually to phi_{phi_0(w)}(0)=phi_{phi_{phi_0(0)}(0)}(0). At each new subscript to phi, the number of steps required to reach the next level increase INSANELY fast. After the first few subscripts of phi_y, the Ackermann function already looks like a microscopic wimp compared to the functions being generated by the phi function.
We can keep going, until we get to phi_phi_phi_... = Gamma_0. This ordinal is known as the Feferman-Schütte ordinal, and is so insanely large that phi_Gamma_0(0) = Gamma_0. It is also so insanely large that performing fixed point operations on it (as the phi function does) does not get you significantly past it. This ordinal has quite an important role in logic and proof theory, but that's not my interest here. My interest here is in that fact that this ordinal should correspond with some function F on the natural numbers. Since Gamma_0 is still countable, and moreoever, still recursive, this means that F must be computable!!!! Yet F is so unimaginably fast-growing that it dwarfs all currently-known large number functions (excepting non-computable ones like the Busy Beaver function), including most attempts at making these functions grow faster. The only function I know of that can go significantly beyond F is the busy beaver function, which is non-computable. As far as computable functions go, F is pretty close to the limit of computability!
We may also derive from Gamma_0 an operation on the natural numbers. As such an operation, it far, far, far, FAR transcends ANY operation that anyone has ever considered before. If you ever need to name the largest computable natural number you can think of, this operation will come in handy.
Anyway, there are still open questions to consider:
- Although we have found elegant constructions for higher-order operations (tetration, pentation, ...) on ordinals where the left argument is w, we haven't really defined these operations for other left arguments. For finite numbers, it's easy to define, but it may not be that easy for transfinite arguments. We could attempt to define x[4]y, for example, as the smallest ordinal z satisfying z=x^z, but I'm not sure if x[4](y+n) always coincides with the n'th ordinal satisfying this relation. More investigation is necessary to prove this.
- It's not at all clear how to compute that super-fast function F derived from the ordinal Gamma_0. We do know that it's computable, and we do know, at least in theory, that recursing up the Veblen hierarchy will give us a way to compute it. However, a lot of details are missing, among the most important of which is, how to computationally jump from the n'th level of a phi subscript to the next subscript. I've actually explored functions much, much farther past the Ackermann function and its iterates as described above, and I still haven't gotten to phi_phi_1(0) yet. We do know that F must be computable, but how to actually compute it seems intractible at the moment.
- It's possible to move even higher past the Veblen hierarchy: Gamma_0 is merely the first fixed point of the phi function. We can move up to Gamma_1, Gamma_2, ... or even Gamma_Gamma_Gamma_.... I believe these huge ordinals must still be computable, because they are still below the so-called Church-Kleene ordinal \( \omega_1^{\mbox{CK}} \), which is the union of all recursive ordinals. Note that even this ordinal is still countable!! (The first uncountable ordinal \( \omega_1 \) is simply far beyond comprehension.) However, I'm not sure if it's even possible to fathom how to compute functions/operations correspond with the higher Gamma ordinals. If anybody has any ideas, I'd be interested.
)Recently, in the course of trying to find extremely fast-growing computable functions, I stumbled upon a curious connection between Cantor's transfinite ordinals and functions on the natural numbers.
I won't repeat the definition of an ordinal number here, it's easily found on Wikipedia or other online sources. Cantor really only developed ordinal arithmetic up to exponentiation: he got as far as the limit of the sequence \( \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots \), calling it epsilon_0. This ordinal satisfies the fixed point property x=w^x. After that, he defined other epsilon numbers as subsequent ordinals with the same property.
In the course of researching higher-order operations such as tetration on the natural numbers, I noticed that epsilon_0 is the ideal candidate for w tetrated to w. Once you accept this, it's not too hard to imagine w[4](w+1), w[4](w+2), .... (I shall use the notation x[4]y to denote x tetrated to y, for the obvious reason that we want to also consider higher-order operations later.) This is very obvious---at least intuitively. However, it's not so simple to define rigorously, as I discovered recently when trying to formalize what I'm dealing with. The main problem is that exponentiation is non-associative, and because of this, one cannot easily define what is meant by w[4]x for x greater than w. (I'm leaving out the details 'cos it's not very interesting.)
So I proceeded along this line of reasoning: we intuitively understand w[4](w+1) to be a tower of exponents containing a stretch of w instances of w, followed by another w in the w'th position. We can lay out each element of the tower in a sequence: w, w, w, ... (w times), w. If we add another w to the base of the tower, we see that this sequence doesn't change. So what that means is that w^(w[4](w+1)) = w[4](w+1). In other words, it must be an epsilon number.
If we then start with w[4]w=epsilon_0, and construct larger ordinals from it, we see that epsilon_0+1, epsilon_0+2, ... all do not satisfy the fixed point property x=w^x. Multiplying epsilon_0 by 2, 3, 4, ... w, etc., all don't satisfy this property either. Neither does epsilon_0^2, epsilon_0^3, ... epsilon_0^w, .... In fact, one quickly realizes that any ordinal between w[4]w and w[4](w+1) does not satisfy this property. Therefore, we must conclude that w[4](w+1) = epsilon_1.
A similar line of reasoning shows that w[4](w+x) = epsilon_x. In other words, even though we don't know how to define ordinal tetration using transfinite recursion on lower-order operations, we can define it in terms of the epsilon numbers.
Now, we move on. Consider the ordinal w[4](w[4]w), which I shall denote as w[4]w[4]w (from now on, we'll assume right-to-left associativity, just to reduce the number of parentheses we need to write). By our definition of tetration, this ordinal is epsilon_epsilon_0. Similarly, w[4]w[4]w[4]w = epsilon_epsilon_epsilon_0. In other words, w[5](n+1) = epsilon_epsilon_...epsilon_0, where there are n epsilon's.
This defines pentation on ordinals up to w[5]w, which is the smallest ordinal satisfying x=epsilon_x. To define pentation for bigger right arguments, we need to go beyond the epsilon numbers.
Fortunately, a system for producing larger ordinals already exists: the Veblen hierarchy. It is defined in terms of a class of functions phi_y:
For y=0, phi_y(x) = w^x (base case)
For y=z+1, phi_y(x) = the x'th fixed point of phi_z
For limit ordinals y, phi_{y}(x) = union of all fixed points of phi_z, where z is less than y
Note that for our construction to be valid, x must be either an ordinal smaller than w or an ordinal we have already constructed with previous applications of the phi function.
So phi_0(0) = w^0 = 1, phi_0(1)=w, phi_0(2)=w^2, etc.. Now that we've constructed w^n for finite n, we can pass these ordinals to phi_0: phi_0(w)=w^w, phi_0(w^w)=w^w^w, and so forth. The limit (fixed point) of phi_0 is phi_0(phi_0(phi_0(...)))=w^w^w^...=epsilon_0. This is, by definition, phi_1(0).
Then again, by definition, phi_1(1) is the next fixed point of phi_0: that is, the next ordinal satisfying x=w^x. In other words, phi_1(1)=epsilon_1=w[4](w+1). So phi_1 is just the epsilon numbers.
Now we come to the interesting part: phi_2(0) is defined to be the first fixed point of phi_1, or, in other words, the fixed point of the epsilon numbers, epsilon_epsilon_epsilon_... = w[4]w[4]w[4]... = w[5]w. So we see that phi_2(0)=w[5]w. What is phi_2(1)? It is the next fixed point of the epsilon function: i.e., the next ordinal satisfying w[4]x = x. Using a parallel argument as we used above to determine that w[4](w+1)=epsilon_1, we can see that phi_2(1) must equal w[5](w+1). In other words, we can now define pentation: w[5]x = phi_2(x).
With this definition, we see that phi_2(phi_2(w)) = w[5]w[5]x, phi_2(phi_2(phi_2(w))) = w[5]w[5]w[5]w, and so forth. The fixed point of phi_2, then, must be w[5]w[5]w[5]... = w[6]w. By the definition of phi, it must be the case that w[6]w = phi_3(0).
The pattern is now clear: w[n]w = phi_{n-3}(0), and w[n](w+x) = phi_{n-3}(x). This gives us a rigorous definition of tetration, pentation, hexation, ... for the ordinals.
The next interesting ordinal is phi_w(0): this is the limit of all the nth order operations. So, it must be the ordinal equivalent of the Ackermann function!
But we have only barely begun. If we let A^i(x) to be the i'th iterate of the Ackermann function (i.e., A^2(x) = A(A(x)), A^3(x) = A(A(A(x))), ...). Then A^w(w) = phi_{w+1}(0). Call this function B. Now let B^i(x) be the i'th iterate of B. Then B^w(w) = phi_{w+2}(0). Call this function C. Then C^w(w) = phi_{w+3}(0). And so on, until we reach the w'th step of creating more iterates. That function then corresponds with phi_{w+w}(0).
As you can see, it's not so much that the ordinals themselves are all that interesting; it is the fact that they let us create larger and larger computable functions on the natural numbers.
As it stands, we've hardly begun to scratch the surface of the Veblen hierarchy. Keep in mind that phi_0(2)=w^2, so we have hardly begun to reach phi_{phi_0(2)}(0) = phi_{w^2}(0). Once we reach that, then we can go further to get to phi_{phi_0(3)}(0), phi_{phi_0(4)}(0), ... and so on, and eventually to phi_{phi_0(w)}(0)=phi_{phi_{phi_0(0)}(0)}(0). At each new subscript to phi, the number of steps required to reach the next level increase INSANELY fast. After the first few subscripts of phi_y, the Ackermann function already looks like a microscopic wimp compared to the functions being generated by the phi function.
We can keep going, until we get to phi_phi_phi_... = Gamma_0. This ordinal is known as the Feferman-Schütte ordinal, and is so insanely large that phi_Gamma_0(0) = Gamma_0. It is also so insanely large that performing fixed point operations on it (as the phi function does) does not get you significantly past it. This ordinal has quite an important role in logic and proof theory, but that's not my interest here. My interest here is in that fact that this ordinal should correspond with some function F on the natural numbers. Since Gamma_0 is still countable, and moreoever, still recursive, this means that F must be computable!!!! Yet F is so unimaginably fast-growing that it dwarfs all currently-known large number functions (excepting non-computable ones like the Busy Beaver function), including most attempts at making these functions grow faster. The only function I know of that can go significantly beyond F is the busy beaver function, which is non-computable. As far as computable functions go, F is pretty close to the limit of computability!
We may also derive from Gamma_0 an operation on the natural numbers. As such an operation, it far, far, far, FAR transcends ANY operation that anyone has ever considered before. If you ever need to name the largest computable natural number you can think of, this operation will come in handy.
Anyway, there are still open questions to consider:
- Although we have found elegant constructions for higher-order operations (tetration, pentation, ...) on ordinals where the left argument is w, we haven't really defined these operations for other left arguments. For finite numbers, it's easy to define, but it may not be that easy for transfinite arguments. We could attempt to define x[4]y, for example, as the smallest ordinal z satisfying z=x^z, but I'm not sure if x[4](y+n) always coincides with the n'th ordinal satisfying this relation. More investigation is necessary to prove this.
- It's not at all clear how to compute that super-fast function F derived from the ordinal Gamma_0. We do know that it's computable, and we do know, at least in theory, that recursing up the Veblen hierarchy will give us a way to compute it. However, a lot of details are missing, among the most important of which is, how to computationally jump from the n'th level of a phi subscript to the next subscript. I've actually explored functions much, much farther past the Ackermann function and its iterates as described above, and I still haven't gotten to phi_phi_1(0) yet. We do know that F must be computable, but how to actually compute it seems intractible at the moment.
- It's possible to move even higher past the Veblen hierarchy: Gamma_0 is merely the first fixed point of the phi function. We can move up to Gamma_1, Gamma_2, ... or even Gamma_Gamma_Gamma_.... I believe these huge ordinals must still be computable, because they are still below the so-called Church-Kleene ordinal \( \omega_1^{\mbox{CK}} \), which is the union of all recursive ordinals. Note that even this ordinal is still countable!! (The first uncountable ordinal \( \omega_1 \) is simply far beyond comprehension.) However, I'm not sure if it's even possible to fathom how to compute functions/operations correspond with the higher Gamma ordinals. If anybody has any ideas, I'd be interested.
