Tarski-Vaught Test

From ProofWiki
Jump to navigation Jump to search


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 Formulas are Preserved by Superstructures, 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)$

if and only if:

$\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)$

if and only if:

$\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 Formulas are Preserved by Superstructures, 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)$

if and only if:

$\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)$

if and only if:

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