0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $S$ is not allowed. $\endgroup$ – user673051 May 12 at 1:44
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber May 12 at 1:51
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber May 12 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy