# Is complement of diagonal language countable? [duplicate]

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?

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

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.
• @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\,$! :-) – David Richerby Dec 14 '16 at 15:22