The most merciful thing in the world, I think, is the inability of the human mind to correlate all its contents. We live on a placid island of ignorance in the midst of black seas of infinity, and it was not meant that we should voyage far.
~Howard Phillips Lovecraft

To infinity, and beyond!
~Buzz Lightyear

Infinity: The Early Years

When I was about ten, I had the following conversation with my friend:

Me: I want Pokemon Yellow the most of anyone!

My Friend: No, I do! I want it twice as much as you!

Me: I want it infinity times as much as you!

Sound familiar? Since ancient times, we’ve contemplated the infinite. Between 490 and 430 BCE, Zeno of Elea put forth his famous paradoxes. Wikipedia describes the dichotomy paradox as follows:

Suppose Homer wants to catch a stationary bus. Before he can get there, he must get halfway there. Before he can get halfway there, he must get a quarter of the way there. Before traveling a quarter, he must travel one-eighth; before an eighth, one-sixteenth; and so on…

This description requires one to complete an infinite number of tasks, which Zeno maintains is an impossibility.

The solution to this particular paradox was first developed by Archimedes, which modern calculus tells us is the convergent geometric series:

   

In the case of the dichotomy paradox, and we find that

   

In other words, if the time taken by an action scales linearly with distance, infinite actions take only two units of time.

But what does infinity actually mean? This question wasn’t resolved until the formal foundations of set theory were laid down by the likes of Georg Cantor (more on him later), Bertrand Russell, and others. To the ancients, infinity was the potential for unbounded growth. For example: In his Elements, Euclid proved that there are infinitely many prime numbers (you may recall that a prime number is any number greater than 1 divisible only by itself and 1). The way he phrased it, though, is a bit subtle (source):

Prime numbers are more than any assigned multitude of prime numbers.

To the ancient Greeks, this is what infinity meant–give me any prime, and I can find you a bigger one. Indeed, Euclid’s proof uses this exact logic. Say I wrote down a list of primes, maybe 2 and 3, and I told you that that’s it. These are all the prime numbers in existence. Well, it turns out that you can use that list to prove me wrong and show that there are more:

• Take the product of all the prime numbers I listed. In this case:

     

• Now add 1, to get:

     

• We know that it must be possible to write every number as a unique (up to order) product of prime numbers. So 7 must be some product of primes.
• Well, there are only two primes, right? 2 and 3? How do we write 7 as a product of 2 and 6? Neither nor is a whole number, so we must be missing a prime.
• Thus, there are more primes than 2 and 3.

In this case, of course, our missing prime is 7 itself, but that’s not always the case. For instance, if I told you that the only primes in existence were 3 and 5, you’d generate a new number,

   

so the missing prime was 2, not 16. No matter the list of primes I give you, though, this procedure will work: you can always find a number that’s divisible by a prime not on my list. To my knowledge, this is the first rigorous mathematical proof that anything (in this case, the set of prime numbers) is infinite.

Infinite Sets

A natural consequence of the infiniteness of the set (don’t worry about the definition of a set too much, it’s exactly what it sounds like) of prime numbers is that the counting numbers (often called the natural numbers) are also infinite in multitude. There’s no “biggest” number. There’s no smallest, either, if you give me a fraction of the form

   

I can always find a bigger , and thus a smaller fraction. (Incidentally, the history of the invention of fractions is really very fascinating. For a long time, mathematicians didn’t believe in fractions, only in ratios between numbers.) Once negative numbers were invented, we found we could make as “negative” a number as we liked; give me a  negative integer , and I can find a more negative one, .

An irrational number is a number that can’t be written as the ratio of two integers. is the classic example of an irrational number, but it turns out there are infinitely many of these, too. , where is an integer, easily generates a set of them. The set of all numbers which are rational, irrational, positive, negative, or zero is called the real numbers–this is the number line you’re used to from school.

After Euclid proved that there were infinite prime numbers, mathematics made great strides. Sir Isaac Newton and Gotfried Leibniz invented calculus. Leonhard Euler more elegantly proved Euclid’s theorem on prime numbers. Carl Friedrich Gauss used calculus to explore worlds that couldn’t be described using Euclid’s geometry. (These great men did a lot more than this, of course; I’m just giving some examples.) For the most part, however, mathematicians shied away from infinity. Although calculus relies on the infinitely small, very little effort was put into understanding the infinite any better, and the task was generally considered impossible. All that changed with Georg Cantor.

Cantor Tames Infinity

Georg Cantor (1845-1918) was a brilliant mathematician, an exceptional violinist, an extraordinary teacher, and, eventually, a madman. Indeed, it’s tempting to say that Cantor went mad from his contemplations of the infinite (we won’t say that, though… will we?), since it was through Cantor that we learned of the different sizes of infinity.

Cantor is who first demonstrated that the real number line is, in some sense, bigger than the set of rational numbers–it somehow contains more elements. Perhaps more surprisingly, the set of rational numbers is the same “size” as that of integers and of natural numbers. How can this be? I’ll show you, but we need to develop a little machinery first.

The first idea we need is that of a bijective map. This is just a one-to-one correspondence between two objects. For instance, I can assign a number between 1 and 26 to each letter of the alphabet so that every letter has a single unique number associated with it, and vice-versa. (Incidentally, this is often how computer programs represent the alphabet–each letter or character is given a unique hexadecimal number, one for each character, so that the computer can convert human language into machine code.) The letters and numbers don’t need to be in any particular order, though.

   

is just as good as

   

is just as good as something else.

We can’t set up a bijective map with the alphabet and 25 or 27 numbers, though. If we used 25, one letter wouldn’t get a number, and if we used 27, one letter would get two. In either case, we don’t have a bijection. The important point here is that a bijection is possible only between objects of the same “size.” In the finite case, where we can count up sizes, we can use this idea to generate the Pigeonhole Principle. In the infinite case, we can use the idea of a bijective map as the definition of “same size.”

This leads us to the following definition:

A set is called countable if it is finite, or can be put into bijective correspondence with the set of natural numbers. It is otherwise uncountable.

This definition splits the infinity into two categories: “Small” infinities, which are the same size as the natural numbers, and “big” infinities, which are somehow larger. The wording is important. We say can be put into bijective correspondence because there could be many bijections. We don’t want to restrict ourselves to only looking for one of them. Any bijection will do. This definition–one of Cantor’s key insights–allows us to compare the sizes of infinitely large things. Using this definition, we can immediately see that the integers are the same size as the natural numbers, despite the fact that there are twice as many integers as there are natural numbers.

Let’s write a list of all the integers:

   

It goes on forever, of course. But let’s assign a natural number to each integer and see if we run out. (Note that I include zero in the natural numbers here. Not everyone does.)

   

We never run out of integers! By our definition, then, the set of natural numbers is “countable” and thus the same size as the set of integers. More surprisingly, the rational numbers are also countable, meaning they’re the same size as the integers and the naturals.

More surprisingly, perhaps, the set of all rational numbers is exactly the same size as the set of all integers and the set of all naturals. How do we know? Let’s try writing out all the rational numbers as a grid of fractions. From the top left, let’s start with . As we move right, let’s increase the numerator, and as we move down, let’s increase the denominator.

Now we need to try assigning natural numbers to each of these rational numbers, which means we have to travel across the grid somehow as we assign numbers. If we try to travel down each row, one after the other, we’ll never get past the first! Each row has infinite columns, after all.However, if we instead iterate across the diagonals, we have a chance. We assign 1 to , 2 to , 3 to , 4 to , and so on. Since each diagonal is only 1 element longer than the previous diagonal, each is finite, and we can (in infinite time) assign a natural number to every single element of every single diagonal. We actually win by a lot here, since there are duplicates in our grid: , and so forth.

Great–we have a bijection! This is really surprising, since, at first glance, there seem to be way more rational numbers than natural numbers. Cantor’s proof, though, shows that it’s not true.

Can we do the same thing with the real numbers? Let’s try and pull the same trick by writing each real number out as an infinitely long decimal expansion:

   

and so forth. Now, since we have our irrational numbers in one big list, we assign a natural number to each one, right? Not so fast. It might look like we have them all, but we don’t. Just like we generated more primes out of any list of primes we were given, we can generate more irrational numbers out of any list of irrational numbers we’re given. Here’s how: Take the first digit of the first number, the second digit of the second number, the third digit of the third number, etc., and combine them into a new number. The first digit before the decimal of the new number is the first digit before the decimal of the first number in our list, the second digit is the second digit of the second number in our list, and so on. For the sake of argument, let’s say that number is

   

Now we change our new number using a special rule. If any digit in our number is 0, we change it to 1, and otherwise we change it to 0. So, in our example, the new number is

   

Here’s the fun part. Our new number isn’t in the list of  numbers we wrote down. It’s not the first number, because the first digit is different. It’s not the second number, because the second digit is different. And so on.

The upside of this is that, no matter how many times we try to write down an infinite list of real numbers and assign each real number a natural number, we’ll be missing a real number. The natural numbers are too small to index the real numbers. Just like we couldn’t write out a finite list of prime numbers, we can’t write out an infinite list of real numbers. The set is just too big. Thus, my friends, we’ve proved that the set of real numbers is uncountable.

There are different sizes to infinity.

Implications

Actually, it turns out that there are infinite sizes to infinity, and the implications of this are far-reaching. Number theory, analysis, geometry, abstract algebra, and many other fields make use of the sizes of infinity. (We have a name for countable infinities and uncountable infinities, but not for any other sizes of infinity.) One important topic I want to discuss briefly is why calculus needs the uncountability of the real line.

Calculus was invented before Cantor discovered the sizes of infinity, but mathematicians ran into trouble when they tried to put calculus on rigorous footing. The derivative is supposed to be the infinitesimally small change in a function, . But which infinity? It turns out that if we only look at rational numbers that are infinitely close to zero, we run into trouble. The argument is subtle, so I won’t go into it here (I fear this post is already tl;dr), but the idea of a derivative in calculus relies on what’s called a limit. The idea is get infinitesimally close to some value and see what does. But what if is missing? Or if numbers around are missing? In that case, it’s not clear what does. The rational numbers are too small to hold all the kinds of numbers around a point , resulting in madness. For this reason, the real numbers are called the completion of the rational numbers. If you’ve heard of the “Completeness Axiom,” that’s related to this. (I’m glossing over a lot of stuff here. Completeness also has to do with open and closed sets, limit points, and topology, and it’s not strictly an axiom.)

Further Reading

If you’re interested in learning more:

• Numberphile has a wonderful video on Cantor’s proof. It’s often helpful to see an argument presented several different ways, so you may want to check it out.
• Logicomix is a sprawling epic on the life of Bertrand Russell and many other great mathematicians in the form of a graphic novel. It has a section on Georg Cantor’s brilliant and tragic career, as well as on some of his ideas.

Questions?

That’s it from me. Now I’d like to know what you guys think. Any questions? Comments? Concerns? Corrections? I think the uncountability of the reals is one of the most surprising and subtle arguments in all of mathematics. I certainly didn’t understand it the first time I saw it. If you want any clarification, don’t hesitate to ask in the comments. If this sparked your interest and you want to hear more about something, don’t hesitate to ask about that, either.