Fixed points of ordinal exponentiation for bases besides $\omega$

fixed points-fixed-point-theoremsordinalsset-theory

The first fixed point of the map $x \to \omega^x$ is the first epsilon number $\epsilon_0$, which is the supremum of $\omega, \omega^\omega, \omega^{\omega^\omega}, … = \omega^{\omega^{\omega^{.^{.^{.}}}}}$.

How does this change if we use a different base for ordinal exponentiation, for instance $x \to (\omega+1)^x$? Then the first fixed point would be the supremum of $\omega+1, (\omega+1)^{(\omega+1)}, (\omega+1)^{(\omega+1)^{(\omega+1)}}, … = (\omega+1)^{(\omega+1)^{(\omega+1)^{.^{.^{.}}}}}$.

In general, my questions are:

Does changing the base to $\omega+1$ yield a different class of fixed points than the epsilon numbers?
What about changing the base to $\omega\cdot2$, or $\omega^2$, or in general, any countable ordinal less than $\epsilon_0$? (Or more than $\epsilon_0$?)
Do you get a different class of fixed points for every base? If not, when do you get a different class?

A nice way to put this is to ask about the fixed points of the general function $f(\alpha, \beta) \to \alpha^\beta$, which should be continuous and strictly increasing (a normal function) in the argument $\beta$. Are these characterized and well-known?

Best Answer

If $\omega\le\alpha<\epsilon_0$, then we get a "dovetailing" phenomenon (and so identical fixed points) - namely, any finite exponential tower of $\alpha$s is bounded by some finite exponential tower of $\omega$s (since $\alpha<\epsilon_0$) and vice versa (since $\omega\le\alpha$). For example, taking $\alpha=\omega^2+1$ we have $\alpha<\omega^\omega$, so $$\alpha^{\alpha^\alpha}\le\omega^{\omega^{\omega^{\omega^{\omega^{\omega}}}}}.$$ In general, it's easy to show that if $f, g$ are normal and for every finite $n$ there is some finite $m$ such that $f(n)<g(m)$ and $g(n)<f(m)$, then the least fixed points of $f$ and $g$ are equal.

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.

Modifying the “base” of Veblen’s hierarchy to exceed $\Gamma_0$

Question 1: If we include finite ordinals, then the only solution is $\Phi_{1,1}(0) = 1$. (and $\Phi_{0,0}(0) = 0$ if one chooses to set $0^0 = 0$) For $\alpha > 1$, the fixed points of $\Phi_{\alpha,0}(x) = \alpha^x$ cannot be $\alpha^0$ or $\alpha^1$, so they must be at least $\alpha^2$. In particular, they will be larger than $\alpha$, and so $\Phi_{\alpha,\alpha}(0)$, being a fixed point of $\alpha^x$, will be larger than $\alpha$ as well.

Question 2: Suppose $\alpha > 1$, and $\beta$ is a fixed point of the function $f(x) = \alpha^x$. As above, we see that $\beta > \alpha$. Also, $\beta = \alpha^\beta \ge 2^\beta \ge \beta$, so $\beta = 2^\beta$. Clearly $\beta$ cannot be finite, and if $\beta \ge \omega+1$ then $\beta \ge \sup \{\omega+1, 2^{\omega+1}, 2^{2^{\omega+1}}, 2^{2^{2^{\omega+1}}},\cdots\} = \sup \{\omega+1, \omega \cdot 2, \omega^2, \omega^\omega, \omega^{\omega^\omega},\cdots\} = \varepsilon_0$. Similarly, if $\beta \ge \varepsilon_{\gamma}+1$, then $\beta \ge \varepsilon_{\gamma+1}$. So $\beta$ must belong to the class $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$. Going the other direction, if $\beta$ is a member of $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$, and is larger than $\alpha$, then $\alpha \beta = \beta$, so $\beta \le \alpha^\beta \le (2^\alpha)^\beta = 2^{(\alpha \beta)} = 2^\beta = \beta$, so $\alpha^\beta = \beta$. Hence the members of the class $\{\Phi_{\alpha,1}(x) | x \in \text{Ord}\}$ are the members of the class $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$ that are larger than $\alpha$. So for $\alpha$ infinite, $\Phi_{\alpha,1}(x) = \varphi_1 (\gamma + x)$ for some ordinal $\gamma$ with $\gamma \le \alpha+1$. (We need $\alpha+1$, since, for instance, $\Phi_{\varphi_2(0),1}(0) = \varphi_1(\varphi_2(0) + 1)$.)

We can now use induction: Given that $\Phi_{\alpha,\beta}(x) = \varphi_\beta(\gamma+x)$ for some $\gamma \le \alpha+1$, we see that for any $\zeta$, $\Phi_{\alpha,\beta+1}(\zeta)$ satisfies $x = \varphi_\beta(\gamma+x)$, and hence is larger than $\gamma$. Also, $x = \varphi_\beta(\gamma+x) \ge \varphi_\beta(x) \ge x$, so $x$ is a fixed point of $\varphi_\beta$. Going the other direction, if $x$ is larger than $\gamma$ and is a fixed point of $\varphi_\beta$, then $x$, being an $\varepsilon$-number, satisfies $\gamma+x = x$, so $x = \varphi_\beta(x) = \varphi_\beta(\gamma+x)$. So the fixed points of $\varphi_\beta(\gamma+x)$ are precisely the fixed points of $\varphi_\beta(x)$ that are greater than $\gamma$, and so $\Phi_{\alpha,\beta+1}(x) = \varphi_{\beta+1}(\gamma' + x)$, for some $\gamma' \le \gamma+1$, with strict inequality when $\gamma = \alpha+1$; hence $\gamma' \le \alpha+1$.

Furthermore, suppose $\beta$ is a limit ordinal, and suppose, for all $\delta < \beta$, we have $\Phi_{\alpha,\delta}(x) = \varphi_\delta(\gamma_\delta + x)$ for some ordinals $\gamma_\delta \le \alpha+1$. We see that $\Phi_{\alpha,\beta}(x)$ must be greater than $\alpha$, and also, since it is a fixed point of $\varphi_\delta$ for all $\delta < \beta$, must be of the form $\varphi_\beta(\chi)$. Going the other direction, if $x$ is greater than $\alpha$ and of the form $\varphi_\beta(\chi)$, then $x$, being an $\varepsilon$-number, satisfies $\gamma_\delta + x = x$ for all $\delta < \beta$. So for any $\delta < \beta$, $\varphi_\delta(\gamma_\delta + x) = \varphi_\delta(x) = x$, and so $x$ is of the form $\Phi_{\alpha,\beta}(\chi')$. So $\Phi_{\alpha,\beta}(x) = \varphi_\beta(\gamma_\beta + x)$ for some $\gamma_\beta \le \alpha+1$.

So, by transfinite induction, there exists ordinals $\gamma_{\alpha,\beta} \le \alpha+1$ such that, for all $\alpha, \beta, x,$ with $\alpha$ infinite, we have $\Phi_{\alpha,\beta}(x) = \varphi_\beta (\gamma_{\alpha,\beta}+x)$. If $\alpha, \beta, x < \Gamma_0$, then $\gamma_{\alpha,\beta} + x < \Gamma_0$, so $\varphi_\beta(\gamma_\beta+x) < \Gamma_0$.