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? :-)
The symmetric difference of two recursive (recursively enumerable) sets is recursive (recursively enumerable)
1
$\begingroup$
computability
-
0Why do you think it's true in the first place? – 2012-12-04
-
0Actually 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
-
0recursive, recursively enumerable – 2012-12-04
-
1The answer is not the same in those two cases. – 2012-12-04
-
0if 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
-
1If the claim were true of two recursively enumerable sets, then every r.e. set would be recursive. – 2012-12-04