If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.

Can someone give a counter example to the claim that if both Q1 and Q2 are c.e. then so is Q1\Q2?

Since H is semi-decidable and hence also c.e., I was thinking of coming up with examples using it, but no success till now.

  • 3
    $\begingroup$ What's "countably enumerable"? Do you mean "recursively enumerable"? $\endgroup$
    – xskxzr
    Commented May 16, 2018 at 2:49
  • 3
    $\begingroup$ Try taking $Q1$ to be the full language. $\endgroup$
    – chi
    Commented May 16, 2018 at 9:17
  • $\begingroup$ A decision problem is countably enumerable if there is a function f:N->Q that enumerates it and f is computable. Equivalently, Q is countably enumerable if there is a register machine/Turing machine that given any i in N, outputs Qi in Q.so if a problem, is semi decidable, we can just run simulate all machine with inputs 1 to infinity in parallel (one step of a machine at a time), to give an enumeration... $\endgroup$ Commented May 16, 2018 at 9:41
  • $\begingroup$ @xskxzr yes, the book mentions in older literature it is called recursively enumerable, please excuse me as I'm a beginner and am learning things for the first time $\endgroup$ Commented May 16, 2018 at 11:13

1 Answer 1


First of all, notice that not all c.e. sets have a c.e. complement, i.e. there are c.e. sets like $Q$ such that $Q^c=\mathbb{N}-Q$ is not c.e. In fact the Halting Problem $H$ is such a c.e. set.

To see why $H^c$ is not c.e., notice that if both a set and its complement are semi-decidable, then both are also decidable. And since $H$ is not decidable, then $H^c$ should not be semi-decidable either.

Now for the counter example to your question, let $Q_1 = \mathbb{N}$ and $Q_2 = H$. Then $\mathbb{N} - H = H^c$, is not c.e.

Edit: Explained $H^c$ and added a simpler and more straightforward counter example.

  • $\begingroup$ Thanks. Is the complement of H, the looping problem, i.e. does this machine loop? Or we can't make statements such as this? $\endgroup$ Commented May 20, 2018 at 5:44
  • $\begingroup$ No. What a looping program itself enumerates (or accepts) is just an empty set, which is computable. $H^c$ contains the codes of looping programs, i.e. codes of machines and inputs on which the corresponding machine does not halt. I have edited my answer for better clarity. $\endgroup$
    – Beleg
    Commented May 20, 2018 at 10:44

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.