A **universal formula** is a formula $ \phi(x) $ of the form

- $ \forall y : \psi(x;y) $

with $ \psi(x;y) $ quantifier-free. (Here, *x* and *y* are tuples).

A **universal theory** is a theory consisting of universal sentences. Give a structure *M*, **the universal theory of M **denotes the set of all universal sentences true in

*M*. More generally, if

*C*is a class of structures in some language, then

**the universal theory of**is the set of all universal sentences true in all structures in

*C**C*.

If *T* is a theory, *T*_{∀} denotes the set of all universal sentences implied by *T*. If *T* is the elementary theory of a class of structures *C*, then *T*_{∀} is the universal theory of *C*.

Similarly, an **existential formula** is a formula $ \phi(x) $ of the form

- $ \exists y : \psi(x;y) $

with $ \psi(x;y) $ quantifier-free. One could also define the notion of "existential theory" but this turns out to not be particularly useful.

## Important FactsEdit

- If
*T*is a universal theory and*M*is a model of*T*, any substructure of*M*is a model of*T*. - Conversely, suppose
*T*is a theory with the property that every substructure of a model of*T*is also a model of*T*. Then*T*is equivalent to a universal theory. - If
*T*is any theory, then a structure*M*is a model of*T*_{∀}if and only if*M*embeds as a substructure into a model of*T*.

On the level of formulas, worthwhile things to know are:

- Positive boolean combinations of universal formulas are (equivalent to) universal formulas. Positive boolean combinations of existential formulas are existential formulas.
- Negations of universal formulas are existential, and vice versa.
- Existential formulas are preserved upwards in inclusions of structures: if
*M*⊆*N*is an inclusion of structures,*a*is a tuple from*M*, and $ \phi(x) $ is an existential formula, then

- $ M \models \phi(a) \implies N \models \phi(a) $

- Universal formulas are preserved downwards in inclusions of structures: if
*M*⊆*N*is an inclusion of structures,*a*is a tuple from*M*, and $ \phi(x) $ is a universal formula, then

- $ N \models \phi(a) \implies M \models \phi(a) $

- Conversely, suppose that $ \phi(x) $ is preserved upwards or downwards in inclusions of structures. Then $ \phi(x) $ is equivalent to an existential or universal formula, respectively.
- More generally, suppose that
*T*is a theory and $ \phi(x) $ is preserved upwards in inclusions of*models of T*. In other words, suppose that whenever*M*⊆*N*is an inclusion of models of*T*, and*a*is a tuple from*M*, we have

- $ M \models \phi(a) \implies N \models \phi(a) $
- THEN $ \phi(x) $ is equivalent mod
*T*to an existential formula. That is, there is an existential formula $ \phi'(x) $ such that - $ T \vdash \forall x : \phi(x) \leftrightarrow \phi'(x) $

- Similarly, if
*T*is a theory and $ \phi(x) $ is preserved downwards in*models of T*, then $ \phi(x) $ is equivalent mod*T*to a universal formula.

These last two points play a key role in the proof that the different characterizations of model completeness are equivalent.

## ProofsEdit

The negation $ \neg \forall y : \psi(x;y) $ of a universal formula is equivalent by De Morgan's laws to the existential formula $ \exists y : \neg \psi(x;y) $. Similarly, the negation of an existential formula is equivalent to a universal formula.

Existential formulas are closed under positive boolean combinations because of the equivalences

- $ \left(\exists y: \phi(x;y)\right) \wedge \left(\exists z : \psi(x;z)\right) \iff \exists y \exists z : \phi(x;y) \wedge \psi(x;z) $
- $ \left(\exists y: \phi(x;y)\right) \vee \left(\exists z : \psi(x;z)\right) \iff \exists y \exists z : \phi(x;y) \vee \psi(x;z) $

By De Morgan's laws, the same holds for universal formulas.

**Lemma 1:** Existential statements are preserved upwards in inclusions: if *M* ⊆ *N*, *a* is a tuple from *M*, $ \phi(x) $ is existential, and $ M \models \phi(a) $, then $ N \models \phi(a) $. Similarly, universal statements are preserved downwards.

*Proof:*
Write $ \phi(x) $ as $ \exists y : \psi(x;y) $. Since $ M \models \phi(a) $, we have $ M \models \psi(a;b) $ for some tuple *b* from *M*. As $ \psi(x;y) $ is quantifier-free, $ \psi(a;b) $ has the same truth value in *M* as in *N*. (The ambient model only affects the interpretation of quantifiers.) Therefore, $ N \models \psi(a;b) $ holds, so

- $ N \models \exists y : \psi(a;y) $,

i.e., $ N \models \phi(a) $. So existential formulas are preserved upwards in inclusions.

Meanwhile, if $ \chi(x) $ is a *universal* formula, then $ \neg \chi(x) $ is an existential formula. Since $ \neg \chi $ is preserved upwards, $ \chi $ is preserved downwards (this is the contrapositive).
QED.

In particular, if *M* ⊆ *N* and *M* satisfies some existential *sentence*, then so does *N*. And if *N* satisfies some *universal* sentence, then so does *M*. Therefore we have:

**Corollary 2:** If *T* is a universal theory, then any substructure of a model of *T* is a model of *T*.

**Lemma 3:** Let *T* be a theory, and suppose *M* is a model of *T*_{∀}. Then *M* embeds into a model of *T*.

*Proof:* Let *L* be the language of *T*. Let $ T' $ be the *L*(*M*)-theory consisting of the union of *T* with the diagram of *M*. If $ T' $ is consistent, it has a model *N*. Then *N* is a model of the diagram of *M*, so *M* is a substructure of *N*. Also, *N* is a model of *T*. So we are done.

Suppose therefore that $ T' $ is not consistent. By compactness, some finite subset of $ T' $ is inconsistent. The part of this finite subset coming from the diagram of *M* can be expressed by a single statement of the form $ \chi(a) $, where *a* is a tuple from *M*, $ \chi(x) $ is a quantifier-free *L*-formula, and $ M \models \chi(a) $.

Then we are saying that $ T \cup \{\chi(a)\} $ is inconsistent. By the Lemma on Constants,

- $ T \vdash \forall x : \neg \chi(x) $

In particular, $ \forall x : \neg \chi(x) $ is part of *T*_{∀}. Therefore it must hold in *M*, by assumption. But

- $ M \models \forall x : \neg \chi(x) $ implies $ M \models \neg \chi(a) $

contradicting the fact that $ M \models \chi(a) $. QED.

**Corollary 4:** Suppose *T* is a theory with the property that every substructure of a model of *T* is itself a model of *T*. Then *T* is equivalent to a universal theory. In fact, *T* is equivalent to *T*_{∀}.

*Proof:*
Indeed, any model of *T* embeds into a model of *T* (namely, itself), and so is a model of *T*_{∀}. Conversely, if *M* is a model of *T*_{∀}, then *M* embeds into a model *N* of *T*. But then *M* is a substructure of a model of *T*, so by assumption, *M* is itself a model of *T*. Therefore, models of *T* are the same thing as models of *T*_{∀}. QED.

We have proven all the claims above except

**Theorem 5:** Let *T* be a theory (possibly the empty theory). Let $ \phi(x) $ be a formula. Suppose that $ \phi(x) $ is preserved upwards in models of *T*, i.e., if *M* ⊆ *N* is an inclusion of models of *T*, and *a* is a tuple from *M*, then

- $ M \models \phi(a) \implies N \models \phi(a) $

Then there is an existential formula $ \phi'(x) $ which is equivalent to $ \phi(x) $ mod *T*. Similarly, any formula which is preserved downwards in inclusions of models of *T* is equivalent to a universal formula.

*Proof:*

First we show that whenever $ \phi(x) $ holds, it holds because of an existential formula.

**Claim:** If *M* is a model of *T* and $ M \models \phi(a) $ for some *a*, then there is an existential formula $ \psi(x) $ such that

- $ T \vdash \forall x : \psi(x) \rightarrow \phi(x) $, i.e., $ \psi $ implies $ \phi $ mod
*T*

and

- $ M \models \psi(a) $.

*Proof:*
Let $ T' $ consist of the the union of *T*, the diagram of *M*, and the statement $ \neg \phi(a) $. If $ T' $ has a model *N*, then *N* is a model of *T* extending *M*, in which $ \neg \phi(a) $ holds. This contradicts the hypothesis that $ \phi(x) $ is preserved upwards in inclusions of models of *T*.

Therefore $ T' $ is inconsistent. By compactness, this inconsistency must be witnessed by a finite part of the diagram of *M*. Therefore, there is some quantifier-free formula $ \chi(x,y) $ and some *b* in *M* such that $ M \models \chi(a,b) $ and

- $ T \cup \{\neg \phi(a)\} \cup \{\chi(a,b)\} $

is inconsistent. By the Lemma on constants,

- $ T \vdash \forall x, y : \chi(x,y) \rightarrow \phi(x) $

Equivalently,

- $ T \vdash \forall x : (\exists y : \chi(x;y)) \rightarrow \phi(x) $

Now let $ \psi(x) $ be the formula $ \exists y : \chi(x;y) $. This is an existential formula, and it implies $ \phi(x) $, mod *T*. Also, $ M \models \psi(a) $, by taking *y* = *c*. So we have proven the claim. QED_{claim}.

Now let $ \Psi(x) $ be the set of all formulas $ \neg \psi(x) $, where $ \psi(x) $ is existential and implies $ \phi(x) $.

Consider the theory

- $ T'' = T \cup \{\phi(a)\} \cup \Psi(a) $

where *a* is a new constant. Suppose $ T'' $ has a model *M*, and let *a* be the interpretation of the symbol *a* in *M*. Then *M* is a model of *T*, and

- $ M \models \phi(a) $.

By the claim, $ \phi(a) $ must hold *because of* some existential formula: there must be an existential formula $ \psi(x) $ which implies $ \phi(x) $, with $ \psi(a) $ holding in *M*. But then $ \neg \psi(x) $ is one of the formulas in $ \Psi(x) $. Since $ M \models T \supset \Psi(a) $, we have $ M \models \neg \psi(a) $, contradicting the fact that $ \psi(a) $ holds in *M*.

In other words, the Claim means exactly that $ T'' $ is inconsistent. Now by compactness, some finite subset of $ T'' $ is inconsistent. Therefore we can find finitely many existential formulas $ \psi_1(x),\ldots,\psi_n(x) $, each implying $ \phi(x) $, such that

- $ T \cup \{\phi(a), \neg \psi_1(a), \ldots, \neg \psi_n(a)\} $

is inconsistent. By the Lemma on Constants, this means that

- $ T \vdash \forall x : \phi(x) \rightarrow \bigvee_{i = 1}^n \psi_i(x) $

So, mod *T*, $ \phi(x) $ implies the formula $ \bigvee_{i = 1}^n \psi_i(x) $. Conversely, since each $ \psi_i(x) $ implies $ \phi(x) $, so does their disjunction $ \bigvee_{i = 1}^n \psi_i(x) $. Therefore,

- $ \phi(x) $ is equivalent to $ \bigvee_{i = 1}^n \psi_i(x) $, mod
*T*.

But $ \bigvee_{i = 1}^n \psi_i(x) $ is a disjunction of existential formulas, so it is itself an existential formula. Thus $ \phi(x) $ is equivalent to an existential formula. This completes the proof of the first claim of the Theorem.

For the other, suppose that $ \phi(x) $ is a formula which is preserved *downwards* in inclusions of models of *T*. Then, contrapositively, $ \neg \phi(x) $ is preserved *upwards*. So, by what we have shown, $ \neg \phi(x) $ is equivalent to an existential formula. Then $ \phi(x) $ is equivalent to the negation of an existential formula, i.e., to a universal formula. QED.