6

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}-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}-Th(\mathbb{N})$ proves the unboundedness of primes?

flag

1 Answer

4

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 to $[0,x]$ can be
made itself $\Delta_0$ by modifying the relation to also require that its output is in $[0,x]$.

link|flag
Thanks for your interesting answer and the link! – shahram Oct 6 at 10:34

Your Answer

Get an OpenID
or

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