Countable

Resources

Every set that can be counted—that is, every finite set—is countable, but this is no surprise. The interesting case comes when we abandon finite sets and consider infinite ones.

An infinite set of numbers, points, or other elements is said to be countable (also called denumerable ) if its elements can be paired one-to-one with the natural numbers, 1, 2, 3, etc. The term countable is somewhat misleading because, of course, it is humanly impossible actually to count infinitely many things.

The set of even numbers is an example of a countable set, as the pairing in Table 1 shows.

Of course, it is not enough to show the way the first eight numbers are to be paired. One must show that no matter how far one goes along the list of even natural numbers there is a natural number paired with

it. In this case this is an easy thing to do. One simply pairs any even number 2n with the natural number n.

What about the set of integers? One might guess that it is uncountable because the set of natural numbers is a proper subset of it. Consider the pairing in Table 2.

Remarkably it works.

The secret in finding this pairing was to avoid a trap. Had the pairing been that which appears in Table 3, one would never reach the negative integers. In working with infinite sets, one considers a pairing complete if there is a scheme that enables one to reach any number or element in the set after a finite number of steps. (Not everyone agrees that that is the same thing as reaching them all. ) The former pairing does this.

Are the rational numbers countable? If one plots the rational numbers on a number line, they seem to fill it up. Intuitively one would guess that they form an uncountable set. But consider the pairing in Table 4, in which the rational numbers are represented in their ratio form.

The listing scheme is a two-step procedure. First, in each ratio, the denominator and numerator are added. All those ratios with the same total are put in a group, and these groups are listed in the order of increasing totals. Within each group, the ratios are listed in order of increasing size. Thus the ratio 9/2 will show up in the group whose denominators and numerators total 11, and within that group it will fall between 8/3 and 10/1. The list will eventually include any positive rational number one can name.

Unfortunately, there are two flaws. The list leaves out the negative numbers and it pairs the same rational number with more than one natural number. Because 1/1, 2/2, and 3/3 have different numerators and denominators, they show up at different places in the list and are paired with different natural numbers. They are the same rational number, however. The first flaw can be corrected by interleaving the negative numbers with the positive numbers, as was done with the integers. The second flaw can be corrected by throwing out any ratio which is not in lowest terms since it will already have been listed.

Correcting the flaws greatly complicates any formula one might devise for pairing a particular ratio a/b with a particular natural number, but the pairing is nevertheless one-to-one. Each ratio a/b will be assigned to a group a + b, and once in the group will be assigned a specific place. It will be paired with exactly one natural number. The set of rational numbers is, again remarkably, countable.

Another countable set is the set of algebraic numbers. Algebraic numbers are numbers that satisfy polynomial equations with integral coefficients. For instance, √2, I, and (-1 + √5 )/2 are algebraic, satisfying x² - 2 = 0, x² + 1 = 0, and x² + x - 1 = 0, respectively.

Are all infinite sets countable?

The answer to this question was given around 1870 by the German mathematician George Cantor. He showed that the set of numbers between 0 and 1 represented by infinite decimals was uncountable. (To include the finite decimals, he converted them to infinite decimals using the fact that a number such as 0.3 can be represented by the infinite decimal. 0.29— where the 9s repeat forever.) He used a reductio ad absurdum proof, showing that the assumption that the set is countable leads to a contradiction. The assumption therefore has to be abandoned.

He began by assuming that the set was countable, meaning that there was a way of listing its elements so that, reading down the list, one could reach any

number in it. This can be illustrated with the example in Table 5.

From this list he constructs a new decimal. For its first digit, he uses a 1, which is different from the first digit in the first number in the list. For its second digit, he uses a 3, which is different from the second digit in the second number. For its third digit, he uses a 3 again, since it is different from the third digit in the third number.

He continues in this fashion, making the n-th digit in his new number different from the n-th digit in the n-th number in the list. In this example, he uses 1s and 3s, but he could use any other digits as well, as long as they differ from the n-th digit in the n-th number in the list. (He avoids using 9s because the finite decimal 0.42 is the same number as the infinite decimal 0.4199999. with 9s repeating.) The number he has constructed in this way is 0.131131. Because it differs from each of the numbers in at least one decimal place, it differs every number in the assumed complete list. If one chooses a number and looks for it in a listing of a countable set of numbers, after a finite number of steps he will find it (assuming that list has been arranged to demonstrate the countability of the set). In this supposed listing he will not. If he checks four million numbers, his constructed number will differ from them all in at least one of the first four million decimal places.

Thus the assumption that the set of infinite decimals between 0 and 1 is countable is a false assumption. The set has to be uncountable. The infinitude of

KEY TERMS

Denumerable— A synonym for “countable.”

Uncountable— A term describing the number of elements in an infinite set whose elements cannot be put into one-to-one correspondence with the natural numbers.

such a set is different from the infinitude of the natural numbers.

Resources

BOOKS

Faticoni, Theodore G. The Mathematics of Infinity. New York: Wiley-Interscience, 2006.

Kaplan, Robert and Ellen Kaplan. The Art of the Infinite: The Pleasures of Mathematics. New York: Oxford University Press, 2004.

Zellini, Paolo. A Brief History of Infinity. New York: Penguin, 2006.

J. Paul Moulton