MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

10 remove ambiguous oxford conjunction; [made Community Wiki]

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), and M(1,b,c) := (b=c). But some predicates which can 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).

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?

9 emphasis only

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), and M(1,b,c) := (b=c). But some predicates which can 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).

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?

8 the theory, not the predicate

In Presburger Arithmetic there is no predicate that can express divisibility, else it 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), and M(1,b,c) := (b=c). But some predicates which can 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).

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?

7 capitalize PA
6 edited tags
5 reverse explication order to clarify
4 s/vs\./versus/, "vs." is a false acronym
3 specify that we don't need multiplication to be available
2 s/powerful/expressive/, i hope this is better terminology
1