A jump operator for subrecursion theories

E-ISSN： 1943-5886|64|2|460-468

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.64, Iss.2, 1999-06, pp. : 460-468

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

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.