Suppose Knuth arrow notation (and hence the hyperoperation sequence) is extended to transfinite ordinal indices as follows:

Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ, and take these to be the same as in the definition of the fast-growing hierarchy of functions ($f_\alpha$). Now define
$$ m\uparrow^\alpha n \ \ = \ \ \begin{cases} m n & \text{if }\alpha=0, \\ (m\uparrow^{\alpha-1})^n 1 & \text{if }\alpha \text{ is a successor ordinal}, \\ m\uparrow^{\alpha[n]}n & \text{if }\alpha \text{ is a limit ordinal}, \end{cases} $$ for all integers $m, n \ge 0$ and ordinal $\alpha < \mu$, where $(\alpha[n])_{n=0,1,2,\dots}$ is the fundamental sequence for $\alpha$.

It can be shown that for all $\alpha < \omega$, there is an $n_0$ (depending on $\alpha$) such that for all $n > n_0$, $$f_\alpha(n) \ \ \lt \ \ 2\uparrow^\alpha n \ \ \le \ \ f_{\alpha+1}(n).\tag{*}$$

Question: Does (*) hold for all $\alpha < \mu$? Or, is there a "cross-over point", i.e., a least ordinal $\beta (< \mu)$ such that for all $\alpha \ge \beta, \ \ \ f_\alpha(n) > 2\uparrow^\alpha n \ $ for all sufficiently large $n$?

EDIT: Small cases $n = 0, 1, 2, 3, ...$ suggest that $\omega$ is actually the cross-over point. Proof?

Motivation: If (*) holds for all $\alpha < \mu$, it would seem that with minor adjustments virtually all of the points of interest concerning the fast-growing hierarchy ($f_\alpha)$ apply as well to the hierarchy of functions $(2\uparrow^\alpha)$.

NB: Arrow notation has been used for convenience. The discussion could be rephrased in terms of extending the hyperoperation sequence $H_\alpha(m,n)$, with a shift in the indexing to accomodate successor and addition.


Certainly this eventual inequality holds for all $\alpha<\omega$. Then note that

$$f_\omega(n)=f_{\omega[n]}(n)\ll2\uparrow^{\omega[n]}n=2\uparrow^\omega n$$

So the lower bound holds for $\omega$. Likewise does the upper bound somewhat trivially. However, it fails for $\omega+1$. Let $\omega[n]=n$. Note that

$$f_\omega(n+1)=f_{n+1}(n+1)\gg2\uparrow^n(n+1)\ge(2\uparrow^nn)+1=(2\uparrow^\omega n)+1$$

Hence by induction,




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.