home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / logic / 1274 < prev    next >
Encoding:
Internet Message Format  |  1992-08-16  |  1.3 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!Sirius.dfn.de!fauern!fauna!cip.informatik.uni-erlangen.de!jnjohann
  2. From: jnjohann@cip.informatik.uni-erlangen.de (Jan Johannsen)
  3. Newsgroups: sci.logic
  4. Subject: Re: Presburger arithmetic axiomatization
  5. Message-ID: <Bt4J2E.Mz0@immd4.informatik.uni-erlangen.de>
  6. Date: 17 Aug 92 10:42:14 GMT
  7. References: <1992Aug13.201939.6369@cs.sfu.ca>
  8. Sender: news@immd4.informatik.uni-erlangen.de
  9. Organization: CSD., University of Erlangen
  10. Lines: 31
  11.  
  12. jamie@cs.sfu.ca (Jamie Andrews) writes:
  13.  
  14. >     Where can I expect to find easily a precise and elegant
  15. >axiomatization of Presburger arithmetic?  (I know it's
  16. >"arithmetic without multiplication" and I can think of some
  17. >horrible axiomatizations; I wanted to find a nice one.)
  18.  
  19. In ZML 12 (1966), pp. 131 - 168, H. Apelt gives the following
  20. axiom system for Presburger Arithmetic:
  21.  
  22.   a+b = b+a
  23.   a+(b+c) = (a+b)+c
  24.   \exists b  ( a+b = c  \or  c+b = a )
  25.   c+a = c+b \to a=b
  26.   a+b = 1 \to ( a=1 \or b=1 )
  27.   a+b = 0 \to b=0
  28.   \not 0=1
  29.  
  30. plus the schema
  31.  
  32.  \exists b ( b+...+b = a \or b+...+b+1 = a \or ... \or b+...+b+1+...+1 = a )
  33.                p b's          p b's                     p b's  p-1 1's
  34.  
  35. for every prime number p.
  36.  
  37. >thanks
  38. >--Jamie.
  39.  
  40. No matter
  41.  
  42. Jan Johannsen   jnjohann@immd1.informatik.uni-erlangen.de
  43.