Re: Completeness
Presburger Arithmetic
Peter Webb wrote:
[Axioms of Presburger Arithmetic
Versus:
[Peano Axioms]
Presburger assumes that 0 exists, assumes every number has a successor (ie
x+1 exists), there is no number that has 0 as a successor is axiom 1, (a<>b)
=> (S(a) <> S(b)) is axiom 2, and induction works the same.
(At least) one constant is necessary to define addition.
The only difference that I can see is Presbeger contains (x + y) + 1 = x +
(y + 1) and I would have thought that the equivalent was in fact a thereom
of PA.
So, what is the difference?
When defining a (first order) theory you (first) define the
sets of the nonlogical symbols, i.e. the symbols used for
functions (and constants) and predicates.
So, Presburger has 0 and 1, but no successor function. Peano
(Arithmetic) has no symbol for 1, but the successor function.
Then, you define the sentences admissible in the theory.
Presburger disallows multiplication between variables.
Only linear terms are allowed. That's the crucial point
making Presburger Arithmetic complete.
And can you give me a model for Presberger other
than the Natural numbers?
Each commutative group where you define a predicate symbol
expressing the divisibility gives a model. Details can be
found in the book on Kreisel and Krivine on Model Theory.
Thomas Kaeufl
.
