Is a model of arithmetic contained in a model of arithmetic an initial segment?

Question

It's easy enough to show that if $\mathbb{N}_1$ is a non-standard model of the Peano axioms, then there is a canonical embedding $\mathbb{N} \to \mathbb{N}_1$, and we have a theorem that if $x \in \mathbb{N}_1$ and $y \in \mathbb{N}$ such that $x < y$, then $x \in \mathbb{N}$.

What if we had two non-standard models $\mathbb{N}_1 \subseteq \mathbb{N}_2$, ideally an elementary embedding? Must it be true that if $x \in \mathbb{N}_2$ and $y \in \mathbb{N}_1$ such that $x < y$, then $x \in \mathbb{N}_1$?

I'm also curious about the analogous questions for models of real analysis or of ZFC; e.g. comparing the set of integers in two nonstandard models of analysis.

Answer 1

Let me address the first question.

We can have models of $\mathsf{PA}$, $M\subsetneq N$ with $M$ cofinal in $N$. In fact, $M$ and $N$ do not even need to have the same cardinality. However, one can prove from the Davis-Matiyasevich-Putnam-Robinson theorem (on Hilbert's tenth problem) that already the assumption $M\subseteq N$ implies that $M$ is $\Sigma_0$ elementary in $N$. This and having $M$ cofinal in $N$ suffice to imply that in fact $M$ is an elementary substructure of $N$.

This is a basic result on models of arithmetic. Kaye's book should have the details. Gaifman improved this by showing that whenever $M$ and $N$ are models of $\mathsf{PA}$ with $M\subseteq N$ then, letting $L$ be the downward closure of $M$ in $N$, that is, $$ L=\{a\in N\mid \exists b\in M\,(N\models a\le b)\}, $$ we have that $L$ is also a model of $\mathsf{PA}$, $M$ is an elementary substructure of $L$, and $N$ is an end-extension of $L$.

Answer 2

Andres has already answered the question for arithmetic; but let me give another answer, which avoids either using uncountable models or any deep facts about models of any of the theories in question.

Take a countable nonstandard model $\mathcal{M}$ of arithmetic, and consider some partition of $\mathcal{M}$ into $A\sqcup B$ with every element of $A$ below every element of $B$ such that $A$ has no largest element. (This can be done since $\mathcal{M}$ is nonstandard.) Now augment the language of arithmetic by constants for every element of $\mathcal{M}$ and one new constant symbol $c$, and let $T$ be the complete diagram of $\mathcal{M}$ augmented by axioms saying that $c$ is above $A$ and below $B$. By Compactness, $T$ has a model, and clearly $\mathcal{M}$ is (isomorphic to) an elementary substructure of that model, but is not an initial segment.

Note that this argument works not just for arithmetic: it applies to any theory $T$ with a definably ordered subset, and which has models where that subset has a partition $A\sqcup B$ as above - as do analysis (the reals) and $ZFC$ (the ordinals) in addition to arithmetic, so this answers all your questions.

Answer 3

Andres Caicedo has answered the question as stated, however let me point out that one can recover a form of the property under further assumptions on the pair of models. Namely, let $\mathbb N_1$ be a model of PA, and $\mathbb N_2$ a model of Robinson arithmetic which is definable in $\mathbb N_1$: that is, there is a definable set $D\subseteq\mathbb N_1$ and definable functions $\oplus,\odot\colon D^2\to D$ such that $\langle D,\oplus,\odot\rangle$ is (isomorphic to) $\mathbb N_2$. Then there exists a (unique) definable embedding of $\mathbb N_1$ onto an initial segment of $\mathbb N_2$.