1,069 views

1 Answer

1 votes
1 votes

We are trying to prove that the set of languages is uncountable. So, first we assume it as countable. We define a matrix 

  1. a row represent a language
  2. a column represent either $0$ or $1$ meaning string represented by that column is in $L$.

So, the matrix is infinite in both row as well as column. 

Now, if the set of languages are countable all languages must be present here. But this is not true and to show why, we define a new language by taking the diagonal entries of the matrix and complementing them. This complementing ensures that at least for one string (the diagonal string for each language) our new language will be different from every other language in the matrix, making it necessarily a new language. And that's all we want. 

Related questions

1 votes
1 votes
1 answer
1
Parimal Paritosh asked Jul 31, 2018
307 views
How is the set of all DFA countably infinite?I understand that TM has a binary encoding, thus it is possible to have a configuration for every TM, thus it is countably in...