Differentiating between standard and non-standard interpretations of 'less than' relation

Question

Take a relation $R$. In Structure $A$, $R$ is interpreted as the 'less than' relation (for natural numbers). In $B$, $R$ is interpreted as a relation (for natural numbers) where $R(a,b)$ holds if and only if either $a$ is less than $b$ and $a,b$ are both odd or both even, or $a$ is even and $b$ is odd. Find a sentence that is true under interpretation $A$ and false under $B$. Besides the relation symbol $R$, the language only has quantifiers, connectives, and $=$.

Intuitively, I understand the difference between the two interpretations. In $A$, $R(1,2)$ holds. In $B$, it does not, since $1$ and $2$ are not both odd/even and $1$ is not even/$2$ not odd. But when it comes to writing a sentence in a language without constant symbols or a successor function, I'm stumped. It looks like a lot of the properties of interpretation $A$ hold for interpretation $B$. For instances, $$R(x,y) \rightarrow \neg R(y,x)$$ $$R(x,y) \wedge R(y,z) \rightarrow R(x,z)$$ $$\neg R(x,y) \rightarrow R(y,x) \vee (x=y)$$ I'm out of ideas on the types of sentences that could work.

Answer 1

The basic idea is that $B$, has two elements without a direct predecessor, namely $0$ and $1$, while $A$ has only one, namely $0$.

Note that given $x$, the sentence $$ \def\pr{\mathsf{prec}}\pr(x) := \exists y \, \forall z: z R x \to (z = y \lor z R y) $$ denote the statement that $x$ has a direct predecessor. Hence $$ \forall x,x': \pr(x) \land \pr(x') \to x= x' $$ is true in $A$, but not in $B$.

Answer 2

To give you a feel for why martini's solution works, it is because $B$ is essentially two copies of $\mathbb{N}$ (odds and evens), where anything in the first copy (even) is less than anything in the second copy (odd), and any two things in each copy is ordered normally (both even or both odd). So what is the difference between the two? Clearly, $A,B$ differ in the number of elements with left neighbours, where "left neighbour of $x$" means an element that is strictly less than $x$ with no element between them. And this explains why both $A$ and $B$ satisfy all the general properties of orderings, since both are indeed total orders.

Now for fun, consider the exact same question but using integers instead of natural numbers, namely that $A$ is the standard ordering on the integers while $B$ is your specified ordering on the integers. The above description of $B$ still works, but now every element has a left neighbour in both $A$ and $B$, so they cannot be distinguished that way. In fact, it turns out that these two structures cannot be distinguished by a first-order formula!