The P vs. NP poll provides 3 possibilities: equal, not equal, and independent. This is reasonable, because despite the law of the excluded middle you must supply a proof for your answer, which itself is insufficient. But then the statement "P vs. NP is independent" itself can be independent, with a proof. And this process can go on indefinitely. One of them must be provable, or did I miss something? Anyway the number of possibilities is infinite, instead of 3. Is this correct?

  • $\begingroup$ you already asked this question 8 years ago did you not? $\endgroup$ – Giacomo Alzetta Aug 24 '18 at 14:20
  • $\begingroup$ Either you can prove that it's true or you can prove that it's false or you can prove neither. Whether or not you consider further refinements of the "you can prove neither" case as different "possibilities" is purely a matter of opinion. $\endgroup$ – David Richerby Aug 24 '18 at 14:48
  • $\begingroup$ @GiacomoAlzetta No, that's a different question -- essentially, "How could it possibly be independent?" $\endgroup$ – David Richerby Aug 24 '18 at 14:48

This isn't really a question about P vs. NP - any other statement would do in its place. The point is that there are a couple different "philosophical contexts" being mixed up here, and depending on exactly how you ask the question each of $2$, $3$, or infinity are reasonable answers (I'm not claiming that these are exclusive, but I think they frame the question well):

  • The Platonic: If we adopt a certain measure of Platonism (for P vs. NP, something like "the natural numbers exist objectively even if our understanding of them is limited") then yes, every statement is either true or false. Provability from a given theory is a purely secondary matter, and the independence of a statement from (say) ZFC has no bearing on its truth.

  • The formalist: If we don't want to make any philosophical commitments, the most we can ask is whether the statement is provable in a given theory. Once we fix a single theory of interest - say, ZFC - the formalist version of the question does indeed boil down to three possibilities: our statement is either provable in that theory, or disprovable in that theory, or independent of that theory. (Or the theory is inconsistent, in which case the first two options hold simultaneously.)

    • Wildness of the type you're asking about emerges when we ask the "broader" formalist question: which theories is our statement provable in? When asked this way we do indeed get a wild situation, since for any interesting statement there will be some theories which prove it and some theories which disprove it. Note that this is really a more "stable" perspective than focusing on a single theory, but in practice mathematicians tend to prefer a single background theory so we can ignore foundational considerations which aren't really germane to the specific mathematics at hand.

Of course this conflicts with the language we often use in actual practice. The "true/false/independent" trichotomy blurs the Platonic and formalist contexts by conflating a fixed theory - usually ZFC - with "truth." This is a common practice, but is at best raising the question of why we assign privileged status to ZFC specifically (why not ZFC + an inaccessible? or ZF? or ZC? or ...). Ultimately it's just a linguistic convention: we recognize that in many situations, in order for our everyday mathematical language to be truly accurate we need to implicitly understand "true" as an abbreviation for "provable in ZFC."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.