Preservation theorems for alternating quantifiers.

Question

I know that in model theory there are preservation theorems for $\forall$ sentences, as well as $\exists$ sentences, and also $\forall \exists$ sentences. It is natural to wonder if one can continue the hierarchy. That is, are there preservation theorems for $\exists \forall$, $\forall \exists \forall$, etc sentences, as well as $\exists \forall \exists$, $\forall \exists \forall \exists$, etc sentences? Basically, I am wondering about preservation theorems for the alternating quantifier hierarchy.

Answer 1

From Mark Kamsma's answer, we learn that $\exists \forall$ formulas are preserved by $\forall$-preserving homomorphisms, $\exists \forall\exists$ formulas are preserved by $\forall\exists$-preserving homomorphisms, etc. This is correct, but it leaves something to be desired: can we give a semantic characterization of the homomorphisms which are $\forall$-preserving, $\forall\exists$-preserving, etc.?

In fact, we can. To set some notation:

• We call quantifier-free formulas $\forall_0$ and $\exists_0$.
• A formula is $\exists_{n+1}$ if it has the form $\exists \overline{y}\,\varphi(\overline{x},\overline{y})$ and $\varphi$ is $\forall_n$. Similarly, a formula is $\forall_{n+1}$ if it has the form $\forall \overline{y}\,\varphi(\overline{x},\overline{y})$ and $\varphi$ is $\exists_n$.
• Note that in both cases, the quantifier block $\exists\overline{y}$ may be empty, so every $\forall_n$ formula is $\exists_{n+1}$ and every $\exists_n$ formula is $\forall_{n+1}$.
• Note also that the negation of an $\exists_n$ formula is equivalent to a $\forall_n$ formula, and the negation of a $\forall_n$ formula is equivlant to an $\exists_n$ formula.

Let $f\colon A\to B$ be a homomorphism and $\varphi(\overline{x})$ a formula.

• We say that $f$ preserves $\varphi$ when for all $\overline{a}$ from $A$, if $A\models \varphi(\overline{a})$, then $B\models \varphi(f(\overline{a}))$.
• We say $f$ reflects $\varphi$ when for all $\overline{a}$ from $A$, if $B\models \varphi(f(\overline{a}))$, then $A\models \varphi(\overline{a})$
• Note that $f$ preserves $\varphi$ if and only if it reflects $\lnot \varphi$. In particular, $f$ preserves all $\exists_n$ formulas if and only if it reflects all $\forall_n$ formulas, and $f$ preserves all $\forall_n$ formulas if and only if it reflects all $\exists_n$ formulas.

---

Let $f$ be a homomorphism. We say $f$ is a $0$-embedding if it is an ordinary embedding. We say $f$ is an $(n+1)$-embedding if there exists an elementary embedding $e \colon A\to C$ and an $n$-embedding $g\colon B\to C$ such that $e = g\circ f$.

For example, $f$ is a $3$-embedding if and only if it fits into a commutative diagram like this: Note that in the diagram, the horizontal arrows are elementary embeddings and $i$ is required to be an embedding. It follows from the existence of the diagram that $h$ is a $1$-embedding, $g$ is a $2$-embedding, and $f$ is a $3$-embedding, but we don't require anything of $f$, $g$, and $h$ other than that they are homomorphisms.

Theorem: Let $f\colon A\to B$ be a homomorphism. The following are equivalent:

1. $f$ is an $n$-embedding.
2. $f$ preserves $\forall_n$ formulas.
3. $f$ preserves $\exists_{n+1}$ formulas.

Proof: First, let's check that 2 and 3 are equivalent. 3 implies 2 is trivial, since every $\forall_n$ formula is an $\exists_{n+1}$ formula. The implication from 2 to 3 is explained in Mark Kamsma's answer: taking $\Delta$ to be $\forall_n$, $\Sigma$ is $\exists_{n+1}$, and any homomorphism preserving $\Delta$ formulas also preserves $\Sigma$ formulas.

Now let's prove that 1 and 2 are equivalent by induction on $n$. In the base case, a homomorphism is an embedding (a $0$-embedding) if and only if it preserves all quantifier-free ($\forall_0$) formulas.

For the inductive step, assume $f$ is an $(n+1)$-embedding. Then there is an elementary embedding $e \colon A\to C$ and an $n$-embedding $g\colon B\to C$ such that $e = g\circ f$. Let $\varphi(\overline{x})$ be a $\forall_{n+1}$-formula, and suppose $A\models \varphi(\overline{a})$. Since $e$ is an elementary embedding, $C\models \varphi(e(\overline{a}))$, so $C\models \varphi(g(f(\overline{a})))$. Since $g$ is an $n$-embedding, by induction $g$ preserves $\exists_{n+1}$ formulas, so $g$ reflects $\forall_{n+1}$ formulas, in particular $\varphi$. So $B\models \varphi(f(\overline{a}))$, as was to be shown.

Conversely, assume $f$ preserves $\forall_{n+1}$ formulas. To show $f$ is an $(n+1)$-embedding, it suffices to show that $\mathrm{EDiag}(A)\cup \mathrm{Diag}_{\forall_n}(B)\cup \{a = f(a)\mid a\in A\}$ is consistent. Indeed, a model $C$ of this theory will admit an elementary embedding $e\colon A\to C$ and a $\forall_n$-preserving map $g\colon B\to C$ (which is an $n$-embedding by induction), such that $e = g\circ f$. By compactness, it suffices to show that $\mathrm{EDiag}(A)\cup \{\psi(\overline{a},\overline{b})\}$ is consistent, where $\psi(f(\overline{a}),\overline{b})$ is an arbitrary sentence in $\mathrm{Diag}_{\forall_n}(B)$, with the parameters $f(\overline{a})$ in the image of $f$ separated from the parameters $\overline{b}$ not in the image of $f$. To do this, it suffices to show that $\exists \overline{y}\,\psi(\overline{a},\overline{y})$ is true in $A$. But $\exists \overline{y}\,\psi(\overline{x},\overline{y})$ is $\exists_{n+1}$, $B\models \exists \overline{y}\,\psi(f(\overline{a}),\overline{y})$, and $f$ reflects $\exists_{n+1}$ formulas, so we're done.

---

Now we can prove preservation results for $\exists_n$ and $\forall_n$ formulas. This answer is already long enough, so I'll just say that the theorem can be proven by standard methods for preservation theorems, as in Tent & Ziegler Section 3.1, for example.

Theorem: Let $\varphi$ be a formula. Then $\varphi$ is equivalent to an $\exists_{n+1}$ formula if and only if it is preserved by all $n$-embeddings, and $\varphi$ is equivalent to a $\forall_{n+1}$ formula if and only if it is reflected by all $n$-embeddings.

Note that this says that a sentence is equivalent to a $\forall_2$ (i.e., $\forall\exists$) sentence if and only if it is reflected by all $1$-embeddings. This is quite different from the Chang-Łoś-Suszko preservation theorem, which characterizes $\forall_2$ sentences as those preserved in directed colimits. I am not aware of any generalization of the Chang-Łoś-Suszko theorem to $\forall_n$ sentences for $n>2$, but it would be interesting if there were one!

Answer 2

Let $\Delta$ be any set of formulas containing all atomic formulas and closed under conjunction ($\wedge$) and disjunction ($\vee$). This includes the propositional constants for true $\top$ and false $\bot$.

Let $\Sigma$ be the set of formulas of the form $\exists \bar{x} \varphi(\bar{x})$, where $\varphi(\bar{x}) \in \Delta$. Similarly, let $\Pi$ be the set of formulas of the form $\neg \exists \bar{x} \varphi(\bar{x})$, where $\varphi(\bar{x}) \in \Delta$. We allow for quantification over an empty string, so in particular $\Delta \subseteq \Sigma$ and $\Delta \subseteq \Pi$.

For convenience we will identify logically equivalent formulas. In particular, this means that $\Sigma$ and $\Pi$ are closed under conjunction and disjunction.

We define a $\Delta$-homomorphism $f: M \to N$ between structures in our language as a function such that for any $\bar{a} \in M$ and any $\varphi(\bar{x}) \in \Delta$ we have that $$ M \models \varphi(\bar{a}) \implies N \models \varphi(f(\bar{a})). $$ For such a $\Delta$-homomorphism we have that:

1. it preserves truth of $\Sigma$-formulas, i.e. for any $\psi(\bar{x}) \in \Sigma$ and $\bar{a} \in M$ such that $M \models \psi(\bar{a})$ we have $N \models \psi(f(\bar{a}))$;
2. it reflects truth of $\Pi$-formulas, i.e. for any $\psi(\bar{x}) \in \Pi$ and $\bar{a} \in M$ such that $N \models \psi(f(\bar{a}))$ we have $M \models \psi(\bar{a})$.

We prove (1) first. Write $\psi(\bar{x})$ as $\exists \bar{y} \varphi(\bar{x}, \bar{y})$ with $\varphi(\bar{x}, \bar{y}) \in \Delta$. Then as $M \models \exists \bar{y} \varphi(\bar{a}, \bar{y})$ we find $\bar{b} \in M$ such that $M \models \varphi(\bar{a}, \bar{b})$. As $f$ is a $\Delta$-homomorphism we then have $N \models \varphi(f(\bar{a}), f(\bar{b}))$ and hence $N \models \psi(f(\bar{a}))$, as required.

For (2) we can use (1). As $\psi(\bar{x}) \in \Pi$ we have $\neg \psi(\bar{x}) \in \Sigma$. So if $M \models \neg \psi(\bar{a})$ then by part (1) we have $N \models \neg \psi(f(\bar{a}))$, which contradicts $N \models \psi(f(\bar{a}))$. We must thus have $M \models \psi(\bar{a})$, as required.

---

If we now take $\Delta$ to be the set of quantifier-free formulas then the $\Sigma$-formulas are exactly the $\exists$-formulas, and the $\Pi$-formulas are exactly the $\forall$-formulas, while $\Delta$-homomorphisms are exactly the embeddings. So we retrieve the motivating "preservation theorems".

Now if we let $\Delta$ be the set of all $\forall$-formulas then $\Sigma$ is the set of all $\exists \forall$-formulas, while $\Pi$ is exactly the set of all $\forall \exists$-formulas. So now you get "preservation theorems" for one alternation of quantifiers with respect to $\Delta$-homomorphisms, which are in this case embeddings $f$ that preserve truth of $\forall$-formulas upwards. The latter is equivalent to $f: M \to N$ being such that for all $\bar{a} \in M$ and all $\varphi(\bar{x})$, which is either an $\exists$-formula or $\forall$-formula, we have $$ M \models \varphi(\bar{a}) \quad \Longleftrightarrow \quad N \models \varphi(f(\bar{a})). $$

So now you can build "preservation theorems" as you want using this tool.

---

All of this is just positive logic in disguise. If we take $\Delta$ to be as small as possible: the set of positive quantifier free formulas (i.e. atomic formulas, and close under conjunction and disjunction) then $\Delta$-homomorphisms become just homomorphisms and $\Sigma$ is the set of all positive formulas. By working in a partially Morleyised theory (introducing relation symbols and declaring them equivalent to certain formulas) we can then obtain any other $\Delta$ that we want.