1
$\begingroup$

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

  • 0
    Can you explain your notation? what does $f_1^{f_2}$ mean? Does it mean $f_1^{f_2(x)}(x)$?2011-09-16
  • 0
    @sligocki, yes, $f_2=f_2(x)$ is the power of $f_1=f_1(x)$.2011-09-17
  • 6
    Please do not ask questions simultaneously here and on MO.2011-09-18
  • 0
    Sorry, but I expect an answer..2011-09-18
  • 0
    You expect an answer? What are we, machines to you? You feed us problems and we feed you answers? I'd rather not be thought that way.2017-07-06

1 Answers 1