Lets say: $G=\text{Graham's Number}$.
And:
$$ \begin{align*} \alpha_1&=G\uparrow^G G, \\ \alpha_2&=\alpha_1\uparrow^{\alpha_1} \alpha_1 \\ &\vdots\\ \beta_1 &= \alpha_G\uparrow^{\alpha_G}\alpha_G \\ \beta_2 &= \beta_1 \uparrow^{\beta_1 }\beta_1 \\ \beta_n &= \beta_{n-1} \uparrow^{\beta_{n-1} }\beta_{n-1} \end{align*} $$

Then: is $\beta_{\beta_G}$ still smaller then $TREE(3)$?

$a\uparrow^nb$ is Knuth's up-arrow notation

Thank you!!

up vote 3 down vote accepted

This is much much smaller than $\operatorname{TREE}(3)$. To give you a rough taste, $G\approx f_{\omega+1}(64)$, and every application of $n\mapsto n\uparrow^nn$ only increases the inner argument by $1$, so $\alpha_n\approx f_{\omega+1}(64+n)$ and $\beta_n\approx f_{\omega+1}(64+G+n)\approx f_{\omega+1}(f_{\omega+1}(64)+64+n)$.

On the other hand, we have $f_{\omega+2}(n)=\overbrace{f_{\omega+1}(f_{\omega+1}(f_{\omega+1}(\dots f_{\omega+1}(}^nn)\dots)))$, so already $f_{\omega+2}(4)>\beta_{\beta_G}$.

In general,

$$f_{\alpha+1}(n)=\overbrace{f_\alpha(f_\alpha(f_\alpha(\dots f_\alpha(}^nn)\dots)))$$

so we likely have $f_{\omega+3}(3)=f_{\omega+2}(f_{\omega+2}(f_{\omega+2}(3)))$ to be much greater than your number.

On the other hand, $\operatorname{TREE}(n)\gtrapprox f_{\vartheta(\Omega^\omega\omega)}(n)$, which is significantly larger.

As a brief explanation of the fast growing hierarchy for a few more ordinals, we have

$$f_0(n)=n+1\\f_1(n)=2n\\f_2(n)=n2^n\\f_k(n)\gtrapprox2\uparrow^{k-1}n\\f_\omega(n)=f_n(n)\approx n\uparrow^nn\\f_{\omega2}(n)=f_{\omega+n}(n)\\f_{\omega k}(n)=f_{\omega(k-1)+n}(n)\\f_{\omega^2}(n)=f_{\omega n}(n)\\\vdots$$

In comparison, $\vartheta(\Omega^\omega\omega)\gg\omega^{\omega^{\omega^{.^{.^.}}}}\gg\omega^\omega\gg\omega^2$, which isn't anywhere near close to a good approximation to $\vartheta(\Omega^\omega\omega)$, which should tell you how frightening large this is.

For some introductions to the fast growing hierarchy, I recommend watching David Metzler's videos or Giroux Studio's videos, and checking out my chatroom.

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.