{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T03:40:59Z","timestamp":1777347659367,"version":"3.51.4"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9232,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:p>In this note we shall be interested in the following problems.<\/jats:p><jats:p>Problem 1. Can <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub> \u22a2 \u2200<jats:italic>x<\/jats:italic>\u2203<jats:italic>y<\/jats:italic> &gt; <jats:italic>x<\/jats:italic>(<jats:italic>y<\/jats:italic> is prime)?<\/jats:p><jats:p>Here <jats:italic>I<\/jats:italic> \u0394<jats:sub>0<\/jats:sub> is Peano arithmetic with the induction axiom restricted to bounded (i.e. \u0394<jats:sub>0<\/jats:sub>) formulae.<\/jats:p><jats:p>Problem 2. Can <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub> \u22a2 \u0394<jats:sub>0<\/jats:sub> PHP?<\/jats:p><jats:p>Here \u0394<jats:sub>0<\/jats:sub> PHP (\u0394<jats:sub>0<\/jats:sub> pigeonhole principle) is the schema<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_eqnU1.png\"\/><\/jats:disp-formula><\/jats:p><jats:p>for <jats:italic>\u03b8<\/jats:italic> \u2208 \u0394<jats:sub>0<\/jats:sub>, or equivalently in <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub>, for a \u0394<jats:sub>0<\/jats:sub> formula <jats:italic>F<\/jats:italic>(<jats:italic>x,y<\/jats:italic>)<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_eqnU2.png\"\/><\/jats:disp-formula><\/jats:p><jats:p>written <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_inline1.png\"\/>.<\/jats:p><jats:p>By obtaining partial solutions to Problem 2 we shall show that Problem 1 has a positive solution if <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub> is replaced by <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub> + \u2200<jats:italic>xx<\/jats:italic><jats:sup>log(<jats:italic>x<\/jats:italic>)<\/jats:sup> exists.<\/jats:p><jats:p>Our notation will be entirely standard (see for example [3] and [4]). In particular all logarithms will be to the base 2 and in expressions like log(<jats:italic>x<\/jats:italic>), (1 + <jats:italic>\u03b5<\/jats:italic>)<jats:italic>x<\/jats:italic>, etc. we shall always mean the integer part of these quantities.<\/jats:p><jats:p>Concerning Problem 2 we remark that it is shown in [5] that for <jats:italic>k<\/jats:italic> \u2208 N and <jats:italic>F<\/jats:italic> \u2208 \u0394<jats:sub>0<\/jats:sub>,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_eqnU3.png\"\/><\/jats:disp-formula><\/jats:p><jats:p>As far as we know this is the best result of this form, in that we do not know how to replace log(<jats:italic>z<\/jats:italic>)<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup> by anything larger. However, as we shall show in Theorem 1, we can do much better if we increase the difference between the sizes of the domain and range of <jats:italic>F<\/jats:italic>.<\/jats:p><jats:p>In what follows let <jats:italic>M<\/jats:italic> be a countable nonstandard model of <jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub>, and let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_inline2.png\"\/> be those subsets of <jats:italic>M<\/jats:italic> defined by \u0394<jats:sub>0<\/jats:sub> formulae with parameters from <jats:italic>M<\/jats:italic>.<\/jats:p><jats:p>Theorem 1. <jats:italic>For k<\/jats:italic> \u2208 N <jats:italic>and<\/jats:italic><jats:italic>F<\/jats:italic> \u2208 \u0394<jats:sub>0<\/jats:sub>,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_eqnU4.png\"\/><\/jats:disp-formula><\/jats:p><jats:p>Here log<jats:sup>0<\/jats:sup>(<jats:italic>x<\/jats:italic>) = <jats:italic>x<\/jats:italic>, log<jats:sup><jats:italic>k<\/jats:italic> + 1<\/jats:sup>(<jats:italic>x<\/jats:italic>) = log(log<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>(<jats:italic>x<\/jats:italic>)).<\/jats:p><jats:p>Proof. To simplify matters, consider first the case <jats:italic>k<\/jats:italic> = 1. So assume M \u22a8 <jats:italic>a<\/jats:italic><jats:sup><jats:italic>log(a)<\/jats:italic><\/jats:sup> exists and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_inline3.png\"\/> with <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200028061_inline4.png\"\/> and <jats:italic>a<\/jats:italic> &gt; 1. The idea of the proof is the following.<\/jats:p>","DOI":"10.2307\/2274618","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:28:19Z","timestamp":1146954499000},"page":"1235-1244","source":"Crossref","is-referenced-by-count":81,"title":["Provability of the pigeonhole principle and the existence of infinitely many primes"],"prefix":"10.1017","volume":"53","author":[{"given":"J. B.","family":"Paris","sequence":"first","affiliation":[]},{"given":"A. J.","family":"Wilkie","sequence":"additional","affiliation":[]},{"given":"A. R.","family":"Woods","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200028061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T10:33:22Z","timestamp":1679481202000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200028061\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":0,"aliases":["10.1017\/s0022481200028061"],"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["S0022481200028061"],"URL":"https:\/\/doi.org\/10.2307\/2274618","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}