Ordinal tetration: The issue of ${}^{\epsilon_0}\omega$

Solution 1:

One very sensible way to define ordinal tetration, pentation, etc is basically what Veblen was getting at with his hierarchy in his 1902 paper. It isn't the same definition as the two given above, but it is a very good one with some particularly deep properties that I think worth understanding.

Veblen did not have the terminology at the time to relate it to what we call tetration today. However, one way to understand it is as a series of higher ordinal operations going transfinitely to "omegation" and beyond.

Below I will give a different exposition of the Veblen hierarchy than usual, as a transfinite generalization of Knuth's up-arrow notation. It yields basically the same result as the original, but with the definition changed slightly in trivial ways to make clear the relationship with iterated operations, using more modern notation. The Veblen normal form theorem holds for this up-arrow notation, so that the set of all ordinals that can be expressed with this notation is exactly those less than or equal to the Feferman–Schütte ordinal.

ADDITION

To get the basic premise, let's start by looking at ordinal addition. Look at the following:

$\omega^2 = \omega+\omega+\omega+...$

In other words, you can think of $\omega^2$ as an infinite chain of additions of order-type $\omega$. As a result, we get the following

$\omega+\omega^2 = \omega+(\omega+\omega+\omega+...) = \omega+\omega+\omega+... = \omega^2$

So we can see that $\omega^2$ is a fixed point of ordinal left-addition.

MULTIPLICATION

We get a similar result with multiplication:

$\omega^\omega = \omega \cdot \omega \cdot \omega \cdot ...$

$\omega \cdot \omega^\omega = \omega \cdot (\omega \cdot \omega \cdot \omega \cdot ...) = \omega \cdot \omega \cdot \omega \cdot ... = \omega^\omega$

Same thing: $\omega^\omega$ is a fixed point of left-multiplication.

EXPONENTIATION

Continuing with exponentiation, we get the following:

$\epsilon_0 = \omega^{\omega^{\omega^{...}}}$

${\omega}^{\epsilon_0} = \omega^{\left(\omega^{\omega^{\omega^{...}}}\right)} = \omega^{\omega^{\omega^{...}}} = \epsilon_0$

GENERALIZING: FIXED POINTS

There is a basic pattern to all these things: we have an infinite chain of order-type $\omega$, we prepend another element to the chain, and we get the same thing. All this is really saying is the basic principle of ordinal notation:

$1 + \omega = \omega$

It turns out we can use this as a starting point to define ordinal tetration, as well as our higher operations. This is a different exposition than Veblen gave, but it gets us to the same place.

Basically, the quantum leap here is to assert that however we define ordinal tetration, we want it to have the following property:

$\alpha \uparrow \uparrow (1+\beta) = \alpha^{\alpha \uparrow \uparrow \beta}$

(Note this is not the same as if we had written $\beta+1$ rather than $1+\beta$ above. Note this is also different from the other two definitions given in the previous answers.)

It is fairly easy to see that the above property holds for the naive definition of ordinal tetration for finite heights. It is also easy to see that assuming we cook up some definition that makes $\omega \uparrow \uparrow \omega = \omega^{\omega^{\omega^{...}}} = \epsilon_0$, that the property will hold.

But of course, the basic question is, what should $\omega \uparrow \uparrow (\omega+1)$ be?

And this is Veblen's basic insight, phrased in a different way: if we the above property holds, then we know that we have

$\omega \uparrow \uparrow (1+\omega+1) = \omega^{\omega \uparrow \uparrow (\omega+1)}$

However, due to the definition of ordinal tetration, we know that $1+\omega+1 = \omega+1$!! So the above simply becomes the following:

$\omega \uparrow \uparrow (\omega+1) = \omega^{\omega \uparrow \uparrow (\omega+1)}$

So we know that whatever this is, it must also be a fixed point of exponentiation! And indeed, this holds for any infinite ordinal $\Omega \geq \omega$:

$\omega \uparrow \uparrow \Omega = \omega^{\omega \uparrow \uparrow \Omega}$

These are all fixed points of exponentiation!

As a result, we can see that assuming our main property holds, we know every infinite height must be a fixed point of exponentiation.

VEBLEN UP-ARROW NOTATION

So now that we know each infinite height is a fixed point, how do we define tetration for infinite heights?

The "Veblen-esque" way to do this would simply define these to be all the fixed points of the exponentiation operator, in sequence. So we would have $\omega \uparrow \uparrow \omega$ be the first fixed point of $\omega^x$ (or $\epsilon_0$), $\omega \uparrow \uparrow (\omega+1)$ be the next fixed point (or $\epsilon_1$), and so on.

That is, rather than trying to find some magical definition of tetration that makes this happen somehow automatically, we simply define this so that it is so, for infinite heights. This yields the following definition for tetration:

$ \alpha \uparrow \uparrow 0 = 1 \\ \alpha \uparrow \uparrow (1+\beta) = \alpha^{\alpha \uparrow \uparrow \beta} \\ \alpha \uparrow \uparrow (\omega+\beta) = \beta\text{'th fixed point of } \alpha^x = x $

As a result, we have:

$\omega \uparrow \uparrow (\omega+n) = \varphi_1(n) = \epsilon_n$

where $\varphi_1(x)$ is the first Veblen function (assuming $\varphi_0(x) = \omega^x$). All we have done is shift the argument by $\omega$, so that we first get finite tetrations before looking at the infinite fixed points. (Note that the argument "catches up" at $\beta=\omega^2$, so that the two sequences agree from that point on.)

It so happens that we can even extend the above to define pentation, hexation, etc, at least for finite values. We simply have the following:

$ \alpha \uparrow^1 \beta = \alpha^\beta \\ \alpha \uparrow^n 0 = 1 \\ \alpha \uparrow^{n+1} (1+\beta) = \alpha \uparrow^{n}(\alpha \uparrow^{n+1} \beta) \\ \alpha \uparrow^{n+1} (\omega+\beta) = \beta\text{'th fixed point of } \alpha \uparrow^{n} x = x $

It is not difficult to see that as a result, we have

$\omega \uparrow^{n+1} (\omega+\beta) = \varphi_n(\beta)$

where $\varphi_n(x)$ is the n'th function in the Veblen hierarchy (assuming $\varphi_0(x) = \omega^x$). The only difference, similar to tetration, is that the argument is shifted by $\omega$, and "catches up" at $\beta=\omega^2$. This is not enough to change the location of the fixed points as we go to higher operations, however, since they are all greater than $\omega^2$ anyway, so we get the same hierarchy.

Additionally, even if the base is not $\omega$, the above is exactly the same as the generalized Veblen hierarchy where we start with $\varphi_0(x) = \alpha^x$ and proceed from there, with the only technicality being if the base is finite (such as $\alpha=2$). In that situation, we still have the Veblen hierarchy, but with the one caveat that $2 \uparrow^n \omega = \omega$ for all $n$, whereas the $n$'th Veblen function $\varphi_n(0)$ "skips" this initial entry of $\omega$, due to the way the argument is shifted. If we prepend an initial $\omega$ to the higher Veblen functions we get the same sequence as our definition, so we have basically the same structure.

So for all our unorthodox exposition here, we have basically just rediscovered the Veblen hierarchy, simply expressed in more familiar terms for those who prefer talking about iterated operations and Knuth's up-arrow notation.

EXAMPLES

Here are some examples:

$ \omega \uparrow^2 \omega = \epsilon_0 \\ \omega \uparrow^2 (\omega+1) = \epsilon_1 \\ \omega \uparrow^2 (\omega+\omega) = \omega \uparrow^2 (\omega\cdot 2) = \epsilon_\omega \\ \omega \uparrow^2 (\omega+\omega^2) = \omega \uparrow^2 \omega^2 = \epsilon_{\omega^2} \quad \small{\text{(note how the argument catches up at } \omega^2 \text{ here)}}\\$

$ \omega \uparrow^3 2 = \omega \uparrow^2 \omega = \epsilon_0 \\ \omega \uparrow^3 3 = \omega \uparrow^2 (\omega \uparrow^2 \omega) = \omega \uparrow^2 \epsilon_0 = \epsilon_{\epsilon_0} \\ \omega \uparrow^3 \omega = \epsilon_{\epsilon_{\epsilon_{...}}} = \zeta_0 \\ \omega \uparrow^3 (\omega+1) = \zeta_1 \\ $

$ \omega \uparrow^4 2 = \omega \uparrow^3 \omega = \zeta_0 \\ \omega \uparrow^4 3 = \omega \uparrow^3 (\omega \uparrow^3 \omega) = \omega \uparrow^3 \zeta_0 = \zeta_{\zeta_0} \\ \omega \uparrow^4 \omega = \zeta_{\zeta_{\zeta_{...}}} = \eta_0 \\ \omega \uparrow^4 (\omega+1) = \eta_1 $

$ \omega \uparrow^5 \omega = \eta_{\eta_{\eta_{...}}} $

TRANSFINITELY ITERATED OPERATIONS

Given the above, we may wonder what the largest ordinal is that we can express using finite numbers, the symbol $\omega$, addition, multiplication, and the up-arrow notation above. It happens that we can express all ordinals less than the following ordinal:

$\omega \uparrow \uparrow \uparrow \uparrow ... \omega$

or, written more formally, the following supremum:

$\sup \left \{\omega \uparrow^1 \omega, \omega \uparrow^2 \omega, \omega \uparrow^3 \omega, ... \right\}$

This is the value $\varphi_\omega(0)$, which is still fairly small. To exceed this, we will need to extend our definition transfinitely to $\omega$ and beyond. This is indeed possible, and several different ways of doing so all end up yielding basically the same thing as Veblen's hierarchy for transfinite indices.

Naively, we might simply decide that for limit ordinal $\gamma$, we have:

$\alpha \uparrow^{\lambda} \beta = \sup \left\{\alpha \uparrow^{\gamma} \beta : \gamma < \lambda\right\}$

The only issue with this definition is that, for example, we get the following:

$\omega \uparrow^\omega \omega = \sup \left\{\omega \uparrow^1 \omega, \omega \uparrow^2 \omega, \omega \uparrow^3 \omega, ...\right\}$

But note that we also have

$\omega \uparrow^\omega 2 = \sup \left\{\omega \uparrow^1 2, \omega \uparrow^2 2, \omega \uparrow^3 2, ...\right\} \\$

And noting that $\omega \uparrow^n 2 = \omega \uparrow^{n-1} \omega$, we get

$\omega \uparrow^\omega 2 = \sup \left\{\omega \cdot \omega, \omega \uparrow^1 \omega, \omega \uparrow^2 \omega, ...\right\} \\$

As a result, we get

$\omega \uparrow^\omega 2 = \omega \uparrow^\omega \omega$

which also holds for all finite heights, not just $2$, and for all limit ordinals, not just $\lambda = \omega$.

In general, as shown in this answer (https://math.stackexchange.com/a/3112095/52694), using the supremum definition, we will get a very strange "dummy" function that remains constant at some value, and then suddenly "skips" to another value at some point and remains constant for another long stretch, and so on.

Interestingly, however, the values at which it "skips" afterward are the fixed points that are common to all previous operations. As a result, we can, if we want, use the above naive definition, and then continue the hierarchy as per usual, regaining the exact definition of the transfinite Veblen hierarchy! The only difference is, we have these weird, superfluous dummy functions inserted at each limit ordinal, but then the function enumerating the fixed points of that is then the same as the traditional definition of the Veblen functions at the limit ordinal. So we have again rediscovered the Veblen hierarchy, except our naive way of doing things has shifted the index of $\varphi_n$ by 1 near each limit ordinal.

Of course, we can simply change our naive definition as follows, to bring everything in line with the Veblen hierarchy, for $\lambda$ a limit ordinal:

$ \alpha \uparrow^{\lambda} (\omega+\beta) = \beta\text{'th fixed point of }\sup \left\{\alpha \uparrow^{\gamma} x : \gamma < \lambda\right\} = x $

which will be the $\beta$'th common fixed point of all previous operations, bringing things in agreement with the usual Veblen hierarchy definition at limit ordinals, although again with the argument shifted by $\omega$.

So once again, in our unorthodox way, we have rediscovered the Veblen hierarchy, simply expressed as a transfinite generalization of Knuth's up-arrow notation.

QUIRK

The only real quirk of the above definition is how we should define $\alpha \uparrow^\omega 2$, for instance, or in general for finite heights. At limit ordinals, there is no predecessor operation to iterate some finite number of times!

It is fairly easy to see the above "fixed point of supremum" definition will set each finite height equal to $\alpha \uparrow^\omega \omega$, so that the function has an initial constant run for all finite values up to and including $\omega$, after which things then proceed in agreement with the usual Veblen definition. However, this is not the only way to do it: you could also leave it undefined for finite values, for instance. Or you could say that at limit ordinals, the fixed-point enumeration begins at $0$, rather than $\omega$ (although this complicates the definition in other ways regarding continuity).

These are basically arcane minutia that, for my purposes, don't really matter. The point is that starting from some simple premises with iterated exponentiation and Knuth's up-arrow notation, we have basically managed to rediscover the Veblen hierarchy, and make sense of it in modern terms.

FEFERMAN–SCHÜTTE ORDINAL

Now that we have done the above, we may finally define the following very large ordinal, for which all ordinals less than it have a finite expression of numbers, the symbol $\omega$, addition, multiplication, and up-arrow:

$\Gamma_0 = \omega \uparrow^{(\omega \uparrow^{(\omega \uparrow^{(...)} \omega)} \omega)} \omega$

or, written formally,

$\Gamma_0 = \sup \left\{ \omega \uparrow \omega, \omega \uparrow^{(\omega \uparrow \omega )} \omega, \omega \uparrow^{(\omega \uparrow^{(\omega \uparrow \omega) } \omega )} \omega, ... \right\}$

This is the famous Feferman–Schütte ordinal.

I am not sure how to extend this to get the small or large Veblen ordinals, because I'm not sure how the multivariate Veblen function relates to the notation presented here. (I would be curious to know if anyone knows how this would fit into this paradigm.)

SUMMARY

Many, many people have had the thought that since $\epsilon_0 = \omega^{\omega^{\omega^{...}}}$, it in some sense should be defined as the infinite ordinal tetration $^{\omega}\omega$, leading to questions about how ordinal tetration or higher operations should be defined.

While the answer to these questions is in some sense a matter of aesthetic and in no way unique, the notion that, for some higher operation, the infinite heights should be fixed points of the previous operation is basically the thought behind Veblen's hierarchy.

The exposition here shows that following this premise, but starting with a more modern perspective, we can basically regain the Veblen hierarchy as a particularly natural transfinite generalization of Knuth's up-arrow notation.

Solution 2:

So while in the main chat room, I devised a way to define tetration, and it works quite nicely.

$$\alpha\uparrow\uparrow\beta=\begin{cases}0,&\beta=-1\\1,&\beta=0\\\alpha,&\beta=1\\\alpha^{\alpha\uparrow\uparrow\zeta},&\alpha<\omega,\beta=\zeta+1>1\\(\alpha\uparrow\uparrow\zeta)^{\alpha\uparrow\uparrow\zeta},&\alpha\ge\omega,\beta=\zeta+1>1\\\sup\{\alpha\uparrow\uparrow(\beta[\eta])|\eta<\operatorname{cf}(\beta)\},&\beta\in\mathbb{Lim}\end{cases}$$

For finite $\alpha,\beta$, $\alpha\uparrow\uparrow\beta$ is what you expect it to be. Then,

$$\alpha\uparrow\uparrow\beta=\omega\forall\alpha<\omega\land\beta\ge\omega$$

Then we have,

$$\omega\uparrow\uparrow1=\omega\\\omega\uparrow\uparrow2=\omega^\omega\\\omega\uparrow\uparrow3=(\omega^\omega)^{\omega^\omega}=\omega^{\omega^\omega}$$

And so forth. Then,

$$\omega\uparrow\uparrow\omega=\varepsilon_0\\\omega\uparrow\uparrow(\omega+1)=\varepsilon_0^{\varepsilon_0}\\\vdots\\\omega\uparrow\uparrow(\omega2)=\varepsilon_1\\\vdots\\\omega\uparrow\uparrow(\omega(1+\beta))=\varepsilon_\beta\forall\beta\le\zeta_0$$

Thus, by this definition,

$$\omega\uparrow\uparrow\varepsilon_0=\varepsilon_{\varepsilon_0}$$

Edit:

The following definition may be nicer to use:

$$\alpha\uparrow^\beta\delta=\begin{cases}\alpha,&\delta=1\\\alpha^\delta,&\beta=1\\\sup\{(\alpha\uparrow^\beta\psi)\uparrow^\gamma(\alpha\uparrow^\beta\psi)|0<\gamma<\beta,0<\psi<\delta\},&\text{else}\end{cases}$$

And likewise extends to higher operations.