# Is there any undecidable language that is countable?

All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.

• $\Sigma^*$, the set of all words, is countable. Therefore, every language is countable. It is certainly not the case that every countable language is recognizable. – Shaull Nov 29 '16 at 20:14
• Every language whose alphabet is finite is countable. Check also this answer: cs.stackexchange.com/a/12665/30527. – André Souza Lemos Nov 29 '16 at 21:32
• @AndréSouzaLemos ​ : ​ ​ ​ Even languages with countably-infinite alphabets are countable. ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Nov 29 '16 at 21:52
• @Shaull Make an answer? – Yuval Filmus Dec 1 '16 at 16:15

Your premise is incorrect. The set of all words, $\Sigma^*$, is countable (as long as the alphabet is countable, and we usually refer to finite alphabets anyway).
Every language is a subset of $\Sigma^*$, and thus every language is countable. In particular, there are undecidable and unrecognizable languages.