🚀 go-pugleaf

In article <1992Aug13.201939.6369@cs.sfu.ca>, jamie@cs.sfu.ca (Jamie Andrews) writes:
>      Where can I expect to find easily a precise and elegant
> axiomatization of Presburger arithmetic?  (I know it's
> "arithmetic without multiplication" and I can think of some
> horrible axiomatizations; I wanted to find a nice one.)
> 
> thanks
> --Jamie.

Should we be saying 'Bratislava arithmetic' now ?!
-- 
Murray A. Jorgensen [ maj@waikato.ac.nz ]    University of Waikato
Department of Mathematics and Statistics     Hamilton, New Zealand      
__________________________________________________________________
'Tis the song of the Jubjub! the proof is complete,
if only I've stated it thrice.'

jamie@cs.sfu.ca (Jamie Andrews) writes:

>     Where can I expect to find easily a precise and elegant
>axiomatization of Presburger arithmetic?  (I know it's
>"arithmetic without multiplication" and I can think of some
>horrible axiomatizations; I wanted to find a nice one.)

In ZML 12 (1966), pp. 131 - 168, H. Apelt gives the following
axiom system for Presburger Arithmetic:

  a+b = b+a
  a+(b+c) = (a+b)+c
  \exists b  ( a+b = c  \or  c+b = a )
  c+a = c+b \to a=b
  a+b = 1 \to ( a=1 \or b=1 )
  a+b = 0 \to b=0
  \not 0=1

plus the schema

 \exists b ( b+...+b = a \or b+...+b+1 = a \or ... \or b+...+b+1+...+1 = a )
               p b's          p b's                     p b's  p-1 1's

for every prime number p.

>thanks
>--Jamie.

No matter

Jan Johannsen   jnjohann@immd1.informatik.uni-erlangen.de

In article <1992Aug16.175540.10118@waikato.ac.nz> maj@waikato.ac.nz writes:
>Should we be saying 'Bratislava arithmetic' now ?!

     Only if the Presburger family retroactively Slovakized
their name...  :-)

     By the way, thanks to all for the suggestions.  I was
thinking erroneously that standard Presburger arithmetic had
negative numbers, which it doesn't.  That makes things easier,
and in the restricted context in which I want to use it, I
think it turns out that I can just use the Peano axioms plus
those for addition and claim to be doing Presburger arithmetic.

--Jamie.
  jamie@cs.sfu.ca
"Every \item command in item_list must have an optional argument." LaTeX pg.168

(Apologies if this reference has appeared on the list already.)

There is a very readable acount of the decidability of Presburger arithmetic in
chapter 21, Boolos & Jeffrey, "Computability & Logic", Cambridge U Press (1974).

They also mention the interesting result that arithmetic with successor and
multiplication but *without* addition, is essentially no restriction, by the
neat trick of identifying  
                             a + b = c
           with    (a.c)' . (b.c)' = ( (a.b)' . (c.c) )'

------------------------------------------------------------------------------
            Bill Taylor              wft@math.canterbury.ac.nz 
------------------------------------------------------------------------------
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------