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$

1 Answer 1

5
$\begingroup$

Hint: each formula uses only finitely many symbols.

$\endgroup$
2
  • $\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, 2015 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$ Apr 22, 2015 at 10:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .