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-examples[]

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.

Examples[]

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 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 $\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 Chains[]

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 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 f₁: M -> N₁ and f₂: M -> N₂ are two elementary embeddings, then there is a structure N₃ and elementary embeddings g₁ : N₁ -> N₃ and g₂ : N₂ -> N₃ 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₁ and N₂, then there is an elementary extension of M into which both N₁ and N₂ can be embedded over M.

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