×

Relative recursive enumerability of generic degrees. (English) Zbl 0753.03017

A set \(A\subseteq\omega\) is called \(n\)-generic if it is Cohen-generic for \(n\)-quantifier arithmetic. We call a Turing degree \(n\)-generic if it has an \(n\)-generic representative. In this paper the following theorem is proved.
Theorem. For any \(n\geq 1\) and any \(n\)-generic degree \(\underset\widetilde{} a\), there is an \(n\)-generic degree \(\underset\widetilde{} c<\underset\widetilde{} a\) such that \(\underset\widetilde{} a\) is recursively enumerable in \(\underset\widetilde{} c\).
This gives an affirmative answer to a question of C. G. Jockusch jun. [Recursion theory, its generalizations and applications, Proc. Logic Colloq., Leeds 1979, Lond. Math. Soc. Lect. Note Ser. 45, 110-139 (1980; Zbl 0457.03042)].

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees

Citations:

Zbl 0457.03042
PDF BibTeX XML Cite
Full Text: DOI