3
$\begingroup$

Suppose we've defined the Ackermann hierarchy as follows:

$$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(n-1)),&n>0,\alpha=\beta+1\end{cases}$$

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_0(n)=f_0(n)$$

$$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)$$

etc.

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)$$

$\endgroup$
2
$\begingroup$

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

$$A_\alpha^n(A_\alpha(1))=A_{\alpha+1}(n)\\f_\alpha^n(n)=f_{\alpha+1}(n)$$

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$.

$\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.