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?
- $W$ can be recursively enumerable and $Z$ is recursive.
- $W$ can be recursive and $Z$ is recursively enumerable.
- $W$ is not recursively enumerable and $Z$ is recursive.
- $W$ is not recursively enumerable and $Z$ is not recursive.
My attempt :
Given, $X$ is REC, and $Y$ is RE only. Since REC is closed under complementation property. So, complement of REC is also REC. RE is not closed under complementation property, so complement of RE may not be RE.
Therefore,
$$Y\leq W$$
So, $W$ can be RE.
$$Z\leq X$$
So, $Z$ is REC. Hence, option $(1)$ is true. But, somewhere answer is given option $(3)$.
Can you explain in formal way, please?
At first I didn't notice the \bar{}s over $X$ and $W$. I changed them to \overline, which is easier to see.
In the case of $X$ it doesn't matter: as $X$ is recursive, $\overline{X}$ is recursive too, so $Z\le_m \overline{X}$ is recursive.
In the case of $W$, it matters a lot. Here's why 3. is true: If $W$ were r.e., we would have $\overline{Y}\le_m W \le_m K$, where K is the halting problem. Thus $\overline{Y}\le_m K$ would be r.e. But then $Y$ would be recursive, which it isn't.