# Can a non-recognisable language have a recognisable subset?

If $$L\notin$$ RE, can there be a language $$L'\subseteq L$$ such that $$L'\in$$ RE? Or is it necessarily true that $$L'\notin$$ RE for all $$L'\subseteq L$$.

• Consider the empty language. Nov 8 '21 at 6:13
• More generally: whenever faced with a question of the form "is there any language such that" or "are all languages such that", always try the empty language and the universal language (of all strings) first. Nov 8 '21 at 11:00

Take any language $$L\notin RE$$. Now, $$\emptyset \subseteq L$$, and clearly $$\emptyset\in RE$$.
FYI, the converse is also not necessarily true: $$L\subseteq \Sigma^*$$, and $$\Sigma^*\in RE$$.
Yes; as others have said, the empty language $$\varnothing$$ is recognizable, and it's a subset of every language.
For a less trivial example, let $$L$$ be an unrecognizable language. Pick any finite subset of strings $$D$$ from $$L$$. That subset $$D$$ is a recognizable language—in fact, it's a regular language! The algorithm that recognizes it is a lookup table that checks whether the input matches any one of the hard-coded strings from $$D$$.