Suppose we've defined the Ackermann hierarchy as follows:


Compare this to the fast growing hierarchy:

$$f_\alpha(n)=\begin{cases}n+1,&\alpha=0\\f_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\f_\beta^n(n)=f_\beta(\dots f_\beta(n)\dots),&\alpha=\beta+1\end{cases}$$

It is easy to see that


$$A_{k+1}(n)\ll f_k(n)\ll A_{k+1}^2(n)\quad\forall0<k<\omega$$

$$A_\omega(n)\ll f_\omega(n)\ll A_\omega^2(n)$$


Using fundamental sequences of the Veblen Hierarchy, is it the case that for $\alpha$ between $\omega$ and the Large Veblen ordinal that we have the following bounds for sufficiently large $n$?

$$A_\alpha(n)\ll f_\alpha(n)\ll A_\alpha^2(n)$$

up vote 2 down vote accepted

Both bounds may be proven with induction. Assume that they hold for some $\alpha$ and all sufficiently large $n$. We then have

$$A_\alpha(n)<f_\alpha(n)\implies A_\alpha^n(n)<f_\alpha^n(n)$$

$$A_\alpha(1)<n\implies A_\alpha^n(A_\alpha(1))<f_\alpha^n(n)$$

From here, we can see by induction and definition that


Since the inequalities hold true for all $\omega\le\beta<\alpha$, they hold true for $\alpha\in\Bbb{Lim}$.

The upper bound is more complicated by follows the same general idea:

$$kn\ll A_{\alpha+1}(n)\quad\forall \alpha\ge\omega$$

$$f_\alpha(n)<A_\alpha^2(n)\implies f_\alpha^{kn}(kn)<A_\alpha^{2kn}(kn)<A_\alpha^{2kn}(A_{\alpha+1}(n))$$

$$\implies f_{\alpha+1}(kn)<A_{\alpha+1}((2k+1)n)\ll A_{\alpha+1}^2(n)$$

This likewise improves the bounds and gives us

$$A_\alpha(n)<f_\alpha(n)\ll A_{\alpha+1}\left(\frac{2k+1}{2k}n\right)$$

For every $k\gg0$ and $n\gg N$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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