Uncountable Sets


In contrast to our first example, the collection of all infinite sequences of 0's and 1's cannot be "counted" (or displayed as a "numbered list").

To see this, suppose that we are handed any numbered list (even an infinite list!), or sequence of elements from our set. We have to show that such a list cannot account for every element from our set, and so we want to find an element from our set which does not appear on the list.

To this end, consider a "typical" list:

You will notice that I have highlighted certain digits: The first digit of , the second digit of , the third digit of , and so on. We will use these to build a sequence of 0's and 1's that is guaranteed not to occur anywhere on the list.

Specifically, set

= 0.10110... (base 2),

where the th digit of is chosen to be the opposite (or "2's complement") of the th digit of . That is, the first digit of is taken to be 1 because the first digit of is 0, the second digit of is taken to be 0 because the second digit of is 1, and so on.

By design, can't possibly occur anywhere on our list. Why? Well, can't equal because they differ in the first decimal place. And can't equal because they differ in the second decimal place. And ... so on. Cool!

This shows that the collection of all infinite sequences of 0's and 1's cannot be counted. Since we've managed to identify this set with the interval [0,1], this means that [0,1] can't be counted either. In other words, these are examples of uncountable sets.

In conclusion, we've seen that uncountable sets are "more infinite" than countably infinite sets. You might find it entertaining to mull over the following characterizations:

A set is infinite if and only if every finite subset is proper.
A set is uncountable if and only if every countably infinite subset is proper.

Another, even more curious, example of an uncountable set is provided by the Cantor set, the next installment in our saga.


Neal Carothers - carother@bgnet.bgsu.edu