# Sentence satisfied by parity ordering and unsatisfied by natural ordering

Let $$>_1$$ be the natural ordering on $$\mathbb{Z}_{>0}$$ and $$>_2$$ be the ordering on $$\mathbb{Z}_{>0}$$ with $$m>_1n\Leftrightarrow m>_2n$$ for all $$m$$ and $$n$$ of the same parity and $$m>_2n$$ for all even $$m$$ and odd $$n$$. Construct a sentence satisfied by the structure $$\langle\mathbb{Z}_{>0},>_2\rangle$$ and unsatisfied by the structure $$\langle\mathbb{Z}_{>0},>_1\rangle$$ containing only $$>$$, variables, propositional connectives, parentheses, $$\forall$$, $$\exists$$, and $$=$$. No constants allowed.

$$>_2$$ corresponds to $$\mathbb{Z}_{>0}$$ stacked on itself: the even numbers are on top and the odd numbers are below. Every even number is greater than every odd number and the even numbers are ordered like $$\mathbb{Z}_{>0}$$, as are the odd numbers. The only functional difference with $$>_1$$ is the chasm between $$2$$ and every odd number, which we should capture in the sentence. The easiest way I thought of is that there exists an integer greater than an infinite number of integers under $$>_2$$ but not $$>_1$$. My attempt to make this a sentence was $$\exists x_0\forall n\exists x_1...\exists x_n(x_0>x_1\land...\land x_{n-1}>x_n)$$, but sentences can't have variable length. I don't see a difference besides the chasm.

Indeed you cannot express "is above infinitely many elements" in a first-order way. However, there is a simpler way to single out $$2$$: instead of the ordering, think about the corresponding successor function $$S$$ (which is definable from the ordering). Do you see a way to single out $$2$$ as being special, in the $$>_2$$-structure, using successor only?
It may also help to think in terms of two different kinds of "chasms" - consider the linear orders which we may informally denote "$$\mathbb{N}+\mathbb{N}$$" (this is your "$$>_2$$"-order) and "$$\mathbb{N}+\mathbb{Z}$$." Each has a "chasm," but the chasm in the second one is "hidden" (and indeed $$\mathbb{N}$$ and $$\mathbb{N}+\mathbb{Z}$$ are elementarily equivalent).
• $S$ is not allowed. – user673051 May 12 at 1:44
• @SeanChen Read the parenthetical comment: it's definable from "$>$" (do you see how?). Any sentence using successor and $>$ can be rewritten to use only $>$ instead. – Noah Schweber May 12 at 1:51
• And even that's not the point - the point is that if you think in terms of successor, it will be easier to pin down the special behavior of $2$ in $>_2$ that you'll express in a first-order way. – Noah Schweber May 12 at 1:59