In the 1995 Pixar 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, there exists a variety of infinities—and some are simply larger than others.
Take, for instance, the so-called natural numbers: 1, 2, 3 and so on. These numbers are unbounded, and so 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, although infinitely numerous, are actually less numerous than another common family of numbers, the "reals." (This set comprises all numbers that can be represented as a decimal, even if that decimal representation is infinite in length. Hence, 27 is a real number, as is π, or 3.14159….)
In fact, Cantor showed, there are more real numbers packed in between zero and one than there are numbers in the entire range of naturals. He did this by contradiction, logically: He assumes that these infinite sets are the same size, then follows a series of logical steps to find a flaw that undermines that assumption. He reasons that the naturals and this zero-to-one subset of the reals having equally many members implies that the two sets can be put into a one-to-one correspondence. That is, the two sets 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 sizes. 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, they are equally numerous; if one crate is exhausted before the other, the one with remaining fruit is more plentiful.
Cantor thus assumes that the naturals and the reals from zero to one have been put into such a correspondence. Every natural number n thus 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 begins to show. He creates 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 binary method would be: choose 0 when the digit in question is 1; otherwise, choose 1.
For demonstration’s sake, say the real number pair for the natural number 1 (r1) is the decimal component of π (0.14159…), the pair for 2 (r2) is George W. Bush’s share of the popular vote in 2000 (0.47868…) and that of 3 (r3) is Ted Williams’s famed .400 batting average from 1941 (0.40570…).
Now create p following Cantor’s construction: the digit in the first decimal place should not be equal to that in the first decimal place of r1, which is 1. Therefore, choose 0, and p begins 0.0…. Then choose the digit in the second decimal place of p so that it does not equal that of the second decimal place of r2, which is 7 (choose 1; p = 0.01…). Finally, choose the digit in the third decimal place of p so that it does not equal that of the corresponding decimal place of r3, which is 5 (choose 1 again; p = 0.011…).
Continuing down the list, this mathematical method (called "diagonalization") generates a real number p between zero and one that, by 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, p is a real number without a natural number partner—an apple without an orange. Thus, the one-to-one correspondence between the reals and the naturals fails, as there are simply too many reals—they are "uncountably" numerous—making real infinity somehow larger than natural infinity.
"The idea of being ‘larger than’ was really a breakthrough," says Stanley Burris, professor emeritus of mathematics at the University of Waterloo in Ontario. "You had this basic arithmetic of infinity, but no one had thought of classifying within infinity—it was just kind of a single object before that."
Adds mathematician Joseph Mileti of Dartmouth College: "When I first heard the result and first saw it, it was definitely something that knocked me over. It’s one of those results that’s short and sweet and really, really surprising."
Via Scientific American