What is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2?
$\begingroup$
$\endgroup$
1
asked Jan 18, 2011 at 20:26
-
2$\begingroup$ Hi David. Are you familiar with the work of Richard? It is not exactly on Presburger arithmetic, so it may not be relevant. In any case: Denis Richard, "All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate", Special volume on ordered sets and their applications (L'Arbresle, 1982), Discrete Math. 53 (1985), 221–247. $\endgroup$– Andrés E. CaicedoCommented Jan 18, 2011 at 20:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
The theory of the natural numbers with addition and $x\mapsto 2^x$ is decidable. One reference is the Cherlin-Point paper "On extensions of Presburger arithmetic". It can be found on Francoise Point's webpage:
http://www.logique.jussieu.fr/~point/papiers/cherlin_point86.pdf
-
$\begingroup$ Dave: How do you get around the fact that $\times$ is definable? $\endgroup$ Commented Jan 19, 2011 at 3:51
-
$\begingroup$ @Andres et al. I made silly mistake writing the preamble to my question. But Dave Marker's answer corrects my mistake and answers my question. Thanks!! $\endgroup$ Commented Jan 19, 2011 at 3:58
-
$\begingroup$ I've edited my mistake out of the question now! (One could define multiplication if one had $2^{(\cdot)}$ and $a^{(\cdot)}$ provided $a$ equals a power of $2$.) $\endgroup$ Commented Jan 19, 2011 at 4:05
-
$\begingroup$ Oh! Of course. @Dave: Thanks for the reference. $\endgroup$ Commented Jan 19, 2011 at 4:23
-
1$\begingroup$ @DavidFeldman Perhaps you meant that you can define multiplication if you have the binary powering operation $a^b$ restricted to $a$ being a power of $2$: $xy=z$ iff $(2^x)^y=2^z$. $\endgroup$ Commented Nov 17 at 18:33