Consider the integers as a first-order structure in the language *{0,+,-}* of abelian groups. I suspect that the collection of definable subsets (without parameters) of this structure is an algebra containing nZ for all natural n (i.e. all periodic sets). This is to say, it's trivial to conclude that the collection of definable subsets contains an algebra containing nZ, however I don't know how to prove if other sets exist. 


Any ideas?



Definable subsets of the integers as an abelian subgroup?
Of course, the definable sets are closed under finite
unions, intersections and complement, and so you will
easily get more than just the sets $n\mathbb{Z}$, since you
also get the complements of these sets and their unions and
so on. But in fact, the definable sets in your structure
are exactly the finite boolean combinations of these sets. 


This is a slightly smaller collection than in Mark's answer, which provides the answer in the case where you allow parameters in the definition. Neverthelss, the same ideas as in [Presburger
arithmetic](http://en.wikipedia.org/wiki/Presburger_arithmetic) provide the answer to your question.


Your question is what are the definable subsets of
$\langle\mathbb{Z},+,-\rangle$. Since both negation and
subtraction are definable from addition, the definable
subsets of that structure are the same as the definable
subsets of $\langle\mathbb{Z},+\rangle$, so let us consider
the language with only addition.


Note that there is an automorphism of this structure taking
every number to its negation, it follows that no non-zero
number is definable, and that every definable subset of
$\mathbb{Z}$ is symmetric about $0$.


**Theorem.** Every formula $\varphi$ in the language of
addition is equivalent in $\langle\mathbb{Z},+\rangle$ to a
quantifier-free assertion in the language of addition
augmented by equivalence $\equiv\_n$ modulo $n$ for every
$n$.


Proof sketch. We follow the standard elimination of
quantifiers argument template, as in the case of Presburger
arithmetic, proving it by induction on $\varphi$. It is
trivial if $\varphi$ is atomic, and the Boolean connective
case is trivial. Suppose that $\varphi=\exists x\psi(x)$,
where $\psi(x)$ is quantifier-free in the expanded
language. We may put $\psi$ in disjunctive normal form, and
distribute the quantifier over the disjunct, to reduce to
the case where $\varphi$ asserts $\exists x\
\psi\_0\wedge\cdots\wedge\psi\_n$, where each $\psi\_n$ is
atomic or negated atomic in the expanded language. If $x=t$
occurs for some term $t$ not involving $x$, then we may
replace $x$ everywhere by $t$ and thereby eliminate the
need for $x$. If $kx=t$ occurs, then we may replace $x$
everywhere by $\frac1kt$, and the clear denominators in the
remaining, thereby eliminating $x$. So we may assume that
none of the $\psi\_i$ are equalities. Note that assertions
of the form $kx\equiv\_n t$ can reduce to remove the $k$,
since if $k$ is relatively prime to $n$, then it has an
inverse $r$ modulo $n$, and so the assertion is equivalent
to $x\equiv\_n rt$, and otherwise the assertion reduces to
the disjunction of finitely many assertions about $x$ and
$t$ via smaller moduli, as in the case of Presburger
arithmetic. So we may assume that $\psi$ is asserting that
$x$ solves a system of congruences of the form $x\equiv\_n
t$ and $x\not\equiv\_m s$. The existence of a solution to
such a system is expressible without $x$, since it amounts
to the large boolean combination of assertions of whether
the modular values of the $t$'s and $s$'s use up all the
values or not. More details would be contained in any of
the full accounts of the Presburger arithmetic argument.
QED


The corollary is that every definable subset of
$\langle\mathbb{Z},+\rangle$ is a finite Boolean
combination of $n\mathbb{Z}$ for various $n$. The reason is
that the solutions of the atomic formulas $kx\equiv\_n 0$
all have this form, and by the theorem, every definable set
is a finite Boolean combination of such sets.


This is perhaps surprising in comparison with the case of
Presburger arithmetic $\langle\mathbb{N},+\rangle$, where
every individual element was definable: $1$ is the only
natural number that is not the sum of two non-zero natural
numbers, and hence every individual natural number is
definable. Thus, in $\langle\mathbb{N},+\rangle$ the
definable sets are closed under finite differences. But
that seems not to the case in $\langle\mathbb{Z},+\rangle$,
where the argument above establishes that the set
$\{-1,1\}$ is not definable.


