“Infinity!” “Infinity plus 1!” “Infinity plus a hundred!” “Infinity times ten!” “Infinity times infinity!” Remember playing this game as a child? Trying to compete to name the biggest infinity? What happens when pure research mathematicians play this game?
Standing outside an auditorium before giving a calculus final exam, some of my students asked what I was reading. It was “The Higher Infinite”, a very advanced tome of mathematics by Akihiro Kanamori. My students were understandably pretty interested to hear about the idea of more than one kinds of infinity. In fact, there are infinitely many levels of infinity. And that’s even pretty well-known, at least among people who read about math. What Kanamori writes about, in rather difficult mathematical language (the book is meant for advanced graduate students or math PhDs), are some lesser-known infinities, which are so big that they literally bend the basic facts of mathematics.
WHAT IS INFINITY?
In formal set theory, there is no single entity called “infinity”. In mathematics, when we say that the answer to some question is “infinity”, we really mean that any finite answer would be too small. The “entity” of infinity is just a kind of shorthand for expressing this idea. But there are infinite sets– that is, collections which are infinite. When we talk about multiple “levels of infinity”, we’re really talking about collections of different, infinite, sizes.
Here’s an example. Take the collection of all natural numbers (the natural numbers are the numbers 0, 1, 2, 3, 4, and so on; the numbers you use to count). How big is this collection? Any finite answer is too small. For example, if we guess that the collection of natural numbers has size one million, then that’s too small because there are more than a million counting numbers. Since any finite answer is too small, we say the collection is infinite.
What about the set of all real numbers, with any number of decimal places, including infinitely many non-repeating decimal places, like in the number pi=3.1415…? If we look at this “continuum” of real numbers, again it’s infinite, because any finite size would be too small. It turns out the set of all real numbers is actually larger than the set of all counting numbers. And that’s the prototypical example to show that there are more than one sizes of infinity. But, what does it mean to say that one infinite collection is larger than another?
To understand how the sizes of infinite collections can be compared, it’s first necessary to understand how the sizes of finite collections are compared. One way to compare the sizes of finite collections is to just count them and compare the numbers. But that doesn’t generalize to infinite collections, because we can’t count an infinite collection– if we could, it would not be infinite.
A better way– or at least, a more generalizable way– to compare the sizes of finite collections is to check whether we can marry their elements together in a nice one-to-one way. If two finite collections have the same size, then we can think of one collection as being the collection of “males”, think of the other as being the collection of “females”, and marry them up so everyone has exactly one partner. If the collections had different sizes, we couldn’t do this, someone would be left out.
This “marriage” idea is referred to in mathematics as a “bijection”. A bijection is just a fancy, smart-sounding way of saying, you assign each member of the first collection to a unique member of the other, so that nothing is left out and nothing is matched up twice. If two collections have a bijection between them, then they have the same size, and if not, then they have different sizes. (The marriage analogy breaks down a little bit when the two sets have some overlap. In that case, an element of one set is allowed to self-marry precisely if it’s an element of both sets.)
You can think of counting small (smaller than size eleven) sets as establishing a bijection between the set and between a certain subset of your fingers. You count “one, two, three, four,” holding up a finger with each utterance, and you’re implicitly “marrying” a certain set of your fingers to elements of the set you’re counting.
The bijection idea naturally generalizes to infinite sets with no extra work. Two sets, whether they be finite or infinite, are said to have the same size if there’s some way to link their elements together bijectively, so that each element of the first gets associated with exactly one element of the second.
Right away, some trippy examples come up. For example, the set of all even counting numbers (0,2,4,6,8,…) has the same size as the set of all counting numbers. That’s because if you take any even counting number and divide it in half, you get a counting number, and the result is unique and no other even number gives the same result. The act of dividing-in-half is a bijection from the set of even counting numbers to the set of all counting numbers.
THERE ARE MORE THAN ONE SIZES OF INFINITY
The famous example which first shows that there are more than one sizes of infinity, is the fact that there are more real numbers than there are counting numbers. A real number being any number, positive or negative, with any number of decimal places, including numbers like pi or √2 where there are infinitely many non-repeating decimal places.
The fact that there are more real numbers than counting numbers was a big surprise to mathematicians; after all, both sets have infinitely many elements, so a mathematician back in the old times might have said both sets have size infinity.
Saying that there are more reals than naturals comes down to saying that there aren’t enough naturals to associate with the reals; if we try to marry each real number to a unique natural number, with no naturals getting married twice, then there won’t be enough natural numbers to go around and some (in fact, most) of the reals will be left out. There is no bijection from the naturals to the reals. Since the naturals are a subset of the reals– every natural is a real– there are at least as many real numbers as there are natural numbers; so if there’s no bijection between them, then the set of real numbers must be strictly bigger.
Georg Cantor, the mathematician who discovered a lot of this stuff about different infinities, published a famous proof that there’s no bijection between the naturals and the real numbers. You can read his proof, the famous “diagonal argument”, at Wikipedia. I’ll give a different proof, one which is in my opinion more acid-trippy and fun.
My proof uses a certain infinite sum which is related to one of the Zeno’s paradoxes, if you’ve ever read about those. Basically, in order to walk across a distance of size 1 meter, first you have to walk one half meter. Then, you have to walk one fourth meter. Then, you have to walk one eighth meter, then one sixteenth meter, and so on. Adding up all those partial walks, each one half as long as the previous, you get the total distance of one meter. This gives the infinite sum, 1/2+1/4+1/8+…=1. What does this have to do with proving there are more reals than naturals? Hold onto your hat…
Suppose that there was a bijection from the naturals to the reals. Then we could “count” the reals (marry them to the counting numbers), saying, this real number is the first real; this real number is the second real; this real number is the third real; and so on.
Now I’m gonna show a way that you can cover the entire real number line with a covering of length 1. That’s ridiculous, because the real number line is infinitely long. There’s no way to cover it with just a covering of length one. For instance the real line contains the interval from -1 to 1, which has length 2 all by itself.
Take the “first” real number (i.e., the number which is associated to the counting number 0). Cover it with a cover of length 1/2. Next, take the “second” real number, and cover it with a cover of length 1/4. Take the “third” real number, and cover it with a cover of length 1/8, then cover the “fourth” real number with a cover of length 1/16, and so on. Even if none of these covers overlapped, the total area of the cover would be at most 1/2+1/4+1/8+…=1. In fact, the covers overlap a lot, so the total area of these covers ends up being less than 1. But every real number is the nth real number for some n; that’s the assumption we made, that we had a bijection between counting numbers and reals. So, every real number gets covered. I’ve covered the whole real line, with a covering scheme where the covers have a total length no longer than 1. Impossible, that’s not even enough to cover just the part of the real line from -1 to 1.
I started out assuming there was a bijection from the naturals to the reals. Then, I showed that the assumption allows me to do something ridiculous. So the assumption must be wrong, and there is no bijection between the naturals and the reals. They have different sizes, and the reals contain the naturals, so there are more reals than naturals.
(Actually the proof is missing a little detail, since I’m assuming some common sense notions about how lengths work. The details are filled in in an advanced branch of math called “measure theory”, but I figured it’d be worth the reduced details to post this alternate proof that there’s no bijection.)
THERE ARE INFINITELY MANY LEVELS OF INFINITY
I just established there are more than one levels of infinity, by showing that the set of real numbers is bigger than the set of natural numbers. But the infinitudes get much, much bigger, and there are far more sizes of infinity than just the size of the set of naturals and the size of the set of reals.
If you take any collection of objects, it makes sense to talk about subsets of that collection. For example, you can ask about the set of all subsets of the natural numbers. This set-of-all-subsets is called the power set. The power set of the natural numbers is the set of all sets of natural numbers.
Here’s the big breakthrough which leads to infinitely many levels of infinity. It’s a fundamental truth discovered by Georg Cantor, and it totally turned mathematics on its head. Cantor showed: if you have any set whatsoever– empty, finite, or any level of infinite– then the power set is even bigger.
For example, the power set of the natural numbers– the set of all sets of natural numbers– is bigger than the set of natural numbers. So that gives another proof that there are more than one levels of infinity.
To get infinitely many levels of infinity, you can just repeat the process. You can take the power set of the power set of the set of naturals, and get something even bigger. And then you can take the power set of that. The process never ends, and it provides infinitely many levels of infinity.
SO HOW MANY LEVELS OF INFINITY ARE THERE?
I’ve shown you how there are infinitely many different levels of infinity, and a natural question which you might ask is, what is the size of the set of all levels of infinity? So far, I’ve showed how to get infinitely many different levels of infinity, but the infinities we can create using just power set, can be placed into a natural association with the natural numbers. I can say that the 0th infinity corresponds to the number of natural numbers. And then I can say the 1st infinity is the power set of the 0th. And the 2nd is the power set of the 1st, and so on. This hits all the infinities we get with just repeated power setting of the naturals. If we just look at repeated power sets, we get as many levels of infinity as there are natural numbers.
But is that all of them?
No. There are infinities so big that no matter how many times I apply the power set operation, I’ll never reach them. Here’s an example. What if we take the set of naturals, and then the power set of that, and combine them into one big set. And then, we throw in everything in the power set of the power set of the naturals. And then, throw in everything in the power set of that. And keep going, forever. So, in other words, we get the set of all things which show up anywhere in any of the repeated power sets starting with the naturals. Since this set contains all those power sets as subsets, it must be bigger than all of them. It’s one mind-bendingly, insanity-destroyingly huge set! (But, it’ll turn out it’s still “tiny” in the world of mathematical logic)
So just how many infinities are there? The answer is unsettling. It turns out, there are so many levels of infinity, that no level of infinity is enough to answer the question. No matter how hard anyone tries to come up with some incomprehendably large level of infinity, there are more levels of infinity than that.
Congratulations, if you’ve read this far, you know just about as much about building really-big-freaking-infinities as a lot of mathematicians. Now strap yourself in, I’m gonna talk about how to go to a whole new level, making the infinities we’ve talked about so far look like tiny insects.
Logicians use the term “LARGE CARDINAL” to refer to some levels of infinity so big that, in a certain sense, they transcend math.
Almost all contemporary mathematics is done under a system of assumptions called ZFC (Zermelo-Frankel set theory with the axiom of Choice). Think of these assumptions like the postulates of Euclid, except they concern abstract sets rather than geometric objects. ZFC is generally assumed to be “consistent”, by which we mean you can’t use it to prove 1=0. If someone did manage to prove 1=0 from ZFC, that would rank among the biggest moments in all of mathematics.
Still, there is the faint, unsettling possibility that maybe ZFC can prove 1=0. Mathematicians would be extremely pleased to prove that it can’t. But a logician named Kurt Gödel crushed any hopes of that. In a move that shocked mathematicians of the time, Gödel proved that any system strong enough to do the most basic arithmetic, is too strong to prove its own consistency– well, unless it’s actually inconsistent (in which case it can prove anything whatsoever). In light of this “2nd Incompleteness Theorem” of Gödel, mathematicians actually dread a proof, in ZFC, of the consistency of ZFC, because if any such proof exists– then ZFC is inconsistent.
However, if you assume additional axioms which go beyond ZFC, then it is sometimes possible to prove the consistency of ZFC in that new system. Such new axioms are generally quite complicated to even state, but one of them is relatively simple: the axiom, “ZFC is consistent”. The system “ZFC+CON(ZFC)”, consisting of ZFC together with the statement that ZFC is consistent, trivially proves CON(ZFC). Of course, by Gödel’s theorem, it can’t prove its own consistency…
Now, one way to prove the consistency of ZFC is to construct a model where ZFC holds, and show that ZFC holds in it. The ZFC axioms are statements saying that certain sets exist; so to prove CON(ZFC), it suffices to construct a set which contains all the sets which ZFC says must exist. Such a set must be quite large; larger, in fact, than anything which ZFC says exists. Its size is a Large Cardinal.
All the levels of infinity which we can possibly conceive using normal math must exist within a large cardinal, because ZFC– and thus, all of “normal math”– exists within the large cardinal. Consequently, the large cardinal is bigger than any level of infinity that we can construct using the axiom system of modern mathematics.
We can extend ZFC to a stronger axiom system, ZFC+, in which we add one new axiom: “There exists a set which is a model of ZFC.” The whole process can be repeated: we can ask about whether a model of ZFC+ necessarily contains a set which, itself, is a model of ZFC+. Gödel’s theorem guarantees that ZFC+ does not prove that a ZFC+ model exists, and if there is a set which is a model of ZFC+, then it is larger than anything which ZFC+ proves exists. Thus, its size is an even “Larger Cardinal”.
These LARGE CARDINALS I’ve talked about are just one type of large cardinal. The general process is: take ZFC (normal modern math) and extend it with some new assumption, strong enough to prove ZFC. Above, I added the axiom “There is a set which models ZFC”, which is the heaviest-handed large cardinal axiom. In actual practice, large cardinal axioms are much more exotic, and in some cases they may not even appear to be related to set theory at all. In fact, one of the goals of the mathematicians who study large cardinals is to troll mathematics by finding the most “harmless” looking large cardinal axioms they can.