This question is inspired by this question. I'm interested in general strategies for showing that a given structure is not expressible as a set of first-order sentences. Right now I'm looking for ways of taking infinitely many $L$-structures and stapling them together in such a way that certain properties hold of the result.
So far, I've had the idea of a possibly-infinite sequence of first-order structures, each one a substructure of the next. I'm pretty sure that any sentence that's eventually constantly true in the sequence is true in the resulting limit structure.
My question is twofold:
- Does the following theorem regarding sequences of substructures hold?
- Is it an immediate consequence of a more general principle?
First, let $A_1, A_2, \cdots$ be a sequence of $L$-structures where $A_i$ is a substructure of $A_{i+1}$.
Let $\mathcal{A}$ be the limit of the $A_1, A_2, \cdots$ formed by taking the union of their domains and defining the constant, function, and relation symbols in the appropriate way.
Is every well-formed formula that's true in every structure after a prefix of finite length true in $\mathcal{A}$?
First, let's consider the quantifier-free case.
Let $\varphi(\vec{v})$ be a quantifier-free formula. Suppose by way of contrapositive that $\mathcal{A} \not\models \varphi(\vec{v})$ that means there exists a $\vec{w}$ such that $\mathcal{A}, \vec{w} \not\models \varphi(\vec{w})$. $\vec{w}$ is finite, therefore there must exist a $k$ such that $A_k$ and all subsequent structures contain all of $\vec{w}$. $A_k, \vec{w} \not\models \varphi(\vec{w})$ as desired.
Next let's consider the case of a formula with $n$ quantifiers and suppose that the inductive hypothesis holds for all formulas with $n-1$ or fewer quantifiers.
Suppose $\varphi(\vec{v})$ is of the form $[\exists x](\psi(x, \vec{v}))$. Suppose by way of contrapositive that $\mathcal{A} \not\models [\exists x](\psi(x, \vec{v}))$. Thus, there exists a $\vec{w}$ so that $\mathcal{A}, \vec{w} \not\models [\exists x](\psi(x, \vec{w}))$ and thus there exists $\vec{u}$ so that $\mathcal{A}, \vec{u} \not\models \psi(\vec{u})$. Thus, by the inductive hypothesis there exists an $A_k$ such that $A_k, \vec{u} \not\models \psi(\vec{u})$ and hence $A_k \not\models [\exists x](\psi(x, \vec{v})$ as desired.
Suppose $\varphi(\vec{v})$ is of the form $[\forall x](\psi(x, \vec{v}))$, then the inductive hypothesis holds of the formula $\psi(\vec{u})$ where $\vec{u}$ is $x, \vec{v}$ and we're done.
No, this is false. For example, suppose $A_n = ([n],\leq)$, where $[n]=\{0,\dots n-1\}$. Then $A= \bigcup A_n=(\mathbb{N},\leq)$. Consider the sentence $\varphi:\exists x\forall y\,(y\leq x)$ asserting that there is a greatest element. We have $A_n\models\varphi$ for all $n$, but $A\not\models\varphi$.
The sentences preserved by unions of chains in your sense are exactly the $\forall\exists$-sentences, i.e., those equivalent to a sentence of the form $\forall\overline{x}\exists\overline{y}\,\varphi(\overline{x},\overline{y})$, where $\varphi$ is quantifier-free. This is called the Chang-Łoś-Suszko theorem. It's one of the classical preservation results in model theory.
The counterexample above is an $\exists\forall$-sentence, with just one quantifier of each kind, which shows the Chang-Łoś-Suszko theorem can't be improved.