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?
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 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.
You are almost right. A subset is definable iff it is a finite union of arithmetic progressions (= cosets of subgroup $n\mathbb{Z}$). See Presburger arithmetic, page 4
