The Diagonalization Principle
Example 1:Â The set 2NÂ is uncountable
Example 2:Â The set of all real numbers in the interval [0,1] is uncountable.
Example 1:
The set 2NÂ is uncountable
Proof:
Let 2N = {R1, R2, … }is the power set of N, it contains all possible subsets of N. We can represent each subset as a sequence of 0s and 1s, where the ithposition is 1 if i is in the subset, and 0 otherwise.
Let us assume that 2NÂ is countable. This means that there is a bijection between 2NÂ and N, so we can order the elements of 2NÂ accordingly. In the ordered sequence we represent each Rk by means of 0s and 1s. Thus we obtain an infinite table filled with 0s and 1s.
Consider now the reverse diagonal D = { d1,d2,….} of that table. It is a sequence of 0s and 1s, so it corresponds to some set of natural numbers D = {n : dn = 1}
This set obviously is a subset of N, so it should be in the power set of N, and should appear somewhere in the ordered elements of 2NÂ , i