5
$\begingroup$

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$.)

$\endgroup$

1 Answer 1

6
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .