A universal formula is a formula of the form

with 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 of the form

with 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 MN is an inclusion of structures, a is a tuple from M, and is an existential formula, then

• Universal formulas are preserved downwards in inclusions of structures: if MN is an inclusion of structures, a is a tuple from M, and is a universal formula, then

• Conversely, suppose that is preserved upwards or downwards in inclusions of structures. Then is equivalent to an existential or universal formula, respectively.
• More generally, suppose that T is a theory and is preserved upwards in inclusions of models of T. In other words, suppose that whenever MN is an inclusion of models of T, and a is a tuple from M, we have

THEN is equivalent mod T to an existential formula. That is, there is an existential formula such that

• Similarly, if T is a theory and is preserved downwards in models of T, then 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 of a universal formula is equivalent by De Morgan's laws to the existential formula . 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

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

Lemma 1: Existential statements are preserved upwards in inclusions: if MN, a is a tuple from M, is existential, and , then . Similarly, universal statements are preserved downwards.

Proof: Write as . Since , we have for some tuple b from M. As is quantifier-free, has the same truth value in M as in N. (The ambient model only affects the interpretation of quantifiers.) Therefore, holds, so

,

i.e., . So existential formulas are preserved upwards in inclusions.

Meanwhile, if is a universal formula, then is an existential formula. Since is preserved upwards, is preserved downwards (this is the contrapositive). QED.

In particular, if MN 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 be the L(M)-theory consisting of the union of T with the diagram of M. If 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 is not consistent. By compactness, some finite subset of is inconsistent. The part of this finite subset coming from the diagram of M can be expressed by a single statement of the form , where a is a tuple from M, is a quantifier-free L-formula, and .

Then we are saying that is inconsistent. By the Lemma on Constants,

In particular, is part of T. Therefore it must hold in M, by assumption. But

implies

contradicting the fact that . 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 be a formula. Suppose that is preserved upwards in models of T, i.e., if MN is an inclusion of models of T, and a is a tuple from M, then

Then there is an existential formula which is equivalent to 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 holds, it holds because of an existential formula.

Claim: If M is a model of T and for some a, then there is an existential formula such that

, i.e., implies mod T

and

.

Proof: Let consist of the the union of T, the diagram of M, and the statement . If has a model N, then N is a model of T extending M, in which holds. This contradicts the hypothesis that is preserved upwards in inclusions of models of T.

Therefore 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 and some b in M such that and

is inconsistent. By the Lemma on constants,

Equivalently,

Now let be the formula . This is an existential formula, and it implies , mod T. Also, , by taking y = c. So we have proven the claim. QEDclaim.

Now let be the set of all formulas , where is existential and implies .

Consider the theory

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

.

By the claim, must hold because of some existential formula: there must be an existential formula which implies , with holding in M. But then is one of the formulas in . Since , we have , contradicting the fact that holds in M.

In other words, the Claim means exactly that is inconsistent. Now by compactness, some finite subset of is inconsistent. Therefore we can find finitely many existential formulas , each implying , such that

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

So, mod T, implies the formula . Conversely, since each implies , so does their disjunction . Therefore,

is equivalent to , mod T.

But is a disjunction of existential formulas, so it is itself an existential formula. Thus is equivalent to an existential formula. This completes the proof of the first claim of the Theorem.

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