Sentence satisfied by parity ordering and unsatisfied by natural ordering

44 Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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).