Today is the 165th birthday of Georg Ferdinand Ludwig Philipp Cantor, the mathematician who indirectly inspired me to major in math. In my first few semesters of college, I was at best an indifferent student, finding little inspiration in the humanities majors I was bouncing around among, playing a prodigious amount of pinball, and attaining (according to rumor) history’s first-ever grade of C in Peter Regenstrief‘s Poltical Science 101. Then one day, my friend Bob Hyman happened to mention that some infinities are larger than others, and set my life on track. This—the vision of Georg Cantor—was something I had to know more about. Before long I was immersed in math.
What does it mean for some infinities to be larger than others? Well, for starters, some infinite sets can be listed, while others are too big to list. The natural numbers, for example, are already packaged as a list:
The integers, by contrast (that is, the natural numbers plus their negatives) aren’t automatically listed because a list, by definition, has a starting point, whereas the integers stretch infinitely far in both directions. But we can fix that by rearranging them:
So the integers can also be listed.
The positive rational numbers (that is, numbers expressible as fractions) appear even harder to list than the integers, because they have no immediate successors. What is the next rational number after 1/2, for example? Answer: there is no next number. Between any two rationals lie infinitely many more.
We can still list them, though—after a suitable rearrangement of course. There are many ways to do this; here’s probably the simplest: First list all the fractions whose numerator and denominator add to 2, then all the fractions whose numerator and denominator add to 3, then all the fractions whose numerator and denominator add to 4, then 5, and so on, like so:
and finally string them all together:
There’s some repetition here (for example, 2/2 is the same number as 1/1), but just cross out the repeats and you’ve got your list.
What if you wanted to list all the rational numbers, both positive and negative? Easy! Just combine the two tricks we’ve already used. Start with the list just above, and stick in the negatives:
Now the only missing rational is zero, which you can throw in anyplace you like—say at the very beginning.
At this point you should begin to suspect that any infinite set can be listed, given enough cleverness. Not so, though. Let’s try to list all the real numbers—that is, all numbers expressible as (possibly infinite) decimals—between 0 and 1.
Now offhand, I can’t think of any way to do this, but that doesn’t prove anything about the real numbers; it might just prove I’m not as clever as I ought to be. But Cantor, with one incredibly simple argument, demonstrated that no attempt to list those real numbers can be successful.
Here’s the argument. Suppose you believe you have managed to list all those real numbers. Maybe your list looks something like this:
(For convenience, I’ve displayed this list vertically instead of horizontally, so the first item on the list is .8410729…., the second is .1415926…, and so on.) Now I’m going to prove you wrong—that is, I’m going to prove your list is incomplete—by writing down a number that’s definitely missing. First I write down a decimal point. Then I write down any first digit other than 8 (say 6). This insures that the number I’m writing down is not the same as .8410729….. Then I write down any second digit other than 4 (say 5). This insures that the number I’m writing down is not the same as .1415926….. Then I’ll write down any third digit other than 3 (say 7). This insures that the the number I’m writing down is not the same as .3333333….. Continuing in this way, I get a number
that is definitely nowhere on your list.
(If it bothers you to imagine that I could make infinitely many choices, just imagine that I make all the choices at once by applying some fixed rule. For example: Whenever I need a digit other than 1, I’ll pick 7; whenever I need a digit other than 2, I’ll pick 5…)
If you say “oops, I forgot that number; I’ll stick it in my list somewhere”, I’ll just pull the same trick again and find another number that’s not on your list. So no matter how clever you are, you can never list all the real numbers—or even just the real numbers between 0 and 1.
But we saw that there is a way to list all the rational numbers. So in what turns out to be a profound and fundamental sense, the infinity of real numbers is bigger than the infinity of rational numbers.
With that discovery, Cantor taught the world how think about infinity, rocked the foundations of mathematics, and, with a lag of a hundred and some years, changed my life.