Hilbert's paradox of the Grand Hotel

https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel

by vinnyglennon • 11 years ago

26 27 11 years ago

en.wikipedia.org

mfoy_• 11 years ago

"If an infinite set can be put into one-to-one correspondence with the natural numbers (N) it is called a countable set. Otherwise it is uncountable."[1]

This paradox hinges on the strange notion of cardinality of infinite sets. Specifically, the set of all even integers, the set of all odd integers, and the set of all integers(!) have the same cardinality, and therefore the same "size".

---

[1]http://www.math.ups.edu/~bryans/Current/Journal_Spring_1999/...

GhotiFish• 11 years ago

I like this paradox for it's simplicity, but there's just one aspect that cracked me up.

Suppose the hotel is next to an ocean, and an infinite number of aircraft carriers arrive, each bearing an infinite number of coaches, each with an infinite number of passengers.

hahaha.

How would we extend that?

suppose we have an infinite number of passengers, carried by an infinite number of coaches, transported by an infinite number of aircraft carriers, shoved in by an infinite number of tsunamis, which occur on an infinite number of continents, on an infinite number of Dyson spheres...

URSpider94• 11 years ago

A related derivation of the "uncountably infinite" is Cantor diagonalization: https://en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Put in more concrete terms (hard to say when we are talking about infinities): there are an infinite number of integers. For each integer, there are an infinite number of real numbers (decimals) between n and n+1. For each of those doubly-infinite real numbers, there are an infinite number of complex numbers with that real component and varying imaginary components. And so on ...

In fact, there are an infinite number of infinities ...

It's turtles all the way down.

lukasb• 11 years ago

That's the clearest, most concise explanation I've seen for how different infinite sets can have different cardinalities. Thanks!

yongjik• 11 years ago

Wait, but between n and n+1 there are also an infinite number of rational numbers, but the cardinality of all rational numbers is the same as that of integers (or that of all rational numbers between a fixed n and n+1).

So, while what the gp wrote is correct, it's not an explanation of why there are more real numbers than integers.

mikeash• 11 years ago

I don't think the summary in the comment is correct, though. There are also an infinite number of rational numbers between any given integer n and n+1, and indeed an infinite number of rational numbers between any two rational numbers, yet the cardinality of the rationals is still the same as the cardinality of the integers.

Diagonalization is brilliant, though!

buzzdenver• 11 years ago

It's a little confusing though, at least for me. There are infinite integers, and "doubly-infinite" reals. But there are also only "doubly-infinite" complex numbers.

IMO the easiest way to illustrate different, and infinite number of, infinities is to think of sets. Suppose you have N-infinite number of things, say triple-infinite to use the grandparent's lingo. Now the number of sets that you can create from these triple-infinite objects is greater than triple-infinite, and it's called quad-infinite. You can prove that indirectly. Assume that there is a one to one mapping of the original object to the sets. That means that some of the objects are mapped to sets that the objects are members of (let's call these red objects), others not (let's call them blue objects). Does the set of blue objects get paired with a blue or a red object ? Cannot be either, so we've reached a contradiction, ergo there are always more subsets of things than things.

lgandersen• 11 years ago

Just to clarify a little bit: For each integer n there is also an infinite amount of rationals (fractions) between n and n+1 and the rationals is also a countable set like the integers (just as 'infinite', so to speak). Quite counter-intuitive, I think.

I usually interpret the first steps in Hilbert's hotel as the first steps in the ordinal hierarchy (https://en.wikipedia.org/wiki/Ordinal_number).

pdkl95• 11 years ago

Vi Hart has a few interesting videos on infinity:

"Proof some infinities are bigger than other infinities" (w/ Cantor's diagonal proof)

https://www.youtube.com/watch?v=lA6hE7NFIK0

"How many kinds of infinity are there?" (a very good list including surreals, P-adic, the long line, others)

http://vihart.com/how-many-kinds-of-infinity-are-there/

Also, I support her suggestion in "Infinite Trees Are Super Weird" that since we call uncountable line segments the "long line", we should call the uncountably-branching tree the "big tree".

https://www.youtube.com/watch?v=BEz-vGJvaik

lancefisher• 11 years ago

And here's a great book that explains it to children: http://www.amazon.com/The-Cat-Numberland-Ivar-Ekeland/dp/081...

ntoronto• 11 years ago

I've posed exactly these problems to children about 15 times now. Most children 10 and up I've talked to can figure out the first (one more guest) easily enough, the second (an infinite bus of new guests) with a little help, and the third (infinitely many infinite buses) if I draw a picture.

It helps a lot to be precise and use concrete examples. "Hilbert has an infinite hotel. We have to be careful with infinities, though, so I'll tell you what that means. If you think of a number zero or bigger, any number at all, Hilbert's hotel has a room with that number on it. Think of a number. ('2 million!') Yep, he's got that room. ('Six googolpillion!') Yep, he's got that room."

"A guest comes into the hotel and asks, 'Mr. Hilbert, do you have one more room?' Mr. Hilbert says, 'Sure!' He picks up his magic phone that calls everyone in the hotel at the same time and gives all the guests exactly the same message. After they do what he says, there's one room empty. What does he tell them to do?"

When they invariably come up with "Move up one room," it helps to belabor a couple of points. First, reformulate it as, "Look at your room number, add 1, and go to that room." (This helps them figure out "Multiply your room number by 2" as the answer to the second problem.) Second, dwell on who goes where, and whether it's a problem. "Where does the guest in room 0 go? ('Room 1.') Doesn't that have someone in it? ('Yes. Oh, no it doesn't, because he went to room 2!')"

No child has figured out my favorite fourth problem, but then it took mathematics until Cantor to figure it out, too.

"An uncountable group of people shows up at the hotel. Let me tell you what that means. They all have infinite name tags, all filled with As and Bs. Every possible name tag is in the group. [Give example names. Blow raspberries to do it.] The head of the group, whose name is 'AAAAAAAAAAAAAA...' [said with a blank look, trailing off] asks Mr. Hilbert if he has room in his hotel. Mr. Hilbert says 'No!' Why does he say that?"

Let them stew for a bit, and ask questions. Going on: "Mr. Hilbert says, 'OK, tell you what. If you give me a room assignment, I can always find someone you left out.' How does Mr. Hilbert do that?"

You can illustrate this with a game, using only four-letter names. Write down something like

AAAA BBAA BABA AABA

"Can you find a four-letter name that's missing?" Play this a few times, and then ask, "Can you come up with an easier way that doesn't make you think of all the names in turn?" Show them how to flip the letters along the diagonal, and then extend to infinite names.

I've had 2 kids and 1 adult follow this to the end. It's always mind-blowing for them, though, no matter how far they get. I follow up with this:

"That stuff they taught you in school, that stuff a lot of people say they hate, is arithmetic. This is math."

EDIT: Come to think of it, I actually helped a friend's 11-year-old daughter decide that she didn't hate math using these problems. She's probably still bummed about being stuck doing arithmetic for now, though...

rootedbox2• 11 years ago

Maybe this is my ignorance of the understanding of countably infinite. But if a hotel has infinite amount of rooms, and all rooms are full. Then why would anyone ever show up to take another room.. To me it would seem that all persons are in the hotel already.

Retra• 11 years ago

You might have an uncountably infinite number of people to draw from. Or really, just 'more people' in another form.

Let's say your hotel is filled with even numbers. There are plenty of numbers not in the hotel that you could add.

NotAPerson• 11 years ago

Imagine you have one person for each (positive) integer, given a unique integer ID at birth, and a hotel with countably infinite rooms, each with a unique room number.

The hotel could have someone in everyone room if every person with an even number as their ID was staying there. That is, for every room number, twice the room number is a unique even number, so there's a 1-to-1 correspondence between the number of rooms and the even integers.

You could then have someone with an odd number ID show up looking for a room, and would have to rearrange from a stay-in-half-your-ID lineup.

It's a (arguably defining) property of infinite sets that they contain a strict subset (at least one guy not in the subset) with the same "size" as the whole set.

So the evens and the integers are an example of this, with both having the same "size", even though the evens are contained in the integers.

rootedbox2• 11 years ago

But the paradox says...

infinite number of rooms are all occupied by a person.. then a person shows up. There is one to one ratio here... of all rooms are occupied by a person.. infinite rooms.. infinite people.. if the infinity of people are all ready in the infinity of rooms..

Then who is showing up? Everyone is already in the rooms.. So no need to worry about moving anyone.

If we change it to be numbers it still doesn't work.. If we have an infinite amount of slots.. and in each slot is a number.. and all slots are full.. how can we make room for another number..

If you say that oh well there were only even numbers in the slots.. well then what you told me isn't true.. all slots aren't full with numbers.. only even numbers..

I understand what the paradox is trying to explain about sets.. but to me it just falls apart as a metaphor.

drdeca• 11 years ago

Suppose people are labeled with positive integers, and rooms are labeled with positive integers.

Suppose first the people labeled with even integers show up, and they each go in the room with half their number. Then each room will have a person.

Then the person with number one shows up, and none of the rooms are empty.

If there are א people that exist, not all collections of א people have all people.

I think I don't have an intuitive understanding of how your intuition works.

unclenoriega• 11 years ago

It seems to me that the only thing that makes this a 'paradox' or is counterintuitive is the idea that a hotel with infinitely many rooms can be full. Is there some math concept that allows this or is it just semantics? It sounds like some sort of "quantum" effect where there's only a room there if you look for it.

gizmo686• 11 years ago

What is the math concept that allows for a hotel with infinitely many rooms in the first place?

One way of (somewhat) formalizing this is to say that you have a set containing infinitely many rooms, and another set containing infinitely many tenants. Intuitively, it does not seem unreasonable that you can give every room its own tenant. Once you do this, then the hotel is "full" in the sense it is impossible to find an empty room.

Of course, we can also think about giving each tenant her own room, which also seems possible. If we can do both of these things, we say that the set of rooms is the same size (or cardinality) as the set of tenants. It is worth noting, that not all infinite sets are the same size [0]. For the purpose of Hilbert's paradox, I believe it is far to assume that we are dealing with countably infinite sets [1]. The mathematical result in Hilbert's paradox is that if you add elements to a countably infinite set, the result is still countable infitite.

[0] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

[1] That is to say, sets which are as large as the set of natural numbers.

deckar01• 11 years ago

I think the term full needs to be defined for an infinite hotel. Instead of defining full as occupancy equal to capacity, it might be more useful to define it as vacancy equal to 0.

mcguire2• 11 years ago

The trick is that the set

N1 = { 1, 2, 3, 4, 5,... }

can be set into a one-to-one relationship with the set

N2 = { 2, 3, 4, 5, 6,... }

by the function

f(n1:N1) -> N2 = { n1 + 1 }

(Using a notation I pulled out of my flying monkeys right at this moment.)

The first set, N1, is the state of the hotel with one guest in every room, i.e. { n | room n is occupied }. The second set is the state of the hotel after Mr. Hilbert's operation, with room 1 empty.

The meta-trick is that an infinite set can be put into a one-to-one relationship with some proper subsets of itself (that's one definition of "infinite", by the way).

plonh• 11 years ago

Yes. Infinitely large sets are decidedly unphysical, and taking the metaphor too literally can be misleading.

Imagine: how could the proprietor even communicate with those infinite guests?

semi-extrinsic• 11 years ago

What's really cool is that physicists have recently been able to realize experimentally some of the room changing operations in Hilbert's hotel, using quantum systems:

https://physics.aps.org/synopsis-for/10.1103/PhysRevLett.115...

tunafishman• 11 years ago

Situations like these are where math stops being an enlightening view on relationships between quantities and starts being a pedantic chore.

lojack• 11 years ago

Reminds me of the proof showing that the set of all fractions are countably infinite.

mcguire2• 11 years ago

If you're interested in this subject, can I suggest Everything and More by David Foster Wallace? (Yes, that DFW.) Sure, as some reviews describe in painful detail, some of it is mathematically sketchy. On the other hand, it's a pretty good discussion of issues around infinity, such as Zeno's (and everybody else's and their cat's) paradoxes (paradices? paradise?), and why a theory of the infinite is so darn necessary.

Hilbert's paradox of the Grand Hotel

Related Stories