patternMinor
Infinite languages and undecidable languages
Viewed 0 times
languagesinfiniteandundecidable
Problem
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?
For every infinite language $L$, does there exists an infinite language $L' \subseteq L$ such that $L'$ is not decidable?
Solution
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.)
Context
StackExchange Computer Science Q#12309, answer score: 7
Revisions (0)
No revisions yet.