# Unboundedness of primes in bounded arithmetic

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?

-

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]\;$.

-
Thanks for your interesting answer and the link! – shahram Oct 6 '12 at 10:34

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$.)

-
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