Show that every infinite language has a non-regular subset

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.

Hint. An infinite language $\mathcal{L}$ doesn't necessarily contain words of all possible lengths but it must contain words of infinitely many different lengths. You can use this to get a non-regular subset of the original language (in fact, even an undecidable subset). For a sketch of how to continue, mouse-over the yellow region below.


Let the set of lengths of words in $\mathcal{L}$ be $\{\ell_1, \ell_2, \dots\}$ and let $U$ be any undecidable set of natural numbers. The language $\{w\in \mathcal{L}\mid |w| = \ell_u \text{ for some } u\in U\}$ is a sublanguage of $\mathcal{L}$ and is undecidable – so it's certainly not regular.

StackExchange Computer Science Q#33189, answer score: 6