-1

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 ?

Carl Mummert
  • 81,604
Out Of Bounds
  • 1,531

1 Answers1

2

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$.

JDH
  • 44,236
  • What do you mean by "strings in a nontrivial signature" ? – Out Of Bounds Nov 09 '14 at 03:23
  • The signature is the set of symbols used to make the strings --- you might call it the "alphabet" of the language. A string is a finite sequence of symbols. A language is a set of strings. Basically, my first counterexample is to let $L$ be everything. This is decidable, but there are undecidable $L'\subset L$. – JDH Nov 09 '14 at 03:24
  • This is an insignificant point, but even when the signature has only has one symbol there are still uncountably many languages. – Carl Mummert Nov 09 '14 at 03:26
  • @CarlMummert Yes, you are right! I added that in, thinking of $2^\omega$, but I don't need it, and so I edited it back out. – JDH Nov 09 '14 at 03:27