# Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

I came across following facts:

1. Set of finite languages over a finite alphabet is countable.
2. Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to below fact number 3.
3. Set of languages over {0,1} is uncountable.

I came across proof of fact 1 here and of fact 3 here.

Summary of fact 1 proof:

Let your finite alphabet be $$Σ={a_1,…,a_ℓ}$$ and let $$\#$$ be some character not in $$Σ$$. Let $$L={w_1,…,w_n}$$ be a finite language over $$Σ$$. Then the string $$\#w_1\#w_2\#…\#w_n$$ maps different $$L$$ to different integer.

Summary of fact 3 proof:

Let $$L$$ be set of all finite length strings over $$\{0,1\}$$. We can generate a one-to-one mapping from $$L$$ to $$\mathbb{N}$$ : just add a 1 in front of each string in W and interpret the resulting strings as binary numbers. So $$L$$ is countable. Now let $$L_{\{0,1\}}$$ is countable, where $$L\{0,1\}=\{L_1,L_2,L_3,…\}$$ with each $$L_i$$ being a language over $$\{0,1\}$$. Given that each $$L_i$$ is a set whose elements are strings from $$L$$, and since $$L$$ is countable, we can build a table whose row indices are language indices and whose column indices are string indices as follows: for each table cell with row index $$i$$ and column index $$j$$, write 1 if the language $$L_i$$ contains the string $$s_j$$ or 0 otherwise.

We flip the value of every diagonal cell on the table above, then collect all strings $$s_j$$ such that the diagonal cell on the column of $$s_j$$ has a 1 after flipping:
Lets call it $$L_{diag}={s_2,s_3,...}$$.
$$L_{diag}$$ is a language with a special property: it is different from every language $$L_i∈L_{\{0,1\}}$$. This implies $$L_{diag}≠L_i$$ for all $$L_i∈L$${{0,1}} and therefore $$L_{diag}∉L_{\{0,1\}}$$. However, since $$L$$ is a set of strings which are in $$L$$, $$L_{diag}$$ is a language over {0,1} and therefore $$L_{diag}∈L_{\{0,1\}}$$, a contradiction. Hence $$L_{\{0,1\}}$$ cannot be countable.

Doubts

I get both the proofs, but I dont get why approaches followed in each of them cannot be used to prove other fact incorrect. That is:

1. Why I cant use fact 1 proof approach to prove fact 3 is incorrect, that is "set of languages over {0,1} is countable". Cant I form similar string string $$\#w_1\#w_2\#…\#w_n$$ for different languages to map them to different integers?

2. Why I cant use fact 3 proof approach to prove fact 1 is incorrect, that is "set of finite languages over a finite alphabet is uncountable"?

Cant I form similar table for finite languages and then form $$L_{diag}$$ which wont belong to the set of finite languages?

1. If the language is infinite, the word $$\# w_1 \# w_2 \ldots$$ would be infinite, and so doesn't map to an integer in any meaningful way.
• I didnt get 2nd point well. Isnt $L_{diag}$ (in given proof of fact 3) infinite? If yes, then how will it matter if $L_{diag}$ turns out to be infinite when we prepare similar proof for fact 1? I feel as long as $s_1,s_2,s_3,s_4,...$ are different in $L_{diag}$ it will not be part of $L_{\{0,1\}}$ making $L_{\{0,1\}}$ uncountable, regardless of $L_{diag}$ is finite or infinite. Is this wrong? – anir Dec 1 '19 at 19:21
• In order to show that a set $S$ isn't countable, you assume it is, and then find some $x \in S$ not in your list. In your case, $S$ is the set of finite language, so $x$ has to be finite. Otherwise there is no contradiction. – Yuval Filmus Dec 1 '19 at 19:27
• Ohh, so you mean to say $L_{diag}$ is infinite and $L_{\{0,1\}}$ is set of finite languages, so it does not makes sense to say $L_{diag}\notin L_{\{0,1\}}$ and hence diagonalization approach does not work here? – anir Dec 1 '19 at 19:40