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
    Dec 5, 2015 at 11:12
  • $\begingroup$ What do you mean by convere of proposition A? I had some problem with its converse. $\endgroup$ 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
    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$ Dec 20, 2015 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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