1
$\begingroup$

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

  • 0
    Why do you think it's true in the first place?2012-12-04
  • 0
    Actually I don't know if it is true, I just don't know how to start with proving/disproving ...2012-12-04
  • 1
    "r. (r.e.)"?${}$2012-12-04
  • 0
    recursive, recursively enumerable2012-12-04
  • 1
    The answer is not the same in those two cases.2012-12-04
  • 0
    if I define it like this: $\chi_{A * B} = \chi_A + \chi_B - 2\chi_{A \cap B}$ - then is it enough to proof that this char. function is $\mu$-recursive ? and then I can say, symmetric difference is recursive ?2012-12-04
  • 1
    If the claim were true of two recursively enumerable sets, then every r.e. set would be recursive.2012-12-04

2 Answers 2

3

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.

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