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:
- $N$ is an elementary substructure of $M$.
- 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?