# which class does this function belong to in the fast growing hierarchy?

the class $\mathfrak{F}_k$ of the fast growing hierarchy is the closure under substitution and limited recursion of the constant, sum,projections and $F_n$ functions for $n\leq k,$where $F_n$ is defined recursively by $$\begin{eqnarray*} F_0(x) &\triangleq & x+1\\ F_{n+1}(x) &\triangleq &F_n^{x+1}(x) \end{eqnarray*}$$

Here, $F_n^{x+1}(x)=\underbrace{F_n(F_n(\cdots (F_n}_{x+1}(x)))$

The hierarchy is strict for $k\geq 1$, i.e. $\mathfrak{F}_{k}\subsetneq \mathfrak{F}_{k+1}$.

Then, if a function $g$ can be written as $$\begin{eqnarray} g=\underbrace{f_1^{f_2^{.^{.^{.{f_L}}}}}}_{L} \end{eqnarray}$$

Here $f_i,L$ are functions with variable $x$, and all belong to$\mathfrak{F}_3,$ then which class does $g$ belong to? Is $g\in \mathfrak{F}_4$?

Note: you can find more information on "the fast growing hierarchy" on page 9 in this following paper: http://arxiv.org/abs/1007.2989

-
Can you explain your notation? what does $f_1^{f_2}$ mean? Does it mean $f_1^{f_2(x)}(x)$? – sligocki Sep 16 '11 at 15:10
@sligocki, yes, $f_2=f_2(x)$ is the power of $f_1=f_1(x)$. – ougao Sep 17 '11 at 5:45
Please do not ask questions simultaneously here and on MO. – Mariano Suárez-Alvarez Sep 18 '11 at 6:36
Sorry, but I expect an answer.. – ougao Sep 18 '11 at 9:01

I don't think so. I don't have a rigorous proof here, but I believe that there are $f_i$ and $L$ such that $g > F_5$ and thus $g \notin \mathcal{F}_4$.

Here is my rough construction:

I will use a different formulation of the Fast-Growing Hierarchy (which I believe will generate the same sets, but this is not proven):

$S_0(x) = x+2$

$S_{n+1}(x) = S_n^x(1)$

Thus, $S_4(x) = S_3^x(1)$, $S_4^2(x) = S_4(S_3^x(1)) = S_3^{S_3^x(1)}(1)$ and furthermore, $S_5(x) = S_4^x(1) = S_3^{S_3^{...^{S_3(1)}}(1)}(1)$ Where there are $x$ $S_3$'s in the tower.

Thus if you let $f_k = S_3$ and $L(x) = x$, then $g(x) = f_1^{f_2^{...^{f_{L(x)}(x)}}(x)}(x) = S_3^{S_3^{...^{S_3(x)}}(x)}(x) > S_5(x)$.

-
Note, the $S_n$ I describe here correspond to the $A_n$ in the paper you link, which are shown to be in $\mathcal{F}_n - \mathcal{F}_{n-1}$, that should complete the proof. – sligocki Sep 18 '11 at 6:28
,Impressing argument! You use the property that $\forall f\in \mathfrak{F}_{k-1},$ when x is sufficiently large, then we have $f(x)< A_k(x).$ Dose the converse also hold true? I mean, how can we judge whether a function belongs to a class $\mathfrak{F}_k$ effectively? since the definition is not easy to check for a specific function. – ougao Sep 19 '11 at 23:55