0
$\begingroup$

"The class of Recursively Enumerable Languages is closed under Union, and Intersection but they are not closed under Complement."

I know why they are not closed under Complement & why they are closed under Union & Intersection but for other classes of languages we use a reasoning for closures based on the De'Morgan Law:

$A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$

That is,
If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third.
So what's wrong with the class of Recursively Enumerable Languages?
are not they sets?
Or am I using implication incorrectly?

$\endgroup$
  • 2
    $\begingroup$ Finite subsets of $\mathbb{N}$ are closed under intersection and union, but not under complement. $\endgroup$ – Andrej Bauer Jan 9 '16 at 9:07
7
$\begingroup$

The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate. I'm not sure where you got it from, but it's not correct.

Recursively enumerable languages are closed under union and intersection. However, they're not closed under complement. And, there's no way to express complement using just union and intersection. So, the fact that they're closed under union and intersection does not imply that they're closed under complete. There's no paradox/contradiction here.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot, I used implication incorrectly here.The correct claim would be "If a class is closed under Union & Complement then it must also be closed under Intersection and consequently under Difference." Right? $\endgroup$ – Romy Jan 9 '16 at 8:06
  • 2
    $\begingroup$ @Romy Yes, that's fine. Also, if it's closed under intersection and complement, then it's closed under union. A formulaic alternative: complement-closure implies (union-closure iff intersection-closure). $\endgroup$ – chi Jan 9 '16 at 11:07

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.