# Are all decidable languages mapping reducible to its complement?

I dont think this is true, take the language with a single element L = {0}, then the complement L' would have infinitely many strings (everything that isn't 0). So if it were true that A is mapping reducible to its complement, everything in L' can be obtained via a computable function from some element in L, i.e 010 is in L' however there is no x in L that gives f(x) = 101, since theres only one element, 0, it maps to one result.

Would this be correct?

• Here is a reduction from $L$ to its complement: map $0$ to $1$ and everything else to $0$. – Yuval Filmus Jun 13 '17 at 5:46

Let $L_1,L_2$ be two languages over $\{0,1\}$. A (computable) mapping reduction from $L_1$ to $L_2$ is a computable function $f\colon \{0,1\}^* \to \{0,1\}^*$ such that for all $x \in \{0,1\}^*$ it holds that $x \in L_1$ iff $f(x) \in L_2$.
In your example, $L_1 = \{0\}$ and $L_2 = \overline{\{0\}}$, there does exist a mapping reduction, given by $$f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases}$$ Clearly $f$ is computable, and you can check that $x \in L_1$ iff $f(x) \in L_2$.
Hence your example doesn't work. You can check, however, that $\emptyset$ and $\{0,1\}^*$ are two examples of languages not reducible to their complement. Indeed, these are the only examples, which you can try to prove.