Łoś–Tarski preservation theorem

Short description: Theorem in model theory

The Łoś–Tarski theorem, also called the Łoś–Tarski preservation theorem or substructure preservation theorem, is a result in model theory that states the first-order properties are preserved when passing to substructures. It states that a first-order sentence is preserved under substructures if and only if it is logically equivalent to a universal sentence.

The theorem is named after Jerzy Łoś and Alfred Tarski. It is one of the classical preservation theorems of model theory, which relate semantic closure properties of classes of structures to syntactic fragments of first-order logic.

Statement

Let $T$ be a theory in a first-order logic language $L$ and $\mathrm{\Phi }(\overline{x})$ a set of formulas of $L$. (The sequence of variables $\overline{x}$ need not be finite.) Then the following are equivalent:

1. If $A$ and $B$ are models of $T$, $A\subseteq B$, $\overline{a}$ is a sequence of elements of $A$. If $B\models \bigwedge \mathrm{\Phi }(\overline{a})$, then $A\models \bigwedge \mathrm{\Phi }(\overline{a})$.
   ($\mathrm{\Phi }$ is preserved in substructures for models of $T$)
2. $\mathrm{\Phi }$ is equivalent modulo $T$ to a set $\mathrm{\Psi }(\overline{x})$ of ${\mathrm{\forall }}_1$ formulas of $L$.

A formula is ${\mathrm{\forall }}_1$ if it is of the form $\mathrm{\forall }\overline{y}\psi (\overline{x},\overline{y})$, where $\psi$ is quantifier-free and $\overline{x}$ denotes the free variables.

In more common terms, this states that every first-order formula is preserved under induced substructures if and only if it is ${\mathrm{\forall }}_1$, i.e. logically equivalent to a first-order universal formula. As substructures and embeddings are dual notions, this theorem is sometimes stated in its dual form: every first-order formula is preserved under embeddings on all structures if and only if it is ${\mathrm{\exists }}_1$, i.e. logically equivalent to a first-order existential formula.

A special case is obtained when $T$ is empty, and $\mathrm{\Phi }$ contains only a single sentence $\phi$. In this case, the theorem states that $\phi$ is preserved under taking substructures if and only if it is logically equivalent to a universal sentence. Applying this characterization to negations gives the extension-preservation result: that a first order sentence is preserved under extensions if and only if it is logically equivalent to an existential sentence.

Note that this property fails for finite models.

Proof

In the usual formulation of the theorem, let $\phi$ be a first order sentence. Suppose first that $\phi$ is logically equivalent to the universal sentence $\mathrm{\forall }\overline{x},\psi (\overline{x})$, where $\psi$ is quantifier free. If $A\subseteq B$ and $B\models \phi$, then for every tuple $\overline{a}$ of elements of $A$, $B\models \psi (\overline{a})$. But quantifier free formulas have the same truth value in a structure and its substructure when evaluated on elements of the substructure, so $A\models \psi (\overline{a})$. Thus, $A\models \phi$. Therefore every universal sentence is preserved under substructures.

Conversely, let $\phi$ be preserved under substructures. Then, let $\mathrm{\Gamma }$ be the set of all universal sentences that logically follow from $\phi$. We show that $\mathrm{\Gamma }\models \phi$.

Let $A\models \mathrm{\Gamma }$. Add a constant symbol for each element of $A$, and let $\mathrm{Diag}(A)$ be the diagram of $A$, consisting of the atomic and negated atomic sentences true in this expanded structure. The theory

$$\phi \cup \mathrm{Diag}(A)$$

is satisfiable. Otherwise, by the compactness theorem, some finite conjunction $\delta (\overline{a})$ of sentences from $\mathrm{Diag}(A)$ would be inconsistent with $\phi$. Replacing the new constant symbols in $\delta (\overline{a})$ with variables gives

$$\phi \models \mathrm{\forall }\overline{x},\mathrm{\neg }\delta (\overline{x}).$$

Since $\delta$ is quantifier free, this is a universal consequence of $\phi$, and thus belongs to $\mathrm{\Gamma }$. But $A\models \delta (\overline{a})$, contradicting $A\models \mathrm{\Gamma }$.

Thus $\phi \cup \mathrm{Diag}(A)$ has a model $B$. By the diagram lemma, $A$ is isomorphic to a substructure of the reduct of $B$. Since $B\models \phi$ and $\phi$ is preserved under substructures, it follows that $A\models \phi$. Thus $\mathrm{\Gamma }\models \phi$.

By compactness, there is a finite subset ${\mathrm{\Gamma }}_0\subseteq \mathrm{\Gamma }$ such that ${\mathrm{\Gamma }}_0\models \phi$. By definition of $\mathrm{\Gamma }$, $\phi$ implies every sentence in ${\mathrm{\Gamma }}_0$. Therefore

$$\phi \equiv \bigwedge {\mathrm{\Gamma }}_0.$$

A finite conjunction of universal sentences is equivalent to a universal sentence. Thus $\phi$ is logically equivalent to a universal sentence, completing the converse and proof.

References

• Hinman, Peter G. (2005). Fundamentals of Mathematical Logic. A K Peters. p. 255. ISBN 1568812620.