On the existence of certain total recursive functions in nontrivial axiom systems, I

1998/04/30 by N. C. A. da Costa, da Costa, N. C. A., F. A. Doria +1
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #cmp-lg #cs.CL

paper · pdf · doi:10.48550/arxiv.cmp-lg/9804005

LaTeX, 16 pages, no figures. This paper was submitted to a major journal in the field and rejected. The referee somehow misundesrtood Corollary 3.8 and wrongly concluded that the proof had either a gap or an error. Can you find whether that error exists?

arxiv created 1998/04/30 · arxiv updated 2009/11/30

Abstract

We investigate the existence of a class of ZFC-provably total recursive unary functions, given certain constraints, and apply some of those results to show that, for Σ₁-sound set theory, ZFC\not\vdash P<NP.

Related

• Axiomatizing some small classes of set functions
• Naive Axiomatic Class Theory: A Solution for the Antinomies of Naive Mengenlehre
• The Provably Total Set-Recursive Functions of KPl
• An arguable inconsistency in ZF
• Classifying the provably total set functions of KP and KP(P)