Many-one Reducibility Understanding Problem

225 Views Asked by At

We know for every set $B$, that be r.e have:

$$B\leq_mK$$

(The set $B$ is many-one reducible, or m-reducible, to the set $K$)

we know $K$ is r.e and define:

$$K=\{ e:e\in W_e\}$$

my challenge is:

if A is a r.e Set why the following is true? $$\overline K\leq_m \overline A$$ $$\overline A\leq_m\overline K$$

1

There are 1 best solutions below

1
On

If $A$ is a recursively enumerable set, it is not true that $\bar{K} \leq_m \bar{A}$. For instance if $A = \emptyset$, which is a recursive set (and hence recursively enumerable). If your claim was true, then

$\bar{K} \leq_m \bar{\emptyset} = \omega$.

This would imply that $\bar{K}$ is computable. Then $K$ is computable, which it is not.