Show that every infinite language has a non-regular subset

Problem Detail: 

I'm trying to solve this problem:

Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular

But can this be correct? If I have the language $\{a\}^*$ for example, that's infinite but you can make a DFA for any sub-language of it, right?

There's a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.

Asked By : Þór Óðinsson

Answered By : muradin

Consider the language $L = \{a^n \mid n \text{ is prime}\}$. $L$ is a subset of $\{a\}^*\!$, which is a regular language but it is not regular so has no DFA.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33189