For $M$ a substructure of $N$, why does $M\prec_{\Sigma_1}N$ not imply $M\prec_{\Sigma_n}N$ for all $n$ by Tarski-Vaught criterion? Here $M\prec_{\Sigma_n}N$ means that for any $\Sigma_n$ formula $\phi(x_1,...,x_k)$ and $a_1,\ldots,a_k \in M$, $$M \vDash \phi[a_1,...,a_k]\quad\mbox{ iff }\quad N \vDash \phi[a_1,...,a_k].$$ The Tarski-Vaught criterion says that once there is an element $a\in M$ for all existential formulas $\exists x\, \psi(x,y)$ with $b\in N$ and $N\vDash \psi(b,y)$, such that $M\vDash \psi(a,y)$ then $M$ is an elementary submodel of $N$, i.e., $M\prec_{\Sigma_n} N$. So $\prec_{\Sigma_1}$ can be regarded as a basis of induction.
1 Answer
Because your statement of the Tarski-Vaught test is wrong. Here's what it really says:
Let $M$ be a substructure of $N$. Then $M\preceq N$ if and only if for every first-order formula $\psi(x,\overline{b})$ with parameters $\overline{b}$ from $M$, if $N\models \exists x\,\psi(x,\overline{b})$, then there exists $a\in M$ such that $N\models \psi(a,\overline{b})$.
This differs from your statement in two important ways. First, the formula $\exists x\,\psi(x,\overline{b})$ can be any formula that starts with an existential quantifier. It is not required to be an existential ($\Sigma_1$) formula, i.e. $\psi$ is not required to be quantifier-free. Second, the truth of $\psi(a,\overline{b})$ is checked in $N$, not in $M$. In some sense, this is the whole point of the Tarski-Vaught test: the definition of $M\preceq N$ requires you to compare truth in $M$ to truth in $N$, while the Tarski-Vaught test is a criterion for $M\preceq N$ that only mentions truth in $N$, never in $M$.
So the statement "the Tarski-Vaught test holds" is really quite different than the statement "$M\preceq_{\Sigma_1} N$". If you try to prove by induction that $M\preceq_{\Sigma_1} N$ implies $M\preceq_{\Sigma_n} N$ for all $n$, you'll run into trouble right away! (Because it's not true.)
-
$\begingroup$ Does either $M\preceq_{\Sigma_1} N$ or Tarski-Vaught imply the other?Is one direction true? $\endgroup$ Aug 7, 2017 at 15:28
-
$\begingroup$ Of course! Tarski-Vaught is equivalent to $M\preceq N$, which implies $M\preceq_{\Sigma_1} N$. $\endgroup$ Aug 7, 2017 at 15:37
-
1$\begingroup$ @user122424 I just noticed your edit. This was not my intention, and I've reversed the edit. My point was that Tarski-Vaught is useful as a test for elementary substructure because while the definition of $\preceq$ requires you to evaluate truth in $M$, Tarski-Vaught does not. $\endgroup$ Aug 11, 2017 at 17:59