On Characterizing Spector Classes

Abstract

We study in this paper characterizations of various interesting classes of relations arising in recursion theory. We first determine which Spector classes on the structure of arithmetic arise from recursion in normal type 2 objects, giving a partial answer to a problem raised by Moschovakis [8], where the notion of Spector class was first essentially introduced. Our result here was independently discovered by S. G. Simpson (see [3]). We conclude our study of Spector classes by examining two simple relations between them and a natural hierarchy to which they give rise.

Files

Additional details