2
$\begingroup$

Let the first-order language ${\mathcal{L}}$ have a single binary predicate $P$. Consider the structure whose underlying set is ${\mathbb{Z}}$, the integers, and an ordered pair $(m,n)$ is in $P$ if and only if $m=n+1$ for some nonzero $n$.

Is the subset of positive integers defineable in $({\mathbb{Z}},P)$, that is to say, is there a first order formula $\phi(x,y_1,\ldots, y_k)$ together with integers $n_1,\ldots, n_k$ such that $\{1,2,3,\ldots\}=\{m\in {\mathbb{Z}}:\, \phi(m,n_1,\ldots,n_k)\}$?

$\endgroup$

1 Answer 1

5
$\begingroup$

No, the structure is definitionally equivalent with $(\mathbb Z,0,S)$ (that is, you make the successor function a function rather than a predicate), which is well-known to have elimination of quantifiers: every formula is equivalent to a Boolean combination of formulas of the form $y=S^n(x)$, where $x,y$ are either variables or $0$, and $n$ is a natural number. For formulas with one free variable, this means that the only definable subsets are finite or cofinite.

In fact, the set of positive integers is not even definable in the structure $(\mathbb Z,0,1,+)$, which also has a form of elimination of quantifiers: every formula $\phi(x_1,\dots,x_k)$ is equivalent to a Boolean combination of linear equalities $n_1x_1+\dots+n_kx_k=n_0$ with $n_0,n_1,\dots,n_k\in\mathbb Z$, and formulas of the form $x_i\equiv n\pmod m$ with $n,m\in\mathbb Z$, $0\le n< m$. Its unary definable subsets are those that are periodic up to finitely many exceptions.

EDIT: In view of the comments, let me clarify how $(\mathbb Z,0,S)$ is definable in $(\mathbb Z,P)$:

$$\begin{align*} x=0&\iff\forall y\\,\neg P(y,x),\\\\ x=1&\iff\forall y\\,\neg P(x,y),\\\\ y=S(x)&\iff P(y,x)\lor(x=0\land y=1). \end{align*}$$

The converse is obvious: $$P(x,y)\iff x=S(y)\land x\ne0.$$

$\endgroup$
2
  • $\begingroup$ Thank you Emil for your answer. In my question, the relation $(n+1)Pn$ holds only for nonzero $n$. The directed graph of $P$ looks something like two copies of the natural numbers, but with the directions reversed. I'm sorry I didn't emphasize the nonzero condition. $\endgroup$
    – user2529
    Apr 12, 2013 at 10:08
  • $\begingroup$ I noticed the condition. The effect of the condition is that not only $S$, but also $0$ becomes definable in the structure, that’s why I used $(\mathbb Z,0,S)$ instead of $(\mathbb Z,S)$. (This makes no difference anyway, as you are asking about definability with parameters.) $\endgroup$ Apr 12, 2013 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.