If T is a theory, a model companion of T is a theory T' with the following properties:

Every model of T embeds into a model of T'.
Every model of T' embeds into a model of T.
T' is model complete

Model companions are unique if they exist. A theory is companionable if it has a model companion.

Examples[]

ACF is the model companion of the theory of fields, or even the theory of integral domains (in the ring language).
RCF (in the language of ordered rings) is the model companion of ordered fields.
RCF (in the pure language of rings) is the momdel companion of orderable fields.
DLO is the model companion of ordered sets
DLO is also the model companion of ordered sets in which every element has a successor and a predecessor (even though models of DLO do not have this property)
The random graph is the model companion of graphs (i.e., sets with an antireflexive symmetric relation)
ACFA is the model companion of difference fields (i.e., fields with an endomorphism)
DCF is the model companion of differential fields (i.e., fields with a Z-linear derivation)
ACVF is the model companion of valued fields.

Uniqueness of the Model Companion[]

Suppose T₁ and T₂ are two model companions of a theory T. Then T₁ = T₂ (or more precisely, T₁ implies and is implied by T₂; they have the same models).

Proof: We will show that every model M of T₁ is a model of T₂. Then by symmetry, T₁ and T₂ have the same models.

Note that every model of T₁ embeds in a model of T, which in turn embeds in a model of T₂. Conversely, every model of T₂ embeds in a model of T₁.

Now given M₁ an arbitrary model of T₁, embed it in a model M₂ of T₂. Then embed M₂ in a model M₃ of T₁. Continuing on in an alternating fashion yields an increasing chain of structures

$M_{1}\subset M_{2}\subset \cdots$

with $M_{2i-1}\models T_{1}$ and $M_{2i}\models T_{2}$ . Then

$M_{1}\subset M_{3}\subset M_{5}\subset \cdots$

is an increasing chain of models of T₁. By model completeness of T₁, this is an elementary chain

$M_{1}\preceq M_{3}\preceq \cdots$

Similarly,

$M_{2}\preceq M_{4}\preceq \cdots$ .

By the Tarski-Vaught Theorem

$M_{1}\preceq \bigcup _{i=1}^{\infty }M_{2i-1}=\bigcup _{i=1}^{n}M_{i}=\bigcup _{i=1}^{\infty }M_{2i}\succeq M_{2}$

Thus M₁ is elementarily equivalent to M₂, which is a model of T₂. In particular, M₁ is a model of T₂. QED.

Model Companions of Inductive Theories[]

Theorem: Let T be an inductive theory. Then T is companionable if and only if the existentially closed model of T form an elementary class, in which case the model companion of T is exactly the class of existentially closed models of T.

To prove this, we need a few lemmas.

Lemma: Let M be a model of a model complete theory. Let S be a substructure of M. Then S is an elementary substructure of M if and only if S is existentially closed in M.

Proof: If $S\preceq M$ , then for every formula $\phi (x)$ and every tuple a from S, we have

$S\models \phi (a)\iff M\models \phi (a)$ .

In particular, this holds for existential formulas, which is what it means for S to be existentially closed in M.

Conversely, suppose S is existentially closed in M. To show that S is an elementary substructure of M, it suffices (by the Tarski-Vaught criterion) to show that every non-empty definable subset of M, definable over S, contains a point of S. Let $\phi (M;b)$ be a non-empty definable subset of M, with b a tuple from S. By model completeness of M, we may assume that $\phi (x;y)$ is an existential formula. Then so is the formula $\psi (y)=\exists x:\phi (x;y)$ . Since $\phi (M;b)$ is non-empty, we have

$M\models \psi (b)$ .

By existential closedness

$S\models \psi (b)$ .

So there is an a in S such that

$S\models \phi (a;b)$

Applying existential closedness another time,

$M\models \phi (a;b)$

Then $a\in \phi (M;b)\cap S$ , so the Tarski-Vaught criterion holds. QED.

Lemma: Suppose M₁ ⊆ M₂ ⊆ M₃ and M₁ is existentially closed in M₃. Then M₁ is existentially closed in M₂.

Proof: Let $\phi (x)$ be an existential formula. Then for any tuple a from M₁, we have

$M_{1}\models \phi (a)\implies M_{2}\models \phi (a)\implies M_{3}\models \phi (a)\implies M_{1}\models \phi (a)$ ,

where the first two implications hold because $\phi (x)$ is an existential formula, and the last holds because of existential closedness. From this we see

$M_{1}\models \phi (a)\iff M_{2}\models \phi (a)$ .

As this holds for arbitrary $\phi (x)$ and a, M₁ is existentially closed in M₂. QED.

Now we prove the theorem.

Proof: Suppose the existentially closed models of T form an elementary class. Then there is a theory ${\overline {T}}$ whose models are exactly the existentially closed models of T. We claim that ${\overline {T}}$ is a model companion of T. Every model of ${\overline {T}}$ is a model of T, so trivially embeds into a model of T. Conversely, if M is a model of T, then M embeds into an existentially closed model of T, i.e., a model of ${\overline {T}}$ , because there are enough existentially closed models in inductive theories. Finally, ${\overline {T}}$ is model complete. Indeed, every model of ${\overline {T}}$ is existentially closed as a model of T, so also existentially closed as a model of ${\overline {T}}$ , since this is a weaker condition. Therefore ${\overline {T}}$ is a model companion of T.

Conversely, suppose that T has a model companion ${\overline {T}}$ . We must show that models of ${\overline {T}}$ are exactly the same thing as existentially closed models of T.

Let M be an existentially closed model of T. Then we can embed M into a model M₂ of ${\overline {T}}$ . As ${\overline {T}}$ is a model companion of T, we can embed M₂ back into a model of T. This model of T can further be embedded into an existentially closed model of T, because T is inductive. So we have

$M\subset M_{2}\subset M_{3}$

with M and M₃ existentially closed models of T, and $M_{2}\models {\overline {T}}$ . As M is existentially closed as a model of T, it is existentially closed in M₃. By the second Lemma, M is existentially closed in M₂. By the first Lemma, $M\preceq M_{2}$ , so in particular $M\equiv M_{2}$ , and M is a model of ${\overline {T}}$ .

Conversely, let M be a model of ${\overline {T}}$ . Then we can embed M in a model of T. This model of T can be further extended to be existentially closed. So we get M ⊆ N with N an existentially closed model of T. By the previous paragraph, N is a model of ${\overline {T}}$ . By model completeness of ${\overline {T}}$ , $M\equiv N$ , so in particular, M is a model of T. To see existential closedness, let N be any model of T extending M. Then N can be embedded into a model M₂ of ${\overline {T}}$ . Then

$M\subset N\subset M_{2}$ .

By model completeness of ${\overline {T}}$ , M is existentially closed in M₂. By the second lemma, M is existentially closed in N.

Thus, models of ${\overline {T}}$ are the same thing as existentially closed models of T. QED.

Non-companionable Theories[]

Here are two examples of theories without model companions

The theory of groups
The theory of dense linear orders with an automorphism $\sigma$

Proof: As both theories are inductive, it suffices to show that the existentially closed models do not form an elementary class.

Claim: Let G be an existentially closed group, and a and b be two elements of G. If some automorphism of G sends a to b, then some inner automorphism sends a to b.

Proof: Let $\sigma$ be the automorphism of G sending a to b. Consider the action of the integers $\mathbb {Z}$ on G by powers of $\sigma$ . Let H be the semidirect product of $\mathbb {Z}$ and G from this action. Then H is a group extending G. In H, the equation xax^{-1} = b has a solution (namely, the generator of the copy of $\mathbb {Z}$ ). But since G is existentially closed in H, this equation also has a solution in G, which means that some inner automorphism sends a to b. QED.

Now suppose that the theory of groups had a model companion. Then there would be a theory T whose models are exactly the existentially closed groups. Let G be a $(2^{\aleph _{0}})^{+}$ -saturated and $(2^{\aleph _{0}})^{+}$ -strongly homogeneous model of T. Then two elements a and b of G have the same type over the empty set if and only if they are in the same orbit of Aut(G), by definition of strong homogeneity. In particular, G/Aut(G) has cardinality at most $2^{\aleph _{0}}$ , because there are at most that many types over the empty set. (There are only $\aleph _{0}$ 0-definable sets). On the other hand, by the claim, G/Aut(G) is the same as the quotient of G by inner automorphisms. This is an interpretable set, and G is saturated, so it must have size at least $(2^{\aleph _{0}})^{+}$ (a contradiction) or it must be finite.

Consequently G has finitely many conjugacy classes, and the conjugacy classes correspond to 1-types over the empty set. But G must also have the property that for every prime p, some element of G has order p. (It is easy to produce an extension of G which has this property, $G\times (\mathbb {Z} /p)$ for example. Then use existential closedness.) If two elements have different orders, they cannot be conjugate. So G has infinitely many conjugacy classes, a contradiction.

Consequently the theory of groups is not companionable.

Next consider the theory of a dense linear order with an automorphism.

Claim: Let (M,<, $\sigma$ ) be an existentially closed DLO-with-automorphism. Let a < b be two elements of M and suppose $\sigma (a)>a$ . Then the following system of equations

$a<x<b$

$\sigma (x)=x$

can be solved if and only if $b>\sigma ^{n}(a)$ for every n.

Proof: If a < x < b and x is fixed by $\sigma$ , then

$\sigma ^{n}(a)<\sigma ^{n}(x)=x<b$ ,

so one direction is clear. Conversely, suppose $b>\sigma ^{n}(a)$ for every n. Let U be the set of elements in M which exceed every $\sigma ^{n}(a)$ . Then U and M\U form a Dedekind cut on M. Also, U and M\U are each stabilized by $\sigma$ . Let N be an extension of M obtained by adding a new element c in this Dedekind cut, and setting $\sigma (c)=c$ . Then N is a legimitate DLO-with-automorphism. The desired system of equations can now be solved in N, specifically by the new element c. By existential closedness, it can also be solved in M. QED.

Now suppose the theory of DLO-with-automorphism had a model companion T. Let M be a $\aleph _{0}$ -saturated model of T. It is easy to create an extension of M in which the equation $\sigma (x)>x$ has a solution, so it must have a solution in M. In particular, we can find some a ∈ M such that $\sigma (a)>a$ .

Now consider the partial type p(y) over a which says the following:

$\neg \exists x:a<x<y\wedge \sigma (x)=x$

$y>a$

$y>\sigma (a)$

$y>\sigma ^{2}(a)$

and so on. Any finite subset of this is satisfiable, by taking $y=\sigma ^{n}(a)$ for n sufficiently large (using the claim). By saturation, the type p(y) should have a realization b in M. But then a and b contradict the Claim above. QED.

Model Completions[]

::: ::: :::