1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 . . .?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – oliverjones May 26 '15 at 1:38
  • $\begingroup$ 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}$.) $\endgroup$ – Noah Schweber May 26 '15 at 1:52
  • $\begingroup$ $\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$ $\endgroup$ – oliverjones May 26 '15 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.