Abstract

It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for $\Gamma_0$. Let T be the set-theoretic ordinal notation system for $\Gamma_0$ and $T^{tree}$ the tree ordinal representation for $\Gamma$. It is shown in this paper that $_{\alpha \in T}$ matches up with the class of functions which are elementary recursive in the Ackermann function as does $_{\alpha \in T^{tree}}$. By thinning out terms in which the addition function symbol occurs we single out subsystems $T* \subseteq T$ and $T^{tree*} \subseteq T^{tree}$ and prove that $_{\alpha \in T^{tree*}}$ still matches up with $_{\alpha \in T^{tree}}$ but $_{\alpha \in T*}$ now consists of elementary recursive functions only. We discuss the relationship between these results and the $\Gamma_0$-based termination proof for the standard rewrite system for the Ackermann function.