Mistake in proof that $\textbf{P}^- +\textbf{I}\Delta^0_0$ proves infinitude of primes

50 Views Asked by At

I know that it is still an open question whether $\textbf{P}^- +\textbf{I}\Delta^0_0$ is able to prove that there are infinitely many primes. I know that $\textbf{P}^- +\textbf{I}Open$ cannot prove that there are infinitely many primes but $\textbf{P}^- +\textbf{I}\Delta^0_0+exp$ is able to. I thought of a possible "proof" and I am quite certain that it is wrong but don't know why.

Given $M\vDash \textbf{P}^- +\textbf{I}\Delta^0_0$ and given $a\in M$ I wish to find a $p\in M$ such that $M\vDash p>a\wedge Prime(p)$. Using the construction done by Paris and Kirby I can find a cut $I\subseteq M$ such that $a\in I$ and $I\vDash \textbf{P}^-+\textbf{I}\Sigma^0_1$ (I'm pretty sure this can be done). But over $\textbf{P}^-+\textbf{I}\Sigma^0_1$ I am able to show that there are infinitely many primes, or rather in $I\vDash \forall x\,\exists p\,(p>x\wedge Prime(p))$ and in particular we have that there is $p\in I$ such that $I\vDash p>a \wedge Prime(p)$. But $Prime(p)$ is expressed by a $\Delta^0_0$ formula over $\textbf{I}Open$ so it is absolute and so $M\vDash p>a \wedge Prime(p)$.

1

There are 1 best solutions below

2
On BEST ANSWER

You claim the existence of a cut $I$ which seems impossible to me.

Let $N$ be a model of true arithmetic. Let $a∈ N$ be non standard. Let $M=\{x∈ N: x<a^n$ for some $n\in\mathbb N\}$. Note that $M⊧ \neg\exists y \exp( a )=y$, therfore $M\not\models I\Sigma_1$. On the other hand, $M\models I\Delta_0$.