2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$

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.