Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct

Question

Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct

I can't figure out this question. Any tips ?

Answer 1

It isn't necessarily true. For a counterexample, take the language $L$ to consist of all strings in a nontrivial signature. This is easily seen to be decidable. But there are some languages $L'$ in the signature that are undecidable, such as the halting problem, and these have $L'\subset L$, making a counterexample.

A different argument shows that the phenomenon is actually pervasive: every infinite language has uncountably many sublanguages, but only countably many of them can be decidable. So every infinite language $L$ has an undecidable sublanguage $L'\subset L$.