## FANDOM

78 Pages

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 $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 MN. 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 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, $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 MN, 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 MN, $\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 bS, 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 ij. (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 Mj 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 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:

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