Relativization of structures arising from computability theory
André Nies · Cambridge University Press eBooks · 1996
: We describe a general method to separate relativizations of structures arising from computability theory. The method is applied to the lattice of r.e. sets, and the partial orders of r.e. m –degrees and T –degrees. We also consider classes of oracles where all relativizations are elementarily equivalent. We hope that the paper can serve as well as an introduction to coding in these structures. Introduction. The relativization of a concept from computability theory to an oracle set Z is obtained by expanding the underlying concept of computation in a way such that, at any step of the computation procedure, tests of the form “ n ∈ Z ”, where n is some number obtained previously in the computation, are allowed. For instance, the relativization of the concept of r.e. sets to Z is “set r.e. in Z ”. In this paper, we study to what extent the isomorphism type and the theory of the relativization A z of a structure A from computability theory depend on the oracle set Z . We consider mainly the case that A is the structure ε of r.e. sets under inclusion or a degree structure on r.e. sets, but first discuss the case that A is the structure of D T all T –degrees or D m of all m –degrees. In this case, is the structure of degrees of subsets of ω under many–one reductions via (total) functions recursive in Z , while is simply the upper cone of D T above the T –degree of Z .