In the 1995 film Toy Story, the gung-ho space action figure Buzz Lightyear tirelessly incants his catchphrase: “To infinity... and beyond!” The joke, of course, is rooted in the perfectly reasonable assumption that infinity is the unsurpassable absolute—that there is no beyond. That assumption, however, is not entirely sound. As German mathematician Georg Cantor demonstrated in the late 19th century, a variety of infinities exist—and they can be classified by their relative sizes.
Take, for instance, the so-called natural numbers: 1, 2, 3, and so on. These numbers are unbounded, and thus the collection, or set, of all the natural numbers is infinite in size. But just how infinite is it? Cantor used an elegant argument to show that the naturals, though infinitely numerous, are actually less numerous than another common family of numbers: the real numbers. This set comprises all numbers that can be represented as a decimal, even if that decimal representation is infinite in length. Hence, pi (3.14159...) is a real number, as is 27 (which is both natural and real).
Cantor's argument used the logic of contradiction: he first assumed that these sets are the same size; next he followed a series of logical steps to find a flaw that would undermine that assumption. He reasoned that if the naturals and the reals have equally many members, then the two sets can be put into a one-to-one correspondence. That is, they can be paired so that every element in each set has one—and only one—“partner” in the other set.
Think of it this way: even in the absence of numerical counting, one-to-one correspondences can be used to measure relative amounts. Imagine two crates of unknown sizes, one of apples and one of oranges. Withdrawing one apple and one orange at a time thus partners the two sets into apple-orange pairs. If the contents of the two crates are emptied simultaneously, the two boxes contain an equal number of fruits; if one crate is exhausted before the other, the one with remaining food is more plentiful.
Cantor thus began by presuming that the naturals and the reals are in such a correspondence. Accordingly, every natural number n has a real partner rn. The reals can then be listed in order of their corresponding naturals: r1, r2, r3, and so on.
Then Cantor's wily side comes out. He created a real number, called p, by the following rule: make the digit n places after the decimal point in p something other than the digit in that same decimal place in rn. A simple method would be: choose 3 when the digit in question is 4; otherwise, choose 4.
For demonstration's sake, say the real-number partner for the natural number 1 is 27 (or 27.00000...), the pair for 2 is pi (3.14159...) and that of 3 is President George W. Bush's share of the popular vote in 2000 (0.47868...). Now create p following Cantor's construction: the digit in the first decimal place of p should not be equal to that in the first decimal place of r1 (27), which is 0. Therefore, choose 4, and p begins 0.4.... (The number before the decimal can be anything; 0 is used here for simplicity.) Then choose the digit in the second decimal place of p so that it does not equal that in the second decimal place of r2 (pi), which is 4. Select 3, and now p = 0.43.... Finally, choose the digit in the third decimal place of p so that it does not equal the one in the corresponding decimal place of r3 (President Bush's percentage), which is 8. Write 4 again, making p = 0.434.... Thus, you have:
This mathematical method (called diagonalization), continued infinitely down the list, generates a real number (p) that, by the rules of its construction, differs from every real number on the list in at least one decimal place. Ergo, it cannot be on the list.
In other words, for any pairing of naturals and reals, there exists a real number p without a natural-number partner—an apple without an orange. Therefore, any one-to-one correspondence between the reals and the naturals fails, which means that the infinity of real numbers is somehow greater than the infinity of natural numbers.