How Big Is Infinity?

At the end of the Marvel blockbuster Avengers: Endgame, a pre-recorded hologram of Tony Stark bids farewell to his young daughter by saying, “I love you 3,000.” The touching moment echoes an earlier scene in which the two are engaged in the playful bedtime ritual of quantifying their love for each other. According to Robert Downey Jr., the actor who plays Stark, the line was inspired by similar exchanges with his own children.

The game can be a fun way to explore large numbers:

“I love you 10.”

“But I love you 100.”

“Well, I love you 101!”

This is precisely how “googolplex” became a popular word in my home. But we all know where this argument ultimately leads:

“I love you infinity!”

“Oh yeah? I love you infinity plus 1!”

Whether it’s on the playground or at bedtime, children encounter the concept of infinity long before math class, and they understandably develop a fascination with this mysterious, complicated and important concept. Some of those children grow up to be mathematicians fascinated with infinity, and some of those mathematicians are discovering new and surprising things about infinity.

You might know that some sets of numbers are infinitely large, but did you know that some infinities are bigger than others? And that we’re not sure if there are other infinities sandwiched between the two we know best? Mathematicians have been pondering this second question for at least a century, and some recent work has changed the way people think about the issue.

In order to tackle questions about the size of infinite sets, let’s start with sets that are easier to count. A set is a collection of objects, or elements, and a finite set is just a set that contains finitely many objects.

Determining the size of a finite set is easy: Just count the number of elements it contains. Since the set is finite, you know you’ll stop counting eventually, and when you’re done you know the size of your set.

This strategy doesn’t work with infinite sets. Here is the set of natural numbers, which is denoted ℕ. (Some might argue that zero is not a natural number, but that debate doesn’t affect our investigations into infinity.)

$latex\mathbb{N} = \{0,1,2,3,4,5,…\}$

What’s the size of this set? Since there’s no biggest natural number, trying to count the number of elements won’t work. One solution is to simply declare the size of this infinite set to be “infinity,” which isn’t wrong, but when you start exploring other infinite sets, you realize it isn’t quite right, either.

Consider the set of real numbers, which are all the numbers expressible in a decimal expansion, like 7, 3.2, −8.015, or an infinite expansion like $latex\sqrt{2} = 1.414213…$. Since every natural number is also a real number, the set of reals is at least as big as the set of natural numbers, and so must also be infinite.

But there’s something unsatisfying about declaring the size of the set of real numbers to be the same “infinity” used to describe the size of the natural numbers. To see why, pick any two numbers, like 3 and 7. Between those two numbers there will always be finitely many natural numbers: Here it’s the numbers 4, 5 and 6. But there will always be infinitely many real numbers between them, numbers like 3.001, 3.01, π, 4.01023, 5.666… and so on.

Remarkably enough, no matter how close any two distinct real numbers are to each other, there will always be infinitely many real numbers in between. By itself this doesn’t mean that the sets of real numbers and natural numbers have different sizes, but it does suggest that there is something fundamentally different about these two infinite sets that warrants further investigation.

The mathematician Georg Cantor investigated this in the late 19th century. He showed that these two infinite sets really do have different sizes. To understand and appreciate how he did that, first we have to understand how to compare infinite sets. The secret is a staple of math classes everywhere: functions.

There are lots of different ways to think about functions — function notation like $latex f(x) = x^2 +1$, graphs of parabolas in the Cartesian plane, rules such as “take the input and add 3 to it” — but here we’ll think of a function as a way to match up the elements of one set with the elements of another.

Let’s take one of those sets to be ℕ, the set of natural numbers. For the other set, which we’ll call S, we’ll take all of the even natural numbers. Here are our two sets:

$latex\mathbb{N} = \{0,1,2,3,4,…\}$                     $latex S= \{0,2,4,6,8,…\}$

There’s a simple function that turns the elements of ℕ into the elements of S: $latex f(x) = 2x$. This function simply doubles its inputs, so if we think of the elements of ℕ as the inputs of $latex f(x)$ (we call the set of inputs of a function the “domain”), the outputs will always be elements of S. For example, $latex f(0)=0$, $latex f(1) = 2$, $latex f(2) = 4$, $latex f(3) = 6$ and so on.

You can visualize this by lining up the elements of the two sets side by side and using arrows to indicate how the function $latex f$ turns inputs from ℕ into outputs in S.

Notice how $latex f(x)$ assigns exactly one element of S to each element of ℕ. That’s what functions do, but $latex f(x)$ does it in a special way. First, $latex f$ assigns everything in S to something in ℕ. Using function terminology, we say that every element of S is the “image” of an element of ℕ under the function $latex f$. For example, the even number 3,472 is in S, and we can find an x in ℕ such that $latex f(x) = 3,472$  (namely 1,736). In this situation we say that the function $latex f(x)$ maps ℕ onto S. A fancier way to say it is that the function $latex f(x)$  is “surjective.” However you describe it, what’s important is this: As the function $latex f(x)$ turns inputs from ℕ into outputs in S, nothing in S gets missed in the process.

The second special thing about how $latex f(x)$ assigns outputs to inputs is that no two elements in ℕ get transformed into the same element in S. If two numbers are different, then their doubles are different; 5 and 11 are different natural numbers in ℕ, and their outputs in S are also different: 10 and 22. In this case we say that $latex f(x)$ is “1-to-1” (also written “1-1”), and we describe $latex f(x)$ as “injective.” The key here is that nothing in S gets used twice: Every element in S is paired with only one element in ℕ.

These two features of $latex f(x)$ combine in a powerful way. The function $latex f(x)$  creates a perfect matching between the elements of ℕ and the elements of S. The fact that $latex f(x)$ is “onto” means that everything in S has a partner in ℕ, and the fact that $latex f(x)$ is 1-to-1 means that nothing in S has two partners in ℕ. In short, the function $latex f(x)$ pairs every element of ℕ with exactly one element of S.

A function that is both injective and surjective is called a bijection, and a bijection creates a 1-to-1 correspondence between the two sets. This means that every element in one set has exactly one partner in the other set, and this is one way to show that two infinite sets have the same size.

Since our function $latex f(x)$ is a bijection, this shows that the two infinite sets ℕ and S are the same size. This might seem surprising: After all, every even natural number is itself a natural number, so ℕ contains everything in S and more. Shouldn’t that make ℕ bigger than S? If we were dealing with finite sets, the answer would be yes. But one infinite set can completely contain another and they can still be the same size, kind of the way “infinity plus 1” isn’t actually a larger amount of love than plain old “infinity.” This is just one of the many surprising properties of infinite sets.

An even bigger surprise may be that there are infinite sets of different sizes. Earlier we explored the different natures of the infinite sets of real and natural numbers, and Cantor proved that these two infinite sets have different sizes. He did so with his brilliant, and famous, diagonal argument.

Since there are infinitely many real numbers between any two distinct reals, let’s just focus for the moment on the infinitely many real numbers between zero and 1. Each of these numbers can be thought of as a (possibly infinite) decimal expansion, like this.

Here $latex a_1,  a_2, a_3$ and so on are just the digits of the number, but we’ll require that not all the digits are zero so we don’t include the number zero itself in our set.

The diagonal argument essentially starts with the question: What would happen if a bijection existed between the natural numbers and these real numbers? If such a function did exist, the two sets would have the same size, and you could use the function to match up each real number between zero and 1 with a natural number. You could imagine an ordered list of the matchings, like this.

The genius of the diagonal argument is that you can use this list to construct a real number that can’t be on the list. Start building a real number digit by digit in the following way: Make the first digit after the decimal point something different from $latex a_1$, make the second digit something different from $latex b_2$, make the third digit something different from $latex c_3 $, and so on.

This real number gets defined by its relationship with the diagonal of the list. Is it on the list? It can’t be the first number on the list, as it has a different first digit. Nor can it be the second number on the list, as it has a different second digit. In fact, it can’t be the nth number on this list, because it has a different nth digit. And this is true for all n, so this new number, which is between zero and 1, can’t be on the list.

But all the real numbers between zero and 1 were supposed to be on the list! This contradiction arises from the assumption that there exists a bijection between the natural numbers and the reals between zero and 1, and so no such bijection can exist. This means these infinite sets have different sizes. A little more work with functions (see the exercises) can show that the set of all real numbers is the same size as the set of all the reals between zero and 1, and so the reals, which contain the natural numbers, must be a bigger infinite set.

The technical term for the size of an infinite set is its “cardinality.” The diagonal argument shows that the cardinality of the reals is greater than the cardinality of the natural numbers. The cardinality of the natural numbers is written $latex \aleph_0$, pronounced “aleph naught.” In a standard view of mathematics this is the smallest infinite cardinal.

The next infinite cardinal is $latex \aleph_1$ (“aleph one”), and a simply stated question has flummoxed mathematicians for more than a century: Is $latex \aleph_1$ the cardinality of the real numbers? In other words, are there any other infinities between the natural numbers and the real numbers? Cantor thought the answer was no — an assertion that came to be known as the continuum hypothesis — but he wasn’t able to prove it. In the early 1900s this question was considered so important that when David Hilbert put together his famous list of 23 important open problems in mathematics, the continuum hypothesis was number one.

A hundred years later, much progress has been made, but that progress has led to new mysteries. In 1940 the famous logician Kurt Gödel proved that, under the commonly accepted rules of set theory, it’s impossible to prove that an infinity exists between that of the natural numbers and that of the reals. That might seem like a big step toward proving that the continuum hypothesis is true, but two decades later the mathematician Paul Cohen proved that it’s impossible to prove that such an infinity doesn’t exist! It turns out the continuum hypothesis can’t be proved one way or the other.

Together these results established the “independence” of the continuum hypothesis. This means that the commonly accepted rules of sets just don’t say enough to tell us whether or not an infinity exists between the natural numbers and the reals. But rather than discourage mathematicians in their pursuit of understanding infinity, it has led them in new directions. Mathematicians are now looking for new fundamental rules for infinite sets that can both explain what is already known about infinity and help fill in the gaps.

Saying “My love for you is independent of the axioms” may not be as fun as saying “I love you infinity plus 1,” but perhaps it will help the next generation of infinity-loving mathematicians get a good night’s sleep.

Exercises

1. Let $latex T = \{1,3,5,7,…\}$, the set of positive odd natural numbers. Is T bigger than, smaller than, or the same size as ℕ, the set of natural numbers?

2. Find a 1-to-1 correspondence between the set of natural numbers, ℕ, and the set of integers $latex\mathbb{Z}=\{…,-3,-2,-1,0,1,2,3,…\}$.

3. Find a function $latex f(x)$ that is a bijection between the set of real numbers between zero and 1 and the set of real numbers greater than zero.

4. Find a function that is a bijection between the set of real numbers between zero and 1 and the set of all real numbers.

Click for Answer 1:

Click for Answer 2:

One way is to visualize the list of matching pairs, like this:

You can also try to define a function that matches up the elements. This function,

$latexf(n) =\begin{cases}
\frac{n+1}{2} &\text{if $n$ is odd} \\
-\frac{n}{2} &\text{if $n$ is even}
\end{cases}$

maps ℕ onto $latex\mathbb{Z}$ and is 1-1. So there are as many integers as natural numbers, another curious feat of infinity.

Click for Answer 3:

Click for Answer 4: