# Infinite recognizable not decidable subsets

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) So $$|\mathbb{P} (L)| = |\mathbb{R}|$$ so that means that it exists $$A \subset L$$ that is not recognizable (for there are not enough Turing machines to recognize them all) If A were finite, then it would be decidable so it would be recognizable which would be a contradiction. Therefore A is infinite and not recognizable.

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

• If you’re not sure, try proving it. – Yuval Filmus Oct 28 '20 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 – user719961 Oct 28 '20 at 23:17
• Does it contain all the words whose indices correspond to a Turing machine which halts on the empty input? – user719961 Oct 28 '20 at 23:19