Comment by Hercuros | Hacker News Reader

Comment by Hercuros | Hacker News Reader

Parent Full thread

Infinity is the only reason: all finite sets of strings are decidable, simply because you can just keep a list and see if a string is in there. Important to mention that there are decidable infinite sets of strings. For instance, deciding whether a string contains only ones is easy, even though there are infinitely many such strings and you couldn’t write all of them down.

A lot of these ideas don’t require any actual “realized” infinity, however. For instance, there are infinitely many natural numbers, but natural numbers themselves are still finite. You can write a program that prints every number at some time in the nearby future (ignoring physical constraints), even though there is no point in time where it will have printed all numbers.

If you want to take away infinity, you have to draw an arbitrary upper bound somewhere, since unbounded things are infinite. Drawing that line is fairly arbitrary since there is no reason why things should no longer work if you add just one more.

Did Godel say infinity is the reason too? Thanks for the response, I don't remember reading about infinity being the reason.

Off topic: Still, you'd run out of matter in the universe (that you could use for ink), before you wrote down a finite amount of numbers while ever reaching a percentage of infinity. That's how unreal infinity is in my mind.

I know the concept of infinity is useful in math, and in this incompleteness theorem, it seems like infinity is the very reason not all truths are provable. But I thought Godel's incompleteness theorem would apply to physical reality, but since infinity doesn't exist in physical reality, I'm not sure the incompleteness theorem would apply to physical reality. Hmmm

Also, didn't Godel show his theorem to be informally true by stating, "This sentence is inprovably true."? There was no infinity invoked in that sentence.

Diagonalization arguments (which are used in Gödel's theorem) do require some infinity.

If there were only a finite number of such "True, but unprovable using your current proof rules" sentences, then you could simply add those sentences to your list of proof rules and there would be nothing "True, but unprovable" anymore. For Gödel's theorem to work, you need at least an infinite supply of those kinds of sentences.

Also here there's no need to actually write down all of them exhaustively. It's just important to be able to find "yet another one" whenever you would like to, which requires an inexhaustible supply.

"which requires an inexhaustible supply. "

But this is how you can stress the theorem. I know it will take a long time, so consider a universe where only 1000 bits of matter actually exist, then try to use the theorem and you won't have enough ink to even hold the theorem, and sets in memory. It's the same for our universe, just with more bits.

"you could simply add those sentences to your list of proof rules " Thanks, for responding. Do you mean axioms? I don't understand why that would be a solution. I'll have to read Godel again.

Yes, strictly speaking that's true, but then if the universe were slightly bigger, or you used a different encoding, you'd get different results. It feels kind of arbitrary to stop thinking about what would happen if the universe contained just one more bit.

Philosophically, I think it's also more interesting that Gödel's theorem would continue to produce such sentences, regardless of how large our universe happens to be. You could never have a universe that is so big that it could contain all Gödel sentences, even if our universe were bigger. This is a much more fundamental limitation.

Gödel's theorem gives you a sentence S where you can prove neither S nor its negation from the current axioms P. Of course, if you then add S (or its negation) as an axiom, then you CAN prove it. But then Gödel's theorem will just give you another sentence S', ad infinitum. You can never win this game.

Reply on news.ycombinator.com