3
$\begingroup$

Let $M$ and $N$ be structures for a first order language $L$, with $M$ an elementary substructure of $N$. This means that $M$ is a substructure of $N$ and if $\varphi(x_1,\ldots,x_n)$ is a formula with free variables, and $m_1,\ldots,m_n$ are elements of $\operatorname{dom}(M)$, then $N \models \varphi(m_1,\ldots,m_n)$ iff $M \models \varphi(m_1,\ldots,m_n)$. Every source that I have looked at concludes that this implies that: if $N \models \exists x \varphi(x,m_1,\ldots,m_n)$, then $M \models \exists x\varphi(x,m_1,\ldots,m_n)$. (For example this implication is used in the proof of the Tarski-Vaught test.)

But doesn't $N\models \exists x \varphi(x,m_1,\ldots,m_n)$ mean only that there exists an $n$ in $\operatorname{dom}(N)$ (which a priori may not be in $\operatorname{dom}(M)$) such that $N \models \varphi (n,m_1,\ldots,m_n)$? Why does this imply that there is an $m$ in $\operatorname{dom}(M)$ such that $M\models \varphi(m,m_1,\ldots,m_n)$? What am I missing here?

$\endgroup$
  • $\begingroup$ I edited this post to use LaTeX markup as appropriate. As you become more established on this site, please learn to write your posts that way and do so in the future. LaTeX is easier to read and is the standard for this site. Also, as you seem to be a math grad student from your questions, you'll have to learn LaTeX at some point anyway; you might as well start now. (This was a good question, otherwise, BTW. +1 from me.) $\endgroup$ – Mike Haskel Apr 19 '16 at 13:22
1
$\begingroup$

If $M \prec N$, $m_1, \dotsc m_n\in M$ and $N\models \exists x\,\varphi(x, m_1, \dotsc m_n)$, then this same formula is true in $M$ of the elements $m_1, \dotsc m_n$. Because $M\models \exists x\,\varphi(x, m_1, \dotsc m_n)$, there is some $m\in M$ such that $M\models \varphi(m, m_1, \dotsc m_n)$. It follows that this is also true in $N$ of $m, m_1, \dotsc m_n$, namely, $N\models \varphi(m, m_1, \dotsc m_n)$.

It's true that $N$ may contain other witnesses to the existential statement that are not in $M$. Nevertheless, when $M$ is an elementary substructure of $N$ and $M$ models an existential statement with parameters in $M$, then $M$ must contain witnesses (like the element $m$, above) to that statement, which are also witnesses in $N$.

$\endgroup$
  • $\begingroup$ For anyone else who was confused in the way I was, it may be helpful to rewrite the formula ∃xφ(x,y1,…,yn) as Ψ(y1,...,yn), [y1,...,yn are the free variables!]. $\endgroup$ – qwert4321 Apr 19 '16 at 1:30
  • $\begingroup$ It probably is better to use $y_i$ rather than $x_i$, but it's not better to suppress display of $x$, and switching from $\phi$ or $\varphi$ to $\Psi$ adds nothing. I haven't displayed the free variables at all :) I stuck to your notation, which is a minor abuse of notation. Strictly speaking, one should write: $$ \exists x\,\varphi(x, y_1, \dotsc y_n)[m_1/y_1, \dotsc m_n/y_n] $$ but I didn't want to get overly fussy with notation. $\endgroup$ – BrianO Apr 19 '16 at 1:48
2
$\begingroup$

The formula with free variables that we use is $\exists x\varphi(x,y_1,\dots,y_n)$.

If for $m_1,m_2,\dots, m_n$ in $M$, we have that $\exists x\varphi(m_1,\dots,m_n)$ is true in $N$, then $\exists x\varphi(m_1,\dots,m_n)$ is true in $M$ by the definition of elementary substructure. And conversely.

$\endgroup$
  • $\begingroup$ But my question is why does N|=∃xφ(x,m1,...,mn) imply M|=∃xφ(x,m1,...,mn) ? So we have a formula φ(x,x1,...,xn) with n+1 free variables, and we know that for any fixed m0,...,mn in dom(M), that M|=φ(m0,m1,...,mn) iff N|=φ(m0,m1,...,mn). It is not clear to me why this means that if there is n in dom(N) such that φ(n,m1,...,mn) is true in N that therefore there is an m in dom(M) such that φ(m,m1,...,mn) is true in M. $\endgroup$ – qwert4321 Apr 19 '16 at 1:05
  • $\begingroup$ @qwert4321 The assumption is that $M$ is an elementary substructure of $N$. So every formula true in $N$ - in particular, the formula $\exists x\varphi$ - is also true in $M$. $\endgroup$ – Noah Schweber Apr 19 '16 at 1:08
  • $\begingroup$ It comes down to the definition of elementary substructure. The shape of the formula (in this case that it has shape $\exists x\varphi(x,y_1,\dots,y_n)$) is irrelevant. $\endgroup$ – André Nicolas Apr 19 '16 at 1:08
  • $\begingroup$ I finally understand and would upvote these comments as well if I could. So in this specific case, if we let Ψ(y1,...,yn) = ∃xφ(x,y1,...,yn) then indeed N|=Ψ(m1,...,mn) iff M|=Ψ(m1,...,mn). Thank you for your patience BrianO, André and Noah. $\endgroup$ – qwert4321 Apr 19 '16 at 1:25
  • $\begingroup$ @qwert4321: You are welcome. "Elementary substructure" is a very strong property, much stronger than mere elementary equivalence. $\endgroup$ – André Nicolas Apr 19 '16 at 1:27

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.