A jump operator for subrecursion theories

Extract

In classical recursion theory, the jump operator is an important concept fundamental in the study of degrees. In particular, it provides a way of defining the hyperarithmetic hierarchy by iterating over Kleene's O. In subrecursion theories, hierarchies (variants of the fast growing hierarchy) are also important in underlying the central concepts, e.g. in classifying provably recursive functions and associated independence results for given theories (see, e.g. [BW87], [HW96], [R84] and [Z77]). A major difference with the hyperarithmetic hierarchy is in the way each level of a subrecursive hierarchy is crucially dependent upon the system of ordinal notations used (see [F62]). This has been perhaps the major stumbling block in finding a classification of all general recursive functions using such hierarchies.

Here we present a natural subrecursive analogue of the jump operator and prove that the hierarchy based on the ”subrecursive jump” is elementarily equivalent to the fast growing hierarchy.

The paper is organised as follows. First the preliminary definitions are given together with a statement of the main theorem and a brief outline of its proof. The proof of the theorem is then given, with the more technical parts separated out as facts which are proven afterwards.

We let {e}^g(x) denote computation of the e-th partial recursion with oracle g, on input x. Furthermore [e] denotes the e-th elementary recursive function, defined so that

Similarly, for a given oracle g the e-th relativized elementary function is denoted by [e]^g.