Let $L$ be a language consisting of a binary relation symbol $R$. Consider the following $L$-structures on $\mathbb N$:

$\mathcal N_1=(\mathbb N, \equiv_2),\quad \mathcal N_2=(\mathbb N,<),\quad\mathcal N_3=(\mathbb N,|),\quad\mathcal N_4=(\mathbb N,E)$
where $m\equiv_2 n$ iff $2|m-n$, $<$ is the usual ordering of natural numbers, $|$ is the usual divisibility relation, and $mEn$ iff $m$ and $n$ are consecutive and the smaller one is even. Show that any two of these structures are not elementarily equivalent to each other.

My attempt:
Definition: $\mathcal M \equiv \mathcal N$ if for every $L$-sentence $\sigma$, we have $\mathcal M\models \sigma \iff \mathcal N\models \sigma$

Take $\mathcal N_1 $ and $\mathcal N_2$:

Let $\varphi:=\exists x \exists y(x=3 \, \wedge \, y=4)$

Now, $\mathcal N_1 \nvDash \varphi$ since $2\nmid 3-4$ but $\mathcal N_2 \models \varphi$ since $3<4$.

So, they are not elementarily equivalent to each other.

I don't know how else argue this.

  • $\begingroup$ You cannot express 3 or 4 in your language, so that is not a valid sentence. You really have to look at the properties of these relations. For example: the relation $E$ (in $\mathcal{N}_4$) is not transitive, but $<$ (in $\mathcal{N}_2$) is transitive. This can be expressed in a logical formula (how?). $\endgroup$ – Mark Kamsma Jun 10 at 21:31
  • $\begingroup$ $\varphi:=\forall x \forall y \forall z(x<y \, \wedge \, y<z \implies x<z)$ How can I generalize this formula(without plugging $<$ in to the formula like I did here) so I can check $\mathcal N_2 \models \varphi$ but $\mathcal N_4 \nvDash \varphi$ @MarkKamsma $\endgroup$ – Leyla Alkan Jun 10 at 21:54
  • $\begingroup$ That is indeed the right idea. As you already said: the way it is written now only makes sense for $\mathcal{N}_2$. In the exercise there is a binary relation symbol $R$ that is interpreted differently in the 4 structures. So for example, $\mathcal{N}_2$ interprets it as $<$. In other words, replacing $<$ by $R$ in your formula gives you a valid formula that just states "$R$ is transitive". This is then true in $\mathcal{N}_2$, but false in $\mathcal{N}_4$. $\endgroup$ – Mark Kamsma Jun 10 at 22:00
  • $\begingroup$ Thanks, I get it now. So, since $\equiv_2$ is an equivalence relation $\mathcal N_1$ differs from all the other structures already. Using transivity $\mathcal N_2$ differs from $\mathcal N_4$ and similarly $\mathcal N_3$ differs from $\mathcal N_4$. Also since $<$ is a linear ordering $\mathcal N_2$ differs from $\mathcal N_3$. $\endgroup$ – Leyla Alkan Jun 10 at 22:22
  • 2
    $\begingroup$ That sounds right. Now all you have to do is formalise these ideas using formulas (as you did for transitivity), and then you have your proof! $\endgroup$ – Mark Kamsma Jun 10 at 22:26

Since your language has no constants you cannot use $3$ or $4$ the way you did there. By finding a sentence that is valid in one but not in other structure, these two structures shall not be elementarily equivalent.

First, observe that $\mathcal N_1$ and $\mathcal N_4$ satisfy the symmetric property, whereas $\mathcal N_2$ and $\mathcal N_3$ do not. Fortunately, this property can be expressed in this language as the sentence $\varphi:= \forall x\forall y\, xRy \to yRx$. So, we only need to show that $\mathcal N_1$ and $\mathcal N_4$ are not elementarily equivalent and that $\mathcal N_2$ and $\mathcal N_3$ aren't either.

For $\mathcal N_1$ and $\mathcal N_4$, observe that $\mathcal N_1\models \exists x\exists y \forall z (zRx\vee zRy)$, i.e. there are two natural numbers that are not related with one another and such that any other number shall be related with one of them. It happens that $\mathcal N_4$ does not satisfy this sentence, by construction of the relation $E$. (this part has been edited following the very useful comment by @Mark Kamsma)

It only remains to be shown that $\mathcal N_2$ and $\mathcal N_3$ are not elementarily equivalent. To this end, observe that $\mathcal N_2$ is a total order while $\mathcal N_3$ is not. The total order formula in this language is $\psi:= \forall x\forall y\, xRy\vee yRx$; it happens that $\mathcal N_2\models \psi$ while $\mathcal N_3\nvDash \psi$.

I hope this helps.

  • $\begingroup$ Addendum: I have just read your conversation with @Mark Kamsma, which wasn't there while I was writing. That is pretty much what you have to do. $\endgroup$ – Sam Skywalker Jun 10 at 22:36
  • 1
    $\begingroup$ Always useful to still have an answer, for people that find this question later on. Although the sentence you used for $\mathcal{N}_1$ versus $\mathcal{N}_4$ is still true in $\mathcal{N}_4$. Given $x$, if $x$ is even (that includes $x=0$) we take $y=x+1$, otherwise we take $y=x-1$. What we can do though, is one of the following "for every $x$ there are at least two different elements related to it" or "there are $x$ and $y$ such that every element is related to $x$ or $y$" (personally I think the second one is the clearest, but they should both work perfectly fine). $\endgroup$ – Mark Kamsma Jun 11 at 7:40
  • $\begingroup$ You are spot on, thanks for pointing it out. I am editing my answer. $\endgroup$ – Sam Skywalker Jun 11 at 7:53
  • $\begingroup$ I could also have opted for the transitive property, but it didn't come to my mind. Really, what was I thinking about to not realise that I was implying that $0$ is not even? $\endgroup$ – Sam Skywalker Jun 11 at 8:03
  • 1
    $\begingroup$ We all have those moments ;) In your current answer the bit $x \not R y$ is not really necessary, but it is also not wrong. So I upvoted anyway. $\endgroup$ – Mark Kamsma Jun 11 at 8:07

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.