# Can a recursive language be uncountable?

Does there exist a recursive language $L$ whose cardinality is uncountable?

I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to reject the initial question.

• Over finite words and a finite alphabet $\Sigma$, every language is countable, since $\Sigma^*$ is countable... – Shaull Apr 29 '15 at 17:12
• so you are saying there is no uncountable language that is recursive? – revisingcomplexity Apr 29 '15 at 17:27
• Yes. To be uncountable is, literally, a big deal. – André Souza Lemos Apr 29 '15 at 17:38

Languages of infinite words, sometimes called $\omega$-languages, are considered in computer science. For example, they are the subject of $\omega$-automata theory. But the Turing machine formalism is about the usual notion of language.
• @revisingcomplexity Shauli gives the proof, assuming that you accept that $|A| \leq |B|$ if $A \subseteq B$. – Raphael Apr 29 '15 at 18:02