Skip to main content
Post Made Community Wiki
Source Link
David Feldman
  • 17.6k
  • 8
  • 67
  • 135

Well you're not going to prove 0=1 in PA, because PA is consistent, (though not PA-provably so), following Gentzen. But I digress.

If you proved 0=1 in, say, ZFC, that would simply mean that ZFC was inconsistent - that the entities it purported to describe had no reasonable interpretation and that logical conclusions derived from the axiom had, in general, no bearing on the world. In particular, it would be irrelevant that you had proved P = NP. But I still digress.

My main point: your 0=1 proof is a purely combinatorial object - a symbol sequence that satisfies syntactic constraints that can be checked in polynomial time. The standard Zero-Knowledge Proof technology would apply to this proof just as to any other. The cataclysmic semantics of the proof's conclusion would simply be irrelevant.

Surely if ZFC turns out inconsistent, much of set theory could still be saved by suitably weakening say, the particular axiom whose self-evidence turned out illusory. (Consensus in the short term concerning which axiom to give up might turn out difficult to achieve). At the end of the day, the offending axiom would simply seem overambitious, just as the occasional large cardinal axiom turns out to be a turkey, roadkill on the transfinite superhighway if you will. Most of classical mathematics will still go through intact, and the theory of finite sets, PA essentially, already strong enough to articulate the P=NP conjecture, will remain consistent.