0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Yuval Filmus Feb 26 '15 at 13:29
  • $\begingroup$ @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 $\endgroup$ – M a m a D Feb 26 '15 at 13:31
  • 1
    $\begingroup$ You ask three questions at once; don't do that. $\endgroup$ – Raphael Feb 26 '15 at 13:54
  • $\begingroup$ @Raphael I corrected the title. three questions are of the same type $\endgroup$ – M a m a D Feb 26 '15 at 14:22
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – M a m a D Feb 26 '15 at 14:23
  • $\begingroup$ @Drupalist Truly. $\endgroup$ – Willard Zhan Feb 26 '15 at 14:26

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.