How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable.

I know this theorem - A language is decidable iff both it and its complement are recognizable

How to explain this?

  • $\begingroup$ Surely you mean "if $A$ is recognizable and $A \leq_m \bar{A}$, then $A$ is decidable"? $\endgroup$
    – mrp
    Feb 11 '15 at 17:48

Let us recall some facts.

Definition 1: We write $A \leq_m B$ if there is a computable function $f$ such that for every $w$, $w \in A \iff f(w) \in B$.

Theorem 1: If $A \leq_m B$ and $B$ is recognizable, then $A$ is recognizable.

Theorem 2: A language $A$ is decidable iff $A$ and $\bar{A}$ is recognizable.

Now assume that $A$ is recognizable and $A \leq_m \bar{A}$. Notice that from Definition 1, $w \in A \iff f(w) \in \bar{A}$ also implies that $w \in \bar{A} \iff f(w) \in A$, so $\bar{A} \leq_m A$. Then, from Theorem 1, we can conclude that $\bar{A}$ is recognizable, and therefore we get from Theorem 2 that $A$ is decidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.