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

1

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

  • 0
    ,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.2011-09-19