Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.