# If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

So this is how i solve it but someone told me its wrong:

$B-C = B\cap \overline C$ and since $B\cap \overline C$ is r.e and B is recursive recursive sets are closed under intersection then $\overline C$ is not Recursive(because if both of them were recursive then the intersection would be recursive), also since r.e sets are closed under intersection then $\overline C$ must be r.e

and since $\overline C$ and $C$ are r.e then C is recursive

so am i wrong? is C recursive or not and why?

The argument is wrong.

Your argument is: $B\cap \bar C$ is r.e., $B$ is recursive, so $\bar C$ has to be non recursive, otherwise $B \cap \bar C$ would be recursive -- contradiction.

However, there is no contradiction: $B\cap \bar C$ can be both r.e. and recursive. This is equivalent to $B\cap \bar C$ being recursive. There is no hypothesis contradicting that.

Indeed, take $C$ to be the halting problem (r.e., and not recursive). Take $B=\emptyset$ which is recursive. Then $B\cap\bar C = \emptyset$ which is (recursive and) r.e. . So all the hypotheses are satisfied, but $C$ is not recursive.

• So is C not recursive? how can i prove it i can't come up with anything – John P Jan 24 '18 at 15:16
• That specific $C$ is, so we can't conclude that $C$ is recursive, in general. (I am not implying here that every $C$ satisfying the hypothesis must be non recursive. For this I don't need a general proof, only a counterexample) – chi Jan 24 '18 at 16:00
• But how can i prove that C is in fact not recursive? – John P Jan 25 '18 at 7:14
• What makes you think you can prove that? Try to find a counterexample. From those hypotheses you can't conclude either C recursive not C not recursive. They are too weak to conclude something. – chi Jan 25 '18 at 9:06
• But my teacher says i can!! this question was on our exam and he says we can prove that C is not recursive – John P Jan 28 '18 at 12:42