{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T10:14:31Z","timestamp":1649153671029},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":1745,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Over 25 years ago, the first author conjectured in [15] that the existence of arbitrarily large primes is provable from the axioms <jats:italic>I\u0394<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>\u03c0<\/jats:italic>) + <jats:italic>def(\u03c0)<\/jats:italic>, where <jats:italic>\u03c0(x)<\/jats:italic> is the number of primes not exceeding <jats:italic>x<\/jats:italic>, <jats:italic>I\u0394<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>\u03c0<\/jats:italic>) denotes the theory of \u0394<jats:sub>0<\/jats:sub> induction for the language of arithmetic including the new function symbol <jats:italic>\u03c0<\/jats:italic>, and <jats:italic>def(\u03c0)<\/jats:italic> is an axiom expressing the usual recursive definition of <jats:italic>\u03c0<\/jats:italic>. We prove a modified version in which <jats:italic>\u03c0<\/jats:italic> is replaced by a more general function <jats:italic>\u03be<\/jats:italic> that counts <jats:italic>some<\/jats:italic> of the primes below <jats:italic>x<\/jats:italic> (which primes depends on the values of parameters in \u03be), and has the property that <jats:italic>\u03c0<\/jats:italic> is provably \u0394<jats:sub>0<\/jats:sub>(<jats:italic>\u03be<\/jats:italic>) definable.<\/jats:p>","DOI":"10.2178\/jsl\/1243948322","type":"journal-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T13:12:25Z","timestamp":1243948345000},"page":"455-473","source":"Crossref","is-referenced-by-count":0,"title":["On bounded arithmetic augmented by the ability to count certain sets of primes"],"prefix":"10.1017","volume":"74","author":[{"given":"Alan R.","family":"Woods","sequence":"first","affiliation":[]},{"given":"Ch.","family":"Cornaros","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200003510_ref015","unstructured":"Woods A. R. , Some problems in logic and number theory, and their connections, Ph.D. thesis, University of Manchester, 1981."},{"key":"S0022481200003510_ref013","first-page":"366","article-title":"M\u00e9moire sur les nombres premiers","volume":"17","author":"Tchebychef","year":"1852","journal-title":"Journal de math\u00e9matiques pares et appliqu\u00e9es, I s\u00e9rie"},{"key":"S0022481200003510_ref012","first-page":"87","article-title":"On arithmetical series","volume":"21","author":"Sylvester","year":"1892","journal-title":"Messenger of Mathematics"},{"key":"S0022481200003510_ref011","doi-asserted-by":"publisher","DOI":"10.2307\/2369154"},{"key":"S0022481200003510_ref014","first-page":"237","volume-title":"Logic Colloquium '77","author":"Wilkie","year":"1978"},{"key":"S0022481200003510_ref009","first-page":"181","article-title":"A proof of Bertrand's Postulate","volume":"11","author":"Ramanujan","year":"1919","journal-title":"Journal of the Indian Mathematical Society"},{"key":"S0022481200003510_ref003","first-page":"12","volume":"57","author":"D'Aquino","year":"1992","journal-title":"Local behaviour of the Chebyshev theorem in models of I\u03940"},{"key":"S0022481200003510_ref010","volume-title":"Introduction to number theory","author":"Shapiro","year":"1983"},{"key":"S0022481200003510_ref004","first-page":"1","article-title":"Some classes of recursive functions","volume":"IV","author":"Grzeoorczyk","year":"1953","journal-title":"Rozprawy Matematycine"},{"key":"S0022481200003510_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00029-3"},{"key":"S0022481200003510_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90096-5"},{"key":"S0022481200003510_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S0022481200003510_ref008","first-page":"1235","volume":"53","author":"Paris","year":"1988","journal-title":"Provability of the pigeonhole principle and the existence of infinitely many primes"},{"key":"S0022481200003510_ref006","first-page":"1","volume-title":"Proving infinitude of prime numbers using binomial coefficients","author":"Nguyen","year":"2008"},{"key":"S0022481200003510_ref005","unstructured":"Nguyen P. , Bounded reverse mathematics, Ph.D. thesis, Graduate Department of Computer Science, University of Toronto, 2008."}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200003510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T13:26:19Z","timestamp":1556630779000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200003510\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["S0022481200003510"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1243948322","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}