If MN is an inclusion of structures, we say that N is an elementary extension of M, or M is an elementary substructure of N, denoted , if for every formula and every tuple in M, we have

.

In other words, if b satisfies 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 MN. However, is a strictly stronger condition than plus .

The elementary inclusion relation is transitive: if , then .

## Non-examples

The rationals are not an elementary substructure of the reals (as rings): . For example, if is the formula asserting that x is a square:

,

then

but

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

It is possible for MN and MN 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, . Indeed, if is the formula

,

then holds in N, but not M, because 1 is not the least element in N, but it is the least element in M.

## Examples

If MN, and b is a tuple from M, and is a quantifier-free formula, then

is automatic. Consequently, if T is a theory with quantifier elimination, then any inclusion of models is an elementary inclusion. Indeed, if MN, is an arbitrary formula, then we can find an equivalent quantifier-free formula . Then for a tuple b from M,

.

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 Criterion

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 and every tuple bS, if 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 be a formula. Suppose that is non-empty. Then

.

In particular, b satisfies the formula . Because , we conclude that

Therefore there is some a in S such that

Again, because , we conclude

.

Therefore , so intersects S.

Conversely, suppose the Tarski-Vaught criterion holds. We prove by induction on n that if is a formula in prenex form with n quantifiers, then

,

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

The base case where n = 0 is the case where is quantifier-free. In this case, it is automatically true that , without any assumptions on S or M.

For the inductive step, write as or for some formula 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

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

(*)

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

By the inductive hypothesis

and therefore .

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

Conversely, suppose that . Then is non-empty, so it intersects S; let b be some point of intersection. Thus

and b is in S. By the inductive hypothesis,

and therefore .

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

## Elementary Chains

An elementary chain is a chain of models

such that for ij. (The chain could have transfinite length). The Tarski-Vaught Theorem on unions of elementary chains says that the union structure

is an elementary extension of Mj for each j.

## Elementary Amalgamation Theorem

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 f1: M -> N1 and f2: M -> N2 are two elementary embeddings, then there is a structure N3 and elementary embeddings g1 : N1 -> N3 and g2 : N2 -> N3 such that everything commutes:

In other words, if M can be elementarily embedded into two structures N1 and N2, then there is an elementary extension of M into which both N1 and N2 can be embedded over M.

This theorem can be proven by extending tp(N1/M) to N2 and realizing the resulting type in an elementary extension of N2. ::: ::: :::