Formulas for $\{1\}$ and $\mathbb{P}$ in $(\mathbb{Z},+)$ I have a homework to find formulas for $\{1\}$ and $\mathbb{P}$ in the L-structure $(\mathbb{Z},+)$ with $L = (+)$. I have a suspicion that I wrote it wrong and it should be $(\mathbb{Z},\cdot)$ instead. Are those sets definable in $(\mathbb{Z},+)$? 
 A: Suppose that $\mathcal{L}$ is a first order language with binary function symbol $+$ and binary relation symbol $=$. Then $\mathfrak{U} = \left(\mathbb{Z},+,=\right)$ is an $\mathcal{L}$-structure with respect to the obvious interpretation. Let $\phi(x)$ be a formula in $\mathcal{L}$ and $\phi^{\mathfrak{U}}$ be its interpretation in $\mathfrak{U}$. Consider
$$Z(\phi) = \{n\in \mathbb{Z}\,|\,\phi^{\mathfrak{U}}(n)\}$$
Since $f:\left(\mathbb{Z},+,= \right)\rightarrow \left(\mathbb{Z},+,=\right)$ given by $f(n) = -n$ is an $\mathcal{L}$-isomorphism, we derive that 
$$\phi^{\mathfrak{U}}(n) \Leftrightarrow \phi^{\mathfrak{U}}(f(n))$$
for every $n\in \mathbb{Z}$. This implies that 
$$f\left(Z(\phi)\right) = Z(\phi)$$
and hence $Z(\phi)$ is symmetric. Set $\mathbb{P}$ of prime numbers is not symmetric.
If you are not satisfied with this answer, let me elaborate more. Consider the language $\mathcal{L}' = \mathcal{L}\cup \{-,0\}$. Theory $\mathbb{Th}\left(\mathbb{Z},+,-,0=\right)$ is contains the first order theory of abelian groups Ab. This follows from the fact that $\left(\mathbb{Z},+,-,0,=\right)$ is a free abelian group. Now theory Ab has quantifier elimination. This implies that any first order formula in $\mathcal{L}'$ is equivalent in $\left(\mathbb{Z},+,-,0,=\right)$ to a formula that is quantifier free in $\mathcal{L}'$. Finally $\mathbb{Th}\left(\mathbb{Z},+,=\right)$ in $\mathcal{L}$ is equivalent to $\mathbb{Th}\left(\mathbb{Z},+,-,0=\right)$ as a theory in $\mathcal{L}'$. So you may consider quantifier free formulas in $\mathcal{L}'$.
Remark.
There is a theory called Presburger Arithmetic. This is a first order theory in the language $\mathcal{L}$ having constants $0, 1$, binary function $+$ and axioms:


*

*$\neg (0 = x+1)$

*$x+1 = y+1 \Rightarrow x=y$

*$x + 0 = x$

*$x+(y+1) = (x+y)+1$

*For every first order formula $\phi(x)$ in $\mathcal{L}$ with free variable $x$ the following sentence is an axiom. 
$$\left(\phi(0)\wedge \left(\forall_x\phi(x)\Rightarrow \phi(x+1)\right)\right) \Rightarrow \forall_x\phi(x)$$
Presburger Arithmetic is a decidable theory. 
I will denote it by $\textbf{PresAr}$. Suppose that we are able to define a formula $\textbf{mul}(x,y,z)$ in the language $\mathcal{L}$ of Presburger Arithmetic that express the fact that $z = x\cdot y$. By this I mean that $\textbf{PresAr}$ proves certain sentences about $\textbf{mul}(x, y, z)$ and these sentences express the usual properties of the multiplication of natural numbers. This would imply that $\textbf{PresAr}$ is equivalent to the usual (first order) Peano Arithmetic (denoted by $\textbf{PAr}$). This is contradiction, because $\textbf{PAr}$ is undecidable.
By similar arguments you can show that primeness, divisibility are udefinable in $\textbf{PresAr}$.
