Induction rules, reflection principles, and provably recursive functions

DOI10.1016/S0168-0072(96)00045-0zbMath0882.03055OpenAlexW2076792546MaRDI QIDQ1361250

Lev D. Beklemishev

Publication date: 12 March 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(96)00045-0

zbMATH Keywords

reflection principleinduction rulesnested applicationsprovably recursive function

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Provability algebras and proof-theoretic ordinals. I ⋮ A NOTE ON FRAGMENTS OF UNIFORM REFLECTION IN SECOND ORDER ARITHMETIC ⋮ Hyperarithmetical worm battles ⋮ Induction rules, reflection principles, and provably recursive functions ⋮ AN INCOMPLETENESS THEOREM VIA ORDINAL ANALYSIS ⋮ ON SHAVRUKOV’S NON-ISOMORPHISM THEOREM FOR DIAGONALIZABLE ALGEBRAS ⋮ Semi-honest subrecursive degrees and the collection rule in arithmetic ⋮ PREDICATIVITY THROUGH TRANSFINITE REFLECTION ⋮ On nested simple recursion ⋮ Parameter free induction and provably total computable functions ⋮ On axiom schemes for \(T\)-provably \(\Delta_1\) formulas ⋮ Local induction and provably total computable functions ⋮ Proof Theoretic Analysis by Iterated Reflection ⋮ Honest elementary degrees and degrees of relative provability without the cupping property ⋮ ARITHMETICAL INTERPRETATIONS AND KRIPKE FRAMES OF PREDICATE MODAL LOGIC OF PROVABILITY ⋮ Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA ⋮ Fragments of Arithmetic and true sentences ⋮ AXIOMATIZATION OF PROVABLE n-PROVABILITY ⋮ On the induction schema for decidable predicates ⋮ Induction rules in bounded arithmetic ⋮ Interpretability in PRA ⋮ The closed fragment of the interpretability logic of PRA with a constant for I\(\Sigma^1\) ⋮ Some results on cut-elimination, provable well-orderings, induction and reflection ⋮ Unprovability results for clause set cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fragments of arithmetic
• On the scheme of induction for bounded arithmetic formulas
• Induction rules, reflection principles, and provably recursive functions
• Herbrand analyses
• The optimality of induction as an axiomatization of arithmetic
• Reflection Principles in Fragments of Peano Arithmetic
• Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
• Hierarchies of Primitive Recursive Functions
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• On n-quantifier induction