Which recursively-defined predicates can be expressed in Presburger Arithmetic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:39:14Z http://mathoverflow.net/feeds/question/37777 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37777/which-recursively-defined-predicates-can-be-expressed-in-presburger-arithmetic Which recursively-defined predicates can be expressed in Presburger Arithmetic? Dan Brumleve 2010-09-05T07:53:16Z 2010-09-06T02:31:20Z <p>In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for example D(a,c) := exists b: M(a,b,c), M(a,b,c) := M(a-1,b,c-b), M(1,b,c) := (b=c). But some predicates which <em>can</em> be expressed in Presburger Arithmetic also have recursive definitions, for example P(x,y,z) := (x+y=z) versus P(x,y,z) := P(x-1,y+1,z), P(0,y,z) := (y=z).</p> <p>How to tell if a predicate, defined recursively without use of multiplication, has an equivalent non-recursive definition which can be expressed in Presburger Arithmetic?</p> http://mathoverflow.net/questions/37777/which-recursively-defined-predicates-can-be-expressed-in-presburger-arithmetic/37786#37786 Answer by Joel David Hamkins for Which recursively-defined predicates can be expressed in Presburger Arithmetic? Joel David Hamkins 2010-09-05T11:46:07Z 2010-09-05T12:52:07Z <p>Presburger arithmetic admits <a href="http://en.wikipedia.org/wiki/Quantifier_elimination" rel="nofollow">elimination of quantifiers</a>, if one expands the language to include truncated minus and the unary relations for divisibility-by-2, divisibility-by-3 and so on, which are definable in Presburger arithmetic. (One can equivalently expand the language to include congruence $\equiv_k$ modulo $k$ for each natural number $k$.) That is to say, every assertion in the language of Presburger arithmetic is equivalent to a quantifier-free assertion in the expanded language.</p> <p>It follows that the definable subsets of $\mathbb{N}$ in the language of Presburger arithmetic are exactly the eventually periodic sets. These are comparatively trivial sets, of course, and it means that the set of prime numbers and other interesting sets of natural numbers are simply not expressible in the language of Presburger arithmetic. A similar analysis holds in higher dimensions, and for this reason, we usually think of Presburger arithmetic as a weak theory.</p> <p>The quantifier elimination argument leads directly to the conclusion that Presburger arithmetic is a decidable theory: given any sentence, one finds the quantifier-free equivalent formulation, and such sentences are easily recognized as true or false. </p> <p>There is an interesting account in <a href="http://www.divms.uiowa.edu/~tinelli/classes/295/notes/quantifier-elim.pdf" rel="nofollow">these slides for a talk</a> by Cesare Tinelli. </p> http://mathoverflow.net/questions/37777/which-recursively-defined-predicates-can-be-expressed-in-presburger-arithmetic/37795#37795 Answer by Michaël for Which recursively-defined predicates can be expressed in Presburger Arithmetic? Michaël 2010-09-05T14:44:02Z 2010-09-05T14:44:02Z <p>Presburger Arithmetic (over the naturals) describes exactly the semi-linear sets. A set ($\subseteq \mathbb{N}^k$) is linear if it can be expressed as $$L(\vec c, P=\{\vec{p_1}, \ldots, \vec{p_n}\}) = \{ \vec c + \sum_{i=1}^pc_i\vec{p_i} \;|\; c_i \in \mathbb{N}\}.$$</p> <p>A set is semi-linear if it can be expressed as a finite union of linear sets. One can deduce a few techniques from this characterization (due to Ginsburg &amp; Spanier).</p>