# Tarski-Vaught Test - why only one variable tested at a time?

The book Model Theory: An Introduction by David Marker states the Tarski-Vaught test for elementary substructures (p45, 2002 edition) as :

Suppose that M is a substructure of N. Then M is an elementary substructure if and only if, for any formula φ(v,$w_1,..w_n$) and any $a_1,..a_n$ ∈ M, if there is a b ∈ N such that N |= φ(b,$a_1,..a_n$), then there is c ∈ M such that N |= φ(c,$a_1,..a_n$).

My question is : Why is only one element of N tested at a time – so above it considers ∀$a_1,..a_n$ ∈ M ∀b ∈ N φ(b,$a_1,..,a_n$). Is it possible for a formula φ(v,$w_1,..w_n$) to be only true when v,$w_1,..,w_n$ are assigned values in N$\backslash$M, or even only true where more than one variable is assigned an element from N$\backslash$M, but false in all other variable assignement combinations in N$\backslash$M (including where only one variable has an element from N). If this were true how would the Tarski – Vaught test pick up these non-elementary cases, since it only appears to test (v,$w_1,..w_n$) for one element in N (v) and the rest $w_1..w_n$ only in M. As these cases could potentially all be false, and so pass the test, but fail to detect the case ∃v∃$w_1..∃w_n$ (φ(v,$w_1,..w_n$)), which may be only true for example when all its variables are assigned values in N$\backslash$M?

To give an example : Suppose c,d ∈ N\M, a,b ∈ M : Consider all possible pairs of the four elements X={a,b,c,d}. Assume is it possible for φ(c,d) to be true but all other φ(x,y) : x,y ∈ X to be false. The Tarski-Vaught test would only appear to consider a single element from N\M at a time, so how does it cover the case of φ(c,d) ? This would be relevant to the case of the sentence ∃x∃yφ(x,y), where its true that N |= ∃x∃yφ(x,y), but not true that (M |= ∃x∃yφ(x,y)). So how does the Tarski-Vaught test address this case - or can't the case occur ?

• There is no "magic" : is the "minimal" condition in order that the induction on formula proof to work : the atomic case and the propositional connectives case are straightforward; the consdition is needed for the $\exists$ quantifier. Dec 2 '15 at 14:52
• Mauro, apologies, I have edited the question - which is really about how does the Tarski-Vaught test pick up the cases mentioned - if they can occur of course ? Dec 2 '15 at 17:47
• Please learn to use MathJax formatting to typeset mathematics here. Dec 2 '15 at 18:22
• Alex - format changed. Dec 2 '15 at 20:34

The Tarski-Vaught test handles the "other cases" (formulas with more than one quantifier) by induction on the complexity of formulas. That is, we prove that for any formula $\varphi(\overline{x})$ and any tuple $\overline{a}$ from $M$, $M\models \varphi(\overline{a})$ if and only if $N\models \varphi(\overline{a})$. The only step in the induction that isn't clear is step where we add a single existential quantifier, which is handled by our assumption.
In the example at the end of your post, clearly $M$ is not an elementary substructure of $N$, since they disagree on the sentence $\exists x\, \exists y\, \varphi(x,y)$. This is witnessed by a failure of the Tarski-Vaught test as follows: There is an element in $N$ (take $c$) satisfying the formula $\psi(x): \exists y\, \varphi(x,y)$, but there is no such element in $M$.