Tarski-Vaught Test
Theorem
Let $\mathcal M, \mathcal N$ be $\mathcal L$-structures such that $\mathcal M$ is a substructure of $\mathcal N$.
Then $\mathcal M$ is an elementary substructure of $\mathcal N$ if and only if:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
The condition on the right side of the if and only if statement above can be rephrased as:
- Every existential statement with parameters from $\mathcal M$ which is satisfied in $\mathcal N$ can be witnessed by an element from the substructure $\mathcal M$.
Generalization
Let $\mathcal N$ be an $\mathcal L$-structure, and $\mathcal M \subseteq \mathcal N$.
Then $\mathcal M$ is the universe of an elementary substructure of $\mathcal N$ if and only if:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
The condition on the right side of the if and only if statement above can be rephrased as::
- Every existential statement with parameters from $\mathcal M$ which is satisfied in $\mathcal N$ can be witnessed by an element from the subset $\mathcal M$.
Proof
Sufficient Condition
Let $\mathcal M$ be an elementary substructure of $\mathcal N$.
Then $\mathcal N \models \exists x \phi \left({x, \bar a}\right)$ implies that $\mathcal M \models \exists x \phi \left({x, \bar a}\right)$.
Hence there exists some $m$ in $\mathcal M$ such that:
- $\mathcal M \models\phi \left({m, \bar a}\right)$.
Passing back up to $\mathcal N$ yields the result.
$\Box$
Necessary Condition
Let $\mathcal M$ be such that:
- For every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
It is to be shown that $\mathcal M$ is an elementary substructure of $\mathcal N$.
That is:
- for every $\mathcal L$-formula $\psi \left({\bar v}\right)$
and:
- for every $\bar a$ in $\mathcal M$:
- $\left({\mathcal M \models \phi \left({\bar a}\right)}\right) \iff \left({\mathcal N \models\phi \left({\bar a}\right)}\right)$
The proof proceeds by induction on complexity of formulas.
Let $\psi$ be quantifier free.
From Quantifier Free Formula is Preserved by Superstructure, quantifier free formulas with parameters from $\mathcal M$ are preserved when passing to and from superstructures.
Hence the result holds.
Let the result holds for $\psi$.
Consider $\neg \psi$:
We have that:
- $\left({\mathcal M \models \neg \psi \left({\bar a}\right)}\right) \iff \left({\mathcal M \not \models \psi \left({\bar a}\right)}\right)$
By the inductive hypothesis:
- $\left({\mathcal M \not\models\psi \left({\bar a}\right)}\right) \iff \left({\mathcal N \not\models\psi \left({\bar a}\right)}\right)$
Thus the result follows for $\neg \psi$.
Let the result hold for $\psi_0$ and $\psi_1$.
Consider $\psi_0 \wedge \psi_1$:
We have:
- $\mathcal M \models \psi_0 \left({\bar a}\right) \wedge \psi_1 \left({\bar a}\right)$
- $\mathcal M \models\psi_0 \left({\bar a}\right)$
and:
- $\mathcal M \models \psi_1 \left({\bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models\psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
- $\mathcal N \models\psi_0 \left({\bar a}\right)$ and $\mathcal N \models \psi_1 \left({\bar a}\right)$
Thus the result follows for $\psi_0 \wedge \psi_1$.
Let the result holds for $\psi$.
Consider:
- $\exists x: \psi \left({x}\right)$
We prove the two directions of this case separately.
First let:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
Then there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
and so:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
Conversely, let:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
By assumption, there exists $m \in \mathcal M$ such that:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
and hence:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
completing the proof.
$\blacksquare$
Proof of Generalization
Sufficient Condition
Let $\mathcal M$ be an elementary substructure of $\mathcal N$.
Then:
- $\left({\mathcal N \models \exists x: \phi \left({x, \bar a}\right)}\right) \implies \left({\mathcal M \models \exists x \phi \left({x, \bar a}\right)}\right)$
Hence there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \phi \left({m, \bar a}\right)$
Passing back up to $\mathcal N$ yields the result.
$\Box$
Necessary Condition
Let $\mathcal M$ be such that:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
It is easily shown, using formulae of the form $\phi \left({x, \bar v}\right) = f \left({\bar v}\right) = x$, that $\mathcal M$ is closed under functions, and hence the universe of a substructure.
It remains to be shown that $\mathcal M$ is an elementary substructure of $\mathcal N$.
That is:
- for every $\mathcal L$-formula $\psi \left({\bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- $\left({\mathcal M \models \phi \left({\bar a}\right)}\right) \iff \left({\mathcal N \models \phi \left({\bar a}\right)}\right)$
The proof proceeds by induction on complexity of formulas.
Let $\psi$ is quantifier free.
From Quantifier Free Formula is Preserved by Superstructure, quantifier free formulas with parameters from $\mathcal M$ are preserved when passing to and from superstructures.
Hence the result holds.
Let the result hold for $\psi$.
Consider $\neg \psi$:
We have:
- $\left({\mathcal M \models \neg \psi \left({\bar a}\right)}\right) \iff \left({\mathcal M \not \models \psi \left({\bar a}\right)}\right)$
By the inductive hypothesis:
- $\left({\mathcal M \not \models \psi \left({\bar a}\right)}\right) \iff \left({\mathcal N \not \models \psi \left({\bar a}\right)}\right)$
Hence the result follows for $\neg \psi$.
Suppose the result holds for $\psi_0$ and $\psi_1$.
Consider $\psi_0 \wedge \psi_1$:
We have that:
- $\mathcal M \models \psi_0 \left({\bar a}\right) \wedge \psi_1 \left({\bar a}\right)$
- $\mathcal M \models \psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
- $\mathcal N \models \psi_0 \left({\bar a}\right)$ and $\mathcal N \models \psi_1 \left({\bar a}\right)$
The result then follows for $\psi_0 \wedge \psi_1$.
Let the result hold for $\psi$.
Consider $\exists x: \psi \left({x}\right)$:
We prove the two directions of this case separately.
First let:
- $\mathcal M \models\exists x \psi \left({x, \bar a}\right)$
Then there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
and so:
- $\mathcal N \models\exists x \psi \left({x, \bar a}\right)$
Conversely, let:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
Then by assumption, there exists $m \in \mathcal M$ such that:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
and hence:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
completing the proof.
$\blacksquare$
Generalization
Another common statement of the theorem does not require $\mathcal M$ to be a substructure of $\mathcal N$, it is enough for it to be a subset of $\mathcal N$.
The ($\implies$) is shown just the same as above, while the other direction easily follows, since $\mathcal M$ satisfying the condition that for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$, if there is an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$, then there is an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$, is closed under functions (by directly applying the condition to formulae of the form $\phi \left({x, \bar y}\right) = \left({x = f \left({\bar y}\right)}\right)$), and hence the universe of a substructure, which reduces it to the statement above.
$\blacksquare$
Source of Name
This entry was named for Alfred Tarski and Robert Lawson Vaught.