Mfcttrf

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_0subseteq M_1subseteq M_2subseteqcdots$$

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

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

A natural generalization would be a coherent system of elementary embeddings $j_n:M_nto N_n$, with possibly different models on each side. The question is whether the limit embedding $j:Mto 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?

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

Let $M_0= (omegatimes 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:= (omegatimes 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, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus 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.

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

Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.

Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, 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_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup 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)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 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_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.

Let $j_n^*colon M^*_nto 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_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.

In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 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 $jcolon Mto 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^*$.