6
$\begingroup$

Is there a tuple of parameter-free formulas $\Phi$ and a nonstandard $M\models PA$ such that $\Phi^M\models PA$, the induced $M$-definable initial segment embedding $j_\Phi^M:M\rightarrow\Phi^M$ is non-surjective, and $M\equiv \Phi^M$?

(Here by "$\Phi^M\models PA$" I mean "$\Phi$ defines an interpretation of a structure in the language of arithmetic in $M$, and that structure satisfies $PA$." Per Joel's comment below, we may freely require additionally that $j^M_\Phi$ be elementary.)

If we allow parameters the answer is yes, but in both the arguments there parameters are absolutely essential. I vaguely recall$^1$ a not-too-hard negative proof via Kripke's notion of fulfillability (see Putnam or Quinsey) but I can't reconstruct it at the moment.


$^1$I also recalled seeing this about the version with parameters, which turned out to be bogus; I think the parameter-free version is what I was actually thinking of, but now I'm much less sure I'm not just making stuff up.

$\endgroup$
  • $\begingroup$ If there is an example, then won't there have to be one where $j$ is elementary, since we can go to the definable hull of $M$, thereby reducing to the case where $M$ is pointwise definable, which will imply that $j$ is elementary as a consequence of elementary equivalence $\equiv$. $\endgroup$ – Joel David Hamkins Mar 1 at 11:35
  • $\begingroup$ @JoelDavidHamkins Derp, of course - fixed! $\endgroup$ – Noah Schweber Mar 1 at 17:14
  • 2
    $\begingroup$ @NoahSchweber Back in the early 1960s Feferman proved that there is no nonstandard model of PA that is elementarily equivalent to the standard model of arithmetic, and whose addition and multiplication are arithmetically definable. This can be found in the book Computability and Logic (by Boolos et al). The proof is very similar to the proof given by Joel in his answer to your question. $\endgroup$ – Ali Enayat Mar 2 at 17:50
  • $\begingroup$ @AliEnayat Oh man I love that book, but I haven't read it in forever and I didn't think to look there. Thanks! $\endgroup$ – Noah Schweber Mar 2 at 17:56
  • $\begingroup$ @NoahSchweber PS to my earlier comment: As I have explained in my comment to Joel's answer, his argument can be made to work ONLY IF we assume that the standard model of arithmetic is an elementary submodel of $M$ (i.e., if we assume that $M$ satisfies "true arithmetic"). This was noted explicitly in Theorem 1.1 of the paper "Nonstandard models that are definable in models of Peano Arithmetic" (Ikeda + Tsuboi, MLQ, 2007). They pose your question as an open question in their paper in item 2 of Remark 3.6, and to my knowledge the problem is wide open. $\endgroup$ – Ali Enayat Mar 3 at 1:02
4
$\begingroup$

This answer is an attempt at explaining my critical posted comments on Hamkins' proposed answer; it also expands my posted comments to the MO question. I will explain: (a) the gap in Hamkins' answer, (b) how it can be fixed (at the cost of considerably strengthening the hypotheses of the question), and (c) relevant history and literature.

(a) [the gap] Suppose $M$ is a model of $PA$ and $\Phi$ consists of pair of arithmetical ternary formulae $\phi_{\rm{add}}(x,y,z)$, $\phi_{\rm{mult}}(x,y,z)$ for how to re-interpret (the graphs of) addition and multiplication such that (1) through (3) below hold:

(1) The model $\Phi^M$ satisfies $PA$, i.e., ($M$, $\phi^{M}_{\rm{add}}(x,y,z)$, $\phi^{M}_{\rm{mult}}(x,y,z)) \models PA$.

(2) $M$ and $\Phi^M$ are elementarily equivalent.

(3) The $M$-induced initial segment embedding $j^M_{\Phi}:M \rightarrow \Phi^M$ is not surjective.

Then as observed by Hamkins in his answer, by replacing $M$ by its elementary submodel $M_0$ of $M$ consisting of definable elements of $M$, the above conditions remain true. So far, so good.

The gap in the proposed proof occurs at the end of its first paragraph, where it is asserted that $j^{M_0}_{\Phi}:M_0 \rightarrow \Phi^M_0$ is an elementary embedding. The reasoning given is: "Since $M_0$ is pointwise definable, however, elementary equivalence will imply full elementarity, since all parameters are definable". However, for $j^{M_0}_{\Phi}$ to be an elementary embedding of $M_0$ into $\Phi^{M_0}$ we need to know that if $a \in M_0$ is definable in $M$ (and also in $M_0$) as the unique $x$ satisfying $\psi(x)$, then $j(a)$ is the unique $x$ satisfying $\psi(x)$ in $\Phi^M_0$, which is not warranted by the mere assumption that $j$ is an initial embedding.

(b) [the fix]. The gap explained above can be readily seen to be fillable if WE ASSUME, FURTHERMORE, THAT $M$ DOES NOT CONTAIN ANY NONSTANDARD DEFINABLE ELEMENTS (equivalently: $M$ is elementarily equivalent to the standard model of arithmetic $\Bbb{N}$, which is often paraphrased as "$M$ is a model of true arithmetic"). The reasoning: initial embeddings are automatically $\Delta_0$-elementary, so this extra assumption guarantees that $ a\in M_0$ is definable in $M$ via "the least $x$ such that $\delta(x)$ holds" for some $\Delta_0$-formula $\delta(x)$, which in turn guarantees that $j(a)$ is the unique $x$ satisfying $\delta(x)$ in $\Phi^M_0$.

(c) [history and literature] A few years before the appearance of Tennenbaum's famous characterization of the standard model of arithmetic as the only model of $PA$ (up to isomorphism) whose addition and multiplication are recursive, Feferman published an abstract in 1958 (in the Notices of AMS) to announce his result that there is no nonstandard model of true arithmetic (i.e., a model elementarily equivalent to the standard model of arithmetic $\Bbb{N}$) whose addition and multiplication are arithmetically definable, i.e., he proved:

Theorem (Feferman, 1958) The standard model of arithmetic $\Bbb{N}$ cannot interpret a nonstandard model of true arithmetic.

An early exposition of the above theorem of Feferman can be found in this 1960 paper of Scott. The theorem is also exposited as Theorem 25.4a in this edition of the textbook Computability and Logic (by Boolos, Burgess, and Jeffrey), but mysteriously with no reference to Feferman.

Many years later, Feferman's theorem was rediscovered and fine-tuned in by K. Ikeda and A. Tsuboi, in their paper Nonstandard models that are definable in models of Peano Arithmetic, Math. Logic Quarterly, 2007. Theorem 1.1 of this paper says the following (in the language used here).

Theorem. (Ikeda and Tsuboi, 2007) Suppose $M$ is an elementary extension of $\Bbb{N}$ (i.e., $M$ is a model of true arithmetic), and suppose that $M$ interprets a model $\Phi^M$ such that $M$ and $\Phi^M$ are elementarily equivalent. Then the $M$-induced initial segment embedding $j^M_{\Phi}:M \rightarrow \Phi^M$ is an isomorphism.

The proof of Ikeda and Tsuboi for Theorem 1.1 is essentially the one obtained by gluing Hamkins' answer (to the MO question) to the fix (b) above.

Ikeda and Tsuboi also pose the MO question and answer discussed here as an open question in their paper in item 2 of Remark 3.6. To my knowledge the problem remains open.

Finally, let me emphasize that the above discussion all pertained to parameter-free interpretations, since it is well-known that if $M$ is a recursively saturated model of $PA$, then there is some $\Phi(x)$ and some parameter $m \in M$, such that $M$ and $\Phi(m)^{M}$ are elementarily equivalent, and the $M$-induced initial segment embedding $j^M_{\Phi(m)}:M \rightarrow \Phi(m)^{M}$ is a nonsurjective embedding. Here is the proof outline: by recursive saturation, Th($M$) is in the standard system of $M$, and coded by some $m \in M$ such that, in the eyes of $M$, $m$ codes a consistent theory. So by the arithmetized completeness theorem, $M$ can build a model of $m$ whose elementary diagram is definable in $M$; the induced initial embedding is not surjective by Tarski's undefinability of truth.

$\endgroup$
  • $\begingroup$ Dear Ali, you seem to be using the Markdown syntax for quotations for things that are not actual quotations. This is certainly confusing for some, so you may consider editing. On the other hand, the layout makes visual sense so you could just warn users of your nonstandard usage of blockquotes to avoid confusion. $\endgroup$ – François G. Dorais Mar 13 at 5:55
  • 3
    $\begingroup$ @FrançoisG.Dorais Well, people use the Markdown quote syntax for all kinds of things, such as highlighting statements of theorems, and this does not seem to confuse anybody. There is no other option how to make a part of text visually stand out in Markdown (except for disasters like making it all bold). $\endgroup$ – Emil Jeřábek Mar 13 at 7:03
  • 3
    $\begingroup$ @FrançoisG.Dorais Thanks for your comment. I have used blockquotes in many of my MO answers for highlight purposes, and this is the first time that I am hearing that this could be confused with actual quotations, so I am not adding any explanations since (a) I feel that the way the blockquotes are used make it very clear that they are used for highlighting, and (b) I would have to add similar explanations in my other answers. $\endgroup$ – Ali Enayat Mar 13 at 14:38
  • 3
    $\begingroup$ @François Is this some new policy? I've been doing this for years here and in the other site. We are talking of hundreds of posts that would need changing. $\endgroup$ – Andrés E. Caicedo Mar 13 at 14:59
  • $\begingroup$ @FrançoisG.Dorais The point is that some administrators have decided to completely change the formatting of this markdown option and destroyed a very useful tool instead of replacing it. It would be worth a meta discussion. $\endgroup$ – YCor Mar 13 at 17:11
4
$\begingroup$

There can be no such model.

The first observation is that if there is a model as you describe, then I claim there will be an instance where $j$ is elementary. To see this, suppose that $M$ is as in your question. Let $M_0$ be the collection of definable elements of $M$. This is an elementary substructure of $M$, and so it also has $\Phi^{M_0}$, which will be a definable interpretation of an elementarily equivalent model. So it will have its own $j_0:M_0\to \Phi^{M_0}$ mapping $M_0$ isomorphically to an initial segment of the interpreted model $\Phi^{M_0}$, and $M_0\equiv\Phi^{M_0}$. Since $M_0$ is pointwise definable, however, elementary equivalence will imply full elementarity, since all parameters are definable.

Let us continue with the main argument, where we assume that $M=M_0$ and $j$ is elementary. The definition $\Phi$ has some definite complexity. Let $N=\Phi^M$ be the interpreted model. Let $n$ be such that the interpretation of the decoding of finite sequences in $N$ has complexity $\Sigma_n$ in $M$. Let $c$ be a number in $N$ larger than every element of $M$ (that is, larger than $j(x)$ for every $x\in M$). Inside $N$, let $t$ be the pseudo-finite enumeration of the $\Sigma_{n+1}$ diagram of $N$ for parameters up to $c$ and formulas with code up to $c$. Since $n$ is standard finite, this is possible to do inside $N$.

In $M$, now, we can tell whether a given $\Sigma_{n+1}$ formula $\varphi$ is true at a particular $x$ by looking at whether $(\varphi,j(x))$ is in $t$. By assumption, this can be done in a $\Sigma_n$ manner. So $\Sigma_{n+1}$ truth is $\Sigma_n$ definable, which is a contradiction, since the arithmetic hierarchy does not collapse.


EDIT by NS:

In fact, what the argument above shows is that whenever $\Phi^M\models PA$ and $j_\Phi^M$ is non-surjective (that is, we drop the elementarity hypothesis) we get a "relative hierarchy collapse:"

There is some $i$ (depending only on the complexity of $\Phi$) such that for all $k$ the $\Sigma_k$-theory of $\Phi^M$ is $\Sigma_i$ over $M$.

Interestingly, this does not neccessarily appear uniform since the complexity of finding the relevant parameter in $\Phi^M$ seems to grow unboundedly with $k$. In both the answers to the earlier MSE question linked in the OP, we did have such uniformity (at least in some fixed parameter from $M$) but it's not clear that this always happens.

$\endgroup$
  • $\begingroup$ Yes, I think that is what I have proved. Feel free to edit! $\endgroup$ – Joel David Hamkins Mar 1 at 18:07
  • $\begingroup$ I've added a bit - of course feel free to remove/edit my remark for any reason. $\endgroup$ – Noah Schweber Mar 1 at 18:14
  • 6
    $\begingroup$ @JoelDavidHamkins There is a very subtle gap at the beginning of your proof, when you transition from the model $M$ to its elementary submodel $M_0$. The model $M_0$ can certainly be elementarily embedded into every model of Th($M$), but there is no guarantee that the embedding $j$, when acting on $M_0$ will carve out an elementary submodel of $\Phi^M$ UNLESS we assume, in addition, that $M_0$ consists of only standard natural numbers, i.e., if we assume that $M$ satisfies "true arithmetic". See also my second comment to Noah's question. $\endgroup$ – Ali Enayat Mar 3 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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