No label defined (Q4934570)

A subrecursive hierarchy \((P_{\alpha})_{\alpha<\varepsilon_0}\) of unary number-theoretic functions is called slow growing if each \(P_{\alpha}\) is dominated by a Kalmar elementary recursive function. The pointwise hierarchy \((P_{\alpha})_{\alpha<\varepsilon_0}\) is recursively defined: \(P_0(x)=0\); \(P_{\alpha+1}(x)=1+P_{\alpha}(x)\); \(P_{\lambda}(x)=P_{\lambda[x]}(x)\) where \(\lambda\) is a limit and \((\lambda[x])_{x<\omega}\) is a distinguished fundamental sequence for \(\lambda\). This paper tries to classify as far as possible those natural assignments of fundamental sequences for which the induced pointwise hierarchy remains slow growing or becomes fast growing in the sense that the resulting hierarchy matches up with the Schwichtenberg-Wainer hierarchy \((F_{\alpha})_{\alpha<\varepsilon_0}\). Then the growing rate of functions which are defined pointwise with respect to a norm function are investigated. Finally, some of the obtained results are reformulated in terms of unprovability results for PA; Friedman's result stating that PA does not prove that \(\varepsilon_0\) is slowly well-ordered is re-obtained. For the entire collection see [Zbl 0919.00040].