9
$\begingroup$

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!

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @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? $\endgroup$
    – Jing Zhang
    Feb 9, 2013 at 19:13
  • $\begingroup$ 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$). $\endgroup$
    – Adam Day
    Feb 10, 2013 at 16:27
  • $\begingroup$ @Adam: Thanks for the note. But I believe in your definition of $W$ it should be $\Phi^\sigma(n)=\varphi_n(n)$ $\endgroup$
    – Jing Zhang
    Feb 11, 2013 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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