Article View: sci.logic
Article #207Re: Presburger arithmetic axiomatization
From: Bill Taylor
Date: Tue, 18 Aug 1992 02:07
Date: Tue, 18 Aug 1992 02:07
16 lines
1419 bytes
1419 bytes
(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.
------------------------------------------------------------------------------
Technical Details
Message-ID:
<1992Aug18.140716.388@csc.canterbury.ac.nz>Path:
arc1-ca.pugleaf.net!sparky!uunet!usc!wupost!waikato.ac.nz!canterbury.ac.nz!math!wftReferences:
<1992Aug13.201939.6369@cs.sfu.ca> <Bt4J2E.Mz0@immd4.informatik.uni-erlangen.de>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!usc!wupost!waikato.ac.nz!canterbury.ac.nz!math!wft Newsgroups: sci.logic Subject: Re: Presburger arithmetic axiomatization Message-ID: <1992Aug18.140716.388@csc.canterbury.ac.nz> From: wft@math.canterbury.ac.nz (Bill Taylor) Date: 18 Aug 92 14:07:16 +1200 References: <1992Aug13.201939.6369@cs.sfu.ca> <Bt4J2E.Mz0@immd4.informatik.uni-erlangen.de> Distribution: world Organization: Department of Mathematics, University of Canterbury Nntp-Posting-Host: math.canterbury.ac.nz Lines: 16