Suppose that $A$ and $B$ are simple sets. How to show that the set $A \oplus B$ is simple?

53 Views Asked by At

Define $A \oplus B=\{2x:x\in A\}\cup\{2x+1:x\in B\}$.

First, show $A⊕B$ is recursively enumerable. Define its partial function by

$h(x)=\begin{cases} 1 & \text{, if $x$ is even and $\frac x 2\in A$, or $x$ is odd and $\frac {x-1} 2$ $\in B$ } \\ undefined & \text{, otherwise} \end{cases}$

Hence, $A⊕B$ is recursively enumerable.

But I don't know how to show $\bar {A⊕B}$ (i.e.,complement of $A⊕B$) is infinite, and contains no infinite r.e. subset?