Exercise 3.4.3 in David Marker's "Model Theory" 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.
 A: 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.
