Let M ⊆ N be an inclusion of structures, in the same signature. One says that M is existentially closed in N (sometimes denoted M ≤₁ N) if for every existential formula $\phi (x)$ and every tuple a from M, one has

$M\models \phi (a)\iff N\models \phi (a)$

The left-to-right direction is automatic, by general properties of existential formulas. So the real content here is that $N\models \phi (a)$ implies $M\models \phi (a)$ .

We can also describe existential closedness in terms of quantifier-free formulas: M is existentially closed in N if and only if for every quantifier-free formula $\psi (x;y)$ , every tuple a from M, and every tuple b from N, if $N\models \psi (a;b)$ , then $M\models \psi (a;b')$ for some tuple b' from M. Equivalently

$N\models \exists y:\psi (a;y)\implies M\models \exists y:\psi (a;y)$ .

Since $\exists y:\psi (x;y)$ can be any existential formula, this is equivalent to the definition in terms of existential formulas.

Another way of paraphrasing this is: if some quantifier-free M-definable set has a point in N, then it has one in M.

If M is a model of a theory T, we say that M is existentially closed if M is existentially closed in every model of T extending M. This depends on the theory T, and is not a property of the structure M alone.

To some extent, one can think of "existential closedness" for models as generalizing the notion of "algebraic closedness" for fields. Indeed, if T is the theory of fields, the existentially closed models of T are exactly the algebraically closed fields (proven below).

Checking existential closedness[]

A theory T is model complete if and only if all models are existentially closed. Equivalently, whenever M ⊆ N is an inclusion of models of T, M is existentially closed in N. There are several other characterizations of model completeness, and it turns out, for example, that any theory with quantifier elimination is model complete.

In checking model completeness, it turns out that one can restrict to the case of very simple formulas:

Lemma: Let M ⊆ N be an inclusion of structures. For M to be existentially closed in N it is sufficient (and obviously necessary) that the following condition holds:

If $\phi _{1}(x;y),\ldots ,\phi _{n}(x;y)$ is a finite list of atomic and negated-atomic formulas, and a is a tuple from M, then

$N\models \exists y:\bigwedge _{i=1}^{n}\phi _{i}(a;y)\implies M\models \exists y:\bigwedge _{i=1}^{n}\phi _{i}(a;y)$

or equivalently,

$\bigcap _{i=1}^{n}\phi _{i}(a;N)\neq \emptyset \implies \bigcap _{i=1}^{n}\phi _{i}(a;M)$ .

Intuitively speaking, the $\phi _{i}(a;y)$ are "equations" in the variables y, with "coefficients" a from M. We are saying that if a system of equations over M has a solution in N, then it has one in M.

Proof: Existential closedness means that for every existential formula $\psi (x)$ and every tuple a from M,

$N\models \psi (a)\implies M\models \psi (a)\qquad (*)$ .

The Lemma is saying that it suffices to check only the existential formulas of the form $\exists y:\phi (x;y)$ with $\phi (x;y)$ a conjunction of atomic and negated atomic formulas.

Why does this suffice? Because of the following three easily-verified facts:

If (*) holds for $\psi _{1}(x)$ and $\psi _{2}(x)$ , then it holds for $\psi _{1}(x)\vee \psi _{2}(x)$ .
Every quantifier free formula can be written as a disjunction of conjunctions of possibly negated atomic formulas. This follows from the distributive law in boolean algebra.
$\exists y:\chi _{1}(y)\vee \chi _{2}(y)$ is logically equivalent to $\left(\exists y:\chi _{1}(y)\right)\vee \left(\exists y:\chi _{2}(y)\right)$ . In particular, we can pull disjunctions outside the quantifiers.

The second two facts imply that any existential formula is a disjunction of existential formulas of the form mentioned in the Lemma (disjunction-free existential formulas). The first bullet point allows us therefore to reduce to just checking those formulas. QED.

Example: Rings[]

Let S be a subring of R. When is S existentially closed in R? By the Lemma above, a necessary and sufficient condition is that whenever $\phi _{i}(x;y)$ is a posibly negated atomic formula for each i, and s is a tuple from S, we have

$R\models \exists y:\bigwedge _{i=1}^{n}\phi _{i}(s;y)\implies S\models \exists y:\bigwedge _{i=1}^{n}\phi _{i}(s;y)$ .

In the language of rings, the $\phi _{i}$ can only be of the form $P(x;y)=0$ or $P(x;y)\neq 0$ , where $P(x;y)$ is a polynomial in the variables x and y, with $\mathbb {Z}$ -coefficients.

In other words, S is existentially closed in R if and only if the following holds:

If a system of algebraic equations and inequations, with coefficients in S, has a solution in R, then it has a solution in S.

Here are some non-examples:

The integers Z are not existentially closed in the rationals Q. Indeed, the equation 2x = 1 has a solution in Q, but not in Z.
The rationals Q are not existentially closed in the reals R because the equation x² = 2 has a solution in R but not in Q.
Similarly, the reals are not existentially closed in C, because -1 has a square root in C but not in R.
The integers Z are not existentially closed in Z × Z, because the system of equations u² = u, u ≠ 0, u ≠ 1 has a solution in Z × Z (namely, the element (1,0)), but does not have a solution in Z.
More generally, if S ⊆ R, S is an integral domain, and R is not, then S is not existentially closed in R', because the system xy = 0, x ≠ 0, y ≠ 0 has a solution in R, but not in S.
If S is a reduced ring (no nilpotents), and R is not, then S is not existentially closed in R, because the system x² = 0, x ≠ 0 has a solution in R, but not in S.

It is less trivial to produce actual examples:

Theorem: Let K be algebraically closed, and let L be an extension field. Then L is existentially closed in K. For example, the field of algebraic numbers is existentially closed in the field of complex numbers.

Proof: Given a system of equations over K, with a solution in L, we can safely replace all inequations with equations, by replacing

$P(x)\neq 0$

with

$P(x)t=1$

where t is a new dummy variable. This can be done safely, because L is a field. So we need to show that any system of equations over K which has a solution in L already has one in K.

Write the system as $\bigwedge _{i=1}^{n}P_{i}({\vec {x}})=0$ , where each $P_{i}({\vec {x}})$ is a polynomial over K. If this system has no solution in K, then by the Nullstellensatz, the polynomials $P_{i}({\vec {x}})$ generate the unit ideal (1) in the polynomial algebra $K[x]$ . That is, there exist polynomials $Q_{i}({\vec {x}})$ such that

$1=\sum _{i}P_{i}({\vec {x}})Q_{i}({\vec {x}})$ .

This remains true after base changing to L, of course, and consequently no point with coordinates in L can be a simultaneous zero of all the $P_{i}$ 's. This contradicts the assumption that the system of equations had some solution in L. QED.

As an example "application" of this fact, we see that the theory of algebraically closed fields is model complete. Also,

Corollary: A field is existentially closed (as a field) if and only if it is algebraically closed.

Proof: By the Theorem, every algebraically closed field is existentially closed. Conversely, if K is a field that is not algebraically closed, then K is not existentially closed in its algebraic closure: some equation in one variable has a solution in the algebraic closure of K, but not in K itself. QED.

Existentially closed models of Inductive Theories[]

In general, a theory may have no existentially closed models. For example, let T be the theory of ordered sets (M,<) with the property that every element of M has a successor and a predecessor, i.e.,

$\forall x\exists y:x<y\wedge \neg \exists z:x<z<y$

$\forall x\exists y:x>y\wedge \neg \exists z:x>z>y$

Then T has models (for example, the integers with the usual order), but T has no existentially closed models. For if M is any model, and a and b are two consecutive elements in M, then we can make an extending model N by adding one new element between a and b. Then the system of equations a < x < b has a solution in N but not in M.

It turns out that the key problem with this theory is that it is not inductive.

Theorem: Let T be an inductive theory. Then every model of T can be embedded into an existentially closed model of T.

Proof: The rough idea is as follows: given a model M, if some system of equations over M has a solution in an extension of M, but doesn't have one in M, then add a solution. Repeat this enough, and M will eventually be existentially closed. This requires transfinite induction, so we need "inductive" to be able to handle the limit ordinals.

More formally, let us first prove

Claim: If M is a model of T, then we can make a model N₁ of T, extending M, with the following property:

If $\phi (x;a)$ is a quantifier-free formula over M, and N_{2</math> is a model of T extending N}1_, then

$N_{2}\models \exists x:\phi (x;a)\implies N_{1}\models \exists x:\phi (x;a)$

So roughly, any system of equations over M which has a solution in an extension of N₁ already has a solution in N₁.

Proof: Let $\{\phi _{\alpha }(x;a_{\alpha }):\alpha <\lambda \}$ be an enumeration of all quantifier-free formulas over M. Build an ascending sequence of models $M_{\alpha }$ for $\alpha \leq \kappa$ inductively as follows:

If $\alpha =0$ , take $M_{\alpha }=M$
If $\alpha$ is a limit ordinal, take $M_{\alpha }=\bigcup _{\beta <\alpha }M_{\beta }$ . This is a model (of T) because T is inductive.
Let $M_{\alpha +1}$ be constructed as follows. If there is a model N of T extending $M_{\alpha }$ such that $\phi _{\alpha }(N;a_{\alpha })$ is non-empty, then take $M_{\alpha +1}=N$ (for some arbitrary choice of N). Otherwise, take $M_{\alpha +1}=M_{\alpha }$ .

Let N₁ be $M_{\lambda }$ . Then N₁ is a model of T extending M. It has the desired property. Indeed, suppose $\phi (x;a)$ is a quantifier-free formula over M, N₂ is a model extending N₁, and suppose that

$N_{2}\models \exists x:\phi (x;a)$

Because we enumerated all the quantifier-free formulas over M, $\phi (x;a)$ is $\phi _{\alpha }(x;a_{\alpha })$ for some $\alpha$ . Now

$M_{\alpha }\subset M_{\lambda }=N_{1}\subset N_{2}$

and $\phi _{\alpha }(N_{2};a_{\alpha })$ is non-empty. Therefore, by choice of $M_{\alpha +1}$ , we also have

$\emptyset \neq \phi _{\alpha }(M_{\alpha +1};a_{\alpha })\subset \phi _{\alpha }(N_{1};a_{\alpha })$

$N_{1}\models \exists x:\phi (x;a)$

Thus

$N_{2}\models \exists x:\phi (x;a)\implies N_{1}\models \exists x:\phi (x;a)$ .

QED_claim.

Now given a model M of T, build an increasing sequence M₁ ⊆ M₂ ⊆ ... of models as follows:

M₁ = M
M_i+1 is obtained by applying the Claim to M_i. In particular, if some existential sentence over M_i holds in an extension of M_i+1, then it holds in M_i+1.

Let N be the union of this chain. This is still a model, because T is inductive. We claim that N is existentially closed. Indeed, let N₂ be a model extending N. Let $\phi (x;a)$ be a quantifier-free formula over N, satisfiable in N₂. The tuple a is finite, so must come from some M_i. Then

$N_{2}\models \exists x:\phi (x;a)\implies M_{i+1}\models \exists x:\phi (x;a)\implies N\models \exists x:\phi (x;a)$

The first implication follows from the choice of M_i+1. The second implication follows from general facts about existential formulas (they are preserved upwards in inclusions). So N is existentially closed in N₂. In conclusion, N is an existentially closed model of T, and it extends the original model M. QED. ::: ::: :::