## 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

### Keywords:

Cohen-generic; Turing degree; $$n$$-generic degree

Zbl 0457.03042
Full Text: