The Hilbert Hotel(opinionator.blogs.nytimes.com)
opinionator.blogs.nytimes.com
The Hilbert Hotel
http://opinionator.blogs.nytimes.com/2010/05/09/the-hilbert-hotel/
15 comments
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.
Expand on that please, so I can make sure I understand what you are writing here.
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.
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.
No wonder they get confused, upset, and occasionally angry when we then introduce 2^N as being "bigger."
As a closet constructivist I feel compelled to point out that 2^N certainly has a more complicated internal structure, but "bigger" is entirely a question of interpretation.
There are a countable number of possible constructions of something in 2^N, and therefore in the traditional interpretation of mathematics all but a countable number of members of 2^N are unconstructable. However a constructivist looks at this and asks what sense it makes to talk about the real "existence" of mathematical objects that cannot be represented in any way, shape or form, even in principle? To a constructivist these don't really exist at all, so there really can't be more of them.
Incidentally the classic picture most mathematicians have of the infinite cardinals being nicely sorted by size depends on the axiom of choice. Specifically Friedrich Hartogs proved in 1915 that if all infinite sets are comparable in size, then the axiom of choice holds. The reverse statement is also true, and is easy to prove from the well-ordering principle. So if you want to be a classical mathematician but are heretic enough to doubt the axiom of choice, then again the simple picture people have of infinite cardinals breaks down.
As a closet constructivist I feel compelled to point out that 2^N certainly has a more complicated internal structure, but "bigger" is entirely a question of interpretation.
There are a countable number of possible constructions of something in 2^N, and therefore in the traditional interpretation of mathematics all but a countable number of members of 2^N are unconstructable. However a constructivist looks at this and asks what sense it makes to talk about the real "existence" of mathematical objects that cannot be represented in any way, shape or form, even in principle? To a constructivist these don't really exist at all, so there really can't be more of them.
Incidentally the classic picture most mathematicians have of the infinite cardinals being nicely sorted by size depends on the axiom of choice. Specifically Friedrich Hartogs proved in 1915 that if all infinite sets are comparable in size, then the axiom of choice holds. The reverse statement is also true, and is easy to prove from the well-ordering principle. So if you want to be a classical mathematician but are heretic enough to doubt the axiom of choice, then again the simple picture people have of infinite cardinals breaks down.
As a closet pragmatist I've always felt that "existence" is not a binary quality, but fuzzy. Things like 0, 1, 2 and 256 have a "strong existence", whereas 38476532 has a very weak existence. You can relate this to saying that the strength of existence is inversely proportional to the size of the turing machine required to compute it.
In this way, infinity of any form doesn't actually exist.
Add to the mix the axiom of infinity and it then does exist, but we're close to the constructivist's world.
However, having said that, there's a lot that I do that relies, underneath, on having the more usual model. Allowing the declaration of the existence of all elements of 2^S for any set S is just too useful not to explore. That's the world I usually inhabit.
However, it's not clear that getting into those discussions will, in any way, help people to understand the more "regular" viewpoints and reasoning. Encouraging people's intuition can be good, but sometimes it simply prevents them from reasoning clearly.
And perhaps that's the most easily defensible aspect of the usual idea (within mathematics) of infinity. Dealing with it forces you not to take things for granted, and to reason carefully about properties. Discovering that 1+aleph_0 = aleph_0 = aleph_0+1 from first principles is useful. Then finding that 1+omega != omega+1 is useful.
Mathematical logic and reasoning is so useful, we need places to exercise it. This is one, there are others.
But personally, I like the idea that there are different sizes of infinity, and the resulting implications such as the Banach-Tarski theorem, the existence of uncomputables, and the tension between Zorn's Lemma and the well-ordering principle.
Although mostly it doesn't really matter.
In this way, infinity of any form doesn't actually exist.
Add to the mix the axiom of infinity and it then does exist, but we're close to the constructivist's world.
However, having said that, there's a lot that I do that relies, underneath, on having the more usual model. Allowing the declaration of the existence of all elements of 2^S for any set S is just too useful not to explore. That's the world I usually inhabit.
However, it's not clear that getting into those discussions will, in any way, help people to understand the more "regular" viewpoints and reasoning. Encouraging people's intuition can be good, but sometimes it simply prevents them from reasoning clearly.
And perhaps that's the most easily defensible aspect of the usual idea (within mathematics) of infinity. Dealing with it forces you not to take things for granted, and to reason carefully about properties. Discovering that 1+aleph_0 = aleph_0 = aleph_0+1 from first principles is useful. Then finding that 1+omega != omega+1 is useful.
Mathematical logic and reasoning is so useful, we need places to exercise it. This is one, there are others.
But personally, I like the idea that there are different sizes of infinity, and the resulting implications such as the Banach-Tarski theorem, the existence of uncomputables, and the tension between Zorn's Lemma and the well-ordering principle.
Although mostly it doesn't really matter.
I think I agree with you. I've always just thought of infinity as having no end - and that's helped me understand all these paradoxes. For any N, 2N is certainly bigger, even if they're both so big I could never measure either. In my mind, infinity follows all the rules of mathematics that other numbers do (i.e. multiplying inifinity by two ensures that it's even, IMO), it's just that it has no end. Parallel lines don't meet at infinity - they have no meeting point.
When you write 2N do you mean "2 times N"? If you do, then your intuition is at odds with mathematics as generally practised, because 2*aleph_0 is aleph_0. Further, two times infinity is the same as three times infinity, and there is no concept of infinity being even or odd. Claiming that 2 times infinity is even can lead to contradictions and inconsistencies.
From that point of view, it would appear that your intuitions are not helping you. More, under some models of geometry it makes a lot of sense to say that parallel lines really do meet at infinity. It makes some theorems a lot easier to state, and easier to prove.
So you may actually agree with a lot of what I'm saying, but your arguments to support that claim appear, at least on the surface, to be wrong. It may be that you have some understanding of these "paradoxes," but your other statements suggest that your inderstanding is not that of current or classical mathematics.
From that point of view, it would appear that your intuitions are not helping you. More, under some models of geometry it makes a lot of sense to say that parallel lines really do meet at infinity. It makes some theorems a lot easier to state, and easier to prove.
So you may actually agree with a lot of what I'm saying, but your arguments to support that claim appear, at least on the surface, to be wrong. It may be that you have some understanding of these "paradoxes," but your other statements suggest that your inderstanding is not that of current or classical mathematics.
[deleted]
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.
On the other hand, it is also rarely necessary.
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.
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.
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....
"Hard" is of course highly subjective, but the material in this article is standard (usually sophomore-junior) undergrad material and is very widely used.
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.
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.)
Most 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.
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.
Are fun things ever really necessary?
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.
It doesn't require binary representation at all. You can write down all the numbers in any base and the argument still holds.
Yes, clearly. I just find it interesting that in his original diagonal argument proof he chose the decimal representation.
Edit: binary not decimal.
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.
For Cantor, I would imagine that the formal proof was simpler to write out using the binary representation. Just a guess.
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.
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.
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.
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.
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.
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.
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.
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.
It's true that you can't extend the number system to include something called "infinity" that would behave like a number. Just like you can't extend the number system to make division by zero make sense while keeping all the usual laws of arithmetic. But this doesn't lead to any philosophical implications like "infinity doesn't exist". In every context where it makes sense to talk about infinities without leading to contradictions, we want to do that, because it enriches our vocabulary and allows us to solve more problems.
Allow me to illustrate. Take the following problem stated in school geometry terms: A square is cut into triangles of equal area, now prove that their number is even. Interestingly, we don't yet know any elementary solution to this problem that can be stated in school math terms. The only solution known was discovered in the 1970s and relies on something called "p-adic numbers". What are those p-adic numbers you ask? They are weird number-like things that have infinitely many digits to the left of the decimal point. Freaky constructs without any counterpart in the real world, but you can still add them, multiply them and all that. Do such things "really exist"? Don't know, don't care. But they helped us solve a difficult problem and that's all that matters.
Allow me to illustrate. Take the following problem stated in school geometry terms: A square is cut into triangles of equal area, now prove that their number is even. Interestingly, we don't yet know any elementary solution to this problem that can be stated in school math terms. The only solution known was discovered in the 1970s and relies on something called "p-adic numbers". What are those p-adic numbers you ask? They are weird number-like things that have infinitely many digits to the left of the decimal point. Freaky constructs without any counterpart in the real world, but you can still add them, multiply them and all that. Do such things "really exist"? Don't know, don't care. But they helped us solve a difficult problem and that's all that matters.
Cool. Thanks.
Edit: but that still seems to me to reflect infinitely, the adjective, as opposed to infinity, the noun. Still, thanks.
Edit: but that still seems to me to reflect infinitely, the adjective, as opposed to infinity, the noun. Still, thanks.
[deleted]
[deleted]
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.
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.
Nice answer, thanks.
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.
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.
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.
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.
I didn't down-vote you, by the way, even though I think you are mis-guided, and probably have been badly taught. From other things you've said I think you could, if it were presented well, find the whole topic intriguing.
Because, in part, you can't have the one without the other. You can't talk about limits without having a model for infinity. They are inextricably entwined, each idea leading to the other.
It's sounds to me like you've simply been put off by loads of badly written Pop-Math articles that attempt to boggle and astound, without showing the real truths as to why the whole subject is really, really cool, and simultaneously, useful and practical.
Because, in part, you can't have the one without the other. You can't talk about limits without having a model for infinity. They are inextricably entwined, each idea leading to the other.
It's sounds to me like you've simply been put off by loads of badly written Pop-Math articles that attempt to boggle and astound, without showing the real truths as to why the whole subject is really, really cool, and simultaneously, useful and practical.
I have no problem conceding that. Do you have anything I could read that might enlighten me on this?
Oh, perfectly reasonable but rather tough question. My thinking about teaching infinity is now at odds both with everything I've read, and how I was taught. It also depends on your own inclinations, strengths and background.
Brian Clegg's book on infinity gets good reviews, but I haven't read it. I'm thinking of starting a blog series on it, but with everything else I have on I may never really get to it.
But as I say, in your specific case it really depends on your background. If you're really interested perhaps you could email me more details on what you've studied and what you've read, and I can write some brief articles by way of reply.
Brian Clegg's book on infinity gets good reviews, but I haven't read it. I'm thinking of starting a blog series on it, but with everything else I have on I may never really get to it.
But as I say, in your specific case it really depends on your background. If you're really interested perhaps you could email me more details on what you've studied and what you've read, and I can write some brief articles by way of reply.
Try _Everything and More: A Compact History of Infinity_ by David Foster Wallace.
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
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
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.
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.
> 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.
Maybe for you, maybe not for someone who enjoys doing it.
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.
But 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.
That'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.
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.
Saying that a function is defined "in terms of itself" is a useful mental shorthand for what's going on, but it only works if you deliberately confuse the function at compile time with the function at run time. If you think about it as a function calling itself, you don't run into this difficulty, since "calling" implies "at run time". There are a lot of things in how computer science is taught that have this "and then some magic happens; just accept it" flavor, when there's really no magic -- everything is ultimately and really imperative.
I'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.
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.
> 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.
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.
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.
Edit - I'd love to know why someone downvoted this.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
f ∈ Ο(g(n)) iff ∃c,n₀ ∀n>n₀ : f(n)≤c*g(n)
No infinity required.
No infinity required.
As per grandparent comment, the symbol ∀ "can't complete during the life of the universe".
Right. I was about to comment that that's because you're assuming an infinite domain, but the above definition becomes useless unless you do.
The point, though, was that the behavior characterized by the notation is perfectly reasonable even with finite domains (even if the specific notation is not, which was a fatal flaw).
The point, though, was that the behavior characterized by the notation is perfectly reasonable even with finite domains (even if the specific notation is not, which was a fatal flaw).
So you don't accept inductive proofs? This will rather limit the amount of mathematical tools available to you.
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.
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.
Well, it's a thought experiment so you don't have to worry about constraints of time and space.
Use lazy evaluation and avoid iterating over an infinite set.
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
[1] See "BBC: Dangerous Knowledge" e.g. http://www.abdn.ac.uk/modern/node/164
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.
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.
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.
Thank you for pointing that out to me. I think my opinion of BBC was too high. Have to be more careful.
David Hilbert's response:
"No one shall expel us from the Paradise that Cantor has created."
http://en.wikipedia.org/wiki/Georg_Cantor
"No one shall expel us from the Paradise that Cantor has created."
http://en.wikipedia.org/wiki/Georg_Cantor
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...
"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?
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?
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.
[deleted]
Did this remind anyone else of continuations and infinite streams?
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.
on a more sensational note, also note that wallace and cantor, both geniuses, also both committed suicide.
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.
you're right
http://www.cosmolearning.com/documentaries/dangerous-knowled... is wrong
http://www.cosmolearning.com/documentaries/dangerous-knowled... is wrong
They both suffered from severe depression. Only Wallace committed suicide.
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.