17
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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... $\endgroup$ – Alex Kruckman Sep 10 at 20:40
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Sep 10 at 20:45
  • $\begingroup$ Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer? $\endgroup$ – Joel David Hamkins Sep 10 at 21:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Alex Kruckman Sep 10 at 21:51
  • $\begingroup$ @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. $\endgroup$ – Joel David Hamkins Sep 11 at 10:14
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Excellent! I like your general method. $\endgroup$ – Joel David Hamkins Sep 11 at 6:44
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see that Alex Kruckman came up with a similar counterexample a few minutes before me. $\endgroup$ – Goldstern Sep 10 at 20:53
  • $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Sep 10 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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