If *M* ⊆ *N* is an inclusion of structures, we say that *N* is an **elementary extension** of *M*, or *M* is an **elementary substructure** of *N*, denoted $ M \preceq N $, if for every formula $ \phi(x) $ and every tuple $ b $ in *M*, we have

- $ M \models \phi(b) \iff N \models \phi(b) $.

In other words, if *b* satisfies $ \phi(x) $ in one of *M* and *N*, then it must satisfy it in the other.

Specializing to the case where *x* is a tuple of length 0, we recover elementary equivalence: if *N* is an elementary extension of *M* then *M* ≡ *N*. However, $ M \preceq N $ is a strictly stronger condition than $ M \subseteq N $ plus $ M \equiv N $.

The elementary inclusion relation is transitive: if $ M \preceq M' \preceq M'' $, then $ M \preceq M'' $.

## Non-examplesEdit

The rationals are not an elementary substructure of the reals (as rings): $ \mathbb{Q} \not\preceq \mathbb{R} $. For example, if $ \phi(x) $ is the formula asserting that *x* is a square:

- $ \phi(x) \iff \exists y : x = y^2 $,

then

- $ \mathbb{Q} \not \models \phi(2) $ but $ \mathbb{R} \models \phi(2) $

because 2 is a square in the reals, but not the rationals.

It is possible for *M* ⊆ *N* and *M* ≡ *N* to hold without *N* being an elementary extension of *M*. For example, let *N* be the natural numbers {0,1,2,...} with the structure of an ordered set. Let *M* be the subset {1,2,3,...}. Then *M* is a substructure of *N* and *M* is elementarily equivalent to *N* (because *M* and *N* are isomorphic). However, $ M \not \preceq N $. Indeed, if $ \phi(x) $ is the formula

- $ \exists y : y < x $,

then $ \phi(1) $ holds in *N*, but not *M*, because 1 is not the least element in *N*, but it *is* the least element in *M*.

## ExamplesEdit

If *M* ⊆ *N*, and *b* is a tuple from *M*, and $ \phi(x) $ is a *quantifier-free* formula, then

- $ M \models \phi(b) \iff N \models \phi(b) $

is automatic. Consequently, if *T* is a theory with quantifier elimination, then any inclusion of models is an elementary inclusion. Indeed, if *M* ⊆ *N*, $ \psi(x) $ is an arbitrary formula, then we can find an equivalent quantifier-free formula $ \phi(x) $. Then for a tuple *b* from *M*,

- $ M \models \psi(b) \iff M \models \phi(b) \iff N \models \phi(b) \iff N \models \psi(b) $.

More generally, if *T* is model complete, then any inclusion of models of *T* is an elementary inclusion. In fact, this is one way of characterizing model completeness.

From this, one gets many examples of elementary extensions:

- The algebraic numbers are an elementary substructure of the field of complex numbers (because ACF is model complete).
- The real algebraic numbers are an elementary substructure of the field of real numbers (because RCF is model complete).
- Any extension of non-trivially valued algebraically closed valued fields is an elementary extension, because ACVF is model complete.

## The Tarski-Vaught CriterionEdit

**Theorem:** Let *M* be a structure, and *S* be a subset of *M*. Then *S* is an elementary substructure of *M* if and only if the following property holds: for every formula $ \phi(x;y) $ and every tuple *b* ∈ *S*, if $ \phi(M;b) $ is non-empty, then it intersects *S*. In other words, every non-empty subset of *M* definable over *S* intersects *S*. (This is called the **Tarski-Vaught Criterion**.)

*Proof:* First suppose that *S* is an elementary substructure of *M*. Let $ \phi(x;y) $ be a formula. Suppose that $ \phi(M;b) $ is non-empty. Then

- $ M \models \exists x : \phi(x;b) $.

In particular, *b* satisfies the formula $ \exists x : \phi(x;y) $. Because $ S \preceq M $, we conclude that

- $ S \models \exists x : \phi(x;b) $

Therefore there is some *a* in *S* such that

- $ S \models \phi(a,b) $

Again, because $ S \preceq M $, we conclude

- $ M \models \phi(a,b) $.

Therefore $ a \in \phi(M;b) $, so $ \phi(M;b) $ intersects *S*.

Conversely, suppose the Tarski-Vaught criterion holds.
We prove by induction on *n* that if $ \psi(x) $ is a formula in prenex form with *n* quantifiers, then

- $ \psi(S) = \psi(M) \cap S $,

which is exactly the condition necessary for $ S \preceq M $ to hold. Since every formula can be written in prenex form, this will suffice.

The base case where *n* = 0 is the case where $ \psi(x) $ is quantifier-free. In this case, it is automatically true that $ \psi(S) = \psi(M) \cap S $, without any assumptions on *S* or *M*.

For the inductive step, write $ \psi(x) $ as $ \exists y : \chi(x;y) $ or $ \forall y : \chi(x;y) $ for some formula $ \chi(x;y) $ with one fewer quantifier. The existential and universal case are related by negation, so it suffices to consider the existential case. The inductive hypothesis says that if *a* and *b* are tuples from *S*, then

- $ S \models \chi(a;b) \iff M \models \chi(a;b) $

Let *a* be a tuple from *S*, we want to show that

- $ S \models \exists y : \chi(a;y) \iff M \models \exists y : \chi(a;y) $ (
*****)

Suppose the right hand side holds. Then there is *b* in *S* such that

- $ S \models \chi(a;b) $

By the inductive hypothesis

- $ M \models \chi(a;b) $ and therefore $ M \models \exists y : \chi(a;y) $.

So the right hand side of (*****) implies the left hand side.

Conversely, suppose that $ M \models \exists y : \chi(a;y) $. Then $ \chi(a;M) $ is non-empty, so it intersects *S*; let *b* be some point of intersection. Thus

- $ M \models \chi(a;b) $

and *b* is in *S*. By the inductive hypothesis,

- $ S \models \chi(a;b) $ and therefore $ S \models \exists y : \chi(a;y) $.

So the two sides of (*****) are equivalent. QED.

## Elementary ChainsEdit

An elementary chain is a chain of models

- $ M_1 \subset M_2 \subset \cdots $

such that $ M_i \preceq M_j $ for *i* ≤ *j*. (The chain could have transfinite length). The **Tarski-Vaught Theorem** on unions of elementary chains says that the union structure

- $ \bigcup_i M_i $

is an elementary extension of *M _{j}* for each

*j*.

## Elementary Amalgamation TheoremEdit

An **elementary embedding** is an injective map *f*: *M* -> *N* which induces an isomorphism between *M* and an elementary substructure of *N*. For example, any inclusion of an elementary substructure into an elementary extension is an elementary embedding.

The **Elementary Amalgamation Theorem** says that if *f*_{1}: *M* -> *N*_{1} and *f*_{2}: *M* -> *N*_{2} are two elementary embeddings, then there is a structure *N*_{3} and elementary embeddings *g*_{1} : *N*_{1} -> *N*_{3} and *g*_{2} : *N*_{2} -> *N*_{3} such that everything commutes:

- $ g_1 \circ f_1 = g_2 \circ f_2 $

In other words, if *M* can be elementarily embedded into two structures *N*_{1} and *N*_{2}, then there is an elementary extension of *M* into which both *N*_{1} and *N*_{2} can be embedded over *M*.

This theorem can be proven by extending tp(*N*_{1}/*M*) to *N*_{2} and realizing the resulting type in an elementary extension of *N*_{2}.