Actually, I hate the reversed syntax. Not only it's ugly and ambiguous (how do you interpret a
xb?), it also cannot be generalized, and fails to adequately convey that it's actually just one in an entire series of higher-level operations, the so-called Grzegorczyk Hierarchy. The first levels of this hierarchy are addition, multiplication, exponentiation, tetration, but it continues: pentation, hexation, heptation, etc.. Each level of this hierarchy represents an operator that's an iterated version of the previous operator in the hierarchy. So just as multiplication is iterated addition, and exponentiation is iterated multiplication, so tetration is iterated exponentiation, and pentation is iterated exponentiation, etc..
You may have heard that exponentiation grow extremely fast -- and you'd be right. But that's nothing compared to tetration. To use an infix notation that I invented for this purpose, we may write x{3}y = x^y, and x{4}y = x^x^x^...(y times). 2{4}3, for example, is 2^2^2 = 2^4 = 16, and 2{4}4 = 2^2^2^2 = 2^16 = 65536. So far so good. But look at 2{4}5 = 2^2^2^2^2 = 2^65536 = ... an insanely huge number with more than 20,000 digits. Then 2{4}6 = 2^(2{4}5) = 2^(that insanely huge number with 20,000+ digits). This monster has so many digits, that the number of digits in its number of digits is far too large to write down.
You may be impressed by how fast-growing the {4} operator is, but wait till you see the {5} operator. 2{5}3, for example, is 2{4}2{4}2, which is 2^(2^2) = 2^4 = 16. But 2{5}4 = 2{4}2{4}2{4}2 = 2{4}(2{4}2{4}2) = 2{4}(2{4}16). Remember how ridiculously huge 2{4}5 is? Well, here, we're not talking about 2{4}5; we're talking about 2{4}
16, and not just 2{4}16 by itself, but 2{4}16 as the argument to another {4} operator!! The number of digits in the number of digits in the number of digits in ... (so many times I don't even know how to write it down) ... in the number of digits in 2{4}16 is a number so huge that it's beyond all description, and now we're taking that, and constructing not a power tower, but a
tetrational tower, with that many levels in it. And by the way, this is just 2{5}4. Do you even want to know what 2{5}5 is?
But it doesn't stop there. 2{6}3, for example, is 2{5}2{5}2, which is 2{5}16. Now just pause for a second. I already have trouble explaining just how incomprehensibly huge 2{5}4 is, and now we're not talking about 2{5}5, or even 2{5}6; we're talking about 2{5}16. But this is merely 2{6}3...(!) Let's not even talk about 2{6}4 or 2{6}5... or, God forbid, 2{6}16 which is 2{6}2{6}2. But that's only 2{7}3. What about 2{7}4? Or, for that matter, 2{8}4? Or, since we're at it, 2{100}4?
But why stop there? We could easily construct 2{2{100}4}4. That is, the order of the operator between the outer 2 and 4, is 2{100}4. In other words, even the level of that operator is so unimaginably huge, that the only sane way to write it down, is as 2{100}4. (Now you know why I chose this notation: we need the level of the operator to be itself expressible in numerical terms.
)
We could keep going, of course. But all of these operators, with a fixed number inside the {}, are only a part of the Grzegorczyk Hierarchy. This hierarchy actually has a limit (in the calculus sense
not in the numerical sense, 'cos the numbers that these operators generate are so huge they will explode your perception of infinity several times over, and then some). This limit is an insanely fast-growing operator that corresponds with the notorious diagonalized Ackermann function, which you may have heard about. It can be defined as x{w}y = x{y}x (where w is my poor man's substitute for lowercase omega, representing the first transfinite ordinal), that is to say, the argument you pass to it determines the order of the operation performed. So 5{w}3 = 5{3}5 = 5^5, and 5{w}4 = 5{4}5 = 5^5^5^5^5, and 5{w}5 = 5{5}5 = ... well, you know how powerful the {5} operator it.
But this only barely scratches the surface of the {w} operator. If you make the argument of the {w} operator variable, then it diagonalizes all the operators of the Grzegorczyk Hierarchy, and becomes an operator that surpasses
all previous operators.
But, when it comes to these things, there is never an end, so you soon learn that actually, the Ackermann function is only but a tiny baby step up the so-called Veblen hierarchy of ordinals, or the initial segment of the so-called "fast-growing hierarchy" that map to these ordinals. In the Veblen hierarchy, an ordinal (or correspondingly, an operator) is assigned an ordinal index. The ordinal index of the {n} operators for finite n is simply the finite number n itself. The ordinal index of the Ackermann function is w (i.e., omega), the first transfinite ordinal. But there are many others to follow... for example, the iteration Ackermann function produces an operator of order w+1, and the iteration of
that produces an operator of order w+2. But we can easily diagonalize the whole series of iterated Ackermann functions, and get w+w = w*2. (Caveat: this is transfinite ordinal arithmetic, not normal finite arithmetic, so operations like + and * do NOT commute.) w*2, therefore, represents an operator so far up the hierarchy, that it requires
two infinite stretches of iteration to describe. But this is rather slow going... if we now diagonalize the process of diagonalization itself, we get w+w+w = w*3... or if we diagonalize the process of diagonalizing diagonalizations, we get w+w+w+... = w*w = w^2. But an operator of order w^2 is still only at the bottom section of the Veblen hierarchy. We can easily go to w^w, then w^w^w, then w^w^w^w, ... etc., and eventually we arrive at epsilon_0 = w^w^w^... (w times). But even epsilon_0 is still only at the very bottom rungs of the Veblen hierarchy.
To go up the Veblen hierarchy significantly, you have to start using the Veblen functions phi_y(x), where y and x are ordinals. This phi function grows so fast, that by the time you get to phi_w(1), you've already left epsilon_0 so far behind you've already forgotten what it was. But since the value of phi_y(x) is, itself, an ordinal, you can
nest the phi function into itself, like phi_(phi_y(x))(x). This, of course, produces a ridiculously huge ordinal, with the corresponding ridiculously huge operator which I won't even attempt to describe because it's far beyond all description. But since phi_(phi_y(x))(x) is also itself an ordinal, you can substitute
that back into the phi function again, and get a 3-level nesting phi_phi_phi_y(x..)...(x). It looks trivial on paper, but you have to keep in mind that every additional nesting of the phi function represents an absolutely
enormous leap in magnitude, and that the size of this step between every successive nesting explodes in a way that makes all previous operators look smaller than a subatomic particle.
At the top of the Veblen hierarchy sits an absolutely ridiculously huge ordinal called the Fefermann-Schütte ordinal, usually referred to as Gamma_0, which equals to phi_phi_phi_phi...(x) where there are w levels of nestings of phi.
The corresponding operator, let's call it {G_0}, is an operation so powerful, that while 2{G_0}2 = 4, 2{G_0}3 is something so indescribably huge, that we have no hope to even begin to write down its value. And just for comparison, 2{4}10 is already so huge that it has exceeded the number of particles in the universe, or, for that matter, the number of particle combinations in the universe throughout its entire lifetime... yet this is less than a puny speck compared to the rest of the Grzegorczyk Hierarchy, which is child's play compared to the Ackermann function, which is less than nothing compared to the 2-level nested phi function... and here we're talking about something that corresponds with an
infinite number of nestings of the phi function! So, shall we talk about 2{G_0}4?
Ahahahaha... I see that Jonathan Bowers beat me to it... (saw his reply as I type mine)
But have no fear, these things have no end, as I said. According to what a mathematician told me, Bowers' BEAF notation is somewhere in the middle of the Veblen Hierarchy, meaning that Gamma_0 completely trumps it in terms of operator power.
But it's far from being the end -- as the _0 subscript hints at.
Now of course, it's trivial to construct Gamma_1, Gamma_2, or even Gamma_Gamma_Gamma_... (w times), but these are actually mere baby steps.
To get significantly beyond Gamma_0, we need to extend the Veblen phi function to take multiple arguments. So phi_z(x,y) would be a 2-argument version of phi_y(x), where the y serves as the equivalent of the original phi function's subscript. And now we get to nest the 2-argument phi function.
But at this point, we might as well just give up distinguishing subscripts from non-subscripts, and write phi(x,y,z). But now that we're at it, why stop at 3 arguments? Why not 5, 6, nay, 100 arguments? But let's not hold back -- let's construct the limiting case of phi with w arguments.
The resulting ordinal, which is so ridiculously and indescribably huge, is the so-called "small Veblen ordinal". Ah, but did you notice the adjective "small"?
Nevermind the fact that the operator corresponding with this hilariously huge ordinal is far beyond being beyond all description... We can go even higher by proceeding in this way: let's imagine a further extension of the phi function, in which the number of arguments is an
ordinal. So the small Veblen ordinal corresponds with a phi function of w arguments, but now we can substitute w with
any ordinal that we've previously constructed. Including the result of applying this insanely huge phi function to some other arguments.
For example, let's say we start with the small Veblen ordinal, let's call it v1 for convenience. We then construct a new phi function, that takes v1 arguments. Let me say that again. We're constructing an extended phi function, in which the number of arguments is the small Veblen ordinal -- which is an insanely huge transfinite ordinal. This isn't just an infinity of arguments; this is an infinity of infinities of infinities of ... infinities of arguments, where the structure of the the nesting of the word "infinity" in the previous sentence is equal to all those levels of nesting we built up starting from the Grzegorczyk Hierarchy to the Ackermann function to Gamma_0 all the way up to the small Veblen ordinal. This function is so ludicrously huge, that we don't even know how to describe the
number of arguments it takes except as an abstract ordinal! Now imagine unpacking such a function, where each level of unpacking represents the entire construction from ground zero to Gamma_0, and the number of levels of unpacking is the small Veblen ordinal.
Well, the thing about these pesky ordinals, is that they never stop.
The output of this insane function with (small Veblen ordinal) number of arguments, is just another ordinal. One that's so huge I don't even know how to describe it. Well, have no fear, we're going to now take this ordinal, far far beyond any means of description or comprehension, and make
that the number of arguments to our
next extension of the phi function. Are you starting to get some idea of where we're going now?
Good, 'cos now we're going to
really step on the gas pedal...
Let x be an ordinal representing the number of arguments our extension of the phi function has. Let's denote this as phi[x](...), where the ... represents x arguments (and remember x is not a finite number, but a transfinite ordinal that, by this point, is far beyond the small Veblen ordinal). Since the value of phi[x](...) is just another ordinal, say y, we can feed it back into the process and construct phi[y](...). We can, of course, do this repeatedly to the limit, i.e., do this w times. But that only actually gets us a few inches farther (relatively speaking, of course... even adding just
one more argument to phi already makes it explode like there's no tomorrow in magnitude, and here we're talking about adding infinitudes of arguments). We now take a step back, and repeat this process an ordinal number of times, and keep going as long as the new phi functions keep giving us larger and larger ordinals.
We'd never stop, of course. However, no matter how crazily huge the ordinals we're getting at every step, even at every limit, they actually remain
below a certain ordinal known as the large Veblen ordinal (finally, it shows its face!). Let's call the large Veblen ordinal v2. v2 is an ordinal that's so huge, that we actually cannot reach it from below using the phi functions. Or, more precisely speaking, in order for us to get v2 out of a phi function, the phi function would require v2 number of arguments. Put another way, v2 is so large that as long as the number of arguments to our phi function is less than v2 itself, the result of the phi function, no matter how large it is, is still smaller than v2. The only way we can get v2 out of a phi function, is if we have already constructed v2 beforehand, so that we can specify v2 as the number of arguments to our phi function.
If we start building hierarchies from below using our extended phi functions and feeding the ordinals they produce back into the system as the number of arguments for the next phi function, we will never reach v2. We can only bridge this chasm if we were given v2 in the first place. And this, ladies and gentleman, is the large Veblen ordinal. Can you imagine what kind of monstrous operator v2 would produce???
I mean, sure we know 2{v2}2 = 4, but 2{v2}3 defies all description, to say the least.
And 2{v2}10...
But wait, there's more!! (Didn't I tell you that when it comes to ordinals, there is no end?
) In spite of how crazily huge v2 is, it still belongs to the "small" class of
countable ordinals, that is, ordinals with cardinality aleph_0. Not only so, v2 is actually only in the initial segment of this class, called the
recursive ordinals. And it's not even anywhere near the end of the recursive ordinals; there are far huger ordinals, such as the Bachmann-Howard ordinal, that I won't even attempt to describe here. The Bachmann-Howard ordinal is so insanely huge, that you can't even
define it from below. At least with v2, you can define it as the supremum of all the ordinals producible by the extended phi functions, but in order to get to the Bachmann-Howard ordinal, you have to actually leap to the
uncountable ordinals and then "collapse" them back into the recursive set. Which, in a very real sense, is "cheating", because the uncountable ordinals include the Bachmann-Howard ordinal by definition, so you're actually implicitly assuming the construction of the Bachmann-Howard ordinal before you can begin to construct it.
Now imagine the operator that corresponds with the Bachmann-Howard ordinal. What would 2{BH}10 be??
But these are still just recursive ordinals...
The intrepid, or shall I say, the insane, would press on farther until they get to the so-called Church-Kleene ordinal, which is so huge that it is
uncomputable. Um... but it's only the first in the set of non-recursive countable ordinals... and we know that the set of
all countable ordinals is uncountable, yet the set of recursive ordinals is still countable, it means that there must be far more uncomputable ordinals than computable ones -- and yet each of them, by themselves, is countable. Meaning that it is still meaningful to speak of operators that we can generate from them -- in theory, anyways; since they're uncomputable, the operators they generate are also uncomputable -- uncomputably
huge, that is. And these uncomputably huge operators exist in a hierarchy
larger than the one we just visited -- they span a far, FAR larger range, than we did in going from +, *, ^ to the Bachmann-Howard ordinal.
But it never ends...
If you're crazy enough, you can push beyond these uncomputable countable ordinals until you reach the first
uncountable ordinal w_1. By which time you're all on your own, because now you're in territory so far out, that you're now at the far edges of set theory, and you can't even move forward without needing
extensions to set theory But that's never a problem for the nutcases who just can't get enough of fast-growing functions or operators. I mean, since we've left constructibility behind a long time ago, we need no longer be held back by such dalliances as the fact that none of the things we're going to talk about can ever be computed, and perhaps not even
defined in any computable sense. Since we're pushing far into the frontier, we might as well just take the liberty to adopt the Continuum Hypothesis as an axiom, which would allow us to translate any cardinal number into a corresponding ordinal in a well-defined way, which in turn lets us define operators that correspond with
uncountable ordinals. Needless to say, there's no hope whatsoever -- not even in theory -- of ever computing anything with these operators, but hey, that's a small price for being able to boast that we absolutely, totally, trumped everybody and everything else, right? And since we're at it, let's just also assume a few Large Cardinal axioms, just for the fun of it. So we can, for example, take the initial ordinal of an n-superstrong cardinal, and make an operator out of it. This operator would be so hilariously huge, that not only it's uncomputable (and arguably nearly undefinable), it may not even be possible to compare whether it's larger than another operator or not.
But the kicker is, the result of even such an unimaginable operator is still a
finite number.
We'll never be able to say pretty much
anything about this number, of course, but you can rest assured that it is absolutely guaranteed to trump any number anybody can ever name.
(Well, until they beat you at your own game by finding a cardinal that's stronger than yours...)
Most people think they understand how huge infinity is. They have
no idea...!!