# Cantor's Diagonalization (Countable Languages)

I'm trying to understand why the set of finite languages over a finite alphabet is countable but the set of languages over a finite alphabet is uncountable. I'm guessing its because the sentences represented by the finite alphabet is infinitely countable and corresponds to a natural number. Thus the set of finite languages over a finite alphabet can be counted by listing them in increasing size (similar to the proof of how the sentences over a finite alphabet are countable). However, if the languages are NOT finite, then I'm assuming Cantor's Diagonalization argument should be used to prove by contradiction that it is uncountable. Am I on the right track? Also, could someone please clear up why Cantor's Diagonalization will not work to contradict the first one but will work to contradict the second one? Is it because in the first one, the languages are finite thus they can be represented by natural numbers so nothing is missed but when they are infinite you can always find a diagonal (flipping the bits) that is not in the list?

Thanks in advance, I thought I understood it completely but I seem to keep fighting the idea of it in my head.

-

Let $\Sigma$ be a finite, non-empty alphabet. $\Sigma^*$, the set of words over $\Sigma$, is then countably infinite. The languages over $\Sigma$ are by definition simply the subsets of $\Sigma^*$.

1. A countably infinite set has countably infinitely many finite subsets, so there are countably infinitely many finite languages over $\Sigma$.

2. A countably infinite set has uncountably many subsets, so there are uncountably many languages over $\Sigma$.

You really don’t have to look at languages per se at all. There is a bijection between $\Sigma^*$ and $\Bbb N$, so just prove that $\Bbb N$, the prototypical countably infinite set, has $\omega$ (or if you prefer $\aleph_0$) finite subsets and uncountably many subsets altogether.

That $\Bbb N$ has uncountably many subsets if easily shown by a form of Cantor’s argument. Suppose that $\{A_0,A_1,\dots\}$ is any countable family of subsets of $\Bbb N$. Now let $S=\{n\in\Bbb N:n\notin A_n\}$. Then for each $n\in\Bbb N$ we have $n\in A_n$ iff $n\notin S$, so $S\ne A_n$. Thus, $\{A_0,A_1,\dots\}$ is not a complete list of the subsets of $\Bbb N$, and $\wp(\Bbb N)$ must be uncountable.

No diagonalization is possible in the case of the finite subsets because we demonstrably can list them all:

$$\begin{array}{c|cc} \text{Row}&\text{Sets}\\ \hline -1&\varnothing\\ &\color{red}{0}\\ 0&\{0\}\\ &\color{red}{1}\\ 1&\{1\}&\{0,1\}\\ &\color{red}{2}&\color{red}{3}\\ 2&\{2\}&\{0,2\}&\{1,2\}&\{0,1,2\}\\ &\color{red}{4}&\color{red}{5}&\color{red}{6}&\color{red}{7}\\ 3&\{3\}&\{0,3\}&\{1,3\}&\{0,1,3\}&\{2,3\}&\{0,2,3\}&\{1,2,3\}&\{0,1,2,3\}\\ &\color{red}{8}&\color{red}{9}&\color{red}{10}&\color{red}{11}&\color{red}{12}&\color{red}{13}&\color{red}{14}&\color{red}{15} \end{array}$$

The organizing principle here is that Row $n$ is obtained by adding the element $n$ to each of the sets in the earlier rows. Thus, all subsets of $\{0,\dots,n\}$ appear in rows $-1,\dots,n$. We can clearly enumerate all of these finite subsets using the numbers in red immediately below them.

-
Nice! I've never seen that argument applied to show the power set of $\mathbb{N}$ is uncountable. It's much cleaner than the characteristic function argument, i.e., identifying each subset of $\mathbb{N}$ with a sequence of $0$'s and $1$'s. –  Patrick Mar 31 '12 at 18:21
I believe you mean that $\{A_0, \ldots\}$ is a countable family of subsets of $\mathbb{N}$, not of $\mathbb{B}$. –  jwodder Mar 31 '12 at 18:27
Thank you so much, that helped clear a few things up. But if I list all the languages in a matrix of binary strings (1 denoting the word is in the language and 0 denoting the word is not in the language), then why wouldn't Cantor's argument hold for finite languages over a finite alphabet as it does for infinite languages over a finite alphabet? I'm just kind of baffled by this, sorry if it's obvious I've just been trying to get a clear understanding of the concept. Thanks again. –  John Long Mar 31 '12 at 18:27
@jwodder: Yep; wrong forefinger triggered. Thanks; fixed. –  Brian M. Scott Mar 31 '12 at 18:30
@John: Because the diagonal language that you get won’t be finite, so there will be no contradiction. –  Brian M. Scott Mar 31 '12 at 18:31