One of the features of infinite sets (in the presence of the usual axioms of set theory, this can in fact be taken as the defining feature) is that an infinite set has proper subsets of the same cardinality. For example, the set of even natural numbers is a proper subset of the set of all natural numbers, yet the two sets have the same cardinality. (This feature of infinite sets is responsible for the following fact about infinite limits that you likely learned in high school calculus: is on the famous list of ‘indeterminate forms.’ If you try to evaluate an infinite limit and obtain , then you do not yet have an answer. You must be more clever.) The same is obviously not true of finite sets; if you take an element away from a finite set, it always becomes strictly smaller.
For this and other reasons, our well-developed intuitions about finite sets, which we encounter every day, often fail to extend to the realm of the infinite. This week, we will look at infinite situations in which our intuition fails us. And in each case, the root of this failure of intuition will be the fact that infinite sets have proper subsets of the same cardinality. Today, we will look at the countably infinite (i.e. at infinite sets of the same cardinality as the set of natural numbers). On Thursday, we will move to the uncountable, which will require us to develop some more mathematical sophistication.
I must first make an obligatory mention of Hilbert’s Hotel, David Hilbert’s famous thought experiment about a hotel with infinitely many rooms that has no vacancy but always has room for more guests. Hilbert’s Hotel is one of those subjects that has been dealt with well by many people, so I’ll let TED-Ed and Jeff Dekofsky do my work for me.
What I really want to share today, though, is a thought experiment brought to my attention by Miklós Erdélyi-Szabó, the professor of my mathematical logic class during the semester I spent in Budapest. The situation is as follows. You have a room. Every night, while you are asleep, a demon comes into your room. First, the demon puts two gold coins into your room. Next, the demon removes one gold coin from your room. Then he leaves. Otherwise, he does nothing, and the gold coins are otherwise untouched and, unless removed by the demon one night, allowed to accumulate in your infinitely expandable room. How many gold coins are in your room after infinitely many nights? (Where ‘infinitely many’ here means what you think it means: a countably infinite sequence of nights whose temporal order is the same as that of the natural numbers.)
Your first thoughts are probably roughly like this: at the end of each night, you have one more gold coin than you had when the night started. Therefore, at the end of infinitely many nights, you must have infinitely many coins. Upon further thought, though, you might begin to feel uneasy. You might realize that what you’re dealing with is something like (the demon has added infinitely many coins to your room but also taken infinitely many away) and conclude that the situation is indeterminate. And here you would be right. In fact, in my statement of the problem, I have not given you enough information to determine the answer.
Let’s reformulate the problem, being a bit more careful. In fact, let’s formulate the problem in two different ways, using our old friends Ada and Bertrand, who we last saw playing an infinite round of Hypergame. Ada and Bertrand are neighbors, and they live around the corner from the Hilbert Hotel. Every night, a demon comes into each of their rooms, and, in each one, first adds two gold coins to the room and then takes one gold coin away and destroys it. This demon is tidy, though, and, in each room, places all of the gold coins in a single stack. Once the coins have been put in the stack, their relative order never changes as long as they remain in the room. In Ada’s room, every night the demon puts two gold coins on top of the stack and them removes a coin from the top of the stack. In Bertrand’s room, the demon puts two gold coins on top of the stack and then removes a coin from the bottom of the stack. After infinitely many nights, how many gold coins do Ada and Bertrand each have?
Take a minute to think about this problem now, and then come back for the solution.
At first glance, Ada and Bertrand seem to be in exactly the same situation. But more careful analysis will reveal that, counter-intuitively, their fortunes diverge wildly after infinitely many nights.
To allow us to think about the problem, let’s fix some notation. Suppose that the coins the demon adds to each room are numbered (mentally, if not physically). Suppose the midnight visits start on Night 0 and, on Night , where is any natural number, the demon adds Coins and to the top of the stack in each room, with Coin put on the stack first and Coin put on top of it. Thus, on Night 0, Coins 0 and 1 are added to each room; on Night 1, Coins 2 and 3 are added to each room, and so on.
Let’s first consider the case of Ada. On Night , after Coins and are added to her stack, the top coin of the stack is removed. The coin that is removed on Night , therefore, is Coin . The coins that get removed from Ada’s stack, then, are exactly the odd-numbered coins. The even-numbered coins stay forever. After infinitely many nights, Ada still has all of the even-numbered coins; in particular, she has infinitely many coins.
Now turn to Bertrand. Let’s think about the first few nights. On Night 0, Coins 0 and 1 get added. Coin 0 is then the bottom coin on the stack, so it gets removed. On Night 1, Coins 2 and 3 get added. The bottom coin on the stack after this, though, is Coin 1, so Coin 1 gets removed. Similarly, on Night 2, Coins 4 and 5 get added and Coin 2 gets removed. You should see an obvious pattern here, and indeed it’s easy to prove that, on Night , the demon always removes Coin from Bertrand’s room. I thus claim that there are no coins left in Bertrand’s room after infinitely many days. For how could there be any? If there is even a single coin in Bertrand’s room, it would have to have a number. Suppose this number is . But now you have an immediate contradiction, since Coin was removed from Bertrand’s room and destroyed on Night ! Even though Bertrand’s stack of coins was steadily growing throughout the process and is at all times the same size as Ada’s, in the end he is left with nothing.
P.S. The story has a happy ending, even for Bertrand. During this whole process, Ada had a lot of time to spend on number theory (Bertrand just played tennis). At the end, feeling sorry that Bertrand’s fortune vanished, she generously(?) told him that he could have any of her remaining coins whose number cannot be expressed as the sum of two prime natural numbers. So now he has at least two gold coins and knows the answer to Goldbach’s conjecture!