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.
On the level of formulas, worthwhile things to know are:
THEN is equivalent mod T to an existential formula. That is, there is an existential formula such that
These last two points play a key role in the proof that the different characterizations of model completeness are equivalent.
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 M ⊆ N, 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 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 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
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 M ⊆ N 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.
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
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,
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. ::: ::: :::