14
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
0
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would Bonse's inequality work? Or does that grow too fast? $\endgroup$
    – The Masked Avenger
    Commented 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$
    – Emil Jeřábek
    Commented Sep 30, 2013 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .