On a subrecursive hierarchy and primitive recursive degrees
Paul Axt · Transactions of the American Mathematical Society · 1959
Finally primitive recursive degrees are studied, and certain similarities to and differences from the theory of general recursive degrees of [5] are obtained.2. For the hierarchy of classes Cy, the "uniqueness property" will be said to hold at an ordinal a if, whenever y, zEO, \y\ =\z\ =a, then Cy= Cz (i.e.hv and hz are of the same primitive recursive degree).As is remarked in [4, §7], the use of the 0 of 53, involving as it does general recursive fundamental sequences, would be out of keeping with the purpose of building a hierarchy based on primitive recursiveness.We now show that if the 0 of 53 is used, the uniqueness property fails at the first possible place in the hierarchy, namely at the co level.In fact, the nonuniqueness occurs in such a way that a function of arbitrary primitive recursive degree for a general recursive predicate is definable at the co level.In this section 0 refers to the 0 of 53.If cp is a function in C", yEO, we shall refer to an index of cp from hy [4, §3] as a "y-index" of cp.Let ei be an index of the primitive recursive function Xba {b, a) (i.e. an index under [4, §3] for / = 0), and hence also a y-index of Xba (b, a) for all yEO.For y, zEO, if p is a y-index of h2', then (4, 2, p, (2, 2, (0, 2, 1», ei) is a y-index of hz.Define the function %(n) primitive recursively as follows: PAUL AXT JulyCznECVn (cf.[4 (13b)]).Recalling the properties of the functions f and fin of §2, observe that f(fin (y") -«') is a (y")0-index of hZn provided fin (y")>«, and that Xn£(hn (yn)~«') is primitive recursive.Then we may write:•&»«*■ (fin (y(6)l) -(i)/),(4).),((J).,«))fcr(A a) = • if z(6)l ^ y(6)"./?"(&, a) if zWl = yWl.Thus &" is primitive recursive in /?".It remains to be shown that hu is primitive recursive in hv.Denote zVn by rn and zv"_i by sn.Since n<zn, y"<0rn and C,"CCn.So &"" is primitive recursive in hSn with index f(y*-(fin (y"))') and we can write *,"(*, «) = MK* ■*■ (fin (y.))0, <*, a))-ThusXw&a ^"(6, a) is primitive recursive inXw&a ^r"(&, fl).Further Xnba hrn(b, a) is primitive recursive in Xnba hZn(b, a) since Xn yn is primitive recursive.And hence Xnba hVn(b, a) is primitive recursive in Xnba hZn(b, a), so hu is primitive recursive in hv.Therefore hu and hv are of the same primitive recursive degree.In case y,<o2o, * = 0, • ■ • , M-l, but z0^oy^, let xn=yn+M.Then Xw x"