Two recursively enumerable sets $A$ and $B$ such that none of union, intersection, one subtracting the other is recursive?

362 Views Asked by At

I was reading the two questions posed here and here and their answers, and my question here is motivated by them.

Do there exist $2$ recursively enumerable sets $A$ and $B$ where none of the $4$ sets$$A \cap B, \quad A \cup B, \quad A - B, \quad B - A$$is recursive?

1

There are 1 best solutions below

3
On BEST ANSWER

Let $S$ be your favorite r.e. but not recursive set, and consider $$ A = \{4n+1\mid n\in S\} \cup \{4n+2\mid n\in S\} \\ B = \{4n+2\mid n\in S\} \cup \{4n+3\mid n\in S\} $$