Some Interesting Connections between the Slow Growing Hierarchy and the Ackermann Function
Weiermann, Andreas
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 609-628 / Harvested from Project Euclid
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 $(G_{\alpha})_{\alpha \in T}$ matches up with the class of functions which are elementary recursive in the Ackermann function as does $(G_{\alpha})_{\alpha \in T^{tree}}$ (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems $T* \subseteq T$ and $T^{tree*} \subseteq T^{tree}$ (both of order type not exceeding $\varepsilon_0$) and prove that $(G_{\alpha})_{\alpha \in T^{tree*}}$ still matches up with $(G_{\alpha})_{\alpha \in T^{tree}}$ but $(G_{\alpha})_{\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.
Publié le : 2001-06-14
Classification: 
@article{1183746461,
     author = {Weiermann, Andreas},
     title = {Some Interesting Connections between the Slow Growing Hierarchy and the Ackermann Function},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 609-628},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746461}
}
Weiermann, Andreas. Some Interesting Connections between the Slow Growing Hierarchy and the Ackermann Function. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  609-628. http://gdmltest.u-ga.fr/item/1183746461/