# Elementarily equivalence of structures

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.

• 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?). – Mark Kamsma Jun 10 at 21:31
• $\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 – Leyla Alkan Jun 10 at 21:54
• 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$. – Mark Kamsma Jun 10 at 22:00
• 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$. – Leyla Alkan Jun 10 at 22:22
• 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! – 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.

• 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. – Sam Skywalker Jun 10 at 22:36
• 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). – Mark Kamsma Jun 11 at 7:40
• You are spot on, thanks for pointing it out. I am editing my answer. – Sam Skywalker Jun 11 at 7:53
• 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? – Sam Skywalker Jun 11 at 8:03
• 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. – Mark Kamsma Jun 11 at 8:07