How big is infinity? Most people, though familiar with the general concept of infinity, would probably answer with a simple, question-dodging response of “infinite.” To be fair, the infinite is a really difficult concept to wrap one’s head around, and still causes challenges and puzzles in mathematics to this day.
This is why I’m somewhat proud to have mused on some deeper issues from a very early age. When I was around 8-10 years old, I distinctly remember explaining to my mother that there had to be different sizes of infinity. My argument was as follows:
Suppose there are an infinite number of stars in the universe: that represents one size of infinity. However, every star in the universe contains a huge amount of atoms, and the total number of atoms must also be infinite. But since, for every star, there are a large number of atoms, the infinite size of the collection of atoms must be larger than the infinite size of the collection of stars.
This was surprisingly deep thinking for a pre-teen, and was at least partially right: there are different sizes to infinity. However, my argument of how to imagine different sizes of infinity was completely wrong!
To understand why, we need to talk a bit about what is known in mathematics as set theory and the properties of the smallest infinite set, which has a “size” labeled as (being pronounced “aleph-zero”). What we will find, in this first post in a series, is that infinity is very weird!
The ideas considered here were first discussed by the brilliant mathematician Georg Cantor (1845-1918), who between 1879 and 1884 published a series of articles introducing the mathematical foundations of set theory and discussions of infinity. So what is a set? A “set” is simply a collection of distinct objects, real or imagined, which are conceptually grouped together. The definition is incredibly broad: a group of students in a high school class forms a set (of actual objects), while the types of monsters described in the Dungeons & Dragons Monster Manual represent another set (of imagined objects).
We can also form sets out of numbers; for instance, the set e of even numbers less than ten consists of the elements:
As another example, the set p of prime numbers (which have no divisors other than themselves or one) less than 20 has the elements:
Once we have a set, we can ask how many elements it contains; this is referred to as the set’s cardinal number, or cardinality. “Cardinality” is, in effect, a fancy way of saying we are using numbers for counting things, not using numbers for ordering things (which would be an “ordinal number.”)
If we consider an infinite set, such as the natural numbers N, given by
we can no longer assign an ordinary number to describe the size of the set. However, we can compare this set to other infinite sets, and ask: which is bigger? For instance, if we consider the set of all positive even numbers E, is this set smaller than the set of natural numbers?
At first glance, we would probably say that the natural numbers are a larger set than the even numbers, just like I said that the number of atoms are greater than the number of planets, but appearances are misleading! In order to measure the size of sets properly, we need to reassess how we go about comparing large sets.
A thought experiment: suppose we have a huge bag of M&Ms (let’s assume it’s an even number, for simplicity), and we want to divide this set into a pair of piles of equal size. The most obvious solution would be to count the entire stack, and then count out exactly half of the total into a separate pile, as illustrated below.
This will of course work, but it is very inefficient: we have to count the whole stack 1 1/2 times, and there’s always the chance of a counting error along the way. If you’re dealing with someone very serious about their M&Ms, this could be a dangerous mistake!
However, there is another, faster and safer, way to count out the piles: build the two piles simultaneously, matching each M&M in one pile with a counterpart in the other. By doing so, we only have to sort through the pile one time.
This method not only saves us effort, but it doesn’t even require us to count the number of M&Ms at all: we can determine that the piles are the same size simply by putting the candy into what is called a “one-to-one correspondence.”
This same idea can be used for comparing the size of infinite sets: if every element of one set can be matched to a corresponding element of the other set, they are of the same size. Even if no ordinary number exists to describe the cardinality of an infinite set, we can discuss whether one infinite set is bigger than another.
This is where things get weird! Let us do, as Cantor did, and label the cardinality of the set N of natural numbers by , “aleph” being the first letter of the Hebrew alphabet. First, let’s look at how the cardinality of the natural numbers changes if we add an extra element to the set, call it a. Our new set, call it , looks like
But let’s compare this set to the natural numbers! If we illustrate the effect, we have:
With that extra element added to , we can still match the natural numbers in one-to-one correspondence; the two sets have the same cardinality! If we treat as a number, we can symbolically write
Or, to put it another way, “infinity plus one = infinity,” at least as far as is concerned! We can continue this logic by adding new elements, one at a time, to the set N. We can therefore say that, for any finite number n,
But this process gets even crazier! Suppose we combine a set of cardinality with another set of cardinality ; what is the size of the new set, i.e. what is ?
Let’s designate the elements of the first set by the natural numbers, and the elements of the second set by the primes of the natural numbers: 1′, 2′, 3′, and so forth. If we arrange the new set by putting each primed element after each unprimed element, we see that we can still put these elements into one-to-one correspondence with the natural numbers!
This means that we may also say that “infinity plus infinity equals infinity!”
DARE WE GO FURTHER!!?? YES, WE DARE! In terms of elements of the set, we may also write
as the sum of two sets of size is equivalent to doubling the set — though it ends up having the same size! Thus
This process can be continued, and for any integer n, we may write
Can you see where this is going? If we take the integer n to be arbitrarily large, it seems to follow that we can write
In other words: “infinity times infinity is the same size as infinity!”
This in fact means that this AT&T commercial, with the slogan “It’s not complicated,” is even less complicated than they imagined!
How can we explain this last result? The key is to show that we can make a correspondence between an infinity-squared set of elements with the natural numbers. This is surprisingly easy to do, and in picture form, as well. Let us suppose that the natural numbers are arranged downwards vertically as an infinite set of points. Multiplying this set by infinity results in a mesh of points that stretches off infinitely to the right and downwards. But it is quite easy to draw a single line that inevitably runs through each point of this grid, as shown below.
On the left, we illustrate that we are in fact looking at infinity times infinity: the grid contains every possible pair of natural numbers. On the right, we show the beginning of the one-to-one correspondence between the natural numbers and the grid.
We can, in a sense, go the other way, and divide as well as multiply (though I use the term “division” loosely). For instance, we can ask: what is the size of the complete set of even numbers, which at first glance would appear to be half as numerous as the natural numbers? In fact, the cardinal number of the even numbers is still just , just like the natural numbers themselves.
Most people at this point instinctively recoil from this sort of argument. “Wait,” they say. “In this correspondence, the even numbers are increasing faster than the natural numbers. We have to run out of the even numbers faster than the naturals at the end of the set — they can’t possibly be the same size!”
The short answer to this is that we never “run out” of numbers — the set is infinite! This response also feels unsatisfying. A better answer is to reverse our thinking about the one-to-one correspondence. Suppose we imagine any natural number, as large as we like, for example 100-billion-billion. We can always easily figure out the even number that is in correspondence with it, in this example 200-billion-billion. For any natural number we choose, we can find the even number that corresponds to it. By our reckoning, the two sets are therefore the same size.
A similar argument applies to the size of the set of prime numbers. Though the prime numbers are less and less frequent in the set of natural numbers the higher we go, we can still make a one-to-one correspondence with the natural numbers. We’ve known since the time of Euclid that the number of prime numbers is infinite — since they also can be arrange in order on a number line, we can set up a one-to-one correspondence. The set of prime numbers also has cardinality .
There’s one more remarkable result to share. There’s another set that is seemingly larger than the natural numbers: the set of all rational numbers. A rational number is one that can be expressed as a fraction with whole numbers, such as 1/2, 2/3, 51/100, 32/67, and so forth. This includes the entire set of natural numbers, because each natural number can be written as a fraction: 5 = 5/1, 15 = 15/1, and so on.
We might think that this set is larger than , but in fact it is again the same size! This can be demonstrated by using a grid construction as above, as first described by Cantor. Each grid point is defined as the fraction given by the ratio of the column number divided by the row number.
Some elements, crossed out in red, are redundant — 2/2 is the same as 1 — and we just skip over them in our correspondence. In the end, though, we find that the entire set of rational numbers does in fact have the same cardinality as the natural numbers: !
The rational numbers include the natural numbers plus a large number of fractional numbers that lie between them on the number line. We can uncover an even more surprising result and demonstrate that the set of algebraic numbers have cardinality as well!
An algebraic number is a number that is a root of an algebraic equation of the general form
where n is any natural number and the coefficients are any integer numbers (positive or negative whole numbers). The set of algebraic numbers includes not only the natural numbers and the rational numbers, but includes roots of numbers as well, such as , and so forth. It can be shown (and I’ve gone on far too long at this point) that even the set of algebraic numbers is the same size as the natural numbers, again!
So, infinity is weird! If this were the end of the story, it would be anti-climactic, and arguably not even mathematics. If all infinite sets were the same size, there would really be nothing interesting to be said about them. However, it can be shown that there are in fact infinities that are bigger than , and even that there are an infinite number of infinities of increasing cardinality…
… but that will be a discussion for the next post in this series!
(Part 2 can be read here.)