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 C is the set of all universal sentences true in all structures in 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 Facts[]

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.

Proofs[]

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. ::: ::: :::