8
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.