# Proving the set of finite languages is countable without using the union of countable sets

The list of finite languages over a finite alphabet is countable.

I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I can prove that the infinite union of countable set is countable.

However, I am sure that there is a simpler proof. Can someone help?

In my example $|\Sigma=\{0,1\}|$

Let your finite alphabet be $\Sigma = \{a_1, \dots, a_\ell\}$ and let $\#$ be some character not in $\Sigma$. Let $L=\{w_1, \dots, w_n\}$ be a finite language over $\Sigma$. You can consider the string $\#w_1\#w_2\#\dots\#w_n$ to be a number in base $|\Sigma|+1$ by associating the symbols $a_1, \dots, a_\ell, \#$ with the base-$(|\Sigma|+1)$ digits $0, \dots, \ell-1, \ell$, respectively (starting the string with $\#$ ensures that the leading digit isn't zero). This gives a map from the set of finite languages over $\Sigma$ to a subset of the integers, so that set of languages is countable.

• can you explain what it means it to be a number in base $|\Sigma|+1$ ? – revisingcomplexity Apr 30 '15 at 18:45
• what about 0#0#0, would that be mapped to the same integer of 0#0? – revisingcomplexity Apr 30 '15 at 18:59
• @revisingcomplexity Does the revised answer make it clearer how the string is a number in base $|\Sigma|+1$? I'm assuming that $w_1, \dots, w_n$ is the list of distinct words in the language, so you couldn't have $\#w_1\#w_2\#w_3=\#0\#0\#0$. – David Richerby Apr 30 '15 at 19:48
• @anir Any finite language of finite strings uses only a finite number of symbols from the alphabet. There are only countably many finite subsets of a countable set. The set of finite languages over any countable alphabet $\Sigma$ is the union over all finite $S\subset\Sigma$ of the set of finite languages over $S$. That's a union of countably many countable sets, so it's countable. (You could probably produce a similar proof to the one in my answer, but I think it's easier to do it this way.) – David Richerby Dec 1 '19 at 18:20
• @anir Comments here aren’t designed for follow up questions and discussion. If you want to know more about countability of sets, I suggest you look up related questions on Mathematics SE and ask a question yourself if they don’t cover what you need. (I’m suggesting Mathematics because your questions are mostly about the fundamentals of countability, and not specific to CS.) – David Richerby Dec 4 '19 at 11:45

Let $A$ be a finite alphabet and let $<$ be a total order on $A$. For instance, if $A = \{a,b,c\}$, let $a < b < c$. Then order the elements of $A^*$ according to the shorlex order: $u \leqslant v$ if either $|u| \leqslant |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$, where $\leqslant_{lex}$ is the usual lexicographic order. For instance, if $A = \{a, b\}$ and $a < b$, you obtain the following sequence of words: $$1, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, \ldots$$ Let $r(u)$ be the rank of a given word $u$ in this sequence. The map $u \to r(u)$ defines a bijection from $A^*$ to $\mathbb{N}$.

Now you want to get an injection from the set $\mathcal{P}_f(A^*)$ of all finite languages on $A^*$ into $\mathbb{N}$. Denote by $p_n$ the $n$-th prime number. Then the map $f: \mathcal{P}_f(A^*) \to \mathbb{N}$ defined, for each $L = \{u_1, ..., u_n\}$, by $$f(L) = p_{r(u_1)}p_{r(u_2)} \dotsm p_{r(u_n)}$$ is injective.

N.B. As you can see, this construction does not use the full power of the prime numbers, and it can be modified to get a bijection from the set $\mathbb{N}\langle A\rangle$ of polynomials over $A$ to $\mathbb{N}$. A polynomial over $A$ (with coefficients in $\mathbb{N}$) can be written as a formal sum, like $$3ab + 2bb + 5bab.$$ Now if $F = k_1u_1 + \dotsm k_nu_n$, where $k_1, \ldots, k_n \in \mathbb{N}$ and $u_1, \ldots, u_n \in A^*$, one extends $f$ by setting $$f(L) = p_{r(u_1)}^{k_1}p_{r(u_2)}^{k_2} \dotsm p_{r(u_n)}^{k_n}$$ and it is now a bijection from $\mathbb{N}\langle A\rangle$ to $\mathbb{N}$.

• Thanks for including a lot of the detail that I skipped in my own answer, and for showing that there are other ways to code these things, too. – David Richerby May 1 '15 at 11:09
• @david-richerby You're welcome. – J.-E. Pin May 1 '15 at 12:02
• Does that $|\Sigma|$ contain $#$ already? – revisingcomplexity May 5 '15 at 22:58
• There is no $#$ in $A$ in my answer. – J.-E. Pin May 5 '15 at 23:02