I have a problem of Theory of Computation i.e.
Prove that
A set of languages over an alphabet Σ = {0, 1} which does not belong to Recursively Enumerable set, are uncountable.
Anyone can explain it in some simple way?
First note that the entire set of languages over the alphabet {0,1} is already uncountable, as it can be put into 1-1 correspondence with the real numbers between 0 and 1.
To see this, associate a real number between 0 and 1 represented in binary with a set using the following construction. (I use a finite real number for demonstration purposes):
0.00111 -> {"0", "01", "001", "0011", "00111", "001110", "0011100", ...}
Hence, for each real number in the range [0,1), there is a unique corresponding language containing a string of each length.
Okay, that's fine for the entire set of languages over {0,1}, but what about the non-R.E. languages? It suffices to show that the set or R.E. languages is countable. If the R.E. languages are countable, the rest of the languages must be the non-R.E. languages, and those must be uncountable.
To help with this, it suffices to know that the set of Turing machines is countable. We will describe each Turing machine with a finite string showing its states, transition function, etc. Finally, note that each R.E. language is computable by a Turing machine, so that the R.E. languages must therefore be countable.