Closure property of recursively enumerable language

Question

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 ?

Answer 1

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).