What independence between ZFC and P vs NP would imply

by alexflint1 min read8th Dec 201163 comments


Personal Blog

Suppose we had a model M that we thought described cannons and cannon balls. M consists of a set of mathematical assertions about cannons, and the hypothesis is that these fully describe cannons in the sense that any question about cannons ("what trajectory do cannon balls follow for certain firing angles?", "Which angle should we pick to hit a certain target?") can be answered by deriving statements from M. Suppose further that M is specified in a certain mathematical system called A, consisting of axioms A1...An.

Now there is much to be said about good ways to find out whether M is true of cannons or not, but consider just this particular (strange) outcome: Suppose we discover that a crucial question about cannons - e.g. Q="Do cannon balls always land on the ground, for all firing angles?" - turned out to be not just un-answerable by our model M but formally independent of the mathematical system A in the sense that the addition of some axiom A0 implies Q, while the addition of its negation, ~A0, implies ~Q.

What would this say about our model for cannons? Let's suppose that we can take Q as a prima facie substantive question with a definitive yes or no answer regardless of any model or axiomatization. At the very least it seems that M must be an incomplete model of cannons if the system in which it is specified is insufficient to answer the various questions of interest. It seems to me that

If a question about reality turns out to be logically independent of a model M, then M is not a complete model of reality.

Now we have an axiomatization of mathematics -- let's say it's ZFC for now -- and we have a model of computation in reality, which is M="The unvierse can contain machines that (efficiently) compute F iff there exists a Turing machine that (efficiently) computes F" with appropriate definitions of what exactly a Turing machine is in terms of ZFC. Suppose we want to answer a question like Q="Can the universe contain machines that efficiently solve SAT?"

Under the premise that M is true, the question Q becomes the pure logical question R="Are there Turing machines that efficiently solve SAT?", i.e. the P versus NP problem.

Now suppose that R was shown to be formally independent of ZFC in the sense that for some axiom A0, ZFC+A0 implies P=NP and ZFC+~A implies P!=NP. This would resolve the mathematical question of P versus NP but the question Q seems like a prima facie concrete question with a definitive yes or no answer that does not rely for its substance on M or ZFC or any other epistemic construct. It would seem that we must have missed something in our description of reality, M.

Perhaps more controversially, I claim: Under the correct model M' it seems that it's impossible for a substantive question (such as Q) to be unanswerable.

All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete.

Personal Blog