# Infinite languages and undecidable languages

I'm having a problem with proving the following statement:

For every infinite language $L$, does there exists an infinite language $L' \subseteq L$ such that $L'$ is not decidable?

• You are having a problem formulating a proper question. Read the faq, and take a little time and effort. – Dave Clarke May 27 '13 at 20:07
• Try writing the question in the body, not in the title. – Dave Clarke May 27 '13 at 21:04
• And making the title descriptive. – Dave Clarke May 27 '13 at 21:07

The set $\{L' : L' \subseteq L\}$ is an uncountable set of languages, and since there is only countably many decidable languages, it has to contain an undecidable language. (You can get a concrete $L'$ by a diagonal argument.)

Since $L'$ is totally free, you can always define it directly as something undecidable.

For example ordering the words of $L$ with lexicographic order and ordering turing machines (in any order you like) you can define $L'$ as: $L'=\{w_i|w_i\text{ ith word in$L$and$M_i$stop on }\epsilon\}$.

If $L'$ is decidable then termination with empty tape of Turing machine is decidable. Contradiction.

Hence $L'\subseteq L$ and $L'$ is undecidable.

Note I assumed $L$ decidable. If $L$ is already undecidable then take $L'=L$.

• I'm afraid this will not work in general - only if $L$ is decidable. $L$ could be a weird undecidable language such that if you filter it to get $L'$, it will become decidable. Here's a sketch of an example. Assume that naturals include 0 (we start indexing from 0), and that the ordering of TMs is such that every $M_{2i}$ stops on $\varepsilon$, which can be done. Suppose that indices of halting machines are 0,1,2,4,6,8,9,10,11,12,13..., and assume $L$ contains $a^0,a^2,a^4,a^5,a^6,a^7,a^8,a^9,a^{10},a^{12},a^{14},a^{16},a^{18},a^{20}...$. – sdcvvc May 27 '13 at 22:35
• Then 0-th element of $L'$ is $a^0$, 1-st element is $a^2$, 2-nd is $a^4$, 3-rd is $a^6$, 4-th is $a^8$ etc. This pattern can be continued. So $L'$ is $a^{2n}$ which is decidable. – sdcvvc May 27 '13 at 22:36
• Thanks @sdcvvc I edited the answer to take in account your comment. – wece May 28 '13 at 12:20
• If $L$ has to be decidable, you don't answer the question. – Raphael May 28 '13 at 17:46
• @Raphael if $L$ is undecidable $L'=L$ trivially answer the question doesn't it? – wece May 28 '13 at 21:19