Abstract first order computability. II
Yiannis N. Moschovakis · Transactions of the American Mathematical Society · 1969
In Abstract first order computability.I (the preceding paper), we initiated a study of computability on abstract structures and carrier1 it up to the theory of the "projective hierarchy," our generalization of the arithmetical hierarchy on the set of integers.Here we study the "hyperprotective hierarchy" which is our abstract version of the hyperarithmetic hierarchy on the integers.The numbering of paragraphs and results is a continuation of the numbering in the first part and we have collected in a partial bibliography at the end those papers which are referred to in this part.10. Hyperprojective functions.In XLIII of [6] Kleene characterizes the hyperarithmetic number-theoretic functions as exactly those functions which are recursive in the type-2 object 2E which embodies number quantification.Similarly here we wish to study the class of functions which are search computable in the object Efi.= E which embodies quantification over B*.We define E(g) for a oneplace p.m.v.function g byit is clear that for single-valued total g we have E(g) = 0 if(Ey)[g(y)^0], = 1 otherwise.We define the class H P(cp) of functions computable in E, cp or hyperprojective (in cp) by adding to C0-C9 the schema C10.f(x) = E(Ayg(j,x)) , and accordingly adding to C0'-C9' the clause C10'.// (yIn the usual way clauses C0'-C10' define a predicate {/}h(«) -»■ z and assign to each feB* a p.m.v.function {/}h(«).We let HP(A, <p) = HPiA) be the class of functions hyperprojective from A, i.e. functions {/}h(«) with/Ey4* and put /ZP(cp) = //P=//P(0) (the absolutely hyperprojective functions), H P(cp) = H P =//P(P), the hyperprojective functions.For each list of variables gi,..., gm we get a functional {/}h(gi, •.., gm, «).