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 ?

  • 2
    $\begingroup$ 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. $\endgroup$ Dec 2 '15 at 14:52
  • $\begingroup$ 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 ? $\endgroup$ Dec 2 '15 at 17:47
  • $\begingroup$ Please learn to use MathJax formatting to typeset mathematics here. $\endgroup$ Dec 2 '15 at 18:22
  • $\begingroup$ Alex - format changed. $\endgroup$ 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.

The proof is right there on p. 45 of Marker - is there a part of the proof you don't understand?

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

  • $\begingroup$ Ah, OK I see the test for ∃x∃yφ(x,y) can be done in one stage by testing for ∃yφ(x,y) - I didn't realise the test allowed for formulae with quantifiers in them - I had thought that ∃yφ(x,y) truth had to be determined first by starting with a quantifier free formula φ(x,y), via iteration (apologies I'm just a beginner). I see now that the test for N |=∃yφ(x,y) is done separately from the test for N |=∃x∃yφ(x,y). So if the formula can have any number of formulae with quantifiers in them I can see the test would pick up the cases in the question. Many thanks for the clarification. $\endgroup$ Dec 2 '15 at 21:28
  • $\begingroup$ So, interestingly, extending your answer to the general case, to test for N|= ∃x∃yφ(x,y), if there is a b ∈ N that satisfies N |= ∃yφ(b,y) then the test could be satisfied if there is a c ∈ M : N |= ∃yφ(c,y). So as the test is only in N the ∃yφ(c,y) could be satisfied with an d ∈ N so N |= φ(c,d) ... but this may not be satisfied in M (i.e. there is no e ∈ M φ(c,e)) ! So the Tarski-Vaught test for ∃x∃yφ(x,y) is passed, even though M does not satisfy it ! However this doesn't matter since all formulae are tested and the none elementarity is picked up in the test for N |= ∃yφ(x,y). $\endgroup$ Dec 3 '15 at 9:58
  • $\begingroup$ So the Tarski-Vaught test, despite only addressing one variable at a time, does actually look at all possible values a,b, .... of the free variables x,y,... of a formula φ(x,y,..) in N and where N |= φ(a,b,..) it tests for a1,b1,... in M with N |= φ(a1,b1,..) which due to the substructure is equivalent to testing for M |= φ(a1,b1,..). This is interestingly achieved via the checking of the satisfaction of quantifiers and testing of all formulas. $\endgroup$ Dec 3 '15 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.