# If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

what about $\cup$ and $\times$ operators? If $A \cup B$ or $A \times B$ is recursively enumerable is it true to say both $A$ and $B$ are R.E.?

• What do you think? Given machines enumerating $A,B$, can you think of a way of enumerating $A\cap B,A\cup B,A\times B$? – Yuval Filmus Feb 26 '15 at 13:29
• @YuvalFilmus if $A$ and $B$ are R.E. then clearly $A \cap B$ and $A \cup B$ and $A \times B$ are R.E. but I have no idea about the reverse of this process – M a m a D Feb 26 '15 at 13:31
• You ask three questions at once; don't do that. – Raphael Feb 26 '15 at 13:54
• @Raphael I corrected the title. three questions are of the same type – M a m a D Feb 26 '15 at 14:22

Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively enumerable.
However, when $A\times B\in\mathsf{RE}$, there is a Turing machine $\mathcal{M}$ accepts $(x,y)$ iff $x\in A$ and $y\in B$. Therefore $\mathcal{M}(x,y_0)$ for fixed $y_0\in B$ accepts the language $A$, and hence $A\in\mathsf{RE}$. For $B$ it is the same.
Update: I notice that I missed something in the case of $A\times B$. The conclusion holds only when both $A,B$ are not empty, since otherwise $A\times B=\varnothing\in\mathsf{RE}$ whatever the other one is.
• So in the aggregate if $A \cup B$ or $A \cap B$ is R.E. we can not say that both $A$ and $B$ are R.E but if $A \times B$ is R.E. we can say $A$ and $B$ are R.E., right? – M a m a D Feb 26 '15 at 14:23