A question on many-one reducibility Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. For each $x\in\mathbb{N}$, let $W_x$ the domain of $\phi_x$, and let $K=\{x\in\mathbb{N}:W_x\neq\emptyset\}$. Is there a recursive set $R$ such that $K\not\leq_m(K\setminus R)\cup(R\setminus K)$ and $(\mathbb{N}\setminus K)\not\leq_m(K\setminus R)\cup(R\setminus K)$?  
 A: No.  The short answer is that the recursion theorem provides us with an infinite computable set of values; if this set has infinite intersection with $R$, then $(\mathbb{N}\setminus K) \le_m (K\setminus R)\cup (R\setminus K)$ because we can code on the $(R\setminus K)$ part and ignore the other part, and if this set has infinite intersection with $(\mathbb{N}\setminus R)$, then $K \le_m (K\setminus R)\cup (R\setminus K)$ because we can code on the $(K\setminus R)$ part and ignore the other part.
For more details: by the $s$-$m$-$n$-theorem, there is a total computable injective $g$ such that $W_{\phi_e(x)} = W_{g(e,x)}$ for all $e$ and $x$.  Using the $s$-$m$-$n$-theorem again, define $f$ as follows: $W_{\phi_{f(e)}(x)} = W_n$ if $g(e,x) \in R$ and there are exactly $n$ values $y < x$ with $g(e,y) \in R$; or $W_{\phi_{f(e)}(x)} = W_n$ if $g(e,x) \not \in R$ and there are exactly $n$ values $y < x$ with $g(e,y) \not \in R$.
By the recursion theorem, there is an $e$ with $\phi_e = \phi_{f(e)}$.  So then for all $x$, $W_{g(e,x)} = W_{\phi_e(x)} = W_{\phi_{f(e)}(x)}$.  Now consider the set $G = \{g(e,x) : x\in\mathbb{N}\}$.
If $G \cap R$ is infinite, then we can effectively locate the $n$th number $x$ with $g(e,x) \in R$.  Then $W_n = W_{g(e,x)}$, so $n \in (\mathbb{N}\setminus K) \iff g(e,x) \in (R\setminus K)$.
If $G \setminus R$ is infinite, then we can effectively locate the $n$th number $x$ with $g(e,x) \not \in R$.  Then again $W_n = W_{g(e,x)}$, so $n \in K \iff g(e,x) \in (K\setminus R)$.
