The union of a recursively enumerable set and its complement is $\Sigma^*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$? $$ \{ \# w : w \in S \} \cup \{ \\\$ w : w \in \overline{S} \} $$ Is the result recursively enumerable?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ The question in the body doesn't really match the title $\endgroup$– ArielCommented Apr 9, 2021 at 5:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The operation you described in actually the join operator in the semilattice of Turing degrees, defined as $A\sqcup B=\{0x | x\in A\}\cup \{1x | x\in B\}$. It is not hard to show that $A,B\le_T A\sqcup B$, thus if $A\in RE\setminus R$ then $\overline{A}\notin RE$ and thus $A\sqcup\overline{A}\notin RE$.
