If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?

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?

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.

StackExchange Computer Science Q#95835, answer score: 3