Find an infinite recognizable not decidable subset of an infinite decidable language

If $$L$$ is an infinite ($$|L|=|\mathbb{N}|$$) decidable language, prove that it contains:
a) An infinite subset that is not recognizable.
b) An infinite subset that is recognizable and not decidable.

For the (a) I considered all the subsets of $$L$$, i.e., $$\mathbb{P}(L)$$. Since $$|\mathbb{P} (L)| = |\mathbb{R}|$$, there exists $$A \subset L$$ that is not recognizable (for there are not enough Turing machines to recognize them all). If $$A$$ were finite, it would be decidable and hence recognizable, which would be a contradiction. Therefore $$A$$ is infinite and not recognizable.

For (b) I thought about $$B=L\setminus A$$. Then $$B$$ is recognizable because $$A$$ is not. But I'm not really sure.

• If you’re not sure, try proving it. Oct 28, 2020 at 6:13

Let $$K$$ be the set of indices of Turing machines which halt on the empty input. Consider the following language:

$$X = \{ 0 w : |w| \in K \} \cup \{ 1 w : |w| \notin K \}.$$

You can check that neither $$X$$ nor its complement are recognizable.

Therefore your proof idea doesn't work. Here is a different idea. Let $$w_1,w_2,w_3,\ldots$$ be the words in $$L$$, enumerated according length and then lexicographically (so if $$L = \Sigma^*$$, the order would be $$\epsilon,0,1,00,01,10,11,\ldots$$). The language

$$Y = \{ w_i : i \in K \}$$

is recognizable but not decidable.

• But I don't understand how are you defining Y Oct 28, 2020 at 23:17
• Does it contain all the words whose indices correspond to a Turing machine which halts on the empty input? Oct 28, 2020 at 23:19