In(finity)ception
A few weeks ago, I had a student in my office one Friday afternoon, looking for a little extra help understanding the material. While she was talking with me, it became clear that my class’s perception of me is that I’m a total nerd who has this strange obsession and fascination with mathematics, which I think most of them are convinced is the most mind-numbing subject in the world. (These weren’t her exact words, but this is the impression I got.)
A nerd who is a math enthusiast. Better than the perception that I don’t really care about the subject or the class. So I’ll take it.
At one point she asked me, “So how long are you going to be here?”
“Oh, on a Friday afternoon? Usually I’m here until around 6, then the other math grad students go out to a bar together.”
“Oh… okay. So why math?”
I frowned. “Well, I dunno. We’re colleagues. Math grads, you know? We work together, we hang out together, and we blow off steam together. We’re work buddies.”
“No, I mean you. Why math?”
I did my best not to light up like a Christmas tree. “Oh,” I nodded. “Well that’s quite different.”
(And yes, that exact conversation DID happen.)
The truth is, I can remember the exact moment I fell in love with mathematics. It came during my Real Analysis class at Hamilton College (my undergraduate institution), in the Fall of 2013. Before I took this class, I more or less believed the same myth about mathematics that almost everyone else does before they begin taking serious proof-based pure math classes. The myth is this:
Mathematics is about manipulating equations and finding solutions to those equations; the only difference from one math class to another is the sophistication of those equations.
Nothing could be farther from the truth. Of course, equations play a pretty significant role in mathematics, especially for those researching applied mathematics, and even for those researching pure mathematics and trying to be as formal as possible. But that’s not what mathematics is about. Mathematics is a study of concepts, not procedures. Solving equations is a procedure; a computer can do that most of the time. But mathematicians research concepts more than procedures. Equations are simply tools to understand these concepts formally; sometimes you don’t even need them.
So I’d like to tell you about a really beautiful mathematics concept, the concept that would eventually lead to the revelation that made me fall in love with the subject. (I apologize in advance if this becomes hard to follow; I’ll do away with some formalism and try to make it as intuitive as I can.)
In the late 19th and early 20th century, there was a German mathematician named Georg Cantor (pictured on the right).
Cantor proved, among other things, that some infinities are “bigger” than others. More specifically, Cantor proved that you can have two infinite sets, where one set is somehow “more infinite.” Here’s the classic example: let N be the set of all positive whole numbers, {1, 2, 3, 4, … }. Clearly N is an infinite set. Now let R be the set of all real numbers—that is, the set of all whole numbers, positive and negative, plus all possible numbers between them (so fractions, square root of 2, pi, etc. are all real numbers, but none of those are positive whole numbers in N). So R is also an infinite set. You could draw these two sets on a number line to see where I’m going with this:
The set N is a string of dots; an infinitely long string of dots, but a string of dots nonetheless. (The arrow denotes that the string of dots continues.) The set R, on the other hand, is the entire number line, a smooth continuum covering those dots and everything between them and before them.
Think about these two sets for a second. Intuitively, you might be able to imagine that even though N and R are both infinite sets, R somehow seems “more infinite.” Or, you might be thinking, “That’s ridiculous. They’re both infinite. How can one be more infinite? Isn’t infinity as big as you can get?”
Well… yes and no. We need to hammer down what we mean when we say that some sets are bigger than others. More specifically, we need to hammer down what we mean when two sets are the same size. If two sets are finite, it’s easy to see whether they’re the same size. If they’re infinite, it can be a little trickier. So let’s do a little thought experiment.
Suppose you are the proprietor of a hotel, called the Hilbert Hotel. It has infinitely many rooms, and each room has a number on it, starting from 1 and working up. Now suppose that one weekend, your entire hotel is full. Each room is occupied. But on this weekend, a young grad student is looking for a place to stay at your hotel. The employee at the front desk tells her, “I’m sorry, miss, but our hotel is full.” You happen to overhear this exchange, and you walk over to try to settle this issue. You consider the situation, and you tell her, “Actually, we can find you a place. We’ll have every occupant in the hotel move down one room, and you can then take Room 1.” Your hotel occupancy hasn’t gone down; every room is still full, and no one has had to leave.
Now, I claim the set N = {1, 2, 3, … }, and the set N_0 = {0, 1, 2, 3, … } are the same size, even though there’s one more point in N_0. Adding one person to your hotel did not change the number of occupied rooms. In the same way, adding 0 to the set of numbers does not change the amount of stuff, the size, of the set. Mathematicians call the amount of stuff inside a set the “cardinality” of a set. So the set of the Beatles has cardinality 4 because there are 4 Beatles. The set of Supreme Court justices has cardinality 9. (Actually I guess it’s currently cardinality 8… sorry, Scalia.)
Okay, fine. But now suppose a bus of people comes up to the Hilbert Hotel. This bus has infinitely many people in it, and your hotel has infinitely many rooms, but each room is still occupied. Your doorman really doesn’t know what to do with this; accommodating one or two other people was easy, but how can you accommodate an additional infinite number of people? Once again, being the brilliant proprietor of the Hilbert Hotel, you find a way to accommodate the infinite number of new guests. You tell the front desk, “Have every current guest move to the room whose number is double their current room number. So the guest in room 1 will move to room 2, the guest in room 2 will move to room 4, the guest in room 3 will move to room 6, and so on. All our guests will still be able to stay, and we’ll have created an infinite number of vacancies to accommodate our new guests.” So if the seats on the bus are numbered, then every current guest living in room n will now live in room 2n, and every person in seat n on the bus will now live in room 2n-1.
Now, I claim that the set N = {1, 2, 3, … } and the set Z = { … , -2, -1, 0, 1, 2, … } are the same size. Here Z is the set of integers, or the set of all whole numbers, positive and negative. Even though the set Z has infinitely many more points than N does, they still have the same size, the same cardinality. This is just like how accommodating an infinite number of new guests to your hotel did not change the occupancy: each room still has a guest in it, and no one has to leave.
But now a train comes to your hotel. This train has an infinite number of train cars, and each train car has an infinite number of people. In(finity)ception! How do you accommodate them all? There are in fact several different ways, but here’s my preferred method. Suppose each train car has a number c, starting at c = 1 for the first car, and each seat in each car has a number n. So each person in the train has a unique pair of numbers, which we’ll write as (c, n). Arrange the room numbers in a descending pyramid; the first 28 rooms are arranged in this way in the figure.
So send the people currently living in the hotel to the rooms in the rightmost diagonal of the pyramid (the yellow diagonal below). If you live in room 1, you stay where you are. If you’re in room 2, you go to the second room in the right diagonal, which is room 3. If you live in room 5, you go to the fifth room in the right diagonal, which is room 15. Continuing in this way, the rightmost downward sloping diagonal has all current guests. Now, if you were on train car 1, you and your fellow passengers fill out the next diagonal to the left. If you were in car 2, you and your fellow passengers fill out the next diagonal to the left of the passengers from car 1. And so on, and so on. Each diagonal has infinitely many rooms, and there are infinitely many diagonals, so everyone gets a room in the Hilbert Hotel, but again, no one has to check out! In the pyramid below, each colored diagonal has passengers from a particular car, and the yellow diagonal on the far right has the original guests. Of course, the pyramid will continue infinitely far downward.
So consider the set of all possible integer fractions. Call this set Q. Every number that can be written as an integer fraction—that is, every number with a finite or repeating decimal expansion—is in Q. So 0 and 1 and 5 are in Q (take 0/1, 1/1, or 5/1), and also 1/2, 5/3, and -2/7 are all in Q, but pi is not. We call Q the set of “rational numbers,” and I claim that there are just as many rational numbers as there are whole numbers in our set N = {1, 2, 3, … }. This is because every number in Q can be written as a pair of integers—indeed, as a fraction. Think about that. Clearly N is contained in Q, and between every two positive integers in N is an infinite number of fractions in Q, but they both have the same cardinality. They have the same amount of stuff.
Incredible, ain’t it?
Now—and here’s the important bit—not only have we found space for an infinite number of people on infinitely many train cars, but also, after everyone moves in, we can look at anyone’s room number, compare it to our pyramid, and determine precisely which car they came from, and which seat on that car they came from (or, for that matter, if they were a guest in the hotel to begin with). Think about a similar assignment from the set Q of all possible fractions. We can similarly write every single fraction into our pyramid, and assign each fraction a unique integer:
This is called a “bijection,” or more precisely, a “bijection of the sets of natural and rational numbers.” I know that sounds advanced, but really, to say that something is a “bijection of sets” is just a sexy way of saying that you can pair up every element in set A with an element in set B and not have anything left over in either set. Much like we did with our set N of all positive whole numbers, and our set Q of all rational numbers.
(Okay, two minor technical details, which you may ignore at your discretion. The first is, strictly speaking, the bijection I described between N and Q is actually a bijection between N and the set of all *positive fractions, which is significant because Q contains negative fractions. I’m ignoring this detail because one can define a similar bijection between Q and Z, where Z is the set of all positive AND negative whole numbers. We already have a bijection between Z and N. It’s relatively easy to prove that because we have a bijection between Z and N, and a bijection between Q and Z, we can create a bijection between N and Q by taking everything in Q, matching it up with everything in Z, and matching all of these pairs with everything in N as we would match elements of N and Z together. The second technical detail is that the bijection I described doesn't account for reducible fractions, e.g. 3/6 = 1/2, but if we eliminate reducible fractions, we are left with a hotel with infinitely many vacancies, so we can shift everyone down accordingly, giving us a slightly more complicated bijection. If this is confusing, then forget this paragraph. Like I said, these are just technicalities.)
So Cantor asserted that two sets—finite or infinite—have the same size, i.e. the same amount of stuff, i.e. the same cardinality, if and only if there is a bijection between them; that is, two sets are of the same size if and only if we can find some way to uniquely match everything up between them and account for everything in both sets. Today, this is the main universal way how we understand infinite sets.
So far, we’ve only discussed sets that have the same infinity; the set N of positive integers, the set Z of positive and negative integers, and the set Q of all possible integer fractions all are equally infinite. Note that in our hotel illustration, whenever we brought in more guests, we had a numbering scheme for the new guests. Either we numbered their seats on the bus, or we numbered their train cars and numbered their seats in the cars. Mathematicians have a special name for this kind of infinity. We say that such sets are “countable,” or “countably infinite.” A little oxy-moronic, perhaps, but it comes from the idea that we can enumerate the elements of such sets so that each element gets a unique positive integer. (Alternatively, you can think of it as, if you count off the guests, you will reach each given guest in a finite amount of time. You won't be able to count all of them together in a finite amount of time, but if you have a guest named Joe, and you list off your guests, you will reach Joe in a finite amount of time.)
Not all infinite sets are countable. Remember how we said the set R of all possible real numbers is more infinite than N? One of the things Cantor proved is that you can’t enumerate the set R in this way. You can try, but if you assume that you have such an enumeration scheme, you can construct an infinite nonrepeating decimal that is not included in this scheme. This is what’s known as the Cantor Diagonalization Argument, and I'll discuss it in more detail in the next post. So Cantor showed that there are some infinite sets between which you do not have a bijection; some infinities are more infinite than others. Understandably, this got on some mathematicians’ nerves, including his Ph.D. advisor, Leopold Kronecker. (Yes, math friends, Kronecker was Cantor’s advisor, and his arch nemesis. Fun bit of math history trivia.)
But that wasn’t the only thing Cantor proved that riled up his contemporaries. Some infinities are more infinite than others, yes. But no infinity is the most infinite. Cantor found that if you have any infinite set A, you can create a new set (known as the “power set” P(A)) that is more infinite than A. Consider that. No such thing as a biggest infinity. What does that say about God? To the Catholic Church at the time, they feared it may imply to some readers that God could not exist, for if He did, then there would be some entity greater than God, a contradiction. But that wasn’t what Cantor showed. That only makes sense if you think God is a set, which is a little silly. To my mind, it just means that we as humans can’t understand what God can do, for if we could encapsulate God’s abilities, even if only in our imagination, God’s abilities would still transcend everything we had encapsulated.
Minus the bit in the end about my interpretation of God and Cantor’s theories, this infinity-of-infinities issue was the subject of a lecture in that Real Analysis class. But that wasn’t the lecture that made me fall in love with mathematics. Actually it was the next one, the lecture that this lecture built up to, when I learned about an object that forever changed how I saw mathematics.
That object is known as the Cantor Set.