## FANDOM

78 Pages

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.

## ApplicationsEdit

The Tarski-Vaught theorem plays a key role in the proofs of the following facts:

## ProofEdit

Let N denote the limit structure. We prove by induction on the number of quantifiers in the prenex form of $\phi(x)$ that for every i, and tuple a from Mi

$M_i \models \phi(a) \iff M \models \phi(a).$

The base case where $\phi(x)$ is quantifier-free is easy. For the inductive step, suppose $\phi(x)$ has n quantifiers. Replacing $\phi(x)$ with $\neg \phi(x)$ if necessary, we may assume that the outermost quantifier is existential. Then we can write $\phi(x)$ as $\exists y : \chi(x;y)$, where $\chi(x;y)$ has n - 1 quantifiers. Now suppose that $\phi(a)$ holds for some tuple a from some Mi. Then in Mi we can find some tuple b such that

$M_i \models \chi(a;b)$

By the inductive hypothesis,

$M \models \chi(a;b)$ and therefore $M \models \phi(a)$

as desired.

Conversely, suppose that a is a tuple from some Mi such that

$M \models \phi(a)$ or equivalently $M \models \exists y : \chi(a;y)$

Take a tuple b from M such that

$M \models \chi(a;b)$

Since M is the union of the Mj, there is some j > i such that b is in Mj. By induction,

$M_j \models \chi(a;b)$,

and in particular,

$M_j \models \exists y : \chi(a;y)$ or equivalently $M_j \models \phi(a)$

Because $M_i \preceq M_j$, we have

$M_i \models \phi(a)$

as well.

In conclusion,

$M_i \models \phi(a) \iff M \models \phi(a)$,

completing the inductive step, as well as the proof. QED