Formulas for $\{1\}$ and $\mathbb{P}$ in $(\mathbb{Z},+)$

Question

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},+)$?

Answer 1

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:

1. $\neg (0 = x+1)$
2. $x+1 = y+1 \Rightarrow x=y$
3. $x + 0 = x$
4. $x+(y+1) = (x+y)+1$
5. 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}$.