A set $A\subseteq\omega$ is called a cohesive set if $C$ is finite for each recursively enumerable set $W\_e$, either $A\cap W\_e$ is finite or $A\cap(\omega\setminus W\_e)$ is finite. And a set $A\subseteq\omega$ is called simple if it is recursively enumerable and its complement has no infinite recursively enumerable subsets.


Let $C$ be a cohesive set. Then my question is, does there always exist a simple set $X$ such that $C\cap X$ is finite, i.e. all but finitely many elements of $C$ belong to $\omega\setminus X$?



Is a cohesive set always an almost subset of a co-simple set?
No, not necessarily. Let $S\_n,n\geq 0$ be an enumeration of all simple sets. Then for every $k$ the intersection $S\_0\cap\dots\cap S\_k$ is infinite - indeed, if not, then taking the least such $k$ we would have that $S\_0\cap\dots\cap S\_{k-1}$ would be an infinite r.e. set which, up to finitely many elements, is contained in the complement of $S\_k$, which contradicts its simplicity. Therefore we may take an infinite increasing sequence $s\_k$ such that $s\_k\in S\_0\cap\dots\cap S\_k$. Let $S$ be the set of those elements, then for every $k$ we have that $S\cap\overline{S\_k}$ is finite.


Let $C$ be any cohesive subset of $S$ (such a subset exists in any infinite set of naturals, see exercise X.3.4 in Soare's Recursively Enumerable Sets and Degrees). Then for each $k$ we still have $C\cap\overline{S\_k}$ finite, which then forces $C\cap S\_k$ to be infinite for every simple set $S\_k$.


