Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

share|cite|improve this question
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)$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.