# Undecidability of the existential theory

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, besides the one of the paper of J. Denef "The diophantine problem for polynomial rings of positive characteristic" ?

In the paper of Denef, the corollary is stated as followed:

Let $p$ be a fixed prime number, $p>1$.

Define the relation $|^p$ by $$x |^p y \leftrightarrow \exists f \in \mathbb{N} : y= \pm x p^f$$

Then the positive existential theory of $(\mathbb{Z}; +, | , |^p)$ is undecidable.

• Could you clarify the relation? Do you mean a binary relation, where $p$ is a fixed prime? Or do you mean a trinary relation, or what? Sep 2, 2015 at 20:52
• I found the relation $(\exists s \in \mathbb{Z})m=np^s$ in the paper jstor.org/stable/2275396?seq=1#page_scan_tab_contents . I added how it is formulated in the paper of Denef. @JoelDavidHamkins Sep 2, 2015 at 21:08
• Based on mathoverflow.net/questions/216251/… , my guess is it is a binary relation (as p is fixed), and that this question will not have a concise and suitable answer. Gerhard "Unsure And Undecided About Suitability" Paseman, 2015.09.02 Sep 2, 2015 at 21:43
• I think I do not understand your question. The statement $\exists s \in \mathbb{Z} (m=np^s)$ is decidable easily: just check all $s$ up to the values of $m$. Sep 3, 2015 at 12:37
• I am looking for the proof that the existential theory of $\mathbb{Z}$ with the structure of addition, divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable. I have found one proof at the paper of Denef and I was wondering if I can find the proof also somewhere else... Do you maybe where I can find it? @DávidTóth Sep 3, 2015 at 14:35