# Reduction to/from REC and RE language?

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?

1. $W$ can be recursively enumerable and $Z$ is recursive.
2. $W$ can be recursive and $Z$ is recursively enumerable.
3. $W$ is not recursively enumerable and $Z$ is recursive.
4. $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?

## 1 Answer

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.

• I got it, Thanks for nice explanation. – Mithlesh Upadhyay Feb 25 '16 at 14:42
• You're welcome, & thank you. – BrianO Feb 25 '16 at 14:42
• Assume complement property for CFLs. Since, we have proved that CFLs are not closed under property complementation. That means, if L is CFL but not regular, then the complement of L may not be CFL. That was my question :) – Mithlesh Upadhyay Feb 25 '16 at 14:46
• I got here, if L and its complement L1, then (i) if L is REC then L1 also REC (ii) if L is RE but not REC then L1 is not RE (iii) if L is not RE then L1 is also not RE. Am I right? – Mithlesh Upadhyay Feb 25 '16 at 14:50
• Ohh, I wouldn't have guessed that was your question :) But is it true? (by "may not be", do you mean "must not be" or "might not be"?) I don't of such a theorem, saying that if $L$ and $\overline{L}$ are both CFL then $L$ is regular. There may be a known or easy-enough counterexample. – BrianO Feb 25 '16 at 14:50