number can be placed in one-to-one correspondence with each other; just
as a child matches a set of three stars with a set of three cookies. Second,
a finite set cannot be matched one-to-one with a set of lesser cardinal-
ity—and in particular, it cannot be matched one-to-one with a proper
subset of itself. If a child starts with three cookies, and eats one, the re-
maining two cookies cannot be matched one-to-one with the original
three cookies.
Hilbert’s Hotel
The German mathematician David Hilbert devised an interesting way of
illustrating that the set of all integers can be matched one-to-one with a
proper subset of itself. He imagined a hotel with an infinite number of
rooms—numbered R1, R2, R3,.... The hotel was full when an infinite
number of new guests, numbered G1, G2, G3,... arrived, requesting
accommodations. Not willing to turn away such a profitable source of
revenue, and being willing to discomfit the existing guests to some ex-
tent, the proprietor moved the guest from R1 into R2, the guest from R2
into R4, the guest from R3 into R6, and so on—moving each guest into a
new room with twice the room number of his or her current room. At the
end of this procedure, all the even-numbered rooms were occupied, and
all the odd-numbered rooms were vacant. The proprietor then moved
guest G1 into vacant room R1, guest G2 into vacant room R3, guest G3
into vacant room R5,.... Unlike every hostelry on planet Earth, Hilbert’s
Hotel never has to hang out the No Vacancy sign.
In the above paragraph, by transferring the guest in room N to room 2N,
we have constructed a one-to-one correspondence between the positive in-
tegers and the even positive integers. Every positive integer is matched with
an even positive integer, via the correspondence N ↔2N, every even positive
integer is matched with a positive integer, and different integers are
matched with different even positive integers. We have matched an infinite
set, the positive integers, in one-to-one fashion with a proper subset, the
even positive integers. In doing so, we see that infinite sets differ in a sig-
nificant way from finite sets—in fact, what distinguishes infinite sets from
finite sets is that infinite sets can be matched one-to-one with proper sub-
sets, but finite sets cannot.
Ponzylvania
There are all sorts of intriguing situations that arise with infinite sets.
Charles Ponzi was a swindler in early twentieth-century America who
devised plans (now known as Ponzi schemes) for persuading people to
16 How Math Explains the World