I came across following facts:
- Set of finite languages over a finite alphabet is countable.
- Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to below fact number 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:
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?
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?