Uncountable Sets


Our first example dealt with a "small" infinite set. This suggests that there are big infinite sets, too. It's easy to give an example of such a set:

Example 2

The interval [0,1] (in R) is an uncountable set.

We're going to take a cue from our first example and consider infinite strings of 0's and 1's. In this case, we make use of the fact that each element of [0,1] can be written as a binary decimal. That is, a number of the form

More generally, each in [0,1] can be written as

where each is either 0 or 1. Here are a couple of easy examples:

(How would you check the second example?)

Now just like ordinary decimals, a given number may have more than one binary decimal representation. For instance,

But this minor inconvenience won't effect our arguments here. In order to be precise, let's agree to always take the representation ending in an (infinite) string of repeating 1's whenever there's a choice.

The point here is that the elements of [0,1] can be thought of as infinite length strings (or sequences) of 0's and 1's. The claim here is that the collection of all infinite sequences of 0's and 1's cannot be counted.


Neal Carothers - carother@bgnet.bgsu.edu