FA18:Lecture 9 countability
Examples of uncountable sets
To use diagonalization to prove that a set is uncountable, you typically do a proof by contradiction: assume that 'is' countable, so that there is a surjection , and then find a contradiction by constructing a diabolical object that is not in the image of . This contradicts the surjectivity of , completing the proof.
To construct infinite) table describing : the row describes . In the table, you represent each element of as an infinite sequence of values; so that the table has a column for each natural number. The exact structure of the table depends on the set ., you typically imagine an (
The set of subsets of the natural numbers
|2||the set of even numbers|
|3||the set of odd numbers|
|2||the set of even numbers||yes||no||(yes)||no||yes|
|3||the set of odd numbers||no||yes||no||(yes)||no|
Now, we construct a new diabolical set by changing each element on the diagonal. In this example, we have a "yes" in the 0th column of row 0 (meaning , so in our diabolical set we put a "no" in column 0 (by ensuring . Similarly, we have a "no" in row 1, column 1 (so ), so we put a "yes" in column 1 of (by placing ). Continuing in this fashion, we have
In general, we include if and only if . We can write this succinctly by defining . Note that although we used a specific example to figure out how to construct , this construction will work for an arbitrary .
Now, cannot be in the image of , because for any , differs from in the th column. If then , and if then . in either case, . Thus cannot be surjective, a contradiction.
The set of real numbers
We can put the real numbers into a common format by listing out their digits:
Now, cannot be in the image of , because for any , differs from in the th digit. This contradicts the fact that is surjective, completing the proof.
We construct a new diabolical number by changing each digit on the diagonal. We can add 5 to each digit (wrapping around if necessary) to set the corresponding digit of . In example table above, we would have .