home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / logic / 1278 < prev    next >
Encoding:
Internet Message Format  |  1992-08-17  |  1.4 KB
  1. Path: sparky!uunet!usc!wupost!waikato.ac.nz!canterbury.ac.nz!math!wft
  2. Newsgroups: sci.logic
  3. Subject: Re: Presburger arithmetic axiomatization
  4. Message-ID: <1992Aug18.140716.388@csc.canterbury.ac.nz>
  5. From: wft@math.canterbury.ac.nz (Bill Taylor)
  6. Date: 18 Aug 92 14:07:16 +1200
  7. References: <1992Aug13.201939.6369@cs.sfu.ca> <Bt4J2E.Mz0@immd4.informatik.uni-erlangen.de>
  8. Distribution: world
  9. Organization: Department of Mathematics, University of Canterbury
  10. Nntp-Posting-Host: math.canterbury.ac.nz
  11. Lines: 16
  12.  
  13. (Apologies if this reference has appeared on the list already.)
  14.  
  15. There is a very readable acount of the decidability of Presburger arithmetic in
  16. chapter 21, Boolos & Jeffrey, "Computability & Logic", Cambridge U Press (1974).
  17.  
  18. They also mention the interesting result that arithmetic with successor and
  19. multiplication but *without* addition, is essentially no restriction, by the
  20. neat trick of identifying  
  21.                              a + b = c
  22.            with    (a.c)' . (b.c)' = ( (a.b)' . (c.c) )'
  23.  
  24. ------------------------------------------------------------------------------
  25.             Bill Taylor              wft@math.canterbury.ac.nz 
  26. ------------------------------------------------------------------------------
  27. Free will - the result of chaotic amplification of quantum events in the brain.
  28. ------------------------------------------------------------------------------
  29.