4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joel David Hamkins Sep 2 '15 at 20:52
  • $\begingroup$ 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 $\endgroup$ – Mary Star Sep 2 '15 at 21:08
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Sep 2 '15 at 21:43
  • $\begingroup$ 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$. $\endgroup$ – Dávid Natingga Sep 3 '15 at 12:37
  • $\begingroup$ 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 $\endgroup$ – Mary Star Sep 3 '15 at 14:35

Your Answer

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

Browse other questions tagged or ask your own question.