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

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.

• What's "countably enumerable"? Do you mean "recursively enumerable"? – xskxzr May 16 '18 at 2:49
• Try taking $Q1$ to be the full language. – chi May 16 '18 at 9:17
• 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... – Anirudh Gangwal May 16 '18 at 9:41
• @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 – Anirudh Gangwal May 16 '18 at 11:13

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.
• 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. – Beleg May 20 '18 at 10:44