FANDOM


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.