PROVING P!=NP IN FIRST-ORDER PA

Abstract

The original inspiration for the argument presented here was the observation, whose proof we sketch first, that it is provable in ZFC+“V =Ultimate-L” that there is a set-theoretically definable sequence {φn : n ∈ ω} of Σ2-sentences, such that - ZFC+{φn : n ∈ ω} is Σ2-sound and Σ2-complete - the length of φn is bounded above by a polynomial function of n with positive leading coefficient - ZFC+φn+1 always proves Σ2-soundness of ZFC+φn. Note that the axiom “V =Ultimate-L” is taken to include the assumption that there is a proper class of Woodin cardinals, so there is no problem with ZFC+“V =Ultimate-L” being able to prove the Σ2-soundness of ZFC. Also, this result is in fact quite easy to prove on much weaker assumptions without any essential use of the concept of Ultimate-L at all, but the key point of interest is that in some sense the sequence of Σ2-sentences grows in logical strength “as fast as possible”, and this aspect of the construction is also mirrored in an adaptation of this result to the context of the language of arithmetic, to be discussed next. We move from there to a result in the context of PA, independent of the previous result; namely that it is provable in PA that there is an arithmetically definable sequence {φn : n ∈ ω} of Π0 2 -sentences, such that - PRA+{φn : n ∈ ω} is Π0 2 -sound and Π0 1 -complete - the length of φn is bounded above by a polynomial function of n with positive leading coefficient - PRA+φn+1 always proves 1-consistency of PRA+φn. Once again one has an analogue of the idea that the growth in logical strength is “as fast as possible”, manifested in the fact that the total general recursive functions whose totality is asserted by the true Π0 2 -sentences in the sequence are cofinal growth-rate-wise in the set of all total general recursive functions. We then develop an argument which makes use of a sequence of sentences constructed by an application of the diagonal lemma, which are generalisations in a broad sense of Hugh Woodin’s “Tower of Hanoi” construction as outlined in his essay “Tower of Hanoi” in Chapter 18 of [1]. The argument establishes the result that it is provable in PA that P 6= NP.