Classifications of recursive functions by means of hierarchies
Solomon Feferman · Transactions of the American Mathematical Society · 1962
SOLOMON FEFERMAN1. Introduction.The motivations for attempting to find a satisfactory classification of recursive functions by ordinals are rather well known; cf., for example [6, pp.67-68].Among other things, such a classification should give insight into how the nonconstructively defined class of arbitrary recursive functions can be successively approximated by classes of functions whose members can be constructively recognized to be everywhere defined and computable.It should also provide a framework for the (partial) characterization of the strength of various formalized theories, through the classification of the provably recursive functions of those theories.Finally, it might be hoped that such a classification would provide a new tool for obtaining results of purely mathematical interest about recursive functions. It has been pointed out by Myhill [ll] and independently by Routledge[13] that the most obvious attempt to define such a classification, namely in terms of recursions over previously constructed recursive well-orderings of the natural numbers, already gives all recursive functions by suitable choice of primitive recursive well-orderings of order type w.This is quite naturally considered a "breakdown," since none of the ends desired from such a classification are at all realized.Another approach to the classification problem has been suggested by Kleene in [6].This harks back to the idea that from any constructively generated class of recursive functions we are able to obtain new functions by diagonalization or, more generally, by enumeration.Transfinite iteration of this procedure leads to a hierarchy of recursive functions, most conveniently described with respect to some class of notations for recursive well-orderings.However, in order that such a classification not be trivialized at level to, the set 0 of notations used should be restricted to those built up only by means of primitive recursive fundamental sequences [6, pp.72-73].We shall follow this restriction throughout this paper.For functions , \f/ on natural numbers put (for the moment) «^ if is primitive recursive in \f/, but not conversely.Kleene's hierarchy of functions Pd (denoted by hi in [6]) has the property (1.1) c pc « pd.