[proofplan] We prove both directions. If $N \preccurlyeq M$, then any existential statement over parameters from $N$ true in $M$ is true in $N$, so it has a witness in $N$, and elementarity transfers the witnessed formula back to $M$. Conversely, assuming the witness condition, we prove by induction on formulas that $N$ and $M$ satisfy the same formulas with parameters from $N$. Atomic formulas agree because $N$ is an $L$-substructure; Boolean connectives follow formally; the existential step is exactly the witness condition together with the induction hypothesis. [/proofplan] [step:Derive the witness condition from elementarity] Assume $N \preccurlyeq M$. Let $\varphi(x,y_1,\dots,y_n)$ be an $L$-formula, let $a = (a_1,\dots,a_n) \in N^n$, and suppose \begin{align*} M \models \exists x\,\varphi(x,a). \end{align*} Since $N \preccurlyeq M$ and all entries of $a$ lie in $N$, elementarity gives \begin{align*} N \models \exists x\,\varphi(x,a). \end{align*} Thus there exists $b \in N$ such that \begin{align*} N \models \varphi(b,a). \end{align*} Applying elementarity once more to the formula $\varphi(x,y_1,\dots,y_n)$ with parameter tuple $(b,a) \in N^{n+1}$ yields \begin{align*} M \models \varphi(b,a). \end{align*} Therefore the witness condition holds. [/step] [step:Prove agreement on atomic formulas from the substructure assumption] Assume now that the witness condition holds. We prove that $N \preccurlyeq M$. Let $\psi(z_1,\dots,z_k)$ be an $L$-formula and let $c = (c_1,\dots,c_k) \in N^k$. We will prove, by induction on the construction of $\psi$, that \begin{align*} N \models \psi(c) \quad \Longleftrightarrow \quad M \models \psi(c). \end{align*} For atomic formulas, first note that every $L$-term $t(z_1,\dots,z_k)$ has the same value in $N$ and in $M$ when evaluated at $c \in N^k$. This follows by induction on the construction of $t$: variables evaluate to the corresponding entries of $c$, constants are interpreted the same in an $L$-substructure, and if \begin{align*} t = f(t_1,\dots,t_m) \end{align*} for an $m$-ary function symbol $f \in L$, then the induction hypothesis gives equality of the values of $t_1,\dots,t_m$ in $N$ and $M$, while the interpretation of $f$ on $N$ is the restriction of its interpretation on $M$. Now let $\psi$ be atomic. If $\psi$ is an equality $t_1 = t_2$, then the equality has the same truth value in $N$ and $M$ because $t_1$ and $t_2$ have the same values in both structures. If $\psi$ is of the form \begin{align*} R(t_1,\dots,t_m) \end{align*} for an $m$-ary relation symbol $R \in L$, then the tuple of term values lies in $N^m$, and $R^N$ is the restriction of $R^M$ to $N^m$. Hence \begin{align*} N \models R(t_1(c),\dots,t_m(c)) \quad \Longleftrightarrow \quad M \models R(t_1(c),\dots,t_m(c)). \end{align*} Thus atomic formulas agree. [/step] [step:Pass agreement through Boolean connectives] Assume the induction statement has been proved for formulas $\theta(z_1,\dots,z_k)$ and $\eta(z_1,\dots,z_k)$. For $c \in N^k$, the case $\psi = \neg \theta$ follows from \begin{align*} N \models \neg\theta(c) &\Longleftrightarrow N \not\models \theta(c) \\ &\Longleftrightarrow M \not\models \theta(c) \\ &\Longleftrightarrow M \models \neg\theta(c). \end{align*} The cases $\psi = \theta \wedge \eta$, $\psi = \theta \vee \eta$, and $\psi = \theta \to \eta$ follow in the same way from the truth definitions for the corresponding Boolean connective and the induction hypotheses for $\theta$ and $\eta$. [/step] [step:Use the witness condition for existential formulas] Assume the induction statement has been proved for $\theta(x,z_1,\dots,z_k)$. Let \begin{align*} \psi(z_1,\dots,z_k) := \exists x\,\theta(x,z_1,\dots,z_k), \end{align*} and let $c = (c_1,\dots,c_k) \in N^k$. First suppose \begin{align*} N \models \exists x\,\theta(x,c). \end{align*} Then there exists $b \in N$ such that \begin{align*} N \models \theta(b,c). \end{align*} By the induction hypothesis applied to the parameter tuple $(b,c) \in N^{k+1}$, \begin{align*} M \models \theta(b,c). \end{align*} Therefore \begin{align*} M \models \exists x\,\theta(x,c). \end{align*} Conversely, suppose \begin{align*} M \models \exists x\,\theta(x,c). \end{align*} By the witness condition, applied to the formula $\theta(x,z_1,\dots,z_k)$ and the tuple $c \in N^k$, there exists $b \in N$ such that \begin{align*} M \models \theta(b,c). \end{align*} By the induction hypothesis applied to $(b,c) \in N^{k+1}$, \begin{align*} N \models \theta(b,c). \end{align*} Hence \begin{align*} N \models \exists x\,\theta(x,c). \end{align*} So existential formulas agree between $N$ and $M$ over parameters from $N$. [/step] [step:Conclude elementarity] The preceding induction proves that for every $L$-formula $\psi(z_1,\dots,z_k)$ and every tuple $c \in N^k$, \begin{align*} N \models \psi(c) \quad \Longleftrightarrow \quad M \models \psi(c). \end{align*} This is precisely the definition of $N$ being an elementary substructure of $M$. Therefore $N \preccurlyeq M$. Combining this implication with the first step proves the equivalence, and hence proves the Tarski-Vaught Test. [/step]