1.4 Countable Sets (A diversion)

A set is said to be countable, if you can make a list of its members. By a list we mean that you can find a first member, a second one, and so on, and eventually assign to each member an integer of its own, perhaps going on forever.

The natural numbers are themselves countable- you can assign each integer to itself. The set \(Z\) of integers is countable- make the odd entries of your list the positive integers, and the even entries the rest, with the even and odd entries ordered from smallest magnitude up. Here is how this particular sequence of numbers begins:

\[1, 0, 2, -1, 3, -2, 4, -3, ...\]

(If a set is countable you can list it in lots of ways.)

The positive rational numbers, are also countable , and here is why. Take first all those whose numerator and denominator sum to \(1\), then \(2\) then \(3\), and so on. When several do so, order them by size. Here is how this list begins. \(\frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}\), and so on. Every positive rational number appears on this list somewhere, and actually appears often on it. (This happens because \(\frac{1}{2}\) appears as \(\frac{1}{2}\) and also as \(\frac{2}{4}\) and \(\frac{3}{6}\) and so on. ) But all fractions eventually appear, and appear over and over again.

The number of positive and negative rational numbers are also countable, and we can list all together by taking alternatively from lists of each separately as done above for integers.

\[\frac{0}{1}, \frac{1}{1}, \frac{-1}{1}, \frac{1}{2}\]

Rational numbers are described by pairs of integers, and the arguments above generalize to imply that any collection of pairs of members of a countable set are countable. And this can be generalized to the statement that a countable set of countable sets is countable.

It follows then that algebraic numbers , which are all solutions to polynomial equations of finite degree with integer coefficients are countable. There are a countable number of finite degrees, and a countable number of sets of coefficients for each degree and a countable number of solutions for each equation, and so the algebraic numbers of countable sets of countable sets of countable sets, which is still countable.

On the other hand, the set of all decimal expansions is not countable.

How come?

Well, if we had a list of all decimal expansions, we could easily construct a number that cannot be on it. Just make its entry \(j\) places beyond the decimal point differ by \(2\) from the entry in that place of the number that is \(j^{th}\) on your list . Then the number we create differs from every number on your list and therefore cannot be on it. All of this means that we cannot list all the real numbers or decimal expansions!

Neither you nor I could actually do the infinite number of acts necessary to construct such a number, but we can imagine it done.

To visualize this imagine the first three numbers on your list were

\(.101010*\)

\(.314720*\)

\(.71324*\)

A number not on the list by the construction given would start by \(.335\) since this sequence differs from the first number by \(2\) in the first place, differs from the second number by \(2\) in the second place and from the third member by 2 in the third place. The number we ultimately get will definitely differ from the three numbers above. With the rest of its digits similarly determined in reference to the next numbers in sequence on the list, we can deduce that this number cannot be on the list anywhere, so long as the number of its digits is the same as the length of the list.

This means that the set of all decimal expansions cannot possibly be listed. The decimal expansions are uncountable.

Are decimal expansions the same as real numbers?

Actually every real number between 0 and 1 has a decimal expansion, but some, namely those rational numbers that end with all \(0\)’s, appear twice as decimal expansions. The reason is that \(0.99999...\) is really the same as \(1.00000\). Since these are a subset of the rational numbers, this difference is of no particular importance.

Exercise: Subtract \(.9*\) from \(1.0*\). What do you get ? If the \(9\)'s stopped somewhere, you could subtract and get a \(1\) in the next place and \(0\)'s everywhere else. But what happens when the \(9\)'s never stop?