2
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Apr 12 '16 at 10:44
  • $\begingroup$ 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 $\endgroup$ – user2619645 Apr 12 '16 at 10:46
  • 2
    $\begingroup$ I thought all languages over finite alphabet were countable... Aren't they? $\endgroup$ – Igor Shinkar Apr 12 '16 at 11:01
7
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Ah thank you, so there are no non-recursive languages that are uncountable. Your proof about enumerating the words in the language in order of increasing length makes sense and solidifies this claim. $\endgroup$ – user2619645 Apr 12 '16 at 12:26
2
$\begingroup$

Per your comment, you say a language is a collection of words of finite length. So you can encode each word as a natural number (for example interpret is as an integer in base size-of-your-alphabet). As you've just assigned a number to each element of your set, your set is countable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.