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 {\displaystyle M\preceq N}, if for every formula {\displaystyle \phi (x)} and every tuple {\displaystyle b} in M, we have

{\displaystyle M\models \phi (b)\iff N\models \phi (b)}.

In other words, if b satisfies {\displaystyle \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 MN. However, {\displaystyle M\preceq N} is a strictly stronger condition than {\displaystyle M\subseteq N} plus {\displaystyle M\equiv N}.

The elementary inclusion relation is transitive: if {\displaystyle M\preceq M'\preceq M''}, then {\displaystyle M\preceq M''}.


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

{\displaystyle \phi (x)\iff \exists y:x=y^{2}},


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

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, {\displaystyle M\not \preceq N}. Indeed, if {\displaystyle \phi (x)} is the formula

{\displaystyle \exists y:y<x},

then {\displaystyle \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.


If MN, and b is a tuple from M, and {\displaystyle \phi (x)} is a quantifier-free formula, then

{\displaystyle 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 MN, {\displaystyle \psi (x)} is an arbitrary formula, then we can find an equivalent quantifier-free formula {\displaystyle \phi (x)}. Then for a tuple b from M,

{\displaystyle 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 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 {\displaystyle \phi (x;y)} and every tuple bS, if {\displaystyle \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 {\displaystyle \phi (x;y)} be a formula. Suppose that {\displaystyle \phi (M;b)} is non-empty. Then

{\displaystyle M\models \exists x:\phi (x;b)}.

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

{\displaystyle S\models \exists x:\phi (x;b)}

Therefore there is some a in S such that

{\displaystyle S\models \phi (a,b)}

Again, because {\displaystyle S\preceq M}, we conclude

{\displaystyle M\models \phi (a,b)}.

Therefore {\displaystyle a\in \phi (M;b)}, so {\displaystyle \phi (M;b)} intersects S.

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

{\displaystyle \psi (S)=\psi (M)\cap S},

which is exactly the condition necessary for {\displaystyle 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 {\displaystyle \psi (x)} is quantifier-free. In this case, it is automatically true that {\displaystyle \psi (S)=\psi (M)\cap S}, without any assumptions on S or M.

For the inductive step, write {\displaystyle \psi (x)} as {\displaystyle \exists y:\chi (x;y)} or {\displaystyle \forall y:\chi (x;y)} for some formula {\displaystyle \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

{\displaystyle S\models \chi (a;b)\iff M\models \chi (a;b)}

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

{\displaystyle 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

{\displaystyle S\models \chi (a;b)}

By the inductive hypothesis

{\displaystyle M\models \chi (a;b)} and therefore {\displaystyle M\models \exists y:\chi (a;y)}.

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

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

{\displaystyle M\models \chi (a;b)}

and b is in S. By the inductive hypothesis,

{\displaystyle S\models \chi (a;b)} and therefore {\displaystyle S\models \exists y:\chi (a;y)}.

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

Elementary Chains[]

An elementary chain is a chain of models

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

such that {\displaystyle M_{i}\preceq M_{j}} for ij. (The chain could have transfinite length). The Tarski-Vaught Theorem on unions of elementary chains says that the union structure

{\displaystyle \bigcup _{i}M_{i}}

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:

{\displaystyle g_{1}\circ f_{1}=g_{2}\circ f_{2}}

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. ::: ::: :::