# Is the union of a chain of elementary embeddings elementary?

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?

• The generalization is not true: For example, you could take $M_n = (\mathbb{N},<)$ for all $n$, and $N_n = (\mathbb{N}\sqcup \frac{1}{n}\mathbb{Z},<)$. Then $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 contains a copy of $\mathbb{Q}$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well... – Alex Kruckman Sep 10 at 20:40
• Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman – Gerhard Paseman Sep 10 at 20:45
• Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer? – Joel David Hamkins Sep 10 at 21:13
• @JoelDavidHamkins Thanks. Yes, the copies of $\mathbb{Z}$ come after the copies of $\mathbb{N}$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer. – Alex Kruckman Sep 10 at 21:51
• @GerhardPaseman, I had tried that initially, thinking it would be like the usual elementary-chain arguments. But things break down in the backwards direction of the existential case. Just because the target has a witness with $\varphi(x,j(b))$, how do you get a witness with $\varphi(x,b)$? In fact, you can't in general, because of the counterexamples that we now know about from Alex and Martin. – Joel David Hamkins Sep 11 at 10:14

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

• Excellent! I like your general method. – Joel David Hamkins Sep 11 at 6:44

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

• I see that Alex Kruckman came up with a similar counterexample a few minutes before me. – Goldstern Sep 10 at 20:53
• Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear. – Joel David Hamkins Sep 10 at 20:56