# Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed

I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable languages (A and B, say) is not itself RE? I.e. why for A-B = Z, Z is not RE?

The basic set notation and maths I understand, but I've added a more textual description as I'm looking for an intuitive answer: let C = complement of B.

Some of the words C contains in its set would cause a TM for B to reject, others would cause it to never halt. So C is not RE.

Now, A-B = A n C, by basic set operations. The theory I've read now says that the intersection of an RE (A) and a non-RE (C) cannot be RE, which is why the original A-B = a non-RE. I accept this logic, but am struggling to understand intuitively how this is true, in terms of picturing a Turing Machine that halts or loops, given the input of words from A n C.

My First Attempt at an Intuitive Explanation:

My guess is that I've missunderstood something fundamental about TMs, and what their acceptance/rejection/looping on words of a language really means, but here we go:

Imagine a TM for the RE lang A. Every word in A will cause TM to accept. Now, isn't A-B just a subset of the words from the language A? Therefore, wouldn't all the words in A-B cause our TM to also accept? By this logic then, wouldn't the difference between two RE's, A-B, be an RE language, too?

My Final Thought:

I tried to picture this in different ways, with say having the condition be that you test your newly outputted language (A-B in this case), on a TM that accepts on each of the initial languages (A, B), and if the new language accepts on all those TMs, it must be RE? But that didn't hold for things like A u B.

So, I'm stuck as for an intuitive understanding as to why A - B is not RE, when A - B is just a subset of words of A, and A will accept on its TM? Further, what's the rule for how your new language (be it A-B, A u B, A* n B, etc) should accept in relation to TMs that accept on the initial languages?

Thanks very much for your help.

Given a language $$L$$, $$L$$ is RE if there is a TM $$M$$ such that $$L(M) = L$$. $$L(M)$$ is the set of words which $$M$$ accepts and it must be equal to $$L$$; words not in $$L$$ must cause $$M$$ either to reject or to never halt. It is not sufficient for $$L$$ to be a subset of $$L(M)$$, which is why your reasoning is incorrect.
Given RE languages $$A$$ and $$B$$, what makes $$A \setminus B$$ not RE (in general) is not the problem of knowing whether the input is in $$A$$; since $$A$$ is RE, there is a TM $$M_A$$ which you can simulate to find out (and if $$M_A$$ does not halt, the input is not in $$A$$ and, hence, not in $$A \setminus B$$ too; so there is no need to halt at all). The problem is that, to accept an input $$w$$ which is not in $$B$$, you need to simulate the respective TM $$M_B$$ on $$w$$ and accept if $$M_B$$ does not halt; hence, you need to solve an instance of the complement of the halting problem, which is (famously) not in RE.
• @TheRealPaulMcCartney That seems correct, yes (though you seem to have written "$B \setminus A$" instead of "$A \setminus B$" in question number 2). I would not say $A \setminus B$ is "accepted" by $M_A$, though; it is only a subset of what $M_A$ accepts, nothing more than that. Jan 8 '19 at 14:44
• @TheRealPaulMcCartney For $A \cap B$ it works because you can simulate $M_A$ and $M_B$ simulatenously and accept if and only if both do. If either $M_A$ or $M_B$ does not accept a word $w$, then $w \not\in A \cap B$, so you need not halt. By the way, subsets of languages are still languages, of course! It is just that every TM accepts a unique language; (by definition) a TM does not "accept" subsets of its language. Jan 8 '19 at 14:57