# Find an undecidable language that is mapping-reducible to its complement

As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

Try the following construction. Given a language $L$, use $$\{0x : x \notin L\} \cup \{1x : x \in L\}.$$

• I'm not quite sure what you mean. Can you perhaps expand a little bit on this? – Aden Dong Oct 17 '12 at 2:42
• Consider all possible words. Prefix those which belong to $L$ by $1$, those that don't by $0$. This may be relevant to your question. – Yuval Filmus Oct 17 '12 at 4:52

Another more advanced answer is to look at a complete problem from a class that is closed under complement. For example, take the arithmetical hierarchy which is closed under complements. Now consider a complete problem for it like:

Given: a sentence in the language of first-order arithmetic,
Question: is the sentence true (in the standard model $\mathbb{N}$)?

It is easy that one can reduce this to its complement by negating the sentence.

This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).