The class of recursive functions
Joseph R. Shoenfield · Proceedings of the American Mathematical Society · 1958
In this note, we find the position of the predicate a% is in the Kleene arithmetical hierarchy.' The proof involves a use of topology; the key step is the application of Baire's category theorem to a suitable function space. We use the notation of [I]. In addition, we write (Ux) for the quantifier there exist infinitely many x. We designate the set of natural numbers by N and the class of mappings of N into N by NN. We consider N as a topological space with the discrete topology, and NN as a topological space with the product topology. We review some known facts about NN. I. Provided with a suitable metric, NN is a complete metric space. (For it is the product of a countable number of discrete spaces.) II. The nonrecursive functions are dense in NN. (For a nonrecursive function remains nonrecursive if its values at a finite number of arguments are changed.) III. If R(ac) is a recursive predicate, then a-(R(a)) is open and closed. (Since the complement of a-(R(a)) is a((a)), it is sufficient to prove a(R(a)) open. This follows from the fact that if R(a), then R(j3) for any function j agreeing with a on a certain finite set of arguments.)