Welcome to MathOverflow

Question

6

Terminology: Cohesive sets: $A\subset \omega$, for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap \omega $\$ 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!

edited Apr 4 at 16:52

asked Feb 7 at 18:18

Zhang Jing
309●1●1●6

Adam Day · Accepted Answer · 2013-02-09 01:12:53Z UTC

5

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' < 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.

answered Feb 9 at 1:12

Adam Day
146●1●2

	@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 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 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 at 8:26

Cohesive sets with degree below some non-high 1-generic degrees?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.