5
$\begingroup$

This question already has an answer here:

I tried to find out how to arrange the complement of diagonal language, but I failed. So I'm about to believe that it's not a countable language. Could you, please, help me?

$\endgroup$

marked as duplicate by Raphael Dec 14 '16 at 21:12

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

9
$\begingroup$

A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.

$\endgroup$
  • 1
    $\begingroup$ Strictly speaking, not all languages are defined over finite alphabets. (But still a nice answer to the question that was clearly intended, if not actually asked.) $\endgroup$ – András Salamon Dec 14 '16 at 13:27
  • $\begingroup$ @AndrásSalamon And people also consider languages of infinite strings over finite (or, I guess, infinite) alphabets. $\endgroup$ – David Richerby Dec 14 '16 at 13:47
  • 1
    $\begingroup$ If your alphabet starts with 1, not 0, your leading-zero special cases simply go away (the empty word will be the only one to map to 0). $\endgroup$ – Ulrich Schwarz Dec 14 '16 at 15:19
  • $\begingroup$ @UlrichSchwarz That's a fair point. I guess I chose the encoding I did because $\{0,1\}$ is a very commonly used alphabet and it seems a little weird to associate strings in $\{0,1\}$ with ternary numbers treating $0$ as $1$ and $1$ as $2$. But you could perfectly well argue that it's weird to associate the string $000$ with the binary number $1000\,$! :-) $\endgroup$ – David Richerby Dec 14 '16 at 15:22

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