# cousin_it comments on What independence between ZFC and P vs NP would imply - Less Wrong

1 08 December 2011 02:30PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

You are viewing a single comment's thread.

Comment author: 08 December 2011 03:48:13PM *  12 points [-]

Your post doesn't seem to have anything to do with P vs NP, it's just a statement of indignation at Gödel's incompleteness theorems :-)

Here's a simplified example. Imagine you have an axiomatic "model of reality" that describes computers. Then I can write a computer program that successively generates all valid proofs in that axiom system. If the program stumbles upon a valid proof that 1=0, it halts, otherwise it goes on searching. It seems to be a "prima facie substantive question" whether the program will halt or not, but our axiom system cannot settle it because it cannot prove its own consistency by Gödel's second incompleteness theorem, unless it is inconsistent.

The root of the problem, IMO, is our inability to describe integers. By the Löwenheim–Skolem theorem, you cannot have an axiomatization of the integers that rules out nonstandard integers. I wrote several posts about this.

Comment author: 09 December 2011 12:36:35AM 2 points [-]

Good point, evidently I failed to really internalize Godel. I had dismissed Godel sentences as not questions about reality but your example is compelling.

Interestingly, your post on integers seemed to suggest you were also thinking that since our models of integers fail to live up to expectations we've somehow failed to describe them, but that it might yet be possible to do so.

Comment author: 09 December 2011 04:23:43PM 0 points [-]

A different perspective: Godel doesn't say that there is any particular question about reality that we cannot answer, only that however far into the model-building enterprise we get, there will always be some undecidable propositions, which can be translated into questions about reality with the TM-enumerating-sentences experiment. So if we have a model of reality M and it fails to answer a question about reality Q then there's always hope that we could discover further regularities in reality to amend M so that it answers Q, but there is no hope that we would ever be free of any open questions. Am I correct in thinking that this rules out the possibility of a GUT, at least if a GUT is defined as a model that answers all questions.

Comment author: 09 December 2011 05:02:23PM *  0 points [-]

Godel doesn't say that there is any particular question about reality that we cannot answer

Of course! It's a theorem about math. There are no theorems about reality.

Am I correct in thinking that this rules out the possibility of a GUT, at least if a GUT is defined as a model that answers all questions.

Yes and no. You can build computers that enumerate proofs even in universes with simple and known physics, like the Game of Life. But to mathematically define something like an infinite Game of Life grid, you need integers, and we don't have a complete axiomatization of those. So you could have a GUT that's completely defined "relative to the integers". I guess most physicists would accept that as a good enough GUT, even though it's incomplete in the Godelian sense.