1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ "C be any nontrivial elementary extension of A". What would this look like? $\endgroup$ – pmac Mar 25 at 20:08
  • $\begingroup$ Also how can we have B = C/A? Then A would not be a subset of B. $\endgroup$ – pmac Mar 25 at 20:19
  • $\begingroup$ Oops, I wrote the wrong definition of $B$. I've fixed it now. $\endgroup$ – Eric Wofsey Mar 25 at 20:33
  • 1
    $\begingroup$ @pmac: Consider $\phi(x)$ which is $\forall y(y\geq x)$. Then $\mathbb{N}\models\phi(0)$ but $\mathbb{Z}\not\models\phi(0)$. $\endgroup$ – Eric Wofsey Mar 25 at 21:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Eric Wofsey Mar 25 at 21:26
1
$\begingroup$

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

$\endgroup$

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.