Can proper elementarily equivalent end extensions ever be definable?

Question

Suppose $M\models PA$. Can there be a tuple of formulas $\Psi$ (possibly with parameters from $M$) such that:

• $\Psi^M\equiv M$ (or more precisely, $\Psi$ is an interpretation of an $\{0,1,+,\cdot,<\}$-structure in $M$, and that structure is elementarily equivalent to $M$), but

• the induced definable initial segment embedding $j_\Psi^M:M\rightarrow\Psi^M$ is not surjective?

(The map $j_\Psi^M$ exists since $M\models PA$: from the point of view of $M$, we have by induction that for each $m\in M$ there is a unique $a\in \Psi^M$ such that $[0,m]^M\cong[0,a]^{\Psi^M}$, with the complexity of $\Psi$ determining how much induction is needed here. Meanwhile, note that non-surjectivity does not imply $M\not\cong \Psi^M$, merely that $M$ and $\Psi^M$ are not "internally" isomorphic.)

I recall seeing an easy proof that this cannot happen via Kripke's notion of fulfillability (see Putnam or Quinsey), but I can't reconstruct it at the moment.

Answer 1

There is a model of $PA$ that interprets a proper end extension with the same theory.

Let $M$ be an $\omega_1$-saturated model of true arithmetic. We will let elements of $n$ code (internally) finite sets in a typical way (such as $n \in m$ if and only if the $n$th binary digit of $m$ is $1$). Let $m$ be an element of $M$ such that for any standard natural $n$, $n \in m$ if and only if $M \models \varphi_n$, where $\varphi_n$ is the $n$th sentence in the language of arithmetic with some computable coding. Such an $m$ exists by $\omega_1$-saturation. Now consider the language $\mathcal{L}$ that is the language of arithmetic $\{0, 1,+,\cdot, <\}$ plus a single new constant $c$.

For any $k \in M$ less than or equal to the number of binary digits of $m$, let $T_k$ be the $\mathcal{L}$-theory that consists of $\varphi_n$ for any $n \in m$ together with the axioms $1+\dots+1 < c$ with $i$ many $1$'s for every positive $i \in M$. There is a single formula $\psi(k,n,m)$ such that $\varphi_n \in T_k$ if and only if $k \leq m$ and $M \models \psi(k,n,m)$.

Because $M$ is a model of true arithmetic, for any standard $k$, $M \models \mathrm{Con}(T_k)$. Therefore the largest $k$ less than or equal to the number of binary digits in $m$ such that $M \models \mathrm{Con}(T_k)$ is nonstandard. Let $k^\prime$ be the maximal such $k$.

Finally $PA$ (and therefore true arithmetic) is enough to prove that any arithmetically definable theory (with parameters) has an arithmetically definable model, specifically we can take the Henkinization of $T_{k^\prime}$ and then take the term model of the leftmost path of the tree of completions of that theory.

By construction this model is also a model of true arithmetic and is a proper end extension of $M$.

Moreover, with some basic model theory it is consistent that this interpreted structure is actually isomorphic to $M$, but obviously by Tarski's undefinability theorem, such an isomorphism can never be definable in the structure itself.

Answer 2

Here's another proof. For simplicity, I'll write "$\Phi$ is an $M$-seed" for "$\Phi^M\models PA$ and $j_\Phi^M$ is non-surjective." Also, complexity classes like $\Delta_2$ are taken with parameters.

---

Via Henkinization and a greedy algorithm, there is some $\Theta$ such that for all $N\models PA$ we have that $\Theta$ is a $N$-seed and every definable subset of $\Theta^N$ is $\Delta_2$ in $N$. That second property means that we can "iterate" $\Theta$ arbitrarily many times and still wind up with a $\Delta_2$ interpretation.

This iterability is nontrivial: in general, what the interpreted model thinks is a bounded quantifier may correspond to an unbounded quantifier in the interpreting model, so a priori composing interpretations increases complexity. Also note that we can do better and get low instead of merely $\Delta_2$, per the low basis theorem appropriately "arithmetized."

This bounded complexity is useful because, while we can't quantify over arbitrary formulas, we can indeed quantify over $\Delta_2$ (say) formulas. This lets us apply compactness (after a quick pigeonhole argument) as follows:

By iterating $\Theta$, starting with any $N\models PA$ whatsoever we get a sequence of models and initial segment embeddings $$N=M_0\rightarrow M_1\rightarrow M_2\rightarrow ...$$ such that for all $i<j$ the induced interpretation and initial segment embedding $M_i\rightarrow M_j$ are appropriately $\Delta_2$ in $M_i$. The pigeonhole principle tells us that for every finite set $F$ of sentences of arithmetic there are $i<j$ such that $Th(M_i)\cap F=Th(M_j)\cap F$, and so a fortiori that we have

for every finite set $F$ of sentences of arithmetic, there is some $M\models PA$ and some $M$-seed $\Phi$ which is $\Delta_2$ in the sense of $M$ and which satisfies $Th(M)\cap F=Th(\Phi^M)\cap F$.

But now by compactness we get an $M$ and a $\Phi$ such that $\Phi$ is an $M$-seed, every definable set in $\Phi^M$ is $\Delta_2$ in $M$, and $M\equiv \Phi^M$.

---

Note that $\Theta$ and its finite iterates are parameter-free; however, the application of compactness does not give us a parameter-free $\Phi$ with the desired property. So as with James Hanson's answer, this leaves open the parameter-free version of this question - and indeed neither of our answers can be easily modified to attack it (basically, because of Tarski's theorem in James' case and the properness of the arithmetical hierarchy in my case). I've asked about this at Mathoverflow.

EDIT: this is impossible without parameters, the key point being that the "hierarchy collapse" phenomenon observed here - which is also present in James' answer - is in fact a necessary feature of any such interpretation (so that absence of parameters would contradict Tarski).

On a more positive note, this argument does not rely on any internal consistency assumptions; e.g. it continues to work if we replace $PA$ with $I\Sigma_1+\neg Con(I\Sigma_1)$ (the initial segment embeddings we need no longer fall out trivially from the ambient theory, which no longer has enough induction, but they're built directly into the specific interpretations we use). So it does have a nontrivial (at first glance) generality.