the first post in a finite series
If there’s one thing about math that people love—and to make it through the average day, I have to believe there’s at least one—it’s infinity.
Throw the word into a math lesson, and ears perk up. Infinity? Did he say infinity? It’s like a distant celebrity, the subject of endless gossip and rumor. “I heard infinity isn’t even a number!” “Only the universe is really infinite.” “My last teacher said infinity times two is the same as infinity.” “I can use infinity to prove that 1 = 0!”
Infinity is a sound too high for our ears, a light too bright for our eyes, a taste so sweet that it would tear through our tongues like acid. Basically, it’s mathematical Mountain Dew.
Tellingly, all of our words for infinity define it by what it isn’t. Infinite: not finite. Unlimited: not limited. Boundless: without bounds. It’s hard to articulate what infinity does, so we settle for naming what it doesn’t: end. Infinity is the Anansi of mathematics, a trickster spider weaving baffling webs of paradox and contradiction.
Take this example: which has more numbers, List A or List B?
Well, they’re both continue forever, so they’re both infinite. But the first list includes every number on the second (2, 4, 6, 8…), and lots more as well (1, 3, 5, 7…). Thus, clearly, List A is the bigger group of numbers. Right?
Wrong. The lists are exactly the same size.
To see why, just go through list A and double every number on it, like so:
Now, doubling each number shouldn’t affect the size of the list. We haven’t added any items, or taken any way. It’s like taking a group of people and giving them fake beards—you don’t create or destroy any humans in the process.
And yet… without changing its size, we’ve somehow turned list A into list B. That can only mean that the two lists were the same size to begin with.
What’s happening here? Throughout our lives, we’ve relied on a simple rule for comparing the sizes of groups: If one group has all the members of another, plus some others, then it must be bigger. For example, if your list of Facebook friends includes all of mine, plus you’re friends with Kanye West, then you have more friends than I do (and probably cooler weekend plans, too).
And that’s perfectly true, for finite groups. But infinite groups… those are another matter.
Infinity shreds our intuitions. The startling truth is that all infinite lists are the same size, regardless of whether one happens to include the other.
The mathematician David Hilbert captured this paradoxical truth with the parable of Hilbert’s Hotel. Imagine there’s an infinite hotel, in which every room is currently occupied. (There’s a very popular convention in town, apparently.)
You show up, asking for a room. “Sorry, they’re all occupied,” says the innkeeper—who’s probably a little frazzled, what with the infinite calls for room service coming in.
“Yes,” you say, “but just ask everyone to move down one room, and there will be space.”
It’s true. The person in Room 1 goes to Room 2. The person in Room 2 goes to Room 3. The person in Room 136,004 goes to Room 136,005. And so on. Everybody has someplace to go.
Now, whether it’s good manners to show up at a hotel and demand that a literally infinite number of people suffer a minor inconvenience just so you can avoid trying the Best Western down the road—that’s another matter. You’re probably a bad person for making this request. But you’re a fine mathematician.
Can we do this without inconveniencing an infinite number of people? Unfortunately, no. For example, if you take Room 1, and send that guy packing, he’s going to have the same problem as you: every room is now occupied. As long as you’re shuffling a finite number of rooms, normal math applies, and somebody will be left out. Your infinite problem demands an infinite solution.
It gets crazier. What if you’re coming straight from the Infinite Man March, and you’ve got an infinite line of new friends in tow? Can the hotel hold you all now?
Impressively: Yes.
This time, each current guest needs to look at their room number, double it, and move to that doubled room. So the chap in Room 1 moves to Room 2. The gal in Room 2 moves to Room 4. The fellow in Room 3003 moves to room 6006. And so on.
At this point, which rooms are filled? Only the evens. So you and your infinity friends fill the odd rooms, and voila! Problem solved.
(Unless you’re the bellhop in charge of setting out the continental breakfast; then, the problems have just begun.)
At this point, infinity is perhaps beginning to feel like a squishy, flexible, silly-putty sort of idea. Infinite lists? They’re the same size. Infinity plus one? Still the same size. Infinity plus another infinity? Yup, still the same size. It raises the provocative question: Are all infinities the same size? Tune in next week for the answer.
Oh, who am I kidding? The answer is no. Some infinities are much bigger than others.
Tune in next week for why.
I’ve always felt that size is not an attribute of infinite sets. If you measure the size of something with a ruler, how do you decided which number on the ruler corresponds to the object’s size? You read off the one that is where the object ends. Size is a limit measurement–something that doesn’t have a limit doesn’t have a size.
Yeah, our definition of “size” for infinite sets certainly isn’t the same as our definition for finite sets. I’d go so far as to call this a theme in math – taking an ordinary word and stretching it to fit a new setting or scenario, losing some of its original meaning in the process. Perhaps always putting “size” in quotation marks better captures the meaning here.
I am hopeful that the Continuum Hypothesis (or its negation) can find its way into a “bad drawing”!
I don’t see why not! I’m building up towards the idea of an uncountable infinity next week; the Continuum Hypothesis would seem to fit in naturally between those two ideas. (Or perhaps NOTHING fits in naturally between those two ideas…)
*rimshot!* But will we get to explore the axiom of choice in specific terms? It’s one of my favorite things to annoy topologists with… “but is there a way to prove that *without* the AoC?” 😉
I do hope you get as far as the Cantor Middle Third set. This is really mind blowing.
Not nearly as mind-blowing as the Cantor middle-quarter set: totally disconnected, nowhere dense, contains no intervals, and yet has positive measure.
Now here’s a puzzle: can a set of real numbers be constructed which has positive measure on every interval, but full measure on no interval?
“Check your assumptions. In fact, check your assumptions at the door.” –Cordelia Vorkosigan
Awesome article !
Ok, the irrational numbers are uncountable, but unfortunately the set of algebraic numbers is countable, and this includes all square roots, cube roots, etc.
A great article that even middle schoolers can get a grasp on to begin to understand this concept.
I once saw an infinite set defined as a set that could be placed in one-to-one correspondence with one of its proper subsets, which I’ve always liked. (It allows us to define what an infinite set is rather than what it is not, and it puts the most counterintuitive property of infinite sets front and center.)
This doesn’t quite work. See Ben’s next post.
It actually does! An infinite set can’t necessarily be placed in one-to-one correspondence with ALL of its proper subsets, but it can with at least one of them.
Thanks. I clearly didn’t do a “close reading” here!
The term for this is Dedekind-infinite (see also: Dedekind-finite).
With the Axiom of Choice, it syncs up with the standard definition of infinite.
I’m not a fan of using the word “Wrong” in reply to “List A is bigger than List B”, for the simple reason that there are several common and useful definitions of “size”, some of which do indeed say List A is bigger than List B.
In addition to cardinality, there is set containment, measure theory, sub-group/ring/field relations, and plenty of other partial orders which formalize various aspects of bigness. Not all of them apply to lists of integers, but another one that does is the concept of natural density.
Cardinality may say the integers are equinumerous with the evens, but set containment and natural density both aver that the former outnumber the latter. That’s two against one, and last I checked two is bigger than one by a factor of, like, six.
@Maya Quinn
The equivalence you mention doesn’t even require all of countable choice, let alone the full axiom of choice. In fact “Dedekind-infinite implies infinite” is true without any form of choice, and “infinite implies Dedekind-infinite” is equivalent to “every infinite set has a countable subset”.
I only wished to indicate that the two notions of infinitude need not be equivalent in a model of ZF, whereas they are equivalent in any model of ZFC.
Yes, if an infinite set has a countable subset enumerated as: a_1, a_2, a_3, …, then the map that sends a_n to a_{n+1} and fixes all other elements gives the desired sort (the image is proper since nothing maps to a_1). I imagine this is the sort of argument you had in mind (?) and, as you note, producing such an enumeration does not require “the full axiom of choice.”
@Maya Quinn
That is one direction, yes. For the converse, given a Dedekind-infinite set S, let f be a bijection from S to its proper subset T. Take x in S but not in T, and the orbit of x under f never hits the same value twice (proof left as an exercise) so it is a countably-infinite subset of S.
Wow, I feel smarter after reading this! Thanks for explaining and giving me a good laugh! (At your drawings’ dialogue)
Great post.
Amusingly, I wrote a short (long?) essay with this *exact* same title about a year ago. It gets a little more technical than this blog usually does, but perhaps some people here will enjoy it:
http://tac-tics.net/blog/infinity-plus-one
Μηχανικος αυτοκινητων στην πατησια αναλαμβανει σερβις αλλαγη λαδιων επισκευαζει μιζα
αυτοκινητου σε mercentes
Good expression
About the guy who wants to check into Hilbert’s Hotel:
He can’t move into room 1 until the guy in room 1 moves into room 2. The guy in room 2 can’t move into room 3 until the guy in room 3 moves into room 4. The guy in room 3 can’t move into room 4 until the guy in room 5 moves into room 6. And so forth.
So when will room 1 be available? Aren’t all these guys waiting on the next room to open up for them?