# Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

It gives the hint to use $x \in \mathbb{N} \leftrightarrow \exists x_0 \exists x_1 \exists x_2 \exists x_3(x \equiv x_0 \cdot x_0 \wedge x_1 \cdot x_1 \wedge x_2 \cdot x_2 \wedge x_3 \cdot x_3)$

i.e. a natural number can be written as a sum of 4 squares

I know the Theory of the Natural Numbers is not R-decidable. Im not quite

sure how to show from that it gives $(\mathbb{Z}, +, \cdot, 1, 0 )$ as being not R-decidable

EDIT: sorry I should have stated the question is restricted to the symbol set $S_{ar} = \{+, \cdot, 0, 1\}$ not $S_{ar,<} = \{+, \cdot, 0, 1, < \}$ So I believe thats why it gives the hint is does.

Hint: reduce the theory of $\mathbb{N}$ to the theory of $\mathbb{Z}$: that is, find a way to turn a sentence $\varphi$ into a new sentence $\psi$ such that $$\mathbb{N}\models\varphi\iff\mathbb{Z}\models\psi$$ (you also need this transformation to be recursive, but put that off for now). If you can do this, then the theory of $\mathbb{Z}$ must be at least as complicated as the theory of $\mathbb{N}$, hence undecidable.
Notice that this amounts to restricting the scope of quantifiers. E.g., given $\varphi\equiv\forall x\exists y(x+y=73)$, the "right" choice for $\psi$ is $\forall x\in\mathbb{N}\exists y\in\mathbb{N}(x+y=73)$ (this is called relativization). Now, how can we write this as a proper sentence . . .?
• sorry I should have stated the question is restricted to the symbol set $S_{ar} = \{+, \cdot, 0, 1\}$ not $S_{ar,<} = \{+, \cdot, 0, 1, < \}$ So I believe thats why it gives the hint is does. – oliverjones May 26 '15 at 1:38
• Indeed - and the issue is how to use what the hint tells you, to relativize the quantifiers. (I've rewritten my example $\varphi$ so it is in the language $S_{ar}$.) – Noah Schweber May 26 '15 at 1:52
• $\psi := \exists x \exists y \exists z \exists w \exists u ( x \equiv y \cdot y \wedge z \cdot z \wedge w \cdot w \wedge u \cdot u)$ Something like that? Clearly the integers contain negative numbers but the naturals do not so we have a similar sentence that $\mathbb{N} \vDash \varphi \leftrightarrow \mathbb{Z} \vDash \psi$ – oliverjones May 26 '15 at 3:20