The symmetric difference of two recursive (recursively enumerable) sets is recursive (recursively enumerable)

Question

I want to prove it, but don't know how... (I've tried to resolve complement by defining characteristic function like this: $\chi_{\bar A} = 1 - \chi_A$) Any ideas please? :-)

Answer 1

The first thing to do is to make an estimate of where in the arithmetical hierarchy the symmetric of two r.e. sets will be.

If it looks like the symmetric difference will be $\Sigma^0_1$, then try to prove it is r.e.; if it looks like the symmetric difference is higher than $\Sigma^0_1$ then try to find an example where the symmetric difference is not r.e.

Then do the same thing but assume the sets are computable ($\Delta^0_1$) instead of r.e. ($\Sigma^0_1$).

Answer 2

If we denote the symmetric difference operator by $\bigtriangleup$, then $$ S_1\bigtriangleup S_2=(S_1\cup S_2)\cap(\overline{S_1}\cup \overline{S_2}) $$ Now you can use the facts that

• Recursive sets are closed under union, intersection, and complement.
• r.e. sets are closed under union and intersection, but not under complement.

This should get you started.