Abstract

Shoenfield [8] has shown that a hierarchy for the functions recursive in a type-2 object can be set up whenever E2 (the type-2 object that introduces numerical quantification) is recursive in that type-2 object. With a restriction that we will discuss in the next paragraph, Moschovakis [4, pp. 254–259] has solved the analogous problem for type-3 objects. His method seems to generalize for any type-n object, where n ≥ 2. We will solve this same problem of finding hierarchies based on type-n objects by a different method. Instead of using ordinal notations for indexing stages of hierarchies, as do Shoenfield and Moschovakis, we will define notation-independent stages.