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](https://math.stackexchange.com/questions/3556846/can-proper-elementarily-equivalent-end-extensions-ever-be-definable), 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](https://projecteuclid.org/euclid.ndjfl/1027953483) or [Quinsey](https://arxiv.org/abs/1904.10540)) 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.



Interpreting proper elementarily equivalent end extensions?

> 
> 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.](https://core.ac.uk/download/pdf/82154856.pdf) The theorem is also exposited as Theorem 25.4a in [this edition](http://alcom.ee.ntu.edu.tw/system/privatezone/uploads/Logic/20090928151927_George_S._Boolos,_John_P._Burgess,_Richard_C._Jeffrey_-_Computability_and_Logic_(5Ed,Cambridge,2007).pdf) 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*](https://onlinelibrary.wiley.com/doi/10.1002/malq.200610020), **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.
> 
> 
> 


