Sometimes slow growing is fast growing

DOI10.1016/S0168-0072(97)00033-XMaRDI QIDQ1377604zbMATH OpenFDO

Authors Andreas Weiermann

Publication date 3 August 1998

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(97)00033-X

zbMATH Keywords

fast growing hierarchyfundamental sequenceshierarchy comparison theoremslow growing hierarchysubrecursive hierarchies

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Hierarchies of computability and definability (03D55) Recursive ordinals and ordinal notations (03F15)

Review text

An important problem in the foudations of subrecursive hierarchies is to explain the role of the choice of a fundamental sequence for the definition of such a hierarchy. In this paper we can see that the study of this problem is very promising and can reveal interesting surprises. The author shows that a version of the hierarchy which is commonly called the slow growing hierarchy (defined with respect to a certain norm-based assignment of fundamental sequences [\textit{E. A. Cichon}, in: P. Aczel et al. (eds.), Proof theory, Int. Summer School and Conference, Leeds 1990, 173-193 (1992; Zbl 0793.03057)]) majorizes each PA-provable recursive function; and that is the property that lets a hierarchy be called fast growing. The proof is quite technical but it is easy to follow since everything is given in full detail. Before the proof of the crucial hierarchy comparison theorem is carried out, the author gives a short calculation that illustrates why the considered ``slow growing hierarchy leaves the scope of elementary recursion.

Recommendations

• Publication:4934570
• Slow versus fast growing
• An extremely sharp phase transition threshold for the slow growing hierarchy
• Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones

Cites work

• A Uniform Approach to Fundamental Sequences and Hierarchies
• scientific article; zbMATH DE number 432704 (Why is no real title available?)
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• Variations on a theme by Weiermann

Cited in

(7)

• A slow growing analogue to Buchholz' proof
• Slow versus fast growing
• An extremely sharp phase transition threshold for the slow growing hierarchy
• scientific article; zbMATH DE number 17786 (Why is no real title available?)
• scientific article; zbMATH DE number 1136114 (Why is no real title available?)
• scientific article; zbMATH DE number 2152691 (Why is no real title available?)
• scientific article; zbMATH DE number 1390283 (Why is no real title available?)

This page was built for publication: Sometimes slow growing is fast growing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377604)