12
$\begingroup$

So in the past few months when trying to learn about the properties of the fixed points in ordinals as I move from $0$ to $\epsilon_{\epsilon_0}$ I noticed when moving from $\epsilon_n$ to the next one $\epsilon_{n+1}$, the operation that does that is a left associative operation i.e.

$${\tiny⋰}^{\epsilon_n^{\epsilon_n}}={}^{\omega}(\epsilon_n)=\epsilon_{n+1}$$

Since the exact same rule holds for all epsilons to those that are indexed by successor ordinals, unwrapping the whole thing gives $\epsilon_{n},n < \omega$ in terms of $\epsilon_0$:

$$\epsilon_n=\underbrace{{}^{\omega}(\cdots{}^{\omega}({}^{\omega}(}_{\textrm{n times}}\epsilon_0)))=\underbrace{{}^{\omega}(\cdots{}^{\omega}({}^{\omega}(}_{\textrm{n-1 times}}\epsilon_1)))=\underbrace{{}^{\omega}(\cdots{}^{\omega}({}^{\omega}(}_{\textrm{n-2 times}}\epsilon_2)))=etc.$$

That means, while $\epsilon_0$ is informally speaking the same as ${}^{\omega}\omega=\omega^{\omega^⋰}$ hence $\omega [5] 2=\omega\uparrow^3 2$, a pentation, all subsequent epsilon numbers are not tetration because the iterative operations that define them recursively is left associative but not right associative (as it would be the case for hyperoperators).

This then prompt the question: What prevent us from defining ordinal tetration, do they end up collapsing into $\epsilon_0$ or related terms thus making them unnecessary, or something else happens

To begin, since $\epsilon_0=\omega[5]2$, the next probable candidate for $\omega [5]3$ will be ${}^{{}^{\omega}}{}^{\omega}\omega=\left(\left({}^{({}^{\omega})}{}^{\omega}\right)\omega\right)$ Note the definition of $\epsilon_0$ means

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

However, because exponentiation already lost associativity, tetration have almost no useful general identities except for finite integers $a,b,n$ (Using exponential identity $\alpha^{\beta\gamma}=(\alpha^\beta)^\gamma$ and that finite integers at the index commute)

$$(a^b)^{{}^{n-1}a}=({}^na)^b$$

Therefore, no known ordinal arithmetic can be used to simplify ${}^{\epsilon_0}\omega$. This prompt me to try a sandwiching approach as follows (where $f$ is some increasing normal function that serves as the iterative operation that climb up this sequence):

$${}^{({}^j\omega)}\omega<f({}^{({}^j\omega)}\omega)<{}^{({}^{j+1}\omega)}\omega$$

If we move through all $j < \omega$ and take the supremum, then we discover that ${}^{\epsilon_0}\omega$ is a fixed point of $f$. But nothing can be deduced further as I have no idea how to derive $f$ explicitly other than it is an operation that is similar to exponentiation, but only applied to the height i.e. $f: {}^j\omega \to \omega^{{}^j\omega}$. Either way, it had said nothing on whether ${}^{\epsilon_0}\omega$ is one of the epsilon number or where it is ordered wrt the usual ordinals.

Wikpedia also has a talk section saying that ordinal tetration is trivial, or that it will collapse into $\epsilon_0$. But as shown with ${}^{\epsilon_0}\omega$, I have so far failed to reproduce their results.

What other squeezing schemes (i.e. where should I put my $j$) I can use (or other properties of ordinals) in order to determine the value of ${}^{\epsilon_0}\omega$ ?

(NB You know my main focus is not large countable numbers since Veblen functions will eventually overshoot any hyperoperation)

$\endgroup$
  • $\begingroup$ For a definition of ordinal tetration, see the 5th comment under my answer here. See also John Baez's 3 essays on Large Countable Ordinals in June-July 2016: Part 1 AND Part 2 AND Part 3 $\endgroup$ – Dave L. Renfro Jun 7 '17 at 16:09
  • $\begingroup$ Incidentally, using the definition of ordinal tetration I gave in my comment (involves a bottom-up evaluation of an exponential tower; the usual top-down evaluation of exponential towers doesn't work because of collapsing problems), if $\alpha \geq 2$ and $\beta \geq \omega,$ then one can show that $^{\alpha}{\beta} = {\alpha}^{{\alpha}^{\beta}}.$ $\endgroup$ – Dave L. Renfro Jun 7 '17 at 16:16
  • $\begingroup$ @DaveL.Renfro Two particularly interesting answers below, the accepted one and then one using fixed-points, may interest you. After noticing your links I can't help to also ask if you are interested in ordinal collapsing functions as well, if you don't mind. $\endgroup$ – Simply Beautiful Art Aug 16 at 12:59
  • $\begingroup$ @Simply Beautiful Art: Since the late 1980s I've been collecting a lot of literature on large ordinals, ordinal notations, and such (no so much in the last 10-15 years, however), but most of it is beyond what I know and thus far I have not made much of an attempt to study it, aside from a little of the Bachmann method for using notation based on the first uncountable ordinal such as is described in Normal functions and constructive ordinal notations by Larry William Miller. (continued) $\endgroup$ – Dave L. Renfro Aug 16 at 17:09
  • $\begingroup$ I spent maybe 4-6 weeks in June-July 2013 working on an extensive revision of this answer, but the result grew to about the nearly 2 maximum-length Stack Exchange answers (50,000 character length) and I didn't really want to shorten it (nor I had completely finished it), and it was extremely time consuming to "compile" due to the complexity of the math expressions, so I wasn't sure what to do, and figured that after a few years maybe at least computers and internet speed would help take care of the second problem. (continued) $\endgroup$ – Dave L. Renfro Aug 16 at 17:20
1
$\begingroup$

Some time ago I happened to stumble upon an extension of the usual ordinal arithmetic, which I've found to satisfy many properties which may be interesting to consider, including nice relationships to Veblen's functions, a tighter version of the "sandwiching" function you sought, and consequentially identities that allow bases to be changed, reducing things such as ${}^{\omega+\omega}\omega$ to ${}^\omega({}^\omega\omega)$.

Motivation

Rather than Mike Battaglia's approach using left-sided recursion $(\omega^{1+x}=\omega\cdot(\omega^x))$, I sought an approach which used right-sided recursion $(\omega^{x+1}=(\omega^x)\cdot\omega)$ which unified the desired tetration $(\omega\uparrow\uparrow3=\omega^{(\omega^\omega)}$ instead of $\omega\uparrow\uparrow3=(\omega^\omega)^\omega)$ with lower hyperoperators.

At the core of this extension was my answer to the question:

Why should $\omega\uparrow\uparrow3=\omega^{\omega\uparrow\uparrow2}$ instead of $(\omega\uparrow\uparrow2)^\omega$, since the usual definitions have $\omega^3=(\omega^2)\cdot\omega$ and more generally $\omega^{\alpha+1}=(\omega^\alpha)\cdot\omega$?

Mike Battaglia's approach answers this question by suggesting the recursion is left-sided, but if we wish to stay true to the right-sided recursion, then we would end up getting

$$\omega\uparrow\uparrow(\alpha+1)=(\omega\uparrow\uparrow\alpha)\uparrow\omega$$

and if we were to use this and its higher hyperoperator extensions, there wouldn't actually be any issues. Note that $\varepsilon_0^\omega>\varepsilon_0$ as well, so this does not end up becoming constant eventually. It also aligns with lower hyperoperators.

So what is the issue with this? Why do we desire the recursion to work out on the other side?

My answer is that it's simply not as big as it could be. With lower hyperoperations, we can get away with saying that using

$$\omega\cdot(\omega^\alpha)\le(\omega^\alpha)\cdot\omega$$

so choosing the right side for $\omega^{\alpha+1}$ guarantees the result is as large as it could be while staying true to being recursively defined, but tetration is the first point where this makes a difference.

Definition

As such my extension of the usual ordinal arithmetic relies on simply taking the larger of $\alpha\uparrow(\alpha\uparrow\uparrow\beta)$ and $(\alpha\uparrow\uparrow\beta)\uparrow\alpha$. In full, my definition is given by

$$\alpha\uparrow^\mu\beta:=\begin{cases}\alpha\cdot\beta,&\mu=0\\1,&\mu\ne0\land\beta=0\\\sup\{\alpha\uparrow^{\mu'}(\alpha\uparrow^\mu\beta'),(\alpha\uparrow^\mu\beta')\uparrow^{\mu'}\alpha~|~\beta'<\beta\land\mu'<\mu\}&\mu\ne0\land\beta\ne0\end{cases}$$

The above definition is meant to encompass all limit cases, such as $\alpha\uparrow^2\omega$ and $\alpha\uparrow^\omega2$. This can be broken down a bit using the facts that my hyperoperators are increasing (strictly in all arguments other than $\alpha$ except for trivial cases such as $\alpha,\beta=0,1$):

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

$\alpha\uparrow^\mu(\beta+1)=\sup\{\alpha\uparrow^{\mu'}(\alpha\uparrow^\mu\beta),(\alpha\uparrow^\mu\beta)\uparrow^{\mu'}\alpha~|~\mu'<\mu\}$

$\alpha\uparrow^\mu\beta=\sup\{\alpha\uparrow^\mu\beta'~|~\beta'<\beta\}$, $\beta$ is a limit ordinal.

Furthermore, one can prove that the only times that right-sided recursion $(\alpha\uparrow\uparrow(\beta+1)=(\alpha\uparrow\uparrow\beta)\uparrow\alpha)$ occurs for $\alpha\uparrow^\mu\beta$ are when $\mu=0,1,$ or is a limit ordinal, or when $\beta$ is the successor of a non-zero limit ordinal. Otherwise left-sided recursion $(\alpha\uparrow\uparrow(\beta+1)=\alpha\uparrow(\alpha\uparrow\uparrow\beta))$ is always used.

$\rm\large Examples$

Below we present some examples in base $\omega$, but we point out that there are interesting examples in bases other than $\omega$ around the base changing formulae section.

Tetration

Here are some examples for base $\omega$:

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

$\omega\uparrow^2(\omega+1)=(\omega\uparrow^2\omega)\uparrow\omega=\varepsilon_0^\omega=\omega^{\omega^{\varepsilon_0+1}}$ (note this is the first point where tetration "swaps" directions)

$\omega\uparrow^2(\omega+2)=\omega\uparrow(\omega\uparrow^2(\omega+1))=\omega^{\omega^{\omega^{\varepsilon_0+1}}}$ (and then we return to the usual tetration recursion)

$\omega\uparrow^2(\omega+\omega)=\omega\uparrow^2(\omega\cdot2)=\varepsilon_1$

$\omega\uparrow^2(\omega\cdot2+1)=\varepsilon_1^\omega=\omega^{\omega^{\varepsilon_1+1}}$ (swap after limit ordinals)

$\omega\uparrow^2(\omega\cdot2+2)=\omega^{\omega^{\omega^{\varepsilon_1+1}}}$ (normal tetration recursion otherwise)

$\omega\uparrow^2(\omega\cdot3)=\varepsilon_2$

$\omega\uparrow^2(\omega^2)=\varepsilon_\omega$

Higher hyperoperators

Some more examples for base $\omega$:

$\omega\uparrow^32=\omega\uparrow^2\omega=\varepsilon_0$

$\omega\uparrow^33=\omega\uparrow^2(\omega\uparrow^32)={}^{{}^\omega\omega}\omega=\varepsilon_{\varepsilon_0}$

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

$\omega\uparrow^3\omega=\zeta_0$

$\omega\uparrow^3(\omega+1)=\zeta_0\uparrow^2\omega=\varepsilon_{\zeta_0+1}$ (swapped direction)

$\omega\uparrow^3(\omega+2)=\varepsilon_{\varepsilon_{\zeta_0+1}}$

$\omega\uparrow^3(\omega\cdot2)=\zeta_1$

$~$

$\omega\uparrow^42=\omega\uparrow^3\omega=\zeta_0$

$\omega\uparrow^43=\zeta_{\zeta_0}$

$\omega\uparrow^4\omega=\eta_0$

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

Transfinite hyperoperators $(\uparrow^{\ge\omega})$

We note that our approach differs from Mike Battaglia's approach for these cases. We do not use continuity in $\mu$ but rather just apply lower hyperoperations and take the supremum of the result. This aligns nicely with the behavior of the $\omega$-th Veblen function, which is equivalent to the supremum over applying all $n$-th Veblen functions.

Examples for base $\omega$:

$\omega\uparrow^\omega2=\varphi_\omega(0)$

$\omega\uparrow^\omega3=\varphi_\omega(1)$

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

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

As with Mike Battaglia's, most other bases will correspond to changing the initial base used in $\varphi_0$, and the above still applies.

Relationship to Veblen's functions

It can be shown that my hyperoperators satisfy

$\omega\uparrow^{1+\mu+1}(\omega+\omega\cdot\beta)=\varphi_{\mu+1}(\beta)$

and for limit ordinals $\mu$,

$\omega\uparrow^\mu(2+\beta)=\varphi_\mu(\beta)$

It is interesting to see that the differences between the successor and limit cases for $\mu$ can be seen from fundamental sequences of $\varphi_\mu$. For successor $\mu=\gamma+1$, one usually iterates over $\varphi_\gamma$, which corresponds to $\omega$ steps in hyperoperators. For limit $\mu$, one can simply take the limit over applying $\varphi_\gamma$ for $\gamma<\mu$, which is what we've done.

In this sense, our hyperoperator can be interpreted as a way of breaking Mike Battaglia's approach down further, giving us ordinals "between" the fixed-points.

It is also interesting to note that the initial "step" between these fixed-points uses right-sided recursion, which causes

$\omega\uparrow^2(\omega+\omega\cdot\beta+1)=\omega\uparrow\omega\uparrow(\varepsilon_\beta+1)$

$\omega\uparrow^{1+\mu+1}(\omega+\omega\cdot\beta+1)=\varphi_\mu(\varphi_{\mu+1}(\beta)+1)$ when $\mu$ is a successor ordinal.

$\omega\uparrow^{1+\mu+1}(\omega+\omega\cdot\beta+1)=\varphi_\mu(\varphi_{\mu+1}(\beta)+\omega)$ when $\mu$ is a limit ordinal.

When attempting to work out these relations further, some peculiar identities arise:

\begin{align}\varepsilon_0&=\omega\uparrow^2\omega=\omega^{\omega^{\omega^{.^{.^.}}}}\\\varepsilon_1&=\varepsilon_0\uparrow^2\omega=\varepsilon_0^{\varepsilon_0^{\varepsilon_0^{.^{.^.}}}}\\\zeta_0&=\omega\uparrow^3\omega={}^{{}^{{}^{{}^{{}^..}.}\omega}\omega}\omega\\\zeta_1&=\zeta_0\uparrow^3\omega={}^{{}^{{}^{{}^{{}^..}.}\zeta_0}\zeta_0}\zeta_0\end{align}

These seemingly coincidential identities which look pleasing are more than coincidence. They are actually consequences of some interesting properties that are satisfied by our definition.

Base Changing Formulae

Just as there are ways to change the base for multiplication $((\alpha\cdot\beta)\cdot\gamma=\alpha\cdot(\beta\cdot\gamma))$ and exponentiation $((\alpha^\beta)^\gamma=\alpha^{\beta\cdot\gamma})$, there are ways to change between bases in my extension, at least to an extent. As it would turn out, these hyperoperations satisfy a generalization of the Knuth arrow theorem which prescribes a bound on the rate at which hyperoperators should grow, analogous to your attempt at "sandwiching".

The proof of the following double inequality is not trivial. Intuitively, the proof relies on the idea that $\alpha\uparrow^\mu(\beta+\gamma)$ is like starting with $\alpha\uparrow^\mu\beta$ and then iterating $\gamma$ steps more. The upper bound can be interpreted as what would happen if those $\gamma$ additional steps were base $\alpha\uparrow^\mu\beta$ instead of base $\alpha$. The lower bound can interpreted as loose enough that a tighter bound (though significantly less pleasing one) can be proven by induction, similar to the proof of the usual Knuth arrow theorem.

For $\alpha,\mu,\beta\ge2$, the following inequalities hold:

$$(\alpha\uparrow^\mu\beta)\uparrow^\mu\gamma\le\alpha\uparrow^\mu(\beta+\gamma+1)\le(\alpha\uparrow^\mu\beta)\uparrow^\mu(\gamma+2)$$

For limit ordinals $\gamma$, this tightens into an equality by continuity/sandwiching:

$$(\alpha\uparrow^\mu\beta)\uparrow^\mu\gamma=\alpha\uparrow^\mu(\beta+\gamma)$$

This gives an interesting interpretation to examples you provide:

\begin{align}{}^\omega\omega&={}^\omega\omega=\varepsilon_0\\{}^{\omega+\omega}\omega&={}^\omega({}^\omega\omega)=\varepsilon_1\\{}^{\omega+\omega+\omega}\omega&={}^\omega({}^\omega({}^\omega\omega))=\varepsilon_2\\{}^{\omega+\omega+\omega+\dots}\omega&={}^\ldots({}^\omega({}^\omega({}^\omega\omega)))=\varepsilon_\omega\end{align}

Quirks

Due to the way this extension is defined, we fail to keep left-sided identities which cause fixed-point behavior. Instead, we have right-sided recursion and attain fixed-points at limit heights.

Many of the results of this extension involved edge cases occuring at limit ordinals or successors of limit ordinals. On its own, it may seem unnatural for tetration to change directions immediately after limit ordinals. We remark, however, that for higher hyperoperators, this tends to give more pleasing results. For example,

$$\omega\uparrow^3(\omega+1)=\zeta_0\uparrow^2\omega=\varepsilon_{\zeta_0+1}$$

And from there, one has

$$\omega\uparrow^3(\omega+n)=\varepsilon_{\varepsilon_{._{._{._{\zeta_0+1}}}}}=\varphi_1^n(\zeta_0+1)$$

Similarly,

$$\omega\uparrow^2(\omega+n)=\varphi_0^{n+1}(\varepsilon_0+1)$$

The behavior of $\uparrow^\omega$ and other such limit cases may also seem unnatural, but appear less so when looking at fundamental sequences of $\varphi_\omega$. This does however cause a shift in $\uparrow^{\omega+1}$'s relation to the Veblen function.

Feferman–Schütte Ordinal

Just as with most other extensions of ordinal arithmetic, the Feferman–Schütte ordinal is the limit of the ordinal notation and can be given by

$$\Gamma_0=\omega\uparrow^{\omega\uparrow^{\omega\uparrow^\vdots\omega}\omega}\omega=\sup\left\{\omega,\omega\uparrow^\omega\omega,\omega\uparrow^{\omega\uparrow^\omega\omega}\omega,\dots\right\}$$

Extensions of these to larger ordinals such as the small Veblen ordinal can probably be made, though this seems to veer far from the point of the question.

Summary

Two major ways to extend the ordinal arithmetic to tetration and beyond often rely on either identities based around $\omega\uparrow\uparrow(1+\beta)$ or $\omega\uparrow\uparrow(\beta+1)$. In this post, we explored an extension following the latter, showing that it not only reproduces the Veblen function at limits but also satisfies desireable bounds which have reasonable interpretations and allow for interesting arithmetic to be performed.

Although our approach to extending ordinal arithmetic using $\omega\uparrow\uparrow(\beta+1)$ is not unique, we point out that it allows a unification between the desired strictly increasing tetration with lower hyperoperations while preserving the original recursive nature of their definitions: a recursion over lower hyperoperations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Under this definition, $0^\omega=1$ which differs from other sources I have seen. Is this intended? $\endgroup$ – Anonymous Aug 16 at 6:28
  • $\begingroup$ No, under this definition one has $0^\omega=\sup\{0\cdot0^n,0^n\cdot0~|~n\in\omega\}=0$ as you would expect. $\endgroup$ – Simply Beautiful Art Aug 16 at 12:44
  • $\begingroup$ I see, I misread, my apologies. But I had another observation. $0\uparrow\uparrow\omega=1$ which means if $x=0\uparrow\uparrow\omega$ then $x$ does not satisfy the identity $0^x=x$. More generally, there seems to be a failure of fixed point identities which another user’s answer did satisfy. Is this intended? $\endgroup$ – Anonymous Aug 16 at 13:48
  • $\begingroup$ @Anonymous I don't think there is any good way to handle base $0$ for tetration and above, and it really shouldn't be of much interest (arguably just let it be either $0$ or $1$). To your second question, this is the point of the Motivation (first) section of my answer. Satisfying fixed-points relies on satisfying identities such as $\alpha\uparrow\uparrow(1+\beta)=\alpha~\widehat~~(\alpha\uparrow\uparrow\beta)$, which is what I refer to as left-sided recursion. Instead we attempt to produce a right-sided recursive definition here. $\endgroup$ – Simply Beautiful Art Aug 17 at 15:07
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The arguments on the the Googology Discord revere have have been amazing, but this is my favourite approach so far! I suggest looking into Bower’s (or Bird’s) array notation to go to higher ordinals like the Ackermann ordinal, SVO, LVO and possible BHO. $\endgroup$ – L. McDonald Nov 6 '19 at 7:22
  • $\begingroup$ Glad you enjoyed it! I will look at the array notation. FWIW, as a quick note, after writing this, I had the thought that $\omega \uparrow \uparrow (\omega+1)$ should be the $\omega$'th fixed point, rather than the second fixed point - which is the same basic pattern as with multiplicative and additive fixed points. Perhaps that would be the right way to do it... $\endgroup$ – Mike Battaglia Nov 6 '19 at 8:24
  • $\begingroup$ If I understand properly, you seem to suggest $1\uparrow\uparrow(\omega+1)$ to be undefined? $\endgroup$ – Simply Beautiful Art Jul 24 at 23:03
  • $\begingroup$ It was also seem to me that your extension is inconsistent with lower hyperoperations since it would imply $\omega^{\omega+x}=\omega^\omega\cdot(1+x)$, assuming $0$ does not count as a fixed-point of $\alpha=\omega\cdot\alpha$? Is there any motivation for the specific choice of fixed-point? $\endgroup$ – Simply Beautiful Art Jul 24 at 23:36
  • $\begingroup$ Per my previous comment: Didn't notice your comment above. Attempting to follow such an approach will notably destroy all of the nice relationships your answer presents, however. $\endgroup$ – Simply Beautiful Art Jul 25 at 3:02
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This definition is pretty good, and though there is no "canonical" way to define ordinal tetration, I think a good property to preserve is $\alpha^{\alpha\uparrow\uparrow\omega}=\alpha\uparrow\uparrow\omega$ and $\alpha^{\alpha\uparrow\uparrow\beta}=\alpha\uparrow\uparrow(\beta+1)$ $\endgroup$ – user477899 Sep 18 '17 at 22:52
  • $\begingroup$ @Zetapology Yeah. However, satisfying both will not allow one to exceed $\varepsilon_0$. In the definition provided above (and in the edit), the second condition is satisfied only for finite $\beta$. $\endgroup$ – Simply Beautiful Art Sep 19 '17 at 0:24
  • $\begingroup$ Good point. Transfinite hyperoperation almost satisfies it though $\endgroup$ – user477899 Sep 19 '17 at 0:28
  • $\begingroup$ @Zetapology You really think so?$$\omega\uparrow\uparrow(\omega+1)=\varepsilon_0^{\varepsilon_0}$$ $\endgroup$ – Simply Beautiful Art Sep 19 '17 at 0:32
  • $\begingroup$ I said almost. By that I meant $\alpha^{\alpha\uparrow\uparrow\omega}=\alpha\uparrow\uparrow (\omega+1)$ $\endgroup$ – user477899 Sep 19 '17 at 0:35
2
$\begingroup$

I believe I incidentally answered this question while working on some research recently -- it is possible to extend the usual hyperoperation sequence $\mathcal{H}_\omega$ on $\mathbb{N}$ to a recursive sequence of operations $\mathcal{H}$ on $O_n$, with the following result:

$$\mathcal{H}_{_\Omega}(\alpha,\beta)=\begin{cases} \mathcal{S}\alpha, & \text{if} \ \Omega=0. \\ \alpha, & \text{if} \ \Omega=1 \ \text{and} \ \beta=0. \\ \mathcal{S}\alpha,& \text{if} \ \Omega=1 \ \text{and} \ \beta=1. \\ 0, & \text{if} \ \Omega=2 \ \text{and} \ \beta=0. \\ \alpha, & \text{if} \ \Omega=2 \ \text{and} \ \beta=1. \\ 1, & \text{if} \ \Omega\geq3 \ \text{and} \ \beta=0. \\ \alpha, & \text{if} \ \Omega\geq3 \ \text{and} \ \beta=1. \\ \mathcal{H}_{_{\Omega-1}}\big(\mathcal{H}_{_\Omega}(\alpha,\beta-1),\alpha\big), & \text{if} \ \Omega=\mathcal{S}\bigcup\Omega \ \text{and} \ 1<\beta=\mathcal{S}\bigcup\beta. \\ \bigcup_{\delta<\beta}\mathcal{H}_{_\Omega}(\alpha,\delta), & \text{if} \ \Omega=\mathcal{S}\bigcup\Omega \ \text{and} \ \ 1<\beta=\bigcup\beta . \\ \bigcup_{\rho<\Omega}\mathcal{H}_{_\rho}(\alpha,\beta), & \text{if} \ 0\neq\Omega=\bigcup\Omega \ \text{and} \ 1<\beta=\mathcal{S}\bigcup\beta. \\ \bigcup_{\rho<\Omega}\bigcup_{\delta<\beta}\mathcal{H}_{_\rho}(\alpha,\delta), & \text{if} \ 0\neq\Omega=\bigcup\Omega \ \text{and} \ 1<\beta=\bigcup\beta. \\ \end{cases}$$

This 'transfinite hyperoperation sequence' is a very 'large' object in the sense that each hyperoperation in the sequence is a proper class, but it is well defined under the appropriate reflection principle or under ETR and satisfies nice relations like $\mathcal{H}_4(\omega,\omega)=^\omega\omega=\omega^{\omega^{\omega^{\dots}}}$ in your question, and $\mathcal{H}_5(\omega,\omega)=^{^{^{\dots}\omega}\omega}\omega$, so on and so forth.

We can also generalize $\gamma$, $\delta$ and $\epsilon$ numbers to the $\Omega^{th}$ hyperoperation, finding ordinals that 'absorb' larger and larger recursively defined binary operations. If you would like to see a proof of the above claims, feel free to check out my paper https://arxiv.org/abs/1706.08908 -- the part involving this hyperoperation sequence begins on page 20.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm assuming here $\bigcup$ is being used in place of $\mathrm{sup}$? $\endgroup$ – user477899 Sep 18 '17 at 23:32
  • $\begingroup$ @Zetapology I'm using the Von-Neumann construction of the orindals. For any class $\mathbb{X}$ in general, $\bigcup\mathbb{X}=\{y:\exists x\big(y\in x\in\mathbb{X}\big)\}$. I'm not familiar with $\sup$. $\endgroup$ – Alec Rhea Sep 19 '17 at 0:49
  • 1
    $\begingroup$ @Simply Beautiful Art, please refrain from making trivial edits. $\endgroup$ – Alec Rhea Sep 19 '17 at 0:54
  • $\begingroup$ Ok, in the Von Neumann construction (when dealing with limit ordinals) infinite unions of previous ordinals are supremums. $\endgroup$ – user477899 Sep 19 '17 at 0:56
  • $\begingroup$ @Zetapology Got it, thanks for the clarification. $\endgroup$ – Alec Rhea Sep 19 '17 at 0:57
0
$\begingroup$

Ordinal number multiplication is not commutative like natural number multiplication is. I think that because natural number multiplication is commutative, we define ordinal exponentation in terms of a right ordinal multiplication. However, since natural number exponentation is not commutative, natural number tetration was just defined in terms of a left exponentation so I guess you're also defining ordinal tetration in terms of a left ordinal exponentation. If that's how you define it, then you get $^{\omega + 1}\omega = \omega^{^{\omega}\omega} = \omega^{\epsilon_0} = \epsilon_0$. If we defined ordinal exponentation in terms of left ordinal multiplication, we would also write that $\omega^{\omega + 1} = \omega \cdot \omega^\omega = \omega^\omega$. Instead, we defined that $\omega^{\omega + 1} = \omega^\omega \cdot \omega = \sup(\omega^\omega, \omega^\omega + \omega^\omega, \omega^\omega + \omega^\omega + \omega^\omega ...)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.