Welcome to MathOverflow

Question

5

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

edited Jan 19 2011 at 3:59

asked Jan 18 2011 at 20:26

David Feldman
11.3k●2●25●79

2

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. – Andres Caicedo Jan 18 2011 at 20:51

Dave Marker · Accepted Answer · 2011-01-19 02:43:34Z UTC

7

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

answered Jan 19 2011 at 2:43

Dave Marker
1,935●7●8

	Dave: How do you get around the fact that $\times$ is definable? – Andres Caicedo Jan 19 2011 at 3:51
	@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!! – David Feldman Jan 19 2011 at 3:58
	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$.) – David Feldman Jan 19 2011 at 4:05
	Oh! Of course. @Dave: Thanks for the reference. – Andres Caicedo Jan 19 2011 at 4:23
	And thanks Andres for also for your reference, but I haven't chased it down yet. – David Feldman Jan 19 2011 at 5:04

Theory of addition and a predicate that recognizes powers of 2

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.