Skip to main content
5 of 6
edited body
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

The question has already been answered by Joel Hamkins. Here I want to elaborate on Joel's answer (see Proposition A below) so as to point out a nontrivial variant of the question (see Question A below).

     In this edit **Proposition A, and the Answers (1) and (2)** have been modified.

Proposition A. Suppose $M$ is a nonstandard model of $I\Delta_0$. If $M$ can be end extended to some $M' \models PA$, then:

(a) $M \models B\Sigma_1$, and

(b) $M \models$ Con($I\Sigma_c$) for some nonstandard $c\in M$.

Explanation. The scheme $B \Sigma_1$ is known as the $\Sigma_1$-collection scheme, it is well-known that if a model $M$ of $I\Delta_0$ can be end extended to a model $M'$ of $I\Delta_0$, then $M$ satisfies $B \Sigma_1$ (see Kaye's textbook on models of PA). It is also well-known that $PA$ proves the consistency of each of its finite subtheories, and that there is a recursive sequence of arithmetical sentences $\langle\sigma_n: n\in\omega \rangle$ such that $PA$ proves "each $\sigma_x$ axiomatizes $I\Sigma_x$" (again, as detailed in Kaye's text). Note that statements of the form Con($ \sigma_n$) are $\Pi_1$-statements and therefore their truth is inherited by initial segments closed under addition and multiplication. Hence by the overspill principle, (b) holds (Note that the overspill principle is applied within $M'$ to find the desired $c$ (which, without loss of generality, can be located in $M$).

In light of the above, the "right" question to ask is:

Question A. Is the converse of Proposition A true?

Answer (1). The answer to Question A is in the positive, if the assumption that $M$ is a model of $I\Delta_0$ is strengthened to the assumption that $M$ is a model of $I\Sigma_1$. This follows from the nontrivial fact that every model of $I\Sigma_1$ (even uncountable ones) has an expansion to a model of $WKL_0$ (a result due originally due to Peter Hájek, and recently revisited in this paper of Tin Lok Wong). Note that the compactness theorem of first order logic holds in $WKL_0$, so an expansion of $M$ to a model of $WKL_0$ can be used to build an end extension of $M$ that satisfies $PA$.

Answer (2). The answer to Question A is also in the positive if we add the requirement that $M$ is countable, and exponentiation is a total function in $M$ (by Corollary 2.8 & Proposition 3.4 of this paper of Wong and myself).

I suspect that (1) and (2) describe the current "state of the art" in relation to Question A.

Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105