if A is turing-recognizable, and A is mapping reducible to complement of A, A is decidable

Question

Here $<$ denotes mapping reducibility.

Show that if $A$ is Turing-recognizable and $A < A'$, then $A$ is decidable.

How can I prove this? I'm not sure I quite understand how $A < A'$ is possible.

Answer 1

I learned about these same ideas using different notation and terms. While the ideas are the same, my notation might be off. Here is what I got.

By $A \leq_m A'$ then for some computable (halts on every input) function $f:N \rightarrow N$ and any $n\in N$ we have.

$$ n \in A \Longleftrightarrow f(n) \in A'$$

equivalently

$$ n \notin A \Longleftrightarrow f(n) \notin A'$$

Then for any $n \in N$ if we want to see if $n \in A$ then because $A$ is turing recognizable we can do this.

For any $n \in N$ to see if $n \notin A$ then because $f$ is computable we have $f(n) \in N$. Because $A$ is turing recognizable, then we can check if $f(n) \in A$. If $f(n) \in A$ then $f(n) \notin A'$, any by the second iff statement above we have $n \notin A$.

So for any $n \in N$ we can see whether $n \in A$ or $n \notin A$, or that $A$ is decidable.