Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Terminology:

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|improve this question
add comment

1 Answer

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.' http://www.comp.nus.edu.sg/~fstephan/coh.ps

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|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? –  Zhang Jing 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)$ –  Zhang Jing Feb 11 '13 at 8:26
add comment

Your Answer

 
discard

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.