What makes a (pointwise) subrecursive hierarchy slow growing? (English) Zbl 0945.03061
Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium ’97, European meeting of the Association for Symbolic Logic, Leeds, UK, July 6-13, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 258, 403-423 (1999).
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].
For the entire collection see [Zbl 0919.00040].
Reviewer: Tao Renji (Beijing)
MSC:
03D20 | Recursive functions and relations, subrecursive hierarchies |
03F30 | First-order arithmetic and fragments |