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?


2 Answers 2


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


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

  • $\begingroup$ Would Bonse's inequality work? Or does that grow too fast? $\endgroup$ Sep 30, 2013 at 18:32
  • $\begingroup$ 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. $\endgroup$ Sep 30, 2013 at 18:39
  • $\begingroup$ Thanks Emil :) If only we knew how close we were to the solution! $\endgroup$
    – shahram
    Oct 1, 2013 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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