Rudimentary relations and primitive recursion: A toolbox

AbstractRudimentary relations are those relations over natural integers that are defined by a first-order arithmetical formula, in which all quantifications are bounded by some variables. The question of whether a given primitive recursive relation is rudimentary is in some cases difficult and related to several well-known open questions in theoretical computer science. In this paper, we present systematic tools to study this question, and various applications. One of them gives a sufficient condition of the collapsing of the first classes of the Grzegorczyk's hierarchy