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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Finite subsets of $\mathbb{N}$ are closed under intersection and union, but not under complement. $\endgroup$
    – Andrej Bauer
    Commented Jan 9, 2016 at 9:07

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 9, 2016 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
    Commented Jan 9, 2016 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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