# Is $\mathbb{N}$ definable in $(\mathbb{Z},0,S)$?

Is the subset of natural numbers (first-order) definable in the structure $(\mathbb{Z},0,S)$ ($S$ is the successor function)? I believe that it cannot, since $\mathbb{N}$ is exactly the set of elements 'reachable' from $0$ by applying $S$, but cannot find a precise argument. The only automorphism of the structure $(\mathbb{Z},0,S)$ is the identity, which of course preserves every subset.

• @AsafKaragila my mistake, I'll delete. – user24142 Feb 3 '15 at 4:12

Hint. Show that $\mathrm{Th}(\mathbb Z,0,S)$ has quantifier elimination. Then enumerate the atomic formulas: from here, show that no boolean combination defines $\mathbb N$.