# Closure property of recursively enumerable language

I read that recursively enumerable languages are closed under intersection but not under set difference.

We know that, $A \cap B = A - ( A - B)$.

Now for LHS (left-hand side) to be closed under intersection, RHS(right-hand side) should be closed under set difference .

But we know that RHS is not closed under set difference so LHS is also not closed under intersection.

Suppose we assume that R.E is closed under intersection then,

$A \cap B = \overline{(\overline{A} \cup \overline{B})}$.

Now LHS can be closed only if RHS is closed under complement (as R.E languages are already closed under union). But we know R.E is not closed under complement, so again a contradiction.

So, R.E should not be closed under intersection right ?

• That's like saying that postive reals must be closed under subtraction because $x + y = 1 - (1 - x - y)$. You're making a logical error. If you manage to do it the other way around, and express set difference in terms of intersection (you will fail), then we'll have something to discuss. – Andrej Bauer Oct 23 '17 at 20:00
• Your argument could be used to prove that if a family of languages are closed under difference, it is closed under intersection. Or, if it is closed by complement and union, it is closed under intersection. You can't conclude the opposite implication. – chi Oct 23 '17 at 20:48

Basically, "R.e. sets are closed under intersection means that for any two r.e. sets $A \cap B$ is again r.e, but when we say that r.e. are not closed under some set-theoretic operation it means there are at least one pair of r.e sets which results in not-r.e. set under that operation no matter it is set-theoretic difference or complement. In other words,
• R.e. sets are closed under a set theoretic operation $\star$ means that for any pair $A$ and $B$, $A\star B$ is r.e.
• R.e. sets are NOT closed under a set theoretic operation $\star$ means that NOT for all pair $A$ and $B$, $A\star B$ is r.e. In simple words, there may be sets $A$ and $B$ such that $A\star B$ is r.e., and there exist other sets $C$ and $D$ such that $C \star D$ is not r.e.
For example, the set $N - 2N$ (the set of all odd positive integers is r.e (even recursive), but the set $N - A_{TM}$ is clearly not r.e. ($A_{TM}$ denotes the set of Halting problem).
• @Zephyr If r.e. sets are not closed under a specific operation $\star$, that does not mean that r.e. sets are (or are not) closed under another operation $*$ even if $*$ can be represented in terms of $\star$. – fade2black Oct 23 '17 at 20:07