Is the difference of two recursively enumerable sets, reducible to $K$?

Question

Is the difference of two recursively enumerable sets, reducible to $K$?

$W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$

$K=\{x|\Phi_x(x) \downarrow\}$

$W_x= \text{dom}(\Phi_x)$

Answer 1

Which kind of reduction are you looking for?

It is trivially Turing reducible, because if you have a $K$-oracle available you can simply decide $W_x$ and $W_y$.

It's not many-one reducible, however, because it you take $W_x$ to be everything, a many-one reduction would tell you that the complement of a r.e. language is r.e. (which is well known to be false).

Answer 2

No.

Let $\omega$ denote the set of natural numbers. $K$ is c.e. but incomputable. If a set $A$ and its complement $\bar{A} = \omega - A$ is c.e., then $A$ must be computable. Hence $\bar{K} = \omega - K$, the complement of $K$, is not a c.e. set.

It is clear that $\omega$, the set of natural numbers, is c.e. (it is computable). $K$ is c.e. Thus

$\omega - K$ is a different of two c.e. sets. $\omega - K = \bar{K}$ which as mentioned above is not c.e.

Suppose $\omega - K = \bar{K}$ was many to one reducible to $K$; in notations $\bar{K} \leq_m K$. Since $K$ is c.e., $\bar{K}$ would have to c.e. (see the little lemma under the line). This a contradiction.

---

If if two set $A \leq_m B$ (are many to one reducible) and $B$ is c.e., then $A$ is c.e.

By definition of $A \leq_m B$, there is a computable function $f$ such that

$x \in A$ if and only if $f(x) \in B$.

Since $B$ is c.e., $B = W_n$ for some $n$. Define a new partial computable function

$\Psi(x) = \begin{cases} 0 & \quad \text{if }\Phi_n(f(x)) \downarrow \\ \uparrow & \quad \text{otherwise} \end{cases}$

Since $\Psi$ is partial computable, it has a index $p$. That is, $\Psi = \Phi_p$. Then $A = W_p$ since $x \in A$ if and only if $f(x) \in B$ if and only if $\Phi_n(f(x)) \downarrow$ if and only if $\Phi_p(x) \downarrow$. $A$ is c.e.