# Show that $\mathcal{L}$ structures $\mathcal{A}$ and $\mathcal{B}$ are not equivalent

Let $$\mathcal{L}=\{\leq\}$$ and $$\mathcal{A}=\{\mathbb{N},\leq\}$$, and $$\mathcal{B}=\{K,\leq\}$$ where $$K=\{(a,b)\in\mathbb{N}^2:a\in\mathbb{N} \text{ and } b=1 \text{ or } b=2\}$$ and pairs $$(a,b)$$ have the natural ordering on themselves but pairs $$(a,2)$$ are strictly greater then all pairs of the form $$(a,1)$$

Show that $$\mathcal{A}\not\equiv\mathcal{B}$$

So I believe what I want is a sentence which is true in one structure but not true in the other structure.

I can obviously identify some things that are properties of the naturals that won't be properties of the set $$K$$ like every natural has only finitely many elements less then or equal to it. But not ones that can be expressed in a single sentence.

• In $\mathbb N$ we have only one number that has no predecessor while in $K$ we have two : $(0,1)$ and $(0,2)$. – Mauro ALLEGRANZA Oct 16 '19 at 15:08
• Right, but without constant $1$, and the $+$ operation in $\mathcal{L}$ can this be expressed as a sentence? – AColoredReptile Oct 16 '19 at 15:09
• What does it mean to be a predecessor? $x$ is a predecessor of $y$ if $x$ is the biggest thing less than $y$. Can you express this with only $<$? – HallaSurvivor Oct 16 '19 at 15:11
• Ok $\neg\exists_z(x\leq z \wedge z\leq y)$ – AColoredReptile Oct 16 '19 at 15:17
• @MauroALLEGRANZA That doesn't work either: your $z$ could be $m$ or any element less than $n$. You want $n\leq m \land n\neq m \land \forall z( (n\leq z \land z\leq m)\rightarrow (z = n\lor z = m))$ – Alex Kruckman Oct 16 '19 at 17:05

Exactly one element of $$\mathcal{A}$$ has no predecessors, while two distinct elements of $$\mathcal{B}$$ have no predecessors. See if you can write $$\text{isPred}(x,y)$$ and use this to distinguish the structures.