How can I show, that in the fast growing hierarchy, every sequence grows faster than the one before ?

A function $f(n)$ is said to grow faster than a function $g(n)$, if for every $k$ there exists $n_0$, such that $f(n)>g(n+k)$ for all $n\ge n_0$.

It is plausible that $g(n)=f^n(n)$ grows faster than $f(n)$, but how can I prove this and how can I handle the diagonalizations ?

Additional question : Is there an easier formulation of the above condition, for example by using landau symbols ?

  • 1
    $\begingroup$ I'll point out that this problem is dependent on choice of fundamental sequences for limit ordinals, because it's possible to have them set up in a way which makes $f_{\omega^\omega}=f_\omega$. $\endgroup$ – Wojowu Jan 4 '15 at 19:57
  • $\begingroup$ I mean the Grzegorczyk hierarchy , but the other hierarchys have the property, that the sequences grow ever faster, too. $\endgroup$ – Peter Jan 4 '15 at 20:01

I’m assuming that $f_0(m)=m+1$ and $f_{n+1}(m)=f_n^m(m)$ for $m,n\in\omega$. I will take it as known that each $f_n$ is an increasing function.

First show that $f_n(m)>m$ for $m>0$, so that $\langle f_n^k(m):k\in\omega\rangle$ is strictly increasing for $m>0$. Then show that $f_n(m)\ge 2m$ for $n\ge 1$. Both of these are inductions on $n$. It follows that

$$f_{n+1}(m)=f_n^m(m)=f_n^{m-1}\big(f_n(m)\big)\ge f_n^{m-1}(2m)=f_n^{m-2}\big(f_n(2m)\big)\ge f_n(2m)$$

for $n\ge 1$ and $m\ge 2$. An immediate consequence is that $f_{n+1}$ grows faster than $f_n$ for all $n\ge 1$, and it’s easy to check that $f_1(n)=2n$ grows faster than $f_0$.

  • $\begingroup$ Good job! Thank you! $\endgroup$ – Peter Jan 5 '15 at 11:23
  • $\begingroup$ @Peter: You're welcome! $\endgroup$ – Brian M. Scott Jan 5 '15 at 11:26
  • $\begingroup$ Perhaps you can say something to the diagonalizations. For example, $f_\omega(n)=f_n(n)$. Does $f_\omega(n)$ grow faster than $f_k(n)$ for all $k$ ? $\endgroup$ – Peter Jan 5 '15 at 11:28

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.