# Hilbert's Hotel and Infinities for Pre-university Students

Hilbert's paradox of the grand hotel is a fun and exciting ground to base a talk on the set theoretic concept of infinity for interested students - even in middle- and high school. However, it does not deal with the question that whether there are different infinities or not.

Question 1. Is it necessary to talk about uncountability of $\mathbb{R}$ after a session on Hilbert's hotel paradox?

Question 2. When teaching gifted middle school students, is it appropriate to use Cantor's diagonal argument to prove that $\mathbb{R}$ is uncountable? Can one hope the students grasp the idea of the proof? How can the idea be illuminated?

• In my opinion, the answers are (1) No, (2) Yes. – DonAntonio Nov 18 '13 at 20:10
• For your second question, see here for an illumination of the argument (which is appropriate for gifted middle school students). For your first question, it certainly isn't necessary, but it may be desirable. – Cameron Buie Nov 18 '13 at 20:12
• @DonAntonio Shouldn't one be afraid that the students come to believe that every two sets with infinitely many elements are of the same cardinality? – Behzad Nov 18 '13 at 20:14
• infinity equals negative zero – EpicGuy Nov 19 '13 at 9:23
• Your students may be interested in supposedly the largest set of all: the so-called Universal Set, the set of everything. They should be able to understand a proof -- a variant of Cantor's diagonal argument -- that such a set cannot exist, and the corollary that every set must exclude something. It is covered in detail in the tutorial (Example 10) that comes with my proof-writing freeware available at my website dcproof.com – Dan Christensen Nov 20 '13 at 5:52

Real numbers are best avoided until properly treated, which requires a fair dose of analysis. Uncountability can be demonstrated on other sets. I had, on several occasions already, explained Hilbert's Hotel to kids of various ages. After the hotel seems never to fill up, I bring in an infinite amount of families to the hotel. Each family has a child. Each child has an infinite string of toys. There are two kinds of toys only, so each child has an infinite string of just these two types of toys. The diagonal argument is then given by hypothesizing each family gets a room, and then looking for the kid whose string of toys is the complement of the diagonal string. Voila, the hotel can't accommodate all families.

Alternatively/complimentarily, you can prove Cantor's Theorem (that the power set of a set is always of larger cardinality than the set) to almost anybody.

• I think you mean "fair dose", no? :-) – Asaf Karagila Nov 18 '13 at 21:29
• @Ittay Weiss Thanks. – Behzad Nov 18 '13 at 21:56
• @AsafKaragila thanks! I needed a fair dose of grammar checking ;) – Ittay Weiss Nov 18 '13 at 23:08

I see no reason you need to get into uncountable sets if you just want to play around with weird things that can happen with infinite sets.

As for your second question, I remember seeing the argument for uncountability of $\mathbb R$ in elementary school and it stuck pretty well then, and I don't consider myself to have been especially precocious, so I see no reason why we can't get middle school students to understand it as well. (We glossed over some nuances about repeating $0$'s vs. repeating $9$'s in the decimal expansion, but of course a clever choice of renumbering obviates this issue.)

I disagree with Ittay and Asaf. Sure, the definition that most students have of $\mathbb R$ (usually something inane like all the rationals plus all the irrationals) makes for poor mathematics, but they work with real numbers anyhow and decimal expansions are all you need. And the uncountability of $\mathbb R$ is a more compelling topic than the uncountability of the set of infinite binary sequences, which students never work with.

Let me just say if you're going to get into the uncountability of $\mathbb R$, you probably want to illustrate that $\mathbb Q$ is countable (or at least the positive rationals), since 1) this isn't at all obvious at first exposure and 2) it makes the fact that $\mathbb R$ is uncountable more interesting.

While my own experience tells me that you absolutely can teach Cantor's diagonal argument to pre-university students, I have also seen some university students fail to grok Cantor's diagonal argument, so here's two things that make it more digestible:

I've seen people use the following game as a warm-up to Cantor's diagonal argument. Player 1 starts by writing down a sequence of $X$'s and $O$'s of length $n$. ($n=5$ seems to be about right for communicating the idea.) Then Player 2 writes down a single $X$ or $O$. After $n$ turns of this, Player 2 has a sequence of length $n$, and he wins if it is different from any of the sequences Player 1 has written down, and Player 1 wins otherwise. Player 2's winning strategy is of course Cantor's diagonal argument.

I also like to introduce Euclid's proof that there are infinitely many primes as a prelude to showing $\mathbb R$ is uncountable. The basic logical outline is the same: every finite list omits a prime, and every countably infinite list omits a real number. I think doing Euclid first is a nice way of modelling the basic architecture of the proof so that the logical structure is a bit easier to follow. Plus, Euclid's proof is beautiful and interesting in its own right.

• Uncountable sets can still be accountable, you know. $\Bbb R$ included. :-) – Asaf Karagila Nov 18 '13 at 20:57
• @AsafKaragila Oh my! That's one of the more amusing typos I've seen in a while. – Brett Frankel Nov 18 '13 at 21:00
• I'm gonna hold you accountable for it! ;-) – Asaf Karagila Nov 18 '13 at 21:02
• @BrettFrankel Thanks. Do you know which book has the game you mentioned first appeared? – Behzad Nov 18 '13 at 21:55
• My wife was a TA for a course that used amazon.com/The-Heart-Mathematics-invitation-Mathematical/dp/… That's how I heard of it. – Brett Frankel Nov 18 '13 at 22:03

Question 1. Is it necessary to talk about uncountability of R after a session on Hilbert's hotel paradox?

No, not on the first day—an introduction to the concept that additional rooms can be made available by just re-arranging people in a hotel with no vacancy is enough to chew on for one day. I might even split this up into two days.

On day one, show how 10 new people can be given rooms by having everyone move into room N+10. This frees up rooms 1-10. For homework, ask how can the hotel accommodate an infinite number of visitors, one for each occupied room? A second discussion after the students have given this some thought would be productive.

Question 2. When teaching gifted middle school students, is it appropriate to use Cantor's diagonal argument to prove that R is uncountable? Can one hope the students grasp the idea of the proof? How can the idea be illuminated?

The late Herbert Enderton who wrote Elements of Set Theory had an excellent introduction to this:

Say you are in pre-school, and you've heard that they have mathematics lessons, and are hesitant to attend because you can only count up to 3. [Show on the whiteboard/projector a picture of 5 houses and 5 people.] Sure enough, on the first day they show you this many houses and people, and ask if there are as many houses as there are people?

Your heart sinks. How can you possibly answer this if there are more houses and people than you can count? [Ask students for answers.]

So you pick up your crayon, and match houses to people in a one-to-one correspondence. Since there are none left over, you know there are as many houses as there are people. And you didn't have to count past 3.

There are infinite sets larger than we can count, so we will apply the same logic as we did in pre-school with the crayon. Etc.

• That is the single most tangible analogy for cardinality that I have ever heard. Thank you +1. – Eric Stucky Nov 18 '13 at 23:42