Is the union of a chain of elementary embeddings elementary?

Question

I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out about which way it goes.

My situation is that I have a chain of submodels, which is not necessarily an elementary chain,

$$M_0\subseteq M_1\subseteq M_2\subseteq\cdots$$

and I have elementary embeddings $j_n:M_n\to M_n$, which cohere in the sense that $j_n=j_{n+1}\upharpoonright M_n$. So there is a natural limit model $M=\bigcup_n M_n$ and limit embedding $j:M\to M$, where $j(x)$ is the eventual common value of $j_n(x)$.

Question. Is the limit map $j:M\to M$ necessarily elementary?

A natural generalization would be a coherent system of elementary embeddings $j_n:M_n\to N_n$, with possibly different models on each side. The question is whether the limit embedding $j:M\to N$ is elementary, where $M=\bigcup_n M_n$, $N=\bigcup_n N_n$ and $j=\bigcup_n j_n$. And of course one could generalize to arbitrary chains or indeed, arbitrary directed systems of coherent elementary embeddings, instead of just $\omega$-chains.

I thought either there should be an easy counterexample or an easy proof, perhaps via Ehrenfeucht-Fraïssé games?

Answer 1

First I'll give a counterexample to the natural generalization, adapted from my earlier comment:

Let $M_n = (\mathbb{N},<)$ for all $n$, and let $N_n = (\mathbb{N}\sqcup \frac{1}{n!}\mathbb{Z},<)$, where all elements of $\frac{1}{n!}\mathbb{Z}$ are greater than all elements of $\mathbb{N}$ in the order. Note that each $N_n$ is isomorphic to $(\mathbb{N}\sqcup\mathbb{Z},<)$, and there is a natural inclusion $N_n\subseteq N_{n+1}$ for all $n$, since $\frac{1}{n!}\mathbb{Z} \subseteq \frac{1}{(n+1)!}\mathbb{Z}$ as subsets of $\mathbb{Q}$.

Now $M_n\preceq N_n$ for all $n$, but $\bigcup_n M_n\not\preceq \bigcup_n N_n$, since the former is $(\mathbb{N},<)$ and the latter is $(\mathbb{N}\sqcup\mathbb{Q},<)$, which is not discrete.

---

Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.

Suppose we have a coherent system of elementary embeddings $j_n\colon M_n \to N_n$ such that the limit map $j\colon M\to N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = L\cup \{E\}$, where $E$ is a new binary relation.

For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_{i\in \mathbb{Z}}$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $i\leq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.

There is a natural inclusion $M_n^*\subseteq M_{n+1}^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_{n+1}^*$ according to the inclusions $M_n\subseteq M_{n+1}$ and $N_n\subseteq N_{n+1}$.

Let $j_n^*\colon M^*_n\to M^*_n$ map $C_i$ to $C_{i+1}$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n \colon M_n\to N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_{n+1}\restriction M_n^*$.

In the limit, $M^* = \bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $i\leq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*\colon M^*\to M^*$ maps $C_i$ to $C_{i+1}$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $j\colon M\to N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.

Answer 2

Here is a counterexample to your "natural generalization": Let $A$ and $B$ be (countably) infinite sets, with $A\subseteq B$, $B\setminus A$ infinite.

Let $M_0= (\omega\times A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $\omega$ columns next to each other. Similarly let $N_0:= (\omega\times B, <)$, and let $j_0$ be the inclusion map.

Let $M_k= M_0$, and $N_k = (\omega \times A )\cup (\omega \cup \{-1,\ldots, -k\}\times (B\setminus A))$, again with the obvious order. So the columns with "indices" in $B\setminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.

But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.