Does every infinite recursive language contain a non-recursive RE subset?

Question

Let $L \in R$ be an infinite recursive language. Is it always possible to find a subset $L' \subseteq L$ such that $L' \in \mathbb{RE} \setminus R$?
In other words, can every infinite decidable language contain a subset that is recursively enumerable but undecidable?

I'm interested in both a general proof and any construction ideas or examples of such a subset $L'$.

Answer 1

As $L$ is infinite and is a subset of words, namely $L\subseteq \Sigma_L^*$ for some finite alphabet $\Sigma_L$, then $|L| = \aleph_0$. Therefore, you can encode the Halting-problem using words in $L$. More formally, let $A$ be an alphabet encoding the Halting-problem. Thus, the Halting-problem $HP_A$ is a subset of $A^*$. Next, as $L$ is decidable, then there is a Turing machine $M_{A^* \to L}$ that computes a bijection $\eta: A^* \to L$. Indeed, given input $x$ for $M_{A^* \to L}$, the machine $M_{A^* \to L}$ can go over all the words in $\Sigma^*_L$ in min-lex order (we order first according to length, and then lexicographically), and compute the word in $L$ corresponding to $x$ according to a min-lex order on $A^*$. Note that the latter can be done as $L$ is decidable, so eventually $M_{A^* \to L}$ finds the word in $L$ corresponding to $x$. Specifically, if $x$ is the $i$’th word in $A^*$ according to the min-lex order on $A^*$, then $\eta(x)$ is the $i$’th word in $L$ according to the min-lex order on $\Sigma^*_L$.

Now consider the language $HP_L = \{ y: \eta^{-1}(y) \in HP_A \} \subseteq L \subseteq \Sigma_L^*$. It is not hard to see that $M_{A^* \to L} $ computes a mapping reduction from $HP_A$ to $HP_L$, and thus $HP_L$ is not decidable. On the other hand, $HP_L$ is in $\text{RE}$ because given any word $y$ over $\Sigma_L$, we can first check if $y \in L$ (since $L$ is decidable), and then check whether $\eta^{-1}(y)\in HP_A$ by first computing $\eta^{-1}(y)$ (similarly to how $M_{A^* \to L}$ works) and then simulate a machine that recognizes $HP_A$ on $\eta^{-1}(y)$.

• csmathstudent8: Thanks for the answer, unfortunately I haven't learnt some of the symbols you used here, suppose I'm attending the first computability course, is there a simpler proof ?
• Ainsley H.: @csmathstudent8 Intuitively, the point is that as long as you have an infinite list of numbers, you can "pretend" that these numbers are $\mathbb N = \{1, 2, 3, ...\},ドル because there must be a bijective function $\eta$ (eta) from $L$ to $\mathbb N$. But then you can take your favorite undecidable problem, e.g. HALT, and "remap" the values using $\eta$.
• Bader Abu Radi: @csmathstudent8 The underlying idea is shown in the comment above. If there are questions about some notations, you are welcome to ask. I am not sure if there is a much simpler proof in terms of used symbols.
• csmathstudent8: I understood now the recap you wrote above, but yes I guess it's currently above my course requirements.