|
Grzegorczyk has defined an
increasing sequence of classes ℰn of functions with the properties that ℰ3 is the class
of elementary functions of Csillag-Kalmar and ∪ℰn is the class of primitive recursive
functions. Further, ℰn+1 properly contains ℰn, if n > 2 then ℰn+1 contains a
“universal function” over all one-argument functions in ℰn, and a sequence of
functions gn(x,y) in terms of which the ℰn are defined has the property that
each gn+1(x,x) (eventually) majorizes all the one-argument functions in
ℰn.
The functions gn(x,y) are defined by somewhat artificial nested recursions, and
Grzegorczyk poses the following question: “Can the same theorems be proved for
classes ℱn as for the classes ℰn?” Here ℱn differs from ℰn only in substituting a more
natural function fn′(x,y) for each gn(x,y) in the definition of the class. In this
paper, we answer his question affirmatively. Indeed, we prove that ℱn = ℰn for all
n ≧ 0, and further, fn+1′(x,x) eventually majorizes all the one-argument functions in
ℱn.
|
