MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Cohesive sets: $A\subset \omega$, for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap(\omega\setminus W_e)$ is finite.

Non-high degrees: Degree $a$ such that $a'\not\geq 0''$.

I'm wondering if it is possible to construct a cohesive set using some non-high 1-generic degree as an oracle? i.e. are there $A$ cohesive, and $B$ non-high 1-generic such that $A\leq_T B$? Thanks in advance!

share|cite|improve this question
up vote 6 down vote accepted

The answer to this question is in Jockusch and Stephan's 1993 paper 'A cohesive set which is not high.'

Take $A$ and $B$ such that $A \le_T B$, $A$ is Cohesive and $B' \not\ge_T 0''$. This implies that $A' \not \ge_T 0''$ and so by the paper mentioned above $A$ computes a diagonally-not-computable function. But no 1-generic can compute such a function hence $B$ cannot be 1-generic.

share|cite|improve this answer
@Adam: Thank you! I would take a look at that paper! Is it also mentioned there why no 1-generic set could compute a DNC function? – Jing Zhang Feb 9 '13 at 19:13
No but this is not so difficult. Fix a functional $\Phi$, define $W$ by adding any string $\sigma$ such that for some $n$, $\varphi_n(n)\downarrow$ and $\Phi^\sigma(n) \ne \varphi_n(n)$. If $G$ is 1-generic and $G$ meets $W$ the $\Phi^G$ is not DNC, if $G$ avoids $W$ (say at $\sigma$) then $\Phi^G$ cannot be total (otherwise build a computable DNC by looking at convergences compatible with $\sigma$). – Adam Day Feb 10 '13 at 16:27
@Adam: Thanks for the note. But I believe in your definition of $W$ it should be $\Phi^\sigma(n)=\varphi_n(n)$ – Jing Zhang Feb 11 '13 at 8:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.