Let $A⊆B⊆C$ and $X<Y$ denote $X$ is an elementary substructure of $Y.$ Does $A<B$ and $A<C$ imply $B<C$?

Let $$A \subseteq B \subseteq C$$ and $$X<$$Y denote $$X$$ is an elementary substructure of $$Y$$. Does $$A < B$$ and $$A < C$$ $$\implies B? My inkling is that this is not true. Here is why:

$$A means for any sentence $$\phi(\overline{x})$$, $$A \models \phi(\overline{a})$$ iff $$B \models \phi(\overline{a})$$ for any tuple $$\overline{a} \in A$$.

Similarly,

$$A means for any sentence $$\psi(\overline{x})$$, $$A \models \psi(\overline{\alpha})$$ iff $$C \models \psi(\overline{\alpha})$$ for any tuple $$\overline{\alpha} \in A$$.

We want to show that for any $$\theta(\overline{x})$$, $$B \models \theta(\overline{b})$$ iff $$C \models \theta(\overline{b})$$ for any tuple $$\overline{b} \in B$$.

From the first two we can only conclude that for any $$\theta(\overline{x})$$, $$B \models \theta(\overline{\text{a}})$$ iff $$C \models \theta(\overline{\text{a}})$$ for any tuple $$\overline{\text{a}} \in A$$, but not for any tuple $$\overline{b} \in B$$.

However, I cannot think of a counter example.

Here's a simple example. Let $$A$$ be $$(\mathbb{N},\leq)$$ and let $$C$$ be any nontrivial elementary extension of $$A$$. Then every element of $$C\setminus A$$ has a predecessor and a successor (since every element of $$A$$ besides $$0$$ has a predecessor and a successor). Pick an element $$c\in C$$ and let $$B=C\setminus \{c\}$$. Note then that $$B$$ is isomorphic to $$C$$ via an isomorphism that fixes $$A$$: just send every element of $$C$$ that is less than $$c$$ to itself, and every element of $$C$$ that is greater than $$c$$ to its predecessor. So since $$A\preceq C$$, $$A\preceq B$$ as well. But $$B\not\preceq C$$: if $$b$$ is the predecessor of $$c$$ and $$d$$ is the successor of $$c$$, then $$B\models\text{"b is the predecessor of d"}$$ but $$C$$ does not.

• "C be any nontrivial elementary extension of A". What would this look like? – pmac Mar 25 at 20:08
• Also how can we have B = C/A? Then A would not be a subset of B. – pmac Mar 25 at 20:19
• Oops, I wrote the wrong definition of $B$. I've fixed it now. – Eric Wofsey Mar 25 at 20:33
• @pmac: Consider $\phi(x)$ which is $\forall y(y\geq x)$. Then $\mathbb{N}\models\phi(0)$ but $\mathbb{Z}\not\models\phi(0)$. – Eric Wofsey Mar 25 at 21:03
• @pmac: No. It is true that $A$ is a substructure of $C$ (sorry I said it wasn't in my previous comment, I misread something). But it is not an elementary substructure. For instance, $A\models\forall x(x=1\vee x=2)$ but $C$ does not. – Eric Wofsey Mar 25 at 21:26

Here's another example. The structure in question is a bit simpler in my opinion. The verification is definitely harder, but it's a good exercise.

Consider a language with a single binary relation symbol $$E$$. Let $$T$$ be the first-order theory in this language whose models are the structures in this language in which:

• $$E$$ is an equivalence relation,

• every $$E$$-class has either $$1$$ or $$2$$ elements, and

• each of the two possible types of equivalence class occurs infinitely often.

(Whipping up such a $$T$$ is a good exercise.)

For the rest of this answer, restrict attention to models of $$T$$.

Let $$A$$ be some infinite model of $$T$$, and let $$B$$ be an extension of $$A$$ gotten by adding a new element $$v$$ not $$E$$-related to anything in $$A$$ (so $$B$$ adds a class to $$A$$). Now let $$C$$ be the extension of $$B$$ gotten by adding a new element $$w$$ and $$E$$-relating $$w$$ to $$v$$ (so $$C$$ adds an element to $$B$$ but does not add a new equivalence class). Clearly $$B\not\preccurlyeq C$$:

The sentence-with-parameters $$\forall x(vEx\leftrightarrow v=x)$$ is true in $$B$$ but not in $$C$$.

On the other hand, it's a good exercise to show that $$A\preccurlyeq B$$ and $$A\preccurlyeq C$$. One way to do this is via automorphisms, via (proving and checking the applicability of) the following:

Lemma. Let $$X, Y$$ be isomorphic structures with $$X\subseteq Y$$ (remember that it's perfectly possible for a structure to be isomorphic to a proper substructure of itself - take e.g. $$(\mathbb{R},<)$$ vs. $$((0,1), <)$$). Suppose that for each finite tuple $$a_1,...,a_n\in X$$ there is an isomorphism $$f:Y\rightarrow X$$ such that $$f(a_i)=a_i$$ for each $$1\le i\le n$$. Then $$X\preccurlyeq Y$$.

HINT: isomorphisms preserve satisfaction of formulas ...