Is this fragment of arithmetic on $p^{-\infty} {\mathbb Z}$ decidable? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T10:39:07Z http://mathoverflow.net/feeds/question/106551 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106551/is-this-fragment-of-arithmetic-on-p-infty-mathbb-z-decidable Is this fragment of arithmetic on $p^{-\infty} {\mathbb Z}$ decidable? Marty 2012-09-06T21:51:59Z 2012-09-06T21:51:59Z <p>Let $p$ be a prime number. Consider the abelian group $p^{-\infty} {\mathbb Z} = \bigcup p^{-n} {\mathbb Z}$ consisting of rational numbers whose denominator is a power of $p$, under addition.</p> <p>View ${\mathbb Z}$ as a predicate on $p^{-\infty} {\mathbb Z}$, in the sense that ${\mathbb Z}(x)$ is true if $x$ is an integer.</p> <p>Let $\phi$ be the function from ${\mathbb Z}$ to $p^{-\infty} {\mathbb Z}$ given by $\phi(n) = p^n$.</p> <p>Is the first order theory of $( p^{-\infty} {\mathbb Z}, =, >, 0, 1, +, {\mathbb Z}, \phi )$ decidable?</p> <p>A bit of background: The theory of $({\mathbb Z}, =, >, 0, 1, +, \phi)$ is decidable (where here $\phi$ is restricted to natural numbers). This is a result of Semenov; see my answer to the question <a href="http://mathoverflow.net/questions/103896/beyond-presburger-arithmetic/103914" rel="nofollow">http://mathoverflow.net/questions/103896/beyond-presburger-arithmetic/103914</a> for more.</p> <p>On the other hand, what I've described is pretty close to undecidable theories. If I included a predicate $f: {\mathbb Z} \times p^{-\infty} {\mathbb Z} \rightarrow p^{-\infty} {\mathbb Z}$ sending $(n,x)$ to $2^n \cdot x$, it would be undecidable by a result of Delon ("${\mathbb Q}$ Muni de l'Arithmetique Faible de Penzin est Decidable," Proc. of AMS, vol. 125, no 9, 1997).</p> <p>Any references or results would be greatly appreciated. </p>