4
$\begingroup$

Recently I'm thinking about question below, but I can not prove or disprove it.

Is it true that for every model $M\models I\Delta_0$ there exists a model $M'\models PA$ such that $M'$ is end extension of $M$?

How can this statement be proved or disproved?

Thanks.

$\endgroup$

3 Answers 3

11
$\begingroup$

It's not true, because perhaps the model of $I\Delta_0$ satisfies $\neg\text{Con}(I\Delta_0)$. Since PA proves the consistency of the bounded induction principles, there can be no model of PA that has such a proof in it.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ It seems the link of your paper joint with Wong does not work correctly. I think it should be logic.univie.ac.at/~wongt9/papers/ew-wkl0star.pdf $\endgroup$
    – Rahman. M
    Commented Dec 5, 2015 at 11:12
  • $\begingroup$ What do you mean by convere of proposition A? I had some problem with its converse. $\endgroup$ Commented Dec 17, 2015 at 22:13
  • $\begingroup$ @Khaniki: The converse to Proposition A says that if $M$ is a model of $I\Delta_0$ for which (a) and (b) are true, then $M$ has an end extension to a model of $PA$. $\endgroup$
    – Ali Enayat
    Commented Dec 30, 2015 at 9:26
7
$\begingroup$

Actually it's not even true that any model of $I\Delta_0$ admits an end extension to a model of this theory.

Even worse, we don't know whether such an end extension exists even if you allow the smaller model to satisfy $B\Sigma_1 + \exp$, when the existence of the end extension to a model of $I\Delta_0$ is the same as being expandable to a model of $WKL*_0$.

$\endgroup$
1
  • $\begingroup$ Could you please introduce me some papers that prove propositions that you said? Thanks! $\endgroup$ Commented Dec 20, 2015 at 12:58

You must log in to answer this question.

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