Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Wilkie's well known question asks whether $I\Delta_{0}$ proves the unboundedness of primes. We know that by adding a sentence to $I\Delta_{0}$ which says "the exponential function is total", it is possible to prove the unboundedness of primes. This sentence is $\Pi_{2}$. Suppose $\Pi_{1}\text{-Th}(\mathbb{N})$ denotes the set of all $\Pi_{1}$ sentences that are true in $\mathbb{N}$. My question is:

Is it known that $I\Delta_{0} +\Pi_{1}\text{-Th}(\mathbb{N})$ proves the unboundedness of primes?

share|improve this question
add comment

2 Answers

up vote 12 down vote accepted

Yes, because $\: I\Delta_0 + \text{WPHP}\left(\Delta_0\right) \:$ proves the unboundedness of primes (see this answer),
since the assetion that a $\Delta_0$-defined relation is an injection from $\:[0\hspace{.01 in},\hspace{-0.02 in}2\hspace{-0.05 in}\cdot\hspace{-0.04 in}x]\:$ to $\:[0,\hspace{-0.01 in}x]$
can be made itself $\Delta_0$ by modifying the relation to also require that its output is in $\:[0,\hspace{-0.01 in}x]\;$.

share|improve this answer
Thanks for your interesting answer and the link! –  shahram Oct 6 '12 at 10:34
add comment

Yes, for trivial reasons: $\forall x>0\,\exists y\le2x\,(y>x\land\mathrm{Prime}(y))$ is a true $\Pi^0_1$ sentence which implies the unboundedness of primes. (Of course, weaker bounds than Bertrand’s postulate would also do, such as $y\le x^2$.)

share|improve this answer
Would Bonse's inequality work? Or does that grow too fast? –  The Masked Avenger Sep 30 '13 at 18:32
The bound needs to be a polynomial in $x$. Bonse’s inequality is not quite stated in that way, but taking $p_1,\dots,p_n$ to be all primes below $x$ makes the bound on $p_{n+1}$ something on the order of $e^{x/2}$, which is much too large. –  Emil Jeřábek Sep 30 '13 at 18:39
Thanks Emil :) If only we knew how close we were to the solution! –  shahram Oct 1 '13 at 7:48
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.