4
$\begingroup$

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 is the empty set or $A \cap B$ 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 (and formally) prove any of those?

$\endgroup$
0
1
$\begingroup$

The empty set is recursive, hence B cannot be the empty set.

You are right the B-A is recursively enumerable.

You cannot prove B-A is not recursive for a good reason: it may be recursive. Maybe you can imagine an example of A recursive, B not recursive, and B-A recursive. Hint: it is not even necessary that B be recursively enumerable, or A recursive.

Proof that $B-A$ can have properties more specific than recursively enumerability (i.e. compatible with being recursively enumerable), indpendently of the properties of B.

Consider 2 disjoint alphabets $\Sigma$ and $\Sigma'$, such that $\Sigma\cap\Sigma'=\emptyset$. Take $C=\Sigma'\,^*$ and $A=\Sigma^*$. Let $E$ be a non-recursive language in $\Sigma^*$. Let $B=C\cup E$. Then $B$ is a non-recursive language on the alphabet $\Sigma\cup\Sigma'$, because $C$ is recursive (trivially). Now you can see that $B-A=C$ since substracting $A$ removes precisely $E$, i.e. all words in B that are in $\Sigma^*$. So you have $B$ non-recursive, and both $A$ and B-A are recursive. Here I chose $A$ recursive. But I could have chosen any non-recursive language on $\Sigma^*$ that contains $E$.

Similarly, you cannot prove anything about A-B. Think why.

$\endgroup$
5
  • $\begingroup$ Can I tell when $B-A$ is recursive and when it's not? For example, if $A \cap B$ is finite and supposing $B-A$ is recursive, then B would be recursive (and I know it isn't), so $B-A$ can't be recursive in this case. I don't know about the other case. Also, can't think of an example of A recursive, B not recursive and $B-A$ recursive. $\endgroup$ – user24532 Dec 7 '14 at 13:17
  • $\begingroup$ @nowembery If A∩B is recursive (finite is a special case) and B-A is recursive, then B is recursive since B=(B-A)∪(A∩B). So you are right that if A∩B is recursive and B is not, then A-B cannot be. But you can imagine hundreds of special cases. For A recursive, B not recursive and B-A recursive, you can build the example starting from any part of the problem. For example you start with a recursive set C that is intended to be B-A. Then you choose a recursive set A that has empty intersection with C, and consider a non-recursive subset of A, and ... (not to spoil the whole fun). $\endgroup$ – babou Dec 7 '14 at 14:32
  • $\begingroup$ Did you get it? To make things simpler, take C in one alphabet, and A in another alphabet with different symbols. $\endgroup$ – babou Dec 7 '14 at 23:22
  • $\begingroup$ Uhm, no, sorry. I've read / learned only about recursive / r.e. functions and sets, and Turing reduction. (Have no idea if I'm asking something stupid: the union of the non-recursive subset of A and C is supposed to be B?) $\endgroup$ – user24532 Dec 8 '14 at 0:06
  • $\begingroup$ Here is the simple version. Consider 2 disjoint alphabets Σ and Σ', such that Σ∩Σ'=∅. Take C=Σ' * and A=Σ*. Let E be a non-recursive language in Σ*. Let B=C∪E. Then B is a non-recursive language on the alphabet Σ∪Σ', because C is recursive (trivially). Now you can see that B-A=C since substracting A removes precisely E, i.e. all words in B that are in Σ*. So you have B non-recursive, and both A and B-A are recursive. Here I chose A recursive. But I could have chosen any non-recursive language on Σ* that contains E. $\endgroup$ – babou Dec 8 '14 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy