Subrecursive degrees and fragments of Peano arithmetic (Q5945568)

Let \(T_{0} \leq T_{1}\) denote that each computable function which is provably total in the first order theory \(T_{0}\) is also provably total in the first oder theory \(T_{1}\). The relation \(\leq\) induces a degree structure on the sound finite \(\Pi_{2}\) extensions of EA (Elementary Arithmetic). The paper under review is devoted to the study of this structure. An isomorphic subrecursive degree structure \((\leq, {\mathcal S})\) is defined and studied by subrecursive and computability-theoretic means. Further some operators on the degrees of \((\leq, {\mathcal S})\) are introduced and investigated. It is shown that they correspond to some rules in formal arithmetic (e.g., to the \(\Sigma_{1}\) collection rule and to the \(\Sigma_{1}\) induction rule).