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?


1 Answer 1


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.

  • $\begingroup$ So is C not recursive? how can i prove it i can't come up with anything $\endgroup$
    – John P
    Jan 24, 2018 at 15:16
  • $\begingroup$ 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) $\endgroup$
    – chi
    Jan 24, 2018 at 16:00
  • $\begingroup$ But how can i prove that C is in fact not recursive? $\endgroup$
    – John P
    Jan 25, 2018 at 7:14
  • $\begingroup$ 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. $\endgroup$
    – chi
    Jan 25, 2018 at 9:06
  • $\begingroup$ But my teacher says i can!! this question was on our exam and he says we can prove that C is not recursive $\endgroup$
    – John P
    Jan 28, 2018 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.