A set $X$ is called cohesive for $(R_i)_{i\in \mathbb{N}}$ if it is infinite and for each $i$ we have $X\subseteq^* R_i$ or $X\subseteq^* \overline{R_i}$. (Where $X\subseteq^*Y$ means that $X$ is contained in $Y$ up to finitely many exceptions.)

A set $X$ is called cohesive if it is cohesive for all computable enumerable sets.

Further, a set $X$ is called 1-generic if for each computably enumerable set $S\subseteq 2^{<\mathbb{N}}$ of strings there is an initial segment of $\sigma$ of $X$ such that either $\sigma \in S$ or $\sigma \not\subseteq \tau$ for all $\tau \in \sigma$.

Both notions are well studies in computability theory. However, I was not able to find a answer to the following question in the literature:

Is (Turing) below each cohesive set a 1-generic set?

To give some background on the question: The reverse of the above question is known to be false. That is there is a 1-generic which has no cohesive set below it. For the proof one has to note that there are low 1-generic sets but no low cohesive sets. (See Jockush, Stephan: A cohesive set which is not high).

Moreover it is known that below each cohesive set is a weakly 1-generic. (A set $X$ is weakly 1-generic if for each dense c.e. set $S$ there is an inital segment $\sigma$ of $X$ with $\sigma\in S$.)


No -- each high degree contains a cohesive set. And Cooper showed there is a high minimal degree. But no 1-generic has minimal degree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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