Definability in a language with a single binary predicate

Question

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)\}$?

Answer 1

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