I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $C \cap B = \emptyset$.

I think one way to construct $C$ is to show that $\bar{A}-\bar{B}$ is c.e., but is the set difference $\bar{A}-\bar{B}$ for this particular case c.e.?

  • 1
    $\begingroup$ Help us out. Why do you suppose your construction may be wrong? $\endgroup$ – Rick Decker Mar 11 at 15:35
  • $\begingroup$ @Rick Decker well... I think the enumerator $E$ works as it should, but to confirm it I've been looking around for results that show that the set difference of two c.e. sets is also c.e. but found none... so am looking for additional tips just in case I missed something in the construction $\endgroup$ – Link L Mar 12 at 0:30
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 12 at 5:44
  • $\begingroup$ @D.W. okay, will keep that in mind, question is edited $\endgroup$ – Link L Mar 12 at 5:51
  • $\begingroup$ The part "... and $A\cap B=\emptyset$" looks wrong. Was that meant to be "... and $C\cap B=\emptyset$", which makes more sense? $\endgroup$ – chi Mar 13 at 19:26

No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).

| cite | improve this answer | |
  • 1
    $\begingroup$ If by "your question" you mean the question at the start of the OP, this is false: any two disjoint co-r.e. sets are indeed separable by a decidable set - think about when elements enter their complements ... (for c.e. sets this is false - but note that here $\overline{A}$ and $\overline{B}$, not $A$ and $B$, are r.e., so the OP is talking about separating co-r.e. rather than r.e. sets). That said, if by "your question" you mean the last sentence of the OP you're correct. (But this is worth clarifying.) $\endgroup$ – Noah Schweber Mar 12 at 13:14
  • $\begingroup$ @NoahSchweber, OK, I'll edit to clarify. Pedantically, there's only one question in the post. The first sentence is a sentence, not a question. But OK. $\endgroup$ – D.W. Mar 12 at 17:25
  • $\begingroup$ @D.W., I found the answer to the problem, apparently it's a common question that comes out in problem sets and textbook exercises $\endgroup$ – Link L Mar 14 at 1:35

Your Answer

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

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