2
$\begingroup$

Setting

For any language $\mathcal L$, two $\mathcal L$-structures $\mathcal M$ and $\mathcal N$ are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage.

Attempt

($\Rightarrow$) Given $\mathcal M\equiv \mathcal N$, so $\mathcal M\models \phi \iff \mathcal N \models \phi$ for every $\mathcal L$-sentence $\phi$. Now suppose there is finite sublanguage of $\mathcal L$ where $\mathcal M\not\equiv \mathcal N$, then it follows that we can find some $\mathcal L$-sentence $\phi$ where $\mathcal M\models \phi$ but $\mathcal N \not\models \phi$, contradicting the assumption that $\mathcal M\models \phi \iff \mathcal N \models \phi$ for every $\mathcal L$-sentence $\phi$.

($\Leftarrow$) Now suppose $\mathcal M\equiv \mathcal N$ in every finite sublanguage, then it follows by compactness $\mathcal M\equiv \mathcal N$.

Problem

In the $\Rightarrow$ direction, I am not confident that I can use compactness. Since each finite sublanguage may not necessarily generate a finite set of sentences, which compactness theorem requires.

$\endgroup$
5
$\begingroup$

Hint: each formula uses only finitely many symbols.

$\endgroup$
  • $\begingroup$ so you're saying group all formulas using certain set of symbols into one set, and the language generating that set is one particular sublanguage we are concerned with? And since the number of symbols used by any formula is finite, the sublanguage is also finite? $\endgroup$ – chibro2 Apr 22 '15 at 2:56
  • 1
    $\begingroup$ Suppose $\mathcal M \not \equiv \mathcal N$. Then there is a formula $\phi$ such that $\mathcal M \models \phi$ and $\mathcal N \models \lnot \phi$. Now use the hint. $\endgroup$ – Levon Haykazyan Apr 22 '15 at 10:24

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.