MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Models with the property you describe---every element of $\mathbb{N}_2\setminus\mathbb{N}_1$ is larger than every element of $\mathbb{N}_1$ are called end-extensions, and are much studied in the models of arithmetic literature. – Henry Towsner Mar 18 '14 at 12:30
In the 1950's, MacDowell and Specker proved that every model of PA has an elementary end extension. Their method has become rather standard by now, but at the time this was a definitely nontrivial result. – Andreas Blass Mar 18 '14 at 14:38
up vote 9 down vote accepted

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$.

share|cite|improve this answer
For a simple example of such a pair, take any uncountable model $N'$ of $\mathsf{PA}$ with at least one point $a$ with uncountably many predecessors. Consider any countable elementary substructure $M$ of $N'$ containing $a$, and let $N$ be its downward closure. – Andrés E. Caicedo Mar 18 '14 at 5:34
Excellent! This not only answers the question I asked, but it answers another question I had that I hadn't yet figured out to ask! – Hurkyl Mar 18 '14 at 7:31

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.

share|cite|improve this answer
A simple construction! Enough to make me feel a bit silly that I failed to come up with it myself. +1 – Hurkyl Mar 18 '14 at 7:34
There's a nice heuristic dichotomy going on here: when trying to come up with a situation "$A\subseteq B$ and …", you basically have to choose between working 'from above' (starting with a $B$ and building an $A$) or 'from below' (starting with an $A$ and building a $B$). Working from above, I find, tends to be the more structural approach, relying on properties of the models in question but giving you more interesting results, while there's usually some trick (often Compactness) which makes working from below simpler. – Noah Schweber Mar 18 '14 at 18:05

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$.

share|cite|improve this answer
It may be worth stressing that every model of PA has plenty of such proper definable extensions. In particular, if $T$ is any recursively axiomatizable theory such that $\mathbb N_1\models\mathrm{Con}_S$ for each (standard) finite fragment $S\subseteq T$, then there is a model $\mathbb N_2\models T$ definable in $\mathbb N_1$. – Emil Jeřábek Mar 18 '14 at 11:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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