# Tarski-Vaught test, unclear implication

We know that Tarski-Vaught criterion says: $M$ is an elementary submodel of $N$ iff $M$ is a submodel of $N$ and when $\overline{a}\in|M|^n$, $b\in |N|$, $N \models\phi[b,\overline{a}]$, then there is $b'\in |M|$ for which $N\models \phi[b',\overline{a}]$.

The direction "only if" is unclear to me. It would be clear if the last part had $M$ instead of $N$, as in the definition of an elementary submodel. But why $N$ in $N\models \phi[b',\overline{a}]$ is correct?

You can show by induction on the complexity of $\phi$ that it doesn't matter.

If $\phi$ is atomic, then just by being a substructure, $M$ and $N$ agree on the interpretation of terms and relations.

If $\phi$ is a conjunction, or negation of a formula then the induction hypothesis works out.

If $\phi$ is $\exists x\theta$, then by taking $\overline{a}'$ to be $\overline{a}$ with the addition of $b$, use the induction hypothesis on $\theta(x,\overline{a}')$ to finish the proof.

With "only if" direction do you mean $\Rightarrow$? (I am always confused.)

Then this is the easy direction and it does not require induction. Assume $M\preceq N$.

$N\models\varphi(a,b)\Leftrightarrow N\models\exists x\,\varphi(a,x)\Leftrightarrow M\models\exists x\,\varphi(a,x)\Leftrightarrow M\models\varphi(a,b')\Leftrightarrow N\models\varphi(a,b')$.

The second and the last equivalence hold by elementarity. (Note parenthetically that the Tarski-Vaught criterion with $M$ for $N$ would be useless.)

• Yes,$\Rightarrow$. I understand perfectly Asaf's proof but not yours.Second and fourth $\Leftrightarrow$ are unclear to me. How do they follow?An answer "by elementarity" is not enough.My original question was exactly about the fourth equivalence.Notice also that if we replaced last $N$ by $M$, it would yield still an interesting thing:the $b$ above is from $|N|$ and now it should be satisfied by $M$.
– user175304
Feb 15 '15 at 18:19
• @user3357120 The very definition of $M \preceq N$ is that the satisfiability of a formula with parameters in $M$ is the same in $N$ and $M$. Formally, for any formula $\psi(x)$ and $m \in M$, one has : $M \models \psi(m)$ if and only if $N \models \psi(m)$. Here $\exists x \varphi(a,x)$ and $\varphi(a,b')$ are both formulas with parameters in $M$, hence the result.
– Pece
Feb 16 '15 at 6:33