2
$\begingroup$

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. Blockquote

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: enter image description here
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?

Improve this question
$\endgroup$
1
$\begingroup$

  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.

  2. Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – anir Dec 1 '19 at 19:21
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 1 '19 at 19:27
  • $\begingroup$ 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? $\endgroup$ – anir Dec 1 '19 at 19:40
  • 1
    $\begingroup$ Right, that's exactly the problem. $\endgroup$ – Yuval Filmus Dec 1 '19 at 19:44

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.