3

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$?

$B-A$ is obviously recursively enumerable (to generate its elements, I can generate B's elements and check if they are in A).

If A and/or B is/are the empty set or their intersection is the empty set, it's easy. Otherwise, I believe $B-A$ is not recursive (I can't tell if a number is in B, since B is not recursive) and $A-B$ is not recursively enumerable (I can generate A's elements, but I can't check if they are in B), so it's not recursive either.

Am I wrong? How can I actually prove any of those?

1 Answers1

1

$A - B$ will be computable if $A - B$ is finite or if $A \cap B$ is finite. In either case, a trivial modification of the procedure to compute $A$ gives a procedure to compute $A - B$.

If $A - B$ and $A \cap B$ are infinite, then $A$ is infinite, so by computably renumbering the sets we can assume $A = \mathbb{N}$. In this case, since $B$ is r.e. but not computable, $B^c$ will not be r.e.

You can expand the arguments in those two paragraphs to make more formal proofs, if needed.

Carl Mummert
  • 81,604
  • Uhm, I'm sorry if I'm asking something obvious, but what exactly means "computably renumbering the sets"? Also, is it enough that for $A = \mathbb{N}$, $A-B$ being recursive implies something false to tell that for any recursive set A and any r.e. set B, $A-B$ is not recursive? –  Dec 07 '14 at 13:43
  • @nowembery: I mean there is a computable bijection between $A$ and $\mathbb{N}$. Take the image of $B$ under that bijection to get a set $\hat B$, which will also be r.e., and which will be computable if and only if the original $B$ was computable. But now instead of $A - B$ we can work with $\mathbb{N} - \hat B$, which is easier. – Carl Mummert Dec 07 '14 at 13:58