Problem Detail: Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A cap B$ be Turing-recognizable too? I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in $A$ and then all the languages in $B$. However, I also know that Turing-recognizable languages are not closed under complement, and $overline{bar{A} cup bar{B}} = A cap B = C$, which seems to suggest that Turing-recognizable languages are not closed under intersection. There is clearly a contradiction somewhere in my reasoning. Where is it?
Asked By : David Faux
Answered By : sdcvvc
Indeed, the recursively enumerable languages are closed under union and intersection, but not complement. This is not a contradiction: the formula $A cap B = overline{overline{A} cup overline{B}}$ tells that a class closed under union and complement is closed under intersection, but does not tell anything otherwise. A similar example: the set of finite subsets of $mathbb N$ is clearly closed under union and intersection, but not complement.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7466
