Countable Sets and Uncountable Sets
Why There are More Real Numbers than There are Natural Numbers
Nov 16, 2009
A countable set, to put it simply, is a set whose elements can be counted. That does not necessarily mean, however, that the number of elements in the set is finite.
For a set to be countable, there must exist a way of putting all its elements into a sequence. That means that there should exist a surjective mapping between the set of natural numbers and the given set. Simply put, there should not be any elements of the set left over after forming the sequence.
A subset of a countable set is also considered countable. Alternatively, a set is countable if there exists a surjective mapping from a subset of the set of natural numbers onto that set. By this definition, all finite sets are countable but not all countable sets are finite. For instance, the set of natural numbers itself is countable, but it is not finite.
Georg Cantor (1845 - 1918) developed the concept of countability and showed that the set of all real numbers has “more” elements than the set of rational numbers.
The Integers and the Rationals are Countable
The set of integers and the set of rational numbers are the most commonly encountered countable sets. The integers can be very easily put into a sequence with alternating positive and negative numbers: 0, 1, -1, 2, -2, 3, -3… Of course, this is not the only way to put the integers into a sequence, but there needs to exist only one such sequence in order to prove that the set is countable.
For the rational numbers, the sequence is not quite as apparent. One way of doing it is to use a matrix [a(i, j)], with i and j each taking natural number values. Using [a(i, j)] = i/j, the matrix is defined, and each rational number, by definition of rational numbers, has a place in the matrix. As a matter of fact, each rational number has multiple places in the matrix, since i/j = 2i/2j = 3i/3j and so on. Traversing each reverse diagonal of the matrix, one by one, gives a sequence which includes each rational number at least once, except 0, which can conveniently be added anywhere in the sequence.
Repetition can be avoided by excluding numbers that are already in the sequence, or it can be ignored, because even if there are repeated elements, the mapping is still surjective.
Real Numbers are Uncountable
This proof works by contradiction. Assuming that the reals are countable, every subset of the set of real numbers must be countable as well. In particular, the set of real numbers between 0 and 1 is countable and can be put into a sequence, t(n). What needs to be proved is that there exists at least one number which is not part of this sequence. This number, say r, can be arrived at in the following way – taking the nth digit of t(n), and choosing a digit different from it for the nth digit of r. The digits 0 and 1 need to be avoided while adding digits to r, in order to ensure that an alternative representation of r is not already in place. For instance, 0.1299999… = 0.1300000… = 0.13. Working in this manner, r is a number that is not part of the sequence t(n), since it varies from each term of the sequence in at least one decimal place.
Now r can be easily added to the sequence, because it’s just one number. But the same process can be repeated to arrive at another number that still isn’t in the sequence. This leads to the conclusion that real numbers cannot be put into a sequence, and are hence not countable.
Suggested Further Reading
Principles of Mathematical Analysis by Walter Rudin, 3rd Edition (McGraw Hill, 1976)
 |
