3
$\begingroup$

If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?
I think that as we know nothin about $M$, in general case we can't determine wherther a random element $m$ belongs to $M$, so we coundn't say anything about $A \cap M$. Am I right?

$\endgroup$
  • 1
    $\begingroup$ You can say it's co-r.e. $\endgroup$ – Yuval Filmus Jul 31 '18 at 18:46
3
$\begingroup$

If $\overline{M}$ is r.e., then we do know something about $M$: namely, that it's co-r.e. And the intersection of any two co-r.e. sets is co-r.e., so $A\cap M$ is co-r.e. (every recursive set is a fortiori co-r.e.). Beyond that, of course, we can't say anything: every co-r.e. set is of the form $A\cap M$ for some recursive $A$ and some co-r.e. $M$ (take $A=\mathbb{N}$ and $M=$ the co-r.e. set in question).

This may seem a bit silly, but being the complement of an r.e. set is a very strong property, even though we think of it less than r.e.-ness. Also, lots of natural sets are co-r.e. but not r.e., like the set of (indices for) Turing machines which never halt on any input. So the conclusion "$A\cap M$ is co-r.e." is actually quite meaningful.


This answers your specific question, but let me say a bit more.

We didn't really use that $A$ was recursive, merely that $A$ was co-r.e. But what if $A$ is merely r.e.? Then in general $A\cap M$ is neither r.e. nor co-r.e. This is the first step into the difference hierarchy: $A\cap M$ can be rewritten as $A\setminus \overline{M}$, that is, as the difference of two r.e. sets, and we can continue further and talk about more complicated Boolean combinations of r.e. sets. It turns out that this gives a proper hierarchy, even in the coarse terms of Turing degree: for each $n$ there is an $(n+1)$-r.e. set which is not of the same Turing degree as any $n$-r.e. set (I believe this was proved by Cooper but I don't have a reference on hand; it certainly followed his proof of the case $n=1$).

We can try to continue the difference hierarchy into the transfinite but one runs into some difficulties in doing so (namely, the issue of finding appropriate "names" for complicated infinite ordinals - this is where Kleene's $\mathcal{O}$ becomes unavoidably relevant). What we get winds up not being a true hierarchy: even though the ordinals are linearly ordered, we can't avoid having different "difference levels" which are incomparable. The resulting "pseudo-hierarchy" is however a quite interesting object, and is called the Ershov hierarchy.

For more information on this, I strongly recommend the first couple sections of the paper The Ershov hierarchy by Stephan, Yang, and Yu.

$\endgroup$

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.