most recent 30 from http://mathoverflow.net 2013-06-19T18:13:41Z http://mathoverflow.net/feeds/question/52433 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52433/theory-of-addition-and-a-predicate-that-recognizes-powers-of-2 David Feldman 2011-01-18T20:26:17Z 2011-01-19T03:59:16Z

<p>What is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2?</p>

http://mathoverflow.net/questions/52433/theory-of-addition-and-a-predicate-that-recognizes-powers-of-2/52459#52459 Dave Marker 2011-01-19T02:43:34Z 2011-01-19T02:43:34Z

<p>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:</p> <p><a href="http://www.logique.jussieu.fr/~point/papiers/cherlin_point86.pdf" rel="nofollow">http://www.logique.jussieu.fr/~point/papiers/cherlin_point86.pdf</a></p>