The Hilbert Hotel

http://opinionator.blogs.nytimes.com/2010/05/09/the-hilbert-hotel/

by dhotson • 16 years ago

124 79 16 years ago

opinionator.blogs.nytimes.com

ynniv• 16 years ago

Hard math is the hardest thing that I can think of. One can learn most other things with enough effort (ie, repetition), but hard math takes immense thought.

On the other hand, it is also rarely necessary.

jallmann• 16 years ago

Are fun things ever really necessary?

Locke1689• 16 years ago

Eh, number theory has a certain draw to it. For one, if you're presented with a problem ostensibly you have all the tools you need to solve it (or you have all the tools you need to build all the tools you need to solve it). There are certain sections of math which I am certainly poor at (complex analysis has just never "clicked" in that way with me) and some sections of math which I'm pretty good at (I have a certain affinity for graph theory). I think different problems require different mindsets in approach. If that mindset comes easier to you then solving problems in that domain may come easier too.

npp2• 16 years ago

"Hard" is of course highly subjective, but the material in this article is standard (usually sophomore-junior) undergrad material and is very widely used.

btilly2• 16 years ago

Very widely used for non-useful uses of used. There aren't a lot of infinite sets in applied math. (The closest thing that I can think of to an actual application was http://xkcd.com/195/ and the same trick has since been used for visualizing other complicated large linear sets.)

tokenadult4• 16 years ago

I was just teaching a class on this topic (Hilbert's Hotel, and the cardinality of infinite sets) to a group of elementary-age learners last Saturday morning. These ideas have a lot of appeal, and if young learners find out early that infinity is not a number, but is a very deep concept, they can gain a lot of motivation for thorough study of math.

jacoblyles2• 16 years ago

I divide proofs into two groups:

1) Clever little things

2) Long, hard slogs

Cantor's proof is a clever little thing. These sorts of proofs can be daunting at first but they become easier, even delightful, as one becomes more familiar with their kind. If you studied the foundations of math in school for as long as an American student takes English literature courses then these proofs would be second nature to you. They aren't really hard, just written in a language unfamiliar to most people.

Then there are the long, hard slogs. Lemma after lemma, with no clue as to where the author is leading, until finally, after an exhausting march, he bludgeons the reader into accepting his conclusions. These are pretty hard for anybody to understand because you can't hold the whole thing in your head. You just have to convince yourself of the truth of each step.

stanleydrew5• 16 years ago

You're leaving out a fairly large middle ground of boring medium-length proofs. See, e.g. construction of the reals from the rationals using Dedekind cuts in Rudin's book: http://en.wikibooks.org/wiki/Real_Analysis/Dedekinds_constru....

zemaj• 16 years ago

I've never liked these thought experiments with infinity in them. They always have "and so on" in them. But if you're dealing with an infinite set, "and so on" can't complete during the life of the universe (or well, ever). This in itself seems like it solves the problem - you can never get pass the first step. It's an event horizon, literally.

jacoblyles2• 16 years ago

Use lazy evaluation and avoid iterating over an infinite set.

ionfish3• 16 years ago

So you don't accept inductive proofs? This will rather limit the amount of mathematical tools available to you.

igravious• 16 years ago

Yo!

Not only that but the obviousness of "and so on" is often elided. "And so on" assumes unbounded time and/or resources and also assumes you know intimately the (undoubtedly recursive) algorithm and can codify it. These proofs often blatantly ignore that _in practice_ someone or something must perform this algorithm. (Er, not sure if I used elided correctly back there.) Anyhow, if you have an innate distaste for these types of proof then rest assured that you are not alone.

You may check out the esoteric philosopher René Guénon, R. (1946) The Metaphysical Principles of the Infinitesimal Calculus http://books.google.com/books?id=9KyLPwielTEC

Also check out intuitionism by keerazy Dutch mathematician L.E.J Brouwer which asserts that we must essentially modify some preconceived logical tenets/laws in the face of infinity.

See also intuitionistic logic, intuitionistic type theory and constructivism (mathematics). http://en.wikipedia.org/wiki/Constructivism_(mathematics)

Apologies if you were aware of all this already. I have found it very helpful to respect my suspicions. Regardless of what people may tell you, this stuff is neither simple nor straight-forward once you start thinking deeply enough about the minutiae.

cousin_it6• 16 years ago

if you're a programmer, disbelieving in infinity is a crippling flaw, because big-O analysis of algorithms faces the exact same kind of "event horizon" that you speak of.

I've never liked people who don't understand math and dress it up with philosophical gook. Math is a practical matter, not high philosophy. If you don't know math, your bridges will fall down and your airplanes won't fly.

ionfish3• 16 years ago

The application of mathematics is a practical matter; I am not entirely sure what "high philosophy" is, but mathematics is also a conceptual, abstract discipline which can be investigated with no concern whatsoever for practical applications.

The reliance of analysis on Cauchy sequences is not "philosophical gook". zemaj may be naïve in her conclusions (or at least unaware of just how much mathematics one must give up when one takes a constructivist view), but she is hardly alone in her hesitancy about infinity. I wouldn't be sure what to make of the claim that Brouwer, Markov or Martin-Löf didn't know mathematics.

dagw2• 16 years ago

I wouldn't call not understanding the theoretical underpinnings of big-O analysis a "crippling flaw" for a programmer. As long as you understand what it means that an algorithm is O(2^n) and what limitations that entails, then you're grand. If you can also look at an algorithm you've written and work out what its big O complexity is then you know more than most programmers. Both of those can trivially be done without ever touching infinity.

Equally if all you care about is working out if your bridge is going to fall down, you don't really have any need for infinity. In fact you can spend an entire career using math to do all kinds of really awesome things without ever actually understanding math. I'd say that a good 95% of engineers fall into that last category, and I'm certainly not worried about driving over bridges because of it.

sesqu2• 16 years ago

f ∈ Ο(g(n)) iff ∃c,n₀ ∀n>n₀ : f(n)≤c*g(n)

No infinity required.

jgrahamc2• 16 years ago

Well, it's a thought experiment so you don't have to worry about constraints of time and space.

davidkellis• 16 years ago

This is a good read.

In a class I took with my thesis advisor, he explained the Hilbert Hotel similarly, and it was as entertaining then as this is now.

fredBuddemeyer2• 16 years ago

if you want to get your head around infinity note that one of the greatest novelists of our time, david foster wallace, wrote a great book about it and cantor: "everything and more".

on a more sensational note, also note that wallace and cantor, both geniuses, also both committed suicide.

gruseom• 16 years ago

I don't think it's true that Cantor committed suicide. Wikipedia mentions no such thing, and the bio at http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Cant... says he died of a heart attack at 72.

fredBuddemeyer2• 16 years ago

you're right

http://www.cosmolearning.com/documentaries/dangerous-knowled... is wrong

ionfish3• 16 years ago

They both suffered from severe depression. Only Wallace committed suicide.

canoebuilder• 16 years ago

"and that you’re convinced that any particular person will be reached in a finite number of steps."

How can any point in an infinite set be reached in a finite number of steps? For that to be the case, isn't the set in question necessarily a finite set between 0 and infinity?

stanleydrew5• 16 years ago

Take the set of natural numbers. Pick any one and count to it. The set of natural numbers has infinite cardinality, but any particular member of the set is finite and can be reached in a finite number of steps.

todd3834• 16 years ago

I listen to a lot of Dr. William Lane Craig and he speaks often about Hilbert's Hotel. Here is a pretty good video on the subject http://vids.myspace.com/index.cfm?fuseaction=vids.individual...

stanleydrew5• 16 years ago

The actual contradiction proof that the reals have larger cardinality than the natural numbers uses the binary representation of decimals. See Cantor's diagonal argument: http://en.wikipedia.org/wiki/Cantors_diagonal_argument.

benmathes• 16 years ago

It doesn't require binary representation at all. You can write down all the numbers in any base and the argument still holds.

stanleydrew5• 16 years ago

Yes, clearly. I just find it interesting that in his original diagonal argument proof he chose the decimal representation.

flatline• 16 years ago

I always found the base-10 argument easier to see at a glance, and most people are probably more familiar with decimal notation. This guy writes to try and make math more popular, so I'd imagine that's his motivation.

For Cantor, I would imagine that the formal proof was simpler to write out using the binary representation. Just a guess.

2rs1• 16 years ago

Am I the only one that has a problem wrapping my head around the infinity times infinity argument?

If you got infinity people on infinity busses, you would only have infinity people, not infinity squared. The moment when you close down the first bus and start with person 1 on bus 2, this person should already be on bus 1, or else must bus 1 be finite.

pilif• 16 years ago

that was IMHO the point of the first part of the article. You would never be able to close down the first bus because it does contain an infinite amount of people, so you need to find a way to process people across buses if you want to process the all.

harpastum• 16 years ago

I think one aspect you're missing is that infinity does not always mean everything. For example, there are infinite decimals between 1.0 and 2.0, and between 3.0 and 4.0 — however, there is no overlap at all between the sets.

That's how I imagined the busses to be; two non-overlapping infinite sets. No one from the first bus was also on the second.

tokenadult4• 16 years ago

The Wikipedia article

http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gran...

relates one method of numbering passengers on the buses to count them (which I found in another source,

http://faculty.cua.edu/glenn/187f09/hilbert_hotel.pdf

which I used to teach my elementary-age class last Saturday the same trick), which shows that countably infinite buses with countably infinite passengers in each bus can still be accommodated by Hilbert's Hotel, even if all rooms are occupied when the buses arrive.

yogipatel• 16 years ago

Did this remind anyone else of continuations and infinite streams?

Bjoern2• 16 years ago

The infinity is a fascinating concept, but be careful it can drive you insane and into madness [1]. At least that happend to Georg Cantor and Kurt Goedel and some other famous minds.

[1] See "BBC: Dangerous Knowledge" e.g. http://www.abdn.ac.uk/modern/node/164

RiderOfGiraffes8• 16 years ago

Much discussion about that programme here:

http://news.ycombinator.com/item?id=797723

http://news.ycombinator.com/item?id=121063

http://news.ycombinator.com/item?id=101255

Frankly, it's a load of crap, and shame on the BBC for having produced it. Contemplating the mathematics of infinity didn't drive them insane, they were already troubled. Hundreds of thousands of mathematicians happily deal with infinity on a daily basis.

What a crock.

jgrahamc2• 16 years ago

Totally agree. That was an awful, awful program. As was the similarly awful thing that "Infinity and Beyond" (http://www.bbc.co.uk/programmes/b00qszch). The truth is that since Cantor we know that infinity is something we can work with in an algebraic pattern and there's really no need for all these BS BBC programs trying to make it look like something totally weird.

Bjoern2• 16 years ago

Thank you for pointing that out to me. I think my opinion of BBC was too high. Have to be more careful.

tokenadult4• 16 years ago

David Hilbert's response:

"No one shall expel us from the Paradise that Cantor has created."

http://en.wikipedia.org/wiki/Georg_Cantor

david9278• 16 years ago

I don't believe in infinity. And most probably the reason is because it doesn't exist.

Every time we expect something infinite in physical phenomenon, it turns out to have some sort of Plank-like constant that compartmentalizes the effect at different levels to avoid that result.

Which is good, because a universe where infinity existed would most likely not be stable enough to support life. I understand that mathematics isn't simply about physical phenomenon. I understand the beauty of i, for example. But I think that screwing around with the bizarre aspects of a concept like infinity is a huge waste of time.

andrew12• 16 years ago

> But I think that screwing around with the bizarre aspects of a concept like infinity is a huge waste of time.

Maybe for you, maybe not for someone who enjoys doing it.

david9278• 16 years ago

Fair enough. But I'm saying, let's get rid of it. Let's kill the concept of infinity, and we'll all be better off for it.

mreid• 16 years ago

> But I think that screwing around with the bizarre aspects of a concept like infinity is a huge waste of time.

It's playing around at the limits of human reason. I don't see it as any different to most sports, music, and art. All are appreciated by different groups of people but, ultimately, "useless" if you do not value the enjoyment gained from exploration for its own sake.

tome2• 16 years ago

What makes you think the universe is finite? As far as I am aware, the prevailing view of cosmologists is that it is finite, but there's certainly plenty who believe it could be infinite.

puredemo• 16 years ago

well the prevailing view of cosmologists is pretty much all we have on that..

RiderOfGiraffes8• 16 years ago

Calculus is pretty tough without infinity. Most of the theory behind fluid dynamics is pretty tough without infinity.

Not knowing that there is an unlimited number of numbers becomes a problem. Trying to do any math without allowing that between any two numbers there's another number is pretty difficult.

There are people who derive a mathematics without the axiom of infinity, but it's weird, distorted, unnatural and doesn't turn out to be as useful as often as the regular variety of math.

Feel free not to believe. Just don't expect to do much advanced math.

Oh, and if you use proof techniques in programming, such as loop invariants or transformation theory, you are using infinity, you just didn't realise it.

david9278• 16 years ago

Sorry for the confusion. I meant infinity, not the limit of infinity.

I have no problem with the concept of infinity in terms of limits, but that's not what this article is about. It's about the concept of infinity itself. And that is what I disagree with.

cousin_it6• 16 years ago

I don't believe in infinity. And most probably the reason is because it doesn't exist.

How about the number three? Does it exist? Or the square root of 2? I can't touch it, that's for sure.

People don't want infinity per se. We want a number system where you can do nice things to numbers and get out other numbers... and have nice theorems like "a continuous graph that goes from negative to positive must cross the zero line somewhere"... and then it turns out that the number system that fulfills our need consists of infinite sequences of digits, and finite sequences won't suffice.

david9278• 16 years ago

Rider has set me straight, but here's my original beef:

I said, quite clearly, "I understand that mathematics isn't simply about physical phenomenon. I understand the beauty of i, for example."

You mention 3 and the square root of 2. You plug both of those in to: (x == x+1) and you'll get an inequality. Not so with infinity.

Again, Rider has set me straight that I need to learn more. I can believe that, but when I see how often in the physical world we creep up on infinity only to have it not exist, I'm definitely skeptical about plugging in infinity into equations like x == x + 1. It seems it doesn't make any sense at all.

_delirium• 16 years ago

Not to express an endorsement in either direction, but you may be interested in the finitist school of thought: http://en.wikipedia.org/wiki/Finitism

or its even stricter cousin, which not only denies the meaningful existence of infinity, but also the meaningful existence of technically finite but infeasibly large numbers: http://en.wikipedia.org/wiki/Ultrafinitism

jerf• 16 years ago

See also Constructivism: http://en.wikipedia.org/wiki/Constructivism_(mathematics) . And the concept of "computable numbers": http://en.wikipedia.org/wiki/Computable_number

That said, I will point out that math is essentially a game played by certain rules known as "axioms", and there is no one true set of axioms. If you choose one set, you get infinity; if you choose another, you don't (but you will pay for that). You can't say which is "more right" or "more wrong" without bringing other subjective standards into it, each of which may have their own utility. While "corresponds to the physical universe" is definitely one useful such standard, it is still not the only one.

Do read up on the limits of computable numbers though; they are interesting, but it's not a free lunch.

amalcon• 16 years ago

When we talk about infinity, we never really talk about it as though it were an actual value. In calculus, we really only talk about limits approaching infinity (sometimes using "infinity" as a shorthand). In set theory, we really only talk about things having infinite cardinality (sometimes using "infinite" as a shorthand). In geometry, we talk about things being "infinite" not to suggest that there's some endpoint that is simply unreachable; we mean something more along the lines of "unbounded."

Hilbert's hotel is more of a set-theory problem than a calculus or geometry problem, so it's best to think of the set of rooms having infinite cardinality. A set of countably infinite cardinality (the guests) is of the same cardinality when another (finite or) countably infinte set is added, so we can develop a one-to-one correspondence between it and another set of countably infinite cardinality (the rooms). Thinking about it this way demystifies the problem a little.

david9278• 16 years ago

Nice answer, thanks.

dalore• 16 years ago

Did you know there are different sizes of infinity?

RiderOfGiraffes8• 16 years ago

There are not only different sizes of infinity, as this article is trying to show, but also different types of infinity?

In fact, I'm coming to believe that the usual methods of teaching infinity are wrong (not the concepts, just the presentation).

People have this intuition that there can't be anything bigger than infinity. We reinforce that by showing that the rationals are countable, that Q^2 is countable, in fact Q^n is countable. Even the algebraics are countable. We create the intuition that anything infinite is countable.

Then we present 2^N and everything goes bizarre. Some people like that, but others decide that it's all meaningless. I think this method of presentation does the majority of people a disservice.

But not only is there the set-theoretic infinity, there is also the geometric infinity. That actually better matches people's intuition. Separating the ideas of the set theoretic and the geometric versions of infinity has, I'm finding, huge benefits when trying to help people understand what's going on.

Of course, there's also cardinal versus ordinal infinities as well. That's fun.

tokenadult4• 16 years ago

Separating the ideas of the set theoretic and the geometric versions of infinity has, I'm finding, huge benefits when trying to help people understand what's going on.

Expand on that please, so I can make sure I understand what you are writing here.

RiderOfGiraffes8• 16 years ago

It might have been you that put me onto this - I did get the idea from HN, but haven't had time to track down the original suggestion.

This is a brief reply - I don't have time for more detail now, I am intending to write this up, but it's about 50th on a very long "To Do" list.

People have this concept that infinity is kind of, well, "out there", as far as you can go. You can't go any further, it's all there is. People talk about parallel lines "meeting at infinity" and "there is no last point on the line" sort of thing.

And that's what their intuition is telling them. There's nothing beyond infinity.

Then when we talk about the cardinals we tend to reinforce that by showing that the odds, evens, squares and primes all have the same cardinality. That's a bit weird for people, but they're getting the idea that infinity is odd, but they can cope with odd.

Then we show that N^2 and Q are both countable, can be put in one-one correspondence with N. They're getting cool with that too. We continue to reinforce the idea that there's infinity, and every time we do something we get the same infinity.

But that's now what they expect. Infinity is kind of as far as you can go. We're matching the set-theoretic cardinals to their geometrical intuition of "out there."

No wonder they get confused, upset, and occasionally angry when we then introduce 2^N as being "bigger."

I'm finding that talking about geometry and the concept of infinity, then talking about sets and the concept of intinity as a different thing, despite the same name is helping people to create different models in their minds. These different models then help them not use the same intuition, and they don't get confused in the same way.

Then, as the final modification, I don't start by showing that loads and loads of things are all countable. I talk about "same size" as being 1-1 matching, and discuss the idea that there could be something "bigger than N."

I do that first, and then go hunting, pointing out from the beginning that historically people found this difficult.

Now they get excited when I show them that 2^N is uncountable. They've been primed to want to find it, and their intuition about "infinity" isn't challenged.

That's an incomplete summary - I hope it helps. Ask for more, or email me if it's not clear.

RyanMcGreal• 16 years ago

If you're interested in infinity, David Foster Wallace's book Everything and More is an entertaining, witty introduction.

Edit - I'd love to know why someone downvoted this.

The Hilbert Hotel

Related Stories