## FANDOM

78 Pages

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.