Proof of the Tarski-Vaught test

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?

• I'm curious how you failed to find a proof of this statement. It's proven in literally every textbook on model theory, and probably in almost all online course notes on model theory. And if you google "Tarski-Vaught test proof", the first result is a Proof Wiki page which contains a proof. May 15 '19 at 12:37
• @AlexKruckman I only checked online. I saw the proof wiki one, but the formatting made it hard to follow. May 15 '19 at 12:46

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).

• This makes sense! The only small question I have is that formulas without quantifiers transfer into any substructure, right? May 15 '19 at 11:18
• @PyRulez exactly, of course that must be proved, but it isn't really hard. Of course difficulty depend on the familiarity one have with the concepts, so feel free to ask if that's not the case. May 15 '19 at 11:29