While studying Model Theory for my exam, I came across the following question:
a) Show that the theory of $(\mathbb{Z}, s)$ has quantifier elimination where $s(x) = x + 1.$
b) Show that the theory of $(\mathbb{N}, s)$ does not have quantifier elimination.
I am not even sure that I understand what the theory is to be honest. I assume that I am not allowed to use $+$, $1$, etc. In that case, I don't know how to approach to the question. I tried to understand intuitively the difference between two theories and why one would have QE and the other does not. Any help would be appreciated.
Let me explain what the question is asking, and then give a hint as to how to approach it.
The theories in question are the theories of the structures. A theory in a language $\Sigma$ is, as you say, just a set of $\Sigma$-sentences (some authors also require that it be "deductively closed"). But each structure $\mathcal{M}$ in a language $\Sigma$ has a particular theory associated to it - its "full" theory, the set of all sentences true in the structure: $$Th(\mathcal{M})=\{\varphi: \mathcal{M}\models\varphi\}.$$ The theory of a structure is always complete (since for each structure $\mathcal{M}$ and each sentence $\varphi$ we either have $\mathcal{M}\models \varphi$ or $\mathcal{M}\models\neg\varphi$). In fact, theories of structures are exactly the complete theories: if $T$ is complete, then for each $\mathcal{M}\models T$ we have $Th(\mathcal{M})=T$.
Now let's think about the two structures in question here, $\mathcal{Z}=(\mathbb{Z}; s)$ and $\mathcal{N}=(\mathbb{N}; s)$. The first thing to note is that their theories are not too different - e.g. both $Th(\mathcal{Z})$ and $Th(\mathcal{N})$ contain the sentence $$\forall x(\neg(s(x)=x)).$$ On the other hand, there is one striking difference between the two structures: $\mathcal{Z}$ "goes to infinity in both directions" but $\mathcal{N}$ "has a beginning."
Can you go from that observation to finding a specific sentence $\varphi$ which is in $Th(\mathcal{Z})$ but not in $Th(\mathcal{N})$? HINT: what makes $0$ special, in terms of the successor operation?
You can turn that sentence into a formula which defines $\{0\}$ in $\mathcal{N}$; this formula will have a quantifier in it. To show that $\mathcal{N}$ doesn't have quantifier elimination, it will be enough to show that $\{0\}$ is not definable by a quantifier-free formula.
Finally, you'll need to show that $Th(\mathcal{Z})$ does have quantifier elimination. But once you understand what $Th(\mathcal{Z})$ is, per the above section, this should fit the pattern of the examples of quantifier elimination you've already seen.