Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Does infinity exist?

plus.maths.org

Post reply on HN
Print view View original

121–127 of 127 posts

Re: Does infinity exist?

#121

Post by ColinWright »

Evbn wrote: post #85
ajanuary wrote: post #21

Earlier quoted context omitted.

I can see how that works if you have an infinite number of rooms and an infinite number of guests, because you still have an unoccupied room to move them up into. But how does that work when you've stated that all rooms are occupied? I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied…

Your intuition is correct. The hotel paradox is a trick of symbolic manipulation, and the analogy to a real hotel is an amusing deceptive misdirection.

  > Your intuition is correct.
No, the intuition is not correct.

  > The hotel paradox is a trick of symbolic manipulation,
  > and the analogy to a real hotel is an amusing deceptive
  > misdirection.
No, it's a visualization to help people understand about matchings between infinite sets. It's an accurate analogy.

Re: Does infinity exist?

#122

Post by gjm11 »

lotharbot wrote: post #118
gjm11 wrote: post #105

Earlier quoted context omitted.

This argument also proves that people can't really think, because I can set you the following challenge: "Work out what number you'd name in response to this question, and then tell me the number one bigger than that."

This doesn't prove that a human "can't think". It proves that a human can't provide a logically consistent answer to a question that doesn't have a logically consistent answer. This isn't quite analogous to the situation in the parent. There exists a logically consistent answer to the question "tell me something other than what [algorithm] would yield from [inputs]" -- it just can't be produced by that algorithm.

It's exactly analogous. There is a logically consistent answer to the question "tell me something other than what Joe McBlow would do in situation X"; it's just that Joe McBlow can't give it to you.

Re: Does infinity exist?

#123

Post by gjm11 »

saurik wrote: post #106
gjm11 wrote: post #66

Earlier quoted context omitted.

This shows that, e.g., there are uncomputable functions, uncomputable sets of natural numbers, etc. But I don't think it's reasonable to say that this shows that there are undecidable problems , because for something to be called a "problem" it has to be something you can actually state -- and there are only countably many of those, for exactly the same reason as there are only countably many programs that might solv…

The proper correction for his terminology is "undecidable languages": a language is a subset of the set of all possible finite strings, and an algorithm that "decides" that language is one that will return correctly either a yes or a no in a finite amount of time for every single element of that language. (This is as opposed to an algorithm that can only "recognize" that language, which will return yes in a finite am…

That would be a correction to tikhonj's terminology -- indeed, the usual formal way of dealing with the kind of issue he described uses the term "language" just as you describe -- but my (perhaps wrong) interpretation was that he was meaning to say something more startling than "there exist undecidable languages" with that definition of "language", and it wasn't his terminology that I was trying to correct.

I'm not sure what question you think I was begging. I was saying (partly implicitly) the following: (1) When you [= tikhonj] say "there are undecidable problems" you may well be thinking of, and will almost certainly be taken to mean, that there are actual questions you could ask a computer program that it can't answer. (2) The cardinality argument doesn't show that there are undecidable problems in that sense. (3) What the cardinality argument shows is of course true, but less interesting than the existence of concrete questions (or families of questions, parameterized by the input) that a computer can't answer. (4) There do exist such questions, but to prove that you need a more complicated argument.

I don't see any circularity there. Perhaps there's some other thing I could have meant that is question-begging, in which case I apologize for not making my meaning clearer. If you still think I begged the question after my attempt at clarification, please let me know so I can fix either my reasoning, my exposition or your reasoning, whichever is at fault :-).

Re: Does infinity exist?

#124

Post by saurik »

gjm11 wrote: post #123
saurik wrote: post #106

Earlier quoted context omitted.

The proper correction for his terminology is "undecidable languages": a language is a subset of the set of all possible finite strings, and an algorithm that "decides" that language is one that will return correctly either a yes or a no in a finite amount of time for every single element of that language. (This is as opposed to an algorithm that can only "recognize" that language, which will return yes in a finite am…

That would be a correction to tikhonj's terminology -- indeed, the usual formal way of dealing with the kind of issue he described uses the term "language" just as you describe -- but my (perhaps wrong) interpretation was that he was meaning to say something more startling than "there exist undecidable languages" with that definition of "language", and it wasn't his terminology that I was trying to correct. I'm not s…

The circularity I am looking at is that my ability to have "actual questions you could ask a computer program that it can't answer" is reliant on my ability to generate them and verify the results (as in, that they answered the question correctly or not) using algorithms, which inherently limits the cardinality of the set of possible questions to the cardinality of the set of possible answers, but I feel only because we are starting from inside of the algorithmic box.

To me, it is very similar to claiming (which many do; I won't, btw, go so far as to say that it is a poor way of looking at the world: this may be more practical) that there is no such thing as a set that has infinite cardinality (whether we are talking countably, uncountably, or something even more infinite than that) because no one would be able to count how many elements are in the set, nor would the set have been able to be constructed in the first place.

Maybe "circular" isn't the right term, but it does seem to rely on an assumption of the result (hence my usage of "begging"). My goal, then, in switching from "problem" to the more specified "language" is that, if you believe in the concept of "infinity" in the first place, I feel justified in my ability to prove that the set of languages is uncountably infinite, and the fact that I can't enumerate (or possibly even choose) elements from that set is not relevant.

Re: Does infinity exist?

#125

Post by [deleted] »

gjm11 wrote: post #122
lotharbot wrote: post #118

Earlier quoted context omitted.

This doesn't prove that a human "can't think". It proves that a human can't provide a logically consistent answer to a question that doesn't have a logically consistent answer. This isn't quite analogous to the situation in the parent. There exists a logically consistent answer to the question "tell me something other than what [algorithm] would yield from [inputs]" -- it just can't be produced by that algorithm.

It's exactly analogous. There is a logically consistent answer to the question "tell me something other than what Joe McBlow would do in situation X"; it's just that Joe McBlow can't give it to you.

[deleted]

Re: Does infinity exist?

#126

Post by jgrahamc »

diminish wrote: post #80
jgrahamc wrote: post #9

Earlier quoted context omitted.

You need to go and read up on the transfinite numbers. Swizec is talking about what happens when you deal with a certain sort of infinity (a countable infinity) where there's a one-to-one mapping between the hotel rooms and the numbers. In the transfinite numbers things that at first seem unintuitive happen, e.g.: 1. There are the same number of integers as there are even numbers. And there are the same number of int…

Here are some interesting questions on the Hilbert hotel which boggles my mind. Shortly, If you can keep as many rooms as you wish unoccupied, can you still claim your hotel is full? (1) Example, if you can move everyone from N to N+1 or (N+5); and get an unoccupied room for new reservations, can you still claim anyone that your hotel with infinite rooms is fully occupied? (2) Or is a fully occupied infinite-roomed h…

I think the mathematical definition of 'the hotel is full' would be 'there is a one-to-one correspondence, also called an isomorphism, between the hotel rooms and occupants'.

So, if the hotel has empty rooms, even if there are an infinite number of occupied rooms it is not 'full'.

On a side note: no matter how many occupants there are in the hotel one might argue that it was also 'empty' given that it can always accommodate a countably infinite number of new arrivals.

Re: Does infinity exist?

#127

Post by jgrahamc »

michaelcampbell wrote: post #91
jgrahamc wrote: post #9

Earlier quoted context omitted.

You need to go and read up on the transfinite numbers. Swizec is talking about what happens when you deal with a certain sort of infinity (a countable infinity) where there's a one-to-one mapping between the hotel rooms and the numbers. In the transfinite numbers things that at first seem unintuitive happen, e.g.: 1. There are the same number of integers as there are even numbers. And there are the same number of int…

Honest question here; is the phrase "same number of X and Y" equivalent mathematically to "the cardinality of X and the cardinality of Y are the same"? I was taught "no", since "number of" doesn't apply to any of the infinities. But perhaps I was taught incorrectly, or I have misremembered.

Well, Cantor's big thing was partly that he extended cardinality to infinite sets (http://en.wikipedia.org/wiki/Cardinal_number). The first infinite cardinal \aleph_0 is the cardinality of the natural numbers.
Post reply on HN