Hilbert's Hotel and Infinities for Pre-university Students

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.