Timeline for Undecidability of the existential theory
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 23 at 16:01 | answer | added | L. Gitin | timeline score: 3 | |
| Sep 3, 2015 at 14:35 | comment | added | Mary Star | 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 12:37 | comment | added | Dávid Natingga | 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 2, 2015 at 21:43 | comment | added | Gerhard Paseman | 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:08 | comment | added | Mary Star | 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:04 | history | edited | Mary Star | CC BY-SA 3.0 |
added 313 characters in body
|
| Sep 2, 2015 at 20:52 | comment | added | Joel David Hamkins | 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:37 | history | asked | Mary Star | CC BY-SA 3.0 |