# 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

## 1 Answer

Languages are collections of words. Words are finite strings.

As Shaull stated in his comment, every language over a finite alphabet is countable. (In fact, every language over a countable alphabet is also countable.)

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.

• How do we prove this though? – revisingcomplexity Apr 29 '15 at 17:50
• what about the language that halts if the first number in a binary number is a 1? – revisingcomplexity Apr 29 '15 at 17:59
• @revisingcomplexity Shauli gives the proof, assuming that you accept that $|A| \leq |B|$ if $A \subseteq B$. – Raphael Apr 29 '15 at 18:02
• Languages are collections of words. Words are finite strings. The input is always finite. That's how languages are defined in the context of computability. Deal with it. – Yuval Filmus Apr 29 '15 at 18:11
• @YuvalFilmus, That was the biggest gap in our knowledge that made us misunderstood most of the concept. Me and other students revising together are really, thankful for your explanation. THANK YOU! – revisingcomplexity Apr 29 '15 at 18:17