2
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Oct 23 '17 at 20:00
  • 1
    $\begingroup$ 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. $\endgroup$ – chi Oct 23 '17 at 20:48
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ See my edit to the question. $\endgroup$ – Zephyr Oct 23 '17 at 19:24
  • $\begingroup$ @Zephyr See updates. Also, please decide on what question you want to ask, and do not change your OP too often. It may make people's answers obsolete and inconsistent. $\endgroup$ – fade2black Oct 23 '17 at 19:39
  • $\begingroup$ wikipedia has used a similar argument (union of complements)for proving closure of CFL 's under intersection en.m.wikipedia.org/wiki/Context-free_language $\endgroup$ – Zephyr Oct 23 '17 at 19:50
  • $\begingroup$ @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$. $\endgroup$ – fade2black Oct 23 '17 at 20:07
  • $\begingroup$ I have one more doubt. R.E is not closed under Set difference property. We know that A - B will always be a subset of A. If we go by that, then as A is R.E, A-B is also R.E as it is subset of A. $\endgroup$ – Zephyr Oct 24 '17 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.