Question

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that $\overline{Y}$ reduces to W, and Z reduces to $\overline{X}$
(reduction means the standard many-one reduction). Which one of the following statements is TRUE?

Answer 1

$X\to REC$
$Y\to REbutnotREC$
$\overline{Y}\le WandZ\le \overline{X}$
Now we know that RE, REC both go in reverse direction on reduction.
Now if Y is RE but not REC, then $\overline{Y}$ is not RE.
Now $\overline{Y}\le W$
If W is RE $\Rightarrow \overline{Y}isRE$
Contrapositive is $\overline{Y}$ is not RE $\Rightarrow W$ is not RE
Now Z$\le \overline{X}$
If X is REC, $\overline{X}$ is also REC
So $\overline{X}REC\Rightarrow ZisREC$
So W is not RE and Z is REC.