# If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$

I found the following question with an answer here, but I can't understand the steps of the solution.

Show that if a language $$A$$ is in RE and $$A \leq_m \overline{A}$$, then $$A$$ is recursive.

Solution. Since $$A \leq_m \overline{A}$$, it follows that $$\overline{A} \leq_m A$$, and since $$A$$ is in RE, it follows that $$\overline{A}$$ is also in RE. Since both $$A$$ and $$\overline{A}$$ are in RE, it follows that $$A$$ is in R (this follows from a theorem you learned in class).

Here $$\le_m$$ demotes mapping reducibility.

Actually I can't understand most of the answer. In particular:

1. Why does $$A \leq_m \overline{A}$$ imply $$\overline{A} \leq_m A$$?
2. I understand the following step (why $$\overline{A}$$ is in RE).
3. Which theorem is used to deduce that $$A$$ is in R? (I'm not a student in this class)

1. It follows immediately from the definition of a mapping reduction that a reduction $$f$$ from $$A$$ to $$B$$ is also a reduction from $$\overline{A}$$ to $$\overline{B}$$. Indeed, if $$f$$ is a reduction from $$A$$ to $$B$$, then, in particular, $$x\in A$$ iff $$f(x)\in B$$, which is equivalent to $$x\notin A$$ iff $$f(x)\notin B$$, which is equivalent to $$x\in \overline{A}$$ iff $$f(x) \in \overline{B}$$. (I only used the fact that $$x \to y$$ is equivalent to $$\neg y \to \neg x$$).

2. This follows form the reduction theorem: if $$A \leq _m B$$, then $$B \in RE \to A\in RE$$. Try to prove it. Hint: use a machine that computes the reduction, and a machine that recognizes $$B$$ in order to define a machine that recognizes $$A$$.

3. To deduce that $$A \in R$$, they've used the fact that $$R \supseteq RE\cap coRE$$ (In fact, equality holds). Hint: If $$M_{A}$$ and $$M_{\overline{A}}$$ are machines that recognize $$A$$ and $$\overline{A}$$, respectively, then you know that for every word $$w$$, at least one of $$M_{A}$$ and $$M_{\overline{A}}$$ halts on $$w$$.

• I think OP understands step 2. They don't understand step 3. – Yuval Filmus Jan 8 at 12:51
The answer to the first question is quite simple. Suppose that $$f$$ is a mapping reduction from $$A$$ to $$\overline{A}$$. Then $$f$$ itself is also a mapping reduction from $$\overline{A}$$ to $$A$$. I'll let you verify that.
Next, let us show that if $$A,\overline{A}$$ are both RE, then $$A$$ is in R. How to show that depends on your definition of RE.
• RE is the set of all languages which can be enumerated. Suppose that we can enumerate both $$A$$ and $$\overline{A}$$. Given a word $$w$$, here is how to decide whether $$w \in A$$ or not. Simply run both enumerators in parallel, until $$w$$ shows up. If it shows up in the enumeration of $$A$$, then $$w \in A$$, and if it shows up in the enumeration of $$\overline{A}$$, then $$w \in \overline{A}$$.
• RE is the set of all recognizable languages, that is, there is a Turing machine which halts on an input iff it belongs to the language. Suppose that there are recognizers for both $$A$$ and $$\overline{A}$$. Given a word $$w$$, run both recognizers, until one of them halts. If the recognizer for $$A$$ halted, then $$w \in A$$, and if the recognizer for $$\overline{A}$$ halted, then $$w \in \overline{A}$$.