Why there is no recursive enumerable set such as B that: > $B \nleq_m K$?

Question

I get stuck in one fact that I see on old-mid exam.

Why there is no recursive enumerable set such as B that:

$B \nleq_m K$

Def: K means Halting Set and $ \leq_m$ means many-one reducible.

anyone could hint or idea for me?

Answer 1

You have to show that for any recursively enumerable language, you can create a many-one reduction to $K$. Since you are only given that the language is r.e., clearly any proof will have to make use of that fact. In other words, provide a mapping reduction that makes use of the recognizer of the language you're reducing from.

Answer 2

The full result is actually a little stronger: For any set $A$, $A'$ is $1$-complete for the r.e. sets in $A$.

To see it for $K (= \varnothing')$. We need to define a $1-1$ recursive function $f$ so that $x \in W_e$ iff $f(x) \in K$. Yet, $x \in W_e$ iff $\varphi_e(x)\downarrow$. By the s-n-m theorem, there is a recursive 1-1 function $k(x)$, so that $\varphi_e(x) = \varphi_{k(x)}(k(x))$ (intuitively, $k$ takes an $x$ and returns an index for a program that simulates $\varphi_e(x)$).

But then, $x \in W_e$ iff $\varphi_e(x)\downarrow$ iff $\varphi_{k(x)}(k(x))\downarrow$ iff $k(x) \in K$.

You can easily relativize this to arbitrary oracle, and, make the reduction uniform in $e$ if you like.