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.

  • $\begingroup$ can you explain what it means it to be a number in base $|\Sigma|+1$ ? $\endgroup$ – revisingcomplexity Apr 30 '15 at 18:45
  • $\begingroup$ what about 0#0#0, would that be mapped to the same integer of 0#0? $\endgroup$ – revisingcomplexity Apr 30 '15 at 18:59
  • $\begingroup$ @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$. $\endgroup$ – David Richerby Apr 30 '15 at 19:48
  • $\begingroup$ Sorry, I am still a bit confuse, to what natural number would #0#0 map? what about #0#0#0? $\endgroup$ – revisingcomplexity Apr 30 '15 at 20:52
  • $\begingroup$ If your alphabet is $\{0,1\}$ then $\#0\#0$ would map to 2020 in base 3, which is 60 decimal; $\#0\#0\#0$ would map to 202020 in base 3, which is 546 decimal. But why do you care about those two strings? They're not produced by my coding. $\endgroup$ – David Richerby Apr 30 '15 at 20:56

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}$.

  • $\begingroup$ 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. $\endgroup$ – David Richerby May 1 '15 at 11:09
  • $\begingroup$ @david-richerby You're welcome. $\endgroup$ – J.-E. Pin May 1 '15 at 12:02
  • $\begingroup$ Does that $|\Sigma|$ contain $#$ already? $\endgroup$ – revisingcomplexity May 5 '15 at 22:58
  • $\begingroup$ There is no $#$ in $A$ in my answer. $\endgroup$ – J.-E. Pin May 5 '15 at 23:02

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.