# Fast growing hierarchy : How can I show that any sequence grows faster than the one before?

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 ?

• 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$. – Wojowu Jan 4 '15 at 19:57
• I mean the Grzegorczyk hierarchy , but the other hierarchys have the property, that the sequences grow ever faster, too. – Peter Jan 4 '15 at 20:01

## 1 Answer

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

• Good job! Thank you! – Peter Jan 5 '15 at 11:23
• @Peter: You're welcome! – Brian M. Scott Jan 5 '15 at 11:26
• 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$ ? – Peter Jan 5 '15 at 11:28