# Is there a non-recursive and uncountable language L?

Does there exist a non-recursive language, L, such that the cardinality of L is uncountable?

I would really like an explanation as to why this question is true or false because at the moment, I have no idea. My understanding is that all recursive languages have to be countable since the set of all finite strings is countable. But I'm not sure if there is a non-recursive language which is uncountable. Any help would be greatly appreciated,

• Well, if there is any uncountable language it's clearly non-recursive, as you argue. So the question is, what definition of "language" do you assume?
– Raphael
Apr 12 '16 at 10:44
• Thanks for responding quickly, The definition of language I am using is that it is a collection of words and each word is a finite string Apr 12 '16 at 10:46
• I thought all languages over finite alphabet were countable... Aren't they? Apr 12 '16 at 11:01

Definition: a word over an alphabet $A$ is a finite sequence of elements of $A$.
Definition: a language over an alphabet $A$ is a set of words over $A$.
With these definitions, if $A$ is a finite set, then any language is countable (either finite, or countably infinite). This is because any language is a subset of the complete language $A^*$ (set of words over $A$).
Direct proof sketch: you can enumerate all the words in the language, in order of increasing length (and in lexicographic order for each given length, having defined an order of $A$). This process is well-defined because set of words of a given length is finite. This process assigns an index to all the words in the language because all words have a finite length.
Follow-up exercise: if $A$ is countably infinite then a language over $A$ is countable. Adapt the proof above (change the enumeration order to cover the whole language in finite batches).