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

1 Answer 1

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$
2
  • $\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, 2015 at 14:23
  • $\begingroup$ @Drupalist Truly. $\endgroup$
    – Wei Zhan
    Feb 26, 2015 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.