Exploration 3: Homomorphism preservation theorems

November 6, 2023.

The goal of this exploration is to show which formulas are preserved by which homomorphisms.

Each section introduces a different kind of formula, and for each we show

• a certain class of homomorphisms preserves this kind of formula
• the homomorphisms that preserve this kind of formula are exactly this class of homomorphisms

and therefore, homomorphisms can be classified by the kinds of formulas they preserve.

---

In this section, we show that homomorphisms are the maps that preserve atomic formulas.

Recall that homomorphisms are maps between $L$-structures preserving a structure’s constant elements, function symbols, and relation symbols.

Homomorphisms are equivalently defined as those which preserve atomic formulas $\phi(\bar{x})$. That is, when $A\models\phi(\bar{a})$, the homomorphisms are those maps $f:A\to B$ for which $B\models\phi(f\bar{a})$.

This equivalence can be proved by a sequence of equivalences:

$$\begin{aligned} &f\text{ is a homomorphism}&\\ \iff&\bar{t}(\bar{a})\in R^A\text{ implies }f\bar{t}(\bar{a})\in R^B&{\footnotesize (f\text{ preserves relations between terms }t(\bar{x})\text{ in }L)}\\ \iff&\bar{t}(\bar{a})\in R^A\text{ implies }\bar{t}(f\bar{a})\in R^B&{\footnotesize (\text{preserving relations also means }f\bar{t}(\bar{a})=\bar{t}(f\bar{a}))}\\ \iff&A\models R(\bar{t}(\bar{a}))\text{ implies }B\models R(\bar{t}(f\bar{a}))&{\footnotesize \bar{t}\in R^A,\text{by definition of}\models,\text{means }A\models R(\bar{t})}\\ \iff&A\models\phi(\bar{a})\text{ implies }B\models\phi(f\bar{a})&{\footnotesize R(\bar{t}(\bar{x}))\text{ defines an arbitrary atomic formula }\phi(\bar{x})}\\ \iff&f\text{ preserves atomic formulas}&{\footnotesize \text{definition of preserving atomic formulas }\phi(\bar{x})} \end{aligned}$$

where $\bar{a}$ is an arbitrary sequence of elements of $A$. The step “Preserving relations means preserving functions” requires some explaining – the idea is that if you preserve the relation $G(x,y,z)\implies G(fx,fy,fz)$, then you preserve a function $g(x,y)=z\implies g(fx,fy)=fz$ and vice versa.

So we’ve shown that if $f$ is a homomorphism, it preserves atomic formulas.

An embedding is a homomorphism where relations are preserved in both directions; that is, $\bar{a}\in R^A\iff f\bar{a}\in R^B$. Then you may replace “implies” with “iff” in each line of the proof above to show a corollary: that the embeddings are precisely the maps $f:A\to B$ where $A\models\phi(\bar{a})$ iff $B\models\phi(f\bar{a})$ for all atomic formulas $\phi$. (Theorem 1.3.1c)

In this section, we define precisely what is meant by $A\models\phi$ (for all first-order formulas in $L_{\infty\omega}$).

Previously we defined $A\models\phi$ only for atomic formulas $\phi$, since that’s all we needed to define canonical models. (We used Hintikka sets to help us define models for non-atomic formulas, but the proof did not require the definition of $A\models\phi$ for non-atomic $\phi$.)

Now we will be diving into such non-atomic formulas $\phi$ in $L_{\infty\omega}$, and as such we require a precise definition of $\models$ on non-atomic formulas. Here is a definition of $\models$ by induction on first-order formulas $\phi$, for which there are six cases:

• $A\models\phi(\bar{a})$ iff $(t_1^A(\bar{a}),\ldots,t_n^A(\bar{a}))\in R^A$. (as defined earlier)
• $A\models\lnot\psi(\bar{a})$ iff $A\not\models\psi(\bar{a})$.
• $A\models\bigwedge\Psi(\bar{a})$ iff $A\models\psi(\bar{a})$ for every formula $\psi\in\Psi$.
• $A\models\bigvee\Psi(\bar{a})$ iff $A\models\psi(\bar{a})$ for some formula $\psi\in\Psi$.
• $A\models\forall y\ldotp\psi(y,\bar{a})$ iff $A\models\psi(x, \bar{a})$ for all $x\in A$.
• $A\models\exists y\ldotp\psi(y,\bar{a})$ iff $A\models\psi(x, \bar{a})$ for some $x\in A$.

In this section, we show that embeddings are the maps that preserve existential formulas.

Not only do homomorphisms preserve atomic formulas, they preserve quantifier-free ones too.

Quantifier-free formulas (atomic formulas composed with just $\lor$, $\land$, and $\lnot$) are preserved by homomorphisms. This amounts to proving $A\models\phi(\bar{a})\iff B\models\phi(f\bar{a})$, which is done by induction on quantifier-free $\phi$ (4 cases).

Proof: by induction on $\phi$.

• $\phi(\bar{a})$ is atomic: all homomorphisms preserve atomic formulas, as discussed previously.
• The remaining cases are true because of the IH: $A\models\psi(\bar{a})\iff B\models\psi(f\bar{a})$.
• $\phi(\bar{a})$ is $\lnot\psi(\bar{a})$: then $A\models\lnot\psi(\bar{a})\iff B\models\lnot\psi(f\bar{a})$, which is true by IH.
• $\phi(\bar{a})$ is $\bigwedge\Psi(\bar{a})$: then $A\models ∧\psi(\bar{a})\iff B\models ∧\psi(f\bar{a})$, which is true by IH.
• $\phi(\bar{a})$ is $\bigvee\Psi(\bar{a})$: then $A\models ∨\psi(\bar{a})\iff B\models ∨\psi(f\bar{a})$, which is true by IH.

In this section, we show existential formulas are preserved by embeddings and that universal formulas are preserved in substructures.

While all homomorphisms preserve quantifier-free formulas, certain homomorphisms will preserve quantified formulas $\phi$ as well.

Recall we proved that the embeddings are precisely the maps $f:A\to B$ where $A\models\phi(\bar{a})$ iff $B\models\phi(f\bar{a})$ for all atomic formulas $\phi$; and that they are the homomorphisms that preserve relations in both directions, that is, $\bar{a}\in R^A\iff f\bar{a}\in R^B$.

For an embedding $f$, we’ve already proved $f$ preserves $\phi$, i.e. $A\models\phi(\bar{a})\iff B\models\phi(f\bar{a})$, in the case where $\phi$ is atomic. In the previous section, we saw that a homomorphism preserving atomic $\phi$ also preserves quantifier-free $\phi$. We will quickly show that embeddings in particular preserve $\exists_1$-formulas (existential formulas) – quantifier-free formulas $\phi(\bar{a})$ with any number of $\exists$ in front (so they look like $\exists x_0\exists x_1\exists x_2\psi$ where $\psi$ is quantifier-free).

Theorem: Embeddings $f:A\to B$ preserve $\exists_1$-formulas.

Proof: by induction on the $\exists_1$-formula $\phi(\bar{a})$.

• If $\phi$ is quantifier-free: already proved above.
• If $\phi$ is $\exists y\ldotp\psi(y,\bar{a})$, we have a chain of equivalences:

$$\begin{aligned} &A\models\phi(\bar{a})&\\ \iff&A\models\exists y\ldotp\psi(y, \bar{a})&{\footnotesize \text{since }\phi\text{ is }\exists\text{ with a quantifier-free part }\psi}\\ \iff&A\models\psi(c, \bar{a})\text{ for some }c\text{ in }A&{\footnotesize \text{by definition of }\models}\\ \iff&B\models\psi(fc, f\bar{a})&{\footnotesize \text{the embedding }f\text{ preserves quantifier-free }\psi\text{ in both directions}}\\ \iff&B\models\exists z\ldotp\psi(z, f\bar{a})&{\footnotesize \text{by definition of }\models}\\ \iff&B\models\phi(f\bar{a})&{\footnotesize \text{since }\phi\text{ is }\exists\text{ with a quantifier-free part }\psi} \end{aligned}$$

So indeed, embeddings preserve some formulas with quantifiers – $\exists_1$-formulas. In fact, since the proof works in reverse, we find that embeddings are the homomorphisms that preserve $_1-formulas.

What about the $\forall_1$-formulas? Just like $\exists_1$-formulas, $\forall_1$-formulas (universal formulas) are quantifier-free formulas $\phi(\bar{a})$ with any number of $\forall$ in front (so they look like $\forall x_0\forall x_1\forall x_2\psi$ where $\psi$ is quantifier-free). There is a dual theorem regarding $\forall_1$-formulas, and the proof relies on the fact that $\forall$ is logically equivalent to $\lnot\exists\lnot$.

Theorem: Substructures preserve $\forall_1$-formulas.

Proof:

• We can represent any $\forall_1$-formula by $\lnot\phi$, since $\phi$ is a $\exists_1$-formula.
• WTS $B\models\lnot\phi(\bar{a})\iff A\models\lnot\phi(f\bar{a})$, given that $A$ is a substructure of $B$.
• Whenever $A$ is a substructure of $B$, we have an embedding $f:A\to B$ (the inclusion map).
• Since $\phi$ is a $\exists_1$-formula, it’s preserved by embeddings: $A\models\phi(\bar{a})\iff B\models\phi(f\bar{a})$.
• The contrapositive is $\lnot(B\models\phi(\bar{a}))\iff\lnot(A\models\phi(f\bar{a}))$.
• By definition of $\models$, we get $B\models\lnot\phi(\bar{a})\iff A\models\lnot\phi(f\bar{a})$.
• So substructures preserve $\forall_1$-formulas $\lnot\phi$.

This proves that substructuring (the “reverse” of an embedding) preserves $\forall_1$-formulas. Since the proof works in reverse as well, we see that substructuring can be defined as the subset operation that preserves $\forall_1$-formulas.

In summary, we have shown that embeddings are the homomorphisms that preserve $\exists_1$-formulas, and restricting into a substructure preserves $\forall_1$-formulas.

In this section, we show positive formulas are the ones preserved by surjective homomorphisms.

A positive formula is one in which has no remaining $\lnot$, after simplifying it down to $\lnot,\lor,\land,\exists,\forall$ and pushing all the $\lnot$ inside quantifiers.

After seeing the previous preservation theorems, you might guess that there is a certain kind of homomorphism that preserves positive formulas:

Theorem: Surjective homomorphisms $f:A\to B$ preserve positive formulas $\phi$.

Proof: by induction on positive formulas $\phi$.

• If $\phi$ is quantifier-free, then we can apply the IH on each subformula. Then $\phi$ is trivially preserved.
• If $\phi$ is $\exists y\ldotp\psi(y,\bar{a})$ for some positive formula $\psi$, then assume that $A\models\phi(\bar{a})$. By definition of $\models$, this means there is some $c$ such that $A$ models the positive formula $\psi(c,\bar{a})$. By IH, $f$ preserves this positive formula and therefore $B\models\psi(fc,f\bar{a})$. Since $f$ is surjective, we know that $fc\in B$, and therefore $B\models\exists y\ldotp\psi(y,f\bar{a})$, i.e. $B\models\phi(f\bar{a})$, proving that $f$ preserves $\phi$.
• If $\phi$ is $\forall y\ldotp\psi(y,\bar{a})$ for some positive formula $\psi$, we proceed by a similar argument. By definition of $\models$ we have $A\models\psi(c,\bar{a})$ for every $c\in A$. By IH, $f$ preserves this positive formula and therefore $B\models\psi(fc,f\bar{a})$. Since $f$ is surjective, every $fc\in B$, and therefore $B\models\forall y\ldotp\psi(y,f\bar{a})$, i.e. $B\models\phi(f\bar{a})$, proving that $f$ preserves $\phi$.

By proving the converse, we get Lyndon’s Positivity Theorem: the homomorphisms that preserve positive formulas are the surjections. The proof of the converse typically goes like this:

Theorem: If a homomorphism $f:A\to B$ preserves positive formulas $\phi$, it is surjective.

Proof:

• If $f$ preserves positive formulas, it preserves the positive formula $\phi(y)\equiv\exists x\ldotp x=y$.
• If $B\models\phi(b)$ for some arbitrary $b\in B$, which it does since $b=b$ for all $b$. Since $f$ preserves the positive formula $\phi(b)$, we must have $A\models\phi(a)$ for the preimage $a\in A$, which is again true since $a=a$.
• This establishes that the preimage $a$ exists in $A$ for an arbitrary element $b\in B$. Therefore, $f$ is surjective.

So we have proved that surjections are exactly the homomorphisms that preserve positive formulas.

In this section, we pinpoint the kind of formulas that are preserved by all homomorphisms.

Every formula is preserved by an isomorphism, but we’ve also explored above that certain homomorphisms preserve certain formulas. To summarize, we have learned

• The Łoś-Tarski preservation theorem:
  • $\forall_1$-formulas are preserved by substructures.
  • $\exists_1$-formulas are preserved by embeddings.
• Lyndon’s positivity theorem:
  • Positive formulas are preserved by surjections.

Meanwhile, we’ve built up the class of formulas that are preserved for all homomorphisms. We first proved that atomic formulas are preserved by all homomorphisms. Then, we used that to show all quantifier-free formulas are preserved by all homomorphisms.

Finally, we can combine the last two results in the previous list; $\exists_1^+$-formulas (positive existential formulas) are preserved by both surjective homomorphisms and embeddings, and so they must be preserved by all homomorphisms. This relies on the fact that every homomorphism $f:A\to B$ can be thought of as a surjection $A\to im(f)$ combined with an inclusion map embedding $im(f)\to B$. Conversely, if your homomorphism $f$ preserves an arbitrary formula, it must be a $\exists_1^+$-formula since the surjection part of f can only preserve positive formulas and its inclusion part of f can only preserve existential formulas.

< Back to category Exploration 3: Homomorphism preservation theorems (permalink)
Exploration 2: Types Exploration 4: Diagrams

---