Counting the Real Numbers

If we are in a room full of ballroom dancers where each male dancer has a female dancer partner, and no one is left without a partner, we can say that there are as many male as female dancers in the room even without counting. In mathematics, we say that there is a one-to-one correspondence between the set of male dancers and the set of female dancers.

Pairing Infinite Sets

In the A Glimpse at Infinite Sets, we have learned that if we can pair two sets in one-to-one correspondence, we can say that the two sets have the same number of elements. The number of elements of a set is its cardinality. Therefore, the cardinality of the binary numbers {1,0} is 2 and the cardinality of the set of the vowel letters in the English alphabet {a, e, i, o, u} is 5.

The pairing of sets can be extended to compare sets with infinite number of elements or infinite sets.  In Figure 1, it is clear that it is possible to pair the set of integers with the set of counting numbers in one-to-one correspondence (can you see why?).  Infinite sets whose elements can be paired with the set of counting numbers in one-to-one correspondence is said to be countably infinite.

As a consequence of the analogy above, we can conclude the cardinality of counting numbers is equal to the cardinality of integers (Can you see why?). It also follows that the set of integers, the set of rational numbers, the set of negative integers, the set of non-negative integers are all countably infinite sets. What is surprising is that all of them have the same cardinality (see the related post mentioned above for details).

Countably and Uncountably Infinite Sets

In the following discussion, we show that the set of positive real numbers is not countably infinite; that is, we cannot pair all of its elements in one-to-one correspondence with the set of counting numbers. We also show that if we pair all the positive real numbers with the set of counting numbers, there will always be some real numbers left unpaired.

In pairing the two sets, we only show that the cardinality of real numbers from 0 to 1 is greater than the cardinality of the set of counting numbers. It is clear that this proof is sufficient to show that the cardinality of real numbers is greater than that of the cardinality of counting numbers.  The argument is as follows.

Assuming that we have listed and paired all the real numbers between 0 and 1 with the set of counting numbers, then our list looks like Figure 2, where the counting numbers are on the left hand side and the real numbers are on the right hand side.  Although the real numbers on the list below are not ordered, we assume that all of them are listed.  Since it is impossible to write all the real numbers, we have used the … symbol to denote that there are infinitely many pairs of numbers following the fifth pair.  Furthermore, we assume that all the real numbers on the list are have non-terminating digits. This is possible because we can always put a string of infinitely many 0’s in every terminating decimal to make the digits non-terminating.  In fact, we can also use the fact that 1 = 0.999… to convert a terminating decimal into a non-terminating decimal. Hence, the number 0.12 can be represented as 0.12000… (with non-terminating zeros) or 0.11999… (with non-terminating nines).

Now, how do we construct a number not on the list? Well, it’s not that hard.

First, we name the n^th digit of the n^th real number (that is the first digit of the first real number, second digit of the second real number, and so on) diagonal numbers (see the colored digits). For brevity’s sake, let , , and be the first, second and third diagonal numbers respectively. In general, we will call the nth diagonal number .

To create a decimal number not on the list, we make the first digit of our new decimal number not equal to (we choose any number not equal to 1), the second digit of our new decimal number not equal to (we choose any number not equal to4), the third digit of our new decimal number not equal to (we choose any number not equal to 3) and so on. If we let , , be the first three decimal digits of our new number, the following conditions must be satisfied: , , , and so on. In general, for all , we have to be sure that .

With the conditions above, we are sure that

is not on the list. As we can observe below, if we pair 0.85863… with any of the real numbers, at least one digit in the same place value (see the digits with similar colors) are not equal. Therefore, we are sure that 0.85863… is not equal to any of the numbers on the list. However, this contradicts our assumption that we have listed all the real numbers from 0 to 1.

Therefore, it must be the case that we cannot pair the set of real number from 0 to 1 to the set of counting numbers.  Therefore, the cardinality of the set of real numbers is greater than that of the cardinality of counting numbers.

You have probably noticed that the proof above is somewhat similar to the proof of the infinitude of primes.

Conclusion

From above, we can also conclude the following:

1. The cardinality of the set of real numbers from 0 to 1 is greater than the cardinality of the set of counting numbers.
2. The set of real numbers from 0 to 1 cannot be paired with the set of counting numbers, and is therefore uncountably infinite. This implies that the set of real numbers is uncountably infinite.
3. We have at least two types of infinity.  The set of counting numbers is infinite, but the set of real numbers is also infinite. The latter however has a larger cardinality.

In higher mathematics, we call the cardinality of counting numbers (aleph null) and we call the cardinality of real numbers .

The question that is probably worth asking is, are there other types of infinity? Well, we do not know yet.  Until now, it has been a big question if other infinities exist.  In fact, it’s one of the hardest problems in modern mathematics. George Cantor, the pioneer of set theory, hypothesized that

There is no set whose cardinality is strictly between that of the integers and that of the real numbers.

His hypothesis is now know as thecontinuum hypothesis.It was included as one of Hilbert’s 23 famous problems.

The proof above is a modified version of Cantor’s diagonalization system or Cantor’s diagonal argument.