1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does either $M\preceq_{\Sigma_1} N$ or Tarski-Vaught imply the other?Is one direction true? $\endgroup$ – user122424 Aug 7 '17 at 15:28
  • $\begingroup$ Of course! Tarski-Vaught is equivalent to $M\preceq N$, which implies $M\preceq_{\Sigma_1} N$. $\endgroup$ – Alex Kruckman Aug 7 '17 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$ – Alex Kruckman Aug 11 '17 at 17:59

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.