Proving that there exists a Recursively Enumerable language that has a special property

Question

1. In an assignment about mapping reductions, we're required to prove the following claim: Prove that there exists $L_2\notin RE$ such that $\overline L_2 \leq_m L_2$. We also got the following guidance: Consider "tweaking" some well known undecidable language. I got the feeling that the language we need to tweak is $REG_{TM}$, but i got stuck in the way.

2. Also: I was wondering the following thing: we have shown that $REG_{TM}\in\overline {RE\cup coRE}$, and that $\overline {REG_{TM}}\notin RE$. Doesn't this mean that also $\overline {REG_{TM}}\notin coRE$ because its complement is not in RE? If so, where exactly is the language $\overline {REG_{TM}}$?

Answer 1

1. Let $L$ be any non-RE subset of $\mathbb N$. Than we can construct $L_2 = 2\cdot L \cup (2 \cdot \overline{L} + 1)$ (element-wise addition and multiplication) - $2k \in L_2 \leftrightarrow k \in L$ and $2k + 1 \in L_2 \leftrightarrow k \notin L$.

We have $2k \in L_2 \leftrightarrow 2k + 1 \notin L_2$, so $\overline{L_2} \leq_m L_2$ (just take function $f(2k) = 2k + 1$, $f(2k + 1) = 2k$).

At other hand, $L \leq_m L_2$ (just take function $f(k) = 2k$), so $L_2 \notin RE$.

(formally here we speak about subsets of $\mathbb N$ instead of languages, but transition is straightforward)

2. Yes, $\overline{REG_{TM}} \notin coRE$. This language is obviously $\Pi_3^0$ (see arithmeical hierarchy), though: $T \notin REG_{TM} \leftrightarrow \forall \text{DFA} \exists \text{word} \forall \text{protocol}$: $\text{protocol}$ either isn't correct for $T$ on $\text{word}$, or it doesn't agree with $\text{DFA}$.

(may be it's even in some lower position of hierarchy, but I can neither prove nor disprove it)