14 ms·
The Hilbert Hotel
- ynniv 16y agoHard 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 16y agoAre fun things ever really necessary?
- Locke1689 16y agoEh, 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.
- npp 16y 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.
- btilly 16y agoVery 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/ http://xkcd.com/195/ and the same trick has since been used for visualizing other complicated large linear sets.)
- npp 16y agoMost banal example is intervals in the real line (e.g. reals between 0 and 1), which show up all the time. But comfort with infinity is needed for other uses also, two examples being convergence and asymptotic analysis of practical algorithms (optimization, statistical estimation, signal processing, machine learning, geometric algorithms, ...) and showing that two classes of objects are equivalent. The latter is useful because it can let you switch representations of things according to which is more efficient in some implementation, or because it shows that two seemingly different objects are basically the same. Any class of objects that can be parameterized with a real-valued parameter (e.g. probability distributions) forms an infinite set, and it is often useful to be able to say things about a whole category of problems at once, even for practical purposes.
- tokenadult 16y agoI 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.
- jacoblyles 16y agoI 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.
- stanleydrew 16y agoYou'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_construction http://en.wikibooks.org/wiki/Real_Analysis/Dedekinds_constru....
- zemaj 16y agoI'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.
- jacoblyles 16y agoUse lazy evaluation and avoid iterating over an infinite set.
- ionfish 16y agoSo you don't accept inductive proofs? This will rather limit the amount of mathematical tools available to you.
- igravious 16y agoYo! 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 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) 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_it 16y agoif 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.
- davidkellis 16y agoThis 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.
- fredBuddemeyer 16y agoif 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 16y agoI 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/Cantor.html http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Cant... says he died of a heart attack at 72.
- fredBuddemeyer 16y agoyou're right http://www.cosmolearning.com/documentaries/dangerous-knowledge-2008/ http://www.cosmolearning.com/documentaries/dangerous-knowled... is wrong
- ionfish 16y agoThey both suffered from severe depression. Only Wallace committed suicide.
- canoebuilder 16y 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?
- stanleydrew 16y agoTake 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 16y agoI 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&videoid=102796188 http://vids.myspace.com/index.cfm?fuseaction=vids.individual...
- stanleydrew 16y agoThe 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 http://en.wikipedia.org/wiki/Cantors_diagonal_argument.
- benmathes 16y agoIt doesn't require binary representation at all. You can write down all the numbers in any base and the argument still holds.
- stanleydrew 16y agoYes, clearly. I just find it interesting that in his original diagonal argument proof he chose the decimal representation.
- stanleydrew 16y agoEdit: binary not decimal.
- flatline 16y agoI 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 16y agoAm 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 16y agothat 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 16y agoI 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.
- tokenadult 16y agoThe Wikipedia article http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel 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 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 16y agoDid this remind anyone else of continuations and infinite streams?
- Bjoern 16y agoThe 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 http://www.abdn.ac.uk/modern/node/164
- RiderOfGiraffes 16y agoMuch discussion about that programme here: http://news.ycombinator.com/item?id=797723 http://news.ycombinator.com/item?id=797723 http://news.ycombinator.com/item?id=121063 http://news.ycombinator.com/item?id=121063 http://news.ycombinator.com/item?id=101255 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.
- jgrahamc 16y agoTotally agree. That was an awful, awful program. As was the similarly awful thing that "Infinity and Beyond" (http://www.bbc.co.uk/programmes/b00qszch 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.
- Bjoern 16y agoThank you for pointing that out to me. I think my opinion of BBC was too high. Have to be more careful.
- tokenadult 16y agoDavid Hilbert's response: "No one shall expel us from the Paradise that Cantor has created." http://en.wikipedia.org/wiki/Georg_Cantor http://en.wikipedia.org/wiki/Georg_Cantor
- david927 16y agoI 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.
- andrew1 16y 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.
- david927 16y agoFair 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.
- andrew1 16y agoBut that's like saying let's get rid of zero. You can make the argument that zero doesn't exist as equally convincingly as you can that infinity doesn't exist.
- tome 16y agoThat's like saying "let's get rid of recursion". Imagine defining a function in terms of itself! That's circular and you can always get away with just using a loop instead. Well, it turns out recursion often works and is very useful. Just like infinity.
- david927 16y agoI'll repeat what I said above here: 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.
- deleted 16y ago[deleted]
- dalore 16y agoDid you know there are different sizes of infinity?
- deleted 16y ago[deleted]
- RiderOfGiraffes 16y agoThere 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.
- tokenadult 16y agoSeparating 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.
- RiderOfGiraffes 16y agoIt 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 16y agoIf 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.