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

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? :-)

-
Why do you think it's true in the first place? – Carl Mummert Dec 4 '12 at 14:22
Actually I don't know if it is true, I just don't know how to start with proving/disproving ... – kolage Dec 4 '12 at 14:24
"r. (r.e.)"?${}$ – David Mitra Dec 4 '12 at 14:24
The answer is not the same in those two cases. – Henning Makholm Dec 4 '12 at 14:38
If the claim were true of two recursively enumerable sets, then every r.e. set would be recursive. – hardmath Dec 4 '12 at 15:17

2 Answers

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.

-

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$).

-