Semi-honest subrecursive degrees and the collection rule in arithmetic
type: Item
instance of: scholarly article
title: Semi-honest subrecursive degrees and the collection rule in arithmetic
author: Andrés Cordón-Franco
author: F. Félix Lara Martin
published in: Archive for Mathematical Logic
publication date: 2024-01-18T00:00:00Z
review text: The paper is devoted to the application of the subrecursive degree theory to the study of fragments of Peano Arithmetic. It is connacted with the result of L.D. Beklemishev who showed that the hierarchy of nested applications of the \(\Sigma_{1}\)-collection rule over any \(\Pi_{2}\)-axiomatizable base theory extending Elementary Arithmetic collapses to its first level. In the paper under review it is proved that this result cannot in general be extended to base theories of arbitrary quantifier complexity. In fact, given any recursively enumerable set of true \(\Pi_{2}\)-sentences, S, a sound \(\Sigma_{2} \vee \Pi_{2}\)- axiomatized theory T extending S is constructed such that the hierarchy of nested applications of the \(\Sigma_{1}\)-collection rule over T is proper. The construction uses some results on subrecursive degree theory obtained by L. Kristiansen.
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 7790935
zbMATH Keywords: fragments of Peano arithmetic
zbMATH Keywords: collection rule
zbMATH Keywords: provably total computable functions
zbMATH Keywords: subrecursive degrees
MaRDI profile type: Publication
cites work: Existentially closed structures and Gödel's second incompleteness theorem
cites work: Saturated models of universal theories
cites work: On the structure of subrecursive degrees
cites work: Induction rules, reflection principles, and provably recursive functions
cites work: A proof-theoretic analysis of collection
cites work: On the induction schema for decidable predicates
cites work: Provability algebras and proof-theoretic ordinals. I
cites work: Reflection principles and provability algebras in formal arithmetic
cites work: Degrees of relative provability
cites work: Computer Science Logic
cites work: Fragments of Arithmetic and true sentences
cites work: Envelopes, indicators and conservativeness
cites work: On axiom schemes for \(T\)-provably \(\Delta_1\) formulas
cites work: Q5286672
cites work: Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
cites work: A jump operator on honest subrecursive degrees
cites work: Subrecursive degrees and fragments of Peano arithmetic
cites work: Degrees of Total Algorithms versus Degrees of Honest Functions
cites work: Streamlined subrecursive degree theory
cites work: Augmented loop languages and classes of computable functions
cites work: The honest subrecursive classes are a lattice
cites work: On the density of honest subrecursive classes
cites work: A Classification of the Recursive Functions
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: Q3325707
DOI: 10.1007/S00153-023-00889-Z
description: scientific article; zbMATH DE number 7790935