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

Question

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<C$? My inkling is that this is not true. Here is why:

$A<B$ 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<C$ 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.

Answer 1

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.

Answer 2

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