A note on da Costa-Doria "exotic formalizations"

作者：Gordeev L^*

来源：Archive for Mathematical Logic, 2010, 49(7-8): 813-821.

DOI：10.1007/s00153-010-0203-x

• First order theories
• Godel's theorem
• Proof theory
• P vs. NP
• Exotic formalizations

We analyze N. C. A. da Costa and F. A. Doria's "exotic formalization" of the conjecture P = NP [3-7]. For any standard axiomatic PA extension T and any number-theoretic sentence phi, we let phi* := boolean OR -Con (T) and prove the following "exotic" inferences 1-3. I. T + phi* is consistent, if so is T, 2. T + phi is consistent, provided that T + phi* is omega-consistent, 3. T + phi consistent, provided that T is consistent and has the same provably total recursive functions as T + (phi <-> phi(star)). Furthermore we show that 1-3 continue to hold for phi* := phi s := phi s boolean OR (sic) S, where S = for all x there exists yR (x, y) is any Pi(0)(2) sentence satisfying: 4. (for all n is an element of omega) (T proves S(x) [(n) under bar]), 5. Con (T) double right arrow T does not prove S. We observe that if phi := [P = NP] and S := [F total], where F = F(T) is da Costa-Doria "exotic" function with respect to T, then 4, 5 are satisfied for most familiar (presumably) consistent T in question, while omega(S) becomes equivalent to cla Costa-Doria "exotic formalization" [P = NP](F). Moreover, the corresponding "exotic" inferences 1-3 generalize analogous da Costa-Doria results. Hence these "exotic" inferences are universal for all number-theoretic sentences and not characteristic to the conjecture P = NP. Nor do they infer relative consistency of P = NP (see Conclusion 15 in the text).

• 出版日期2010-12