(The idea of using a game with the devil to understand the sizes of infinite sets is due to Raymond Smullyan)
After death, you find yourself near a lake of fire and you hear wailing and gnashing of teeth. Unfortunately, you've stumbled upon hell. The devil approaches you looking positively evil, but he has a smirk on his face. Yes, the devil is in a good mood today, so instead of condemning you to hell for eternity, he decides to play a little mathematical game with you. If you win, he'll send to purgatory (where you'll have to play another mathematical game with God in order to get into heaven).
The game is simple. The devil fixes a certain collection of numbers and tells you what they are. Then, he chooses a number from this collection and holds onto it for all of eternity. On each day, you are allowed to guess what number the devil chose. If you guess correctly, you win. Otherwise, you wait until the next day to try again.
Suppose the collection of numbers consists of the natural numbers between 1 through 100 (remember the natural numbers are the numbers 0,1,2,3,...). If you play foolishly, you may end up in hell forever, for the devil may have chosen 7 while you could (stupidly) guess the number 4 each day. However, there is a clear strategy that will ensure that you will eventually be free. Choose number 1 on day 1, number 2 on day 2, etc. Since the devil never changes his number, you will escape in at most 100 days.
Similarly, if the collection of numbers is any finite set, there is a straightforward strategy. Simply list the finite set in some order, and go through the numbers one at a time. Notice the key fact that you can order the numbers in a list, and then proceed step-by-step through it.
Suppose the collection of numbers consists of all positive natural numbers 1,2,3,... . Although at first glance this looks dangerous, the same strategy works. Choose 1 on day 1, then choose 2 on day 2, then 3 on day 3, etc. Again, since the devil doesn't change his number, you will eventually be set free (if the devil chose number n, it will take you n days to escape with this strategy). The only difference here is that we no longer have an upper bound on the number of days that we can expect to spend in the tropical wonderland of hell. Notice that our strategy still involved listing all the possible elements, and running through them one by one.
Suppose the collection of numbers consists of all integers, i.e. the natural numbers and all of their negatives ..., -2, -1, 0, 1, 2,... . This looks bad. The above strategy of choosing 1 on day 1, then 2 on day 2, etc. will not guarantee safety since the devil could have chosen -7. Stop for a minute and think about a possible strategy to ensure your eventual release. It would be nice if we could list the integers in some manner so that we have a first integer, then a second integer, then a third integer, and so on while still exhausting them all. How can we do this? The key is to stop thinking that you have to list them in order. We are free to jump around in any way that we would like. What if instead of trying to run through all of the positive numbers first, we jump back and forth from a positive, to a negative, then back to a positive, and so on? How about if we list the integers as follows: 0,1,-1,2,-2,3,-3,... ? This gives us exactly what we desired, a listing of all the integers. Hence, we can still ensure that we win the game by choosing 0 on day 1, then 1 on day 2, then -1 on day, then 2 on day 4, etc.
Suppose now that the collection of numbers consists of all positive rational
numbers, that is all positive fractions. Can we form a list of all of these
numbers? Now this looks impossible. After all, the rational numbers are dense in
the sense that between any 2 rational numbers sits a third (if we are given
fractions a/b and c/d, then (a/b + c/d) / 2 = (ad + bc) / (2bd) lies between
both of them). How can we possibly list them all? Once again, spend a little
time thinking this over, and try to develop a strategy. Given any positive
natural number n, we can list all of the rational numbers with denominator n.
For example, if n=3, we can list all of the rational numbers with denominator 3
as follows: 1/3, 2/3, 3/3, 4/3, 5/3,... . The problem is that we have to form
one list which traverses infinitely many such lists, one for each possible
denominator. Again, the key is to jump around from list to list. Imagine having
each of the lists sitting before us in the following 2-dimensional grid:
1/1, 2/1, 3/1, 4/1, 5/1, ...
1/2, 2/2, 3/2, 4/2, 5/2, ...
1/3, 2/3, 3/3, 4/3, 5/3, ...
1/4, 2/4, 3/4, 4/4, 5/4, ...
1/5, 2/5, 3/5, 4/5, 5/5, ...
...
Can we unravel this into one long list? The answer is a bit tricky, and consists
of following the *diagonals* in order. First, we list the numbers on the first
diagonal, i.e the fraction 1/1. Next we list the numbers on the second diagonal,
i.e. 1/2 and 2/1. We continue with the third diagonal (1/3, 2/2, 3/1), then the
fourth diagonal (1/4, 2/3, 3/2, 4/1), etc. Thus, our list will start out reading
1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, etc. The cleverness of this
approach lies in the fact the each diagonal has only finitely many fractions, so
we can finish off one diagonal before moving on to the next. Notice that we have
listed some fractions twice (since 1/1 = 2/2 for example), but we can just pull
these duplicates out of the list if we cared about efficiency. The important
fact is that by listing the numbers in this way, we have a strategy that
guarantees our eventual freedom.
Exercise: What if the collection of the numbers consists of all rational numbers (positive and negative fractions, along with 0)? Can we still list this collection?
You may begin to wonder whether there is any collection of numbers which precludes us from devising a winning strategy. Can all collections be listed as above? What if the devil chose the collection of all real numbers (which for now we can think of as all infinite decimals, but see ---- in order to fully understand the technicalities of such a view)? This looks even more hopeless that the rational numbers. Spend some time thinking about a strategy. After some reflection, you may throw your hands in the air and exclaim "It can't be done!". We need to be careful though. At first glance, it looked impossible to win when the collection was the rational numbers, but we were able to escape using some cleverness. Perhaps we just aren't ingenious enough to devise the correct strategy. Is it possible to rigorously prove that no possible strategy can guarantee safety?
The surprising answer is yes, we can rigorously prove that every strategy is
flawed. The idea is subtle and clever. We will take an arbitrary strategy, that
is, any list of real numbers, and show that some real number fails to appear in
the list. Suppose that r_1, r_2, r_3, etc. is a list of real numbers (so the
purported strategy is to guess r_1 on day 1, then r_2 on day 2, then r_3 on day
3, etc). We construct a new real number s between 0 and 1 by describing each
digit after the decimal point. To determine the first digit after the decimal
point, we simply pick a number different than the first digit after the decimal
point of r_1. To determine the second digit after the decimal point, we pick a
number different than the second digit after the decimal point of r_2. Continue
by making digit n of s different from digit n of the number r_n. An example will
help. Suppose we have the following list:
r_1 = 3.14159...
r_2 = 12.00000...
r_3 = .32145...
r_4 = 83.45454...
r_5 = 2.71828...
...
We determine s as follows. Make the first digit of s after the decimal point
different from the first digit after the decimal point in r_1. In this case,
that means different from 1. Make the second digit of s different from the
second digit after the decimal point in r_2. In this case, that means different
from 0. Similary, the third digit should be different from 1, the fourth digit
different from 5, and the fifth digit different from 8. This process is called
diagonalization, since we going down the diagonal (in this case the diagonal
starts out as 1,0,1,5,8,...) changing every number we encounter. To be precise,
choose the digit 1 whenever possible (whenever 1 is different from the diagonal
element), and 2 otherwise. Thus, the s that we construct in this case will start
out as .21211... . What have we done? We've created a real number, and the trick
is to notice that it does not appear in the list. The reason it does not appear
is because it differs from each number r_n in the position n after the decimal
point by construction. Hence, if the devil chose the number s, then we would
never escape.
We have just shown that real numbers can not be listed like the other infinite sets that we have encountered. In some sense, every other infinite set above has the same size, but the real numbers somehow have *more* elements than each of them.
back to diversions