By a result of L.D. Beklemishev, 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. We prove 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, we construct a sound $$(\Sigma _2 \! \vee \! \Pi _2)$$ -axiomatized theory T extending S such that the (...) hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over T is proper. Our construction uses some results on subrecursive degree theory obtained by L. Kristiansen. (shrink)

There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.