Countable Sets

A bit of binary arithmetic, will show you how this list is generated. If we consider each string as a binary, or base 2, number, then we may easily determine its value as a base 10 number. For example,

More generally, the string , where each of the 's is either a 0 or a 1, is the base 2 representation of the base 10 number

Now we simply list the strings of 0's and 1's, first by increasing length, and then by increasing value of the strings of a given length.

Suppose, for example, that we're handed the string 1010. How do we determine where this string appears on the list (without actually writing out the entire list until we find it)?

Well, since 1010 is a string of length 4, we know that there are

strings of length 1, 2, and 3 ahead of it. Next, if we treat this string as a binary number, then the value of this string will tell us where it appears among the strings of length 4. In this case, 1010 (base 2) = 10, and there are 10 entries in the strings of length 4 smaller than 1010 (notice that each "sublist" starts with a string of all 0's). Thus, 1010 appears as the 11th entry among the strings of length 4, and as entry 14 + 10 +1 = 25 on our "big list".

It's possible to give a general formula for the position of a given string of 0's and 1's on the list.

Conversely, if we're given an entry number, we can easily tell which string sits at that position without actually writing out all the entries. For example, how could we determine which string lives at position 47 on the list?

First we determine the length of the string at entry 47. Since we know that

and

it follows that entry 47 must be a string of length 5, and that it occurs as entry number among the strings of length 5.

Since the strings of length 5 are listed according to their value, beginning with 00000, our final step is to convert to a binary string of length 5. Since, 01000 is the base 2 representation for 16, we know that entry number 47 must be 01000.

Again, it's possible to give a general formula for the binary string that resides at a given position on the list.

The conclusion to be drawn from all of this is that we have displayed the collection of all finite length strings of 0's and 1's as a "numbered list". In other words, we've counted the elements of the set! For obvious reasons, any set that can be so enumerated is called a countable set. (A countable, infinite set is sometimes called countably infinite to distinguish it from finite sets.)

An infinite yet countable set is a "small" infinite set. Our second example concerns a bigger variety of infinite set, an uncountable set.