Proof of the Tarski-Vaught test

Question

The Tarski-Vaught test is a way to determine if a substructure is elementary. To my understanding, here is the theorem:

Tarski-Vaught Test Let $N$ be a substructure of $M$. Then the following two statements are equivalent:

1. $N$ is an elementary substructure of $M$.
2. For any formula $\phi$ and elements $p_1,p_2,\dots,p_n \in N$ such that $M \models \exists x. \phi(x,p_1,p_2,\dots,p_n)$, there exists $q \in N$ such that $M \models \phi(q,p_1,p_2,\dots,p_n)$.

However, I have not been able to find a proof of this statement. 1 implies 2 is clear to me, but I am not sure how to prove 2 implies 1.

What is a proof of the Tarski-Vaught test?

Answer 1

This is more a sketch of proof, but I hope it will be sufficient, if not feel free to ask for additional details.

Basically one have to prove that every formula $\phi$ with parameters in $N$ is true in $M$ if and only if it is true in $N$.

The way to prove that is by induction on the complexity of the formula:

• the case for atomic formulas with parameters in $N$ follows easily by the fact that $N$ is a substructure
• the case for formulas without quantifier follows easily
• the case for existentially quantified formulas follows by the hypothesis
• the case for universally quantified formulas follows from the logical equivalence $\forall x. \phi(x)\Leftrightarrow \neg \exists x.\neg \phi(x)$ and by the other cases.

I hope this helps (if not, as I said above, please ask).