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

Question

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)

Answer 1

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$.

Answer 2

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}$.