|
10
|
|
edited Sep 6 2010 at 2:31 |
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
|
|
edited Sep 5 2010 at 10:02 |
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
|
|
edited Sep 5 2010 at 9:56 |
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
|
|
edited Sep 5 2010 at 9:48 |
In Presburger Arithmetic there is no predicate that can express divisibility, else it 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 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?
|
|
|
|
|
6
|
|
edited Sep 5 2010 at 9:30 |
|
|
|
|
|
|
5
|
|
edited Sep 5 2010 at 9:18 |
In Presburger Arithmetic there is no predicate that can express divisibility, else it 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) := P(x-1,y+1,z), P(0,y,z) := (y=z) x+y=z) versus P(x,y,z) := P(x-1,y+1,z), P(0,y,z) := (x+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?
|
|
|
|
|
4
|
|
edited Sep 5 2010 at 8:49 |
In Presburger Arithmetic there is no predicate that can express divisibility, else it 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) := P(x-1,y+1,z), P(0,y,z) := (y=z) vs. versus P(x,y,z) := (x+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?
|
|
|
|
|
3
|
|
edited Sep 5 2010 at 8:22 |
In Presburger Arithmetic there is no predicate that can express divisibility, else it 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) := P(x-1,y+1,z), P(0,y,z) := (y=z) vs. P(x,y,z) := (x+y=z).
How to tell if a recursively-defined predicate, defined recursively without use of multiplication, has an equivalent non-recursive definition which can be expressed in Presburger Arithmetic?
|
|
|
|
|
2
|
|
edited Sep 5 2010 at 7:59 |
In Presburger Arithmetic there is no predicate that can express divisibility, else it would be as powerful 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) := P(x-1,y+1,z), P(0,x,yP(0,y,z) := (x=y) y=z) vs. P(x,y,z) := (x+y=z).
How to tell if a recursively-defined predicate has an equivalent non-recursive definition which can be expressed in Presburger Arithmetic?
|
|
|
|
|
1
|
|
|
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else it would be as powerful 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) := P(x-1,y+1,z), P(0,x,y) := (x=y) vs. P(x,y,z) := (x+y=z).
How to tell if a recursively-defined predicate has an equivalent non-recursive definition which can be expressed in Presburger Arithmetic?
|
|
|
