Streamlined subrecursive degree theory

DOI10.1016/J.APAL.2011.11.004MaRDI QIDQ408165zbMATH OpenOpenAlexFDO

Authors Lars Kristiansen, Jan-Christoph Schlage-Puchta, Andreas Weiermann

Publication date 29 March 2012

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

Full work available at URL https://doi.org/10.1016/j.apal.2011.11.004

zbMATH Keywords

honest functionsprovability in PAsubrecursive degrees

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) First-order arithmetic and fragments (03F30)

Review text

The paper under review consists of two parts. Part I is devoted to the investigation of the structure of honest elementary degrees, i.e., the degree structure induced on the honest functions by the reducibility relation ``being (Kalmar) elementary in. In Part II the degree theory found in Part I is generalized. The reducibility relation ``being \(\alpha\)-elementary in, where \(\alpha\) is an ordinal \(\leq \varepsilon_{0}\), is introduced and the structure of honest \(\alpha\)-elementary degrees is investigated. Relations between the degree theory developed in the paper and provability in Peano arithmetic is also discussed.

Recommendations

• scientific article; zbMATH DE number 1507242
• Degrees of relative provability
• Subrecursive degrees and fragments of Peano arithmetic
• A jump operator on honest subrecursive degrees
• Degrees of total algorithms versus degrees of honest functions

Cites work

• A Classification of the Recursive Functions
• A jump operator on honest subrecursive degrees
• A Uniform Approach to Fundamental Sequences and Hierarchies
• Augmented loop languages and classes of computable functions
• Classical recursion theory. Vol. II
• scientific article; zbMATH DE number 3125697 (Why is no real title available?)
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 1062120 (Why is no real title available?)
• scientific article; zbMATH DE number 1507242 (Why is no real title available?)
• scientific article; zbMATH DE number 922625 (Why is no real title available?)
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On the density of honest subrecursive classes
• Subrecursive degrees and fragments of Peano arithmetic
• The honest subrecursive classes are a lattice

Cited in

(12)

• A jump operator on honest subrecursive degrees
• Dedekind cuts and long strings of zeros in base expansions
• Computable irrational numbers with representations of surprising complexity
• On the structure of the degrees of relative provability
• Degrees of total algorithms versus degrees of honest functions
• Sub-computabilities
• Honest elementary degrees and degrees of relative provability without the cupping property
• Proof lengths for instances of the Paris-Harrington principle
• Subrecursive degrees and fragments of Peano arithmetic
• Semi-honest subrecursive degrees and the collection rule in arithmetic
• Interplay between insertion of zeros and the complexity of Dedekind cuts
• On S-degrees of some representations of irrational numbers

This page was built for publication: Streamlined subrecursive degree theory

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