FANDOM


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 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 MN 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 MN 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 MN 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 MN, 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 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 $ 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 MN 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. QEDclaim.

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.