On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
History and Philosophy of Logic 12 (2):225-233 (1991)
Presburger's essay on the completeness and decidability of arithmetic with integer addition but without multiplication is a milestone in the history of mathematical logic and formal metatheory. The proof is constructive, using Tarski-style quantifier elimination and a four-part recursive comprehension principle for axiomatic consequence characterization. Presburger's proof for the completeness of first order arithmetic with identity and addition but without multiplication, in light of the restrictive formal metatheorems of Gödel, Church, and Rosser, takes the foundations of arithmetic in mathematical logic to the limits of completeness and decidability
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Kevin Woods (2015). Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials. Journal of Symbolic Logic 80 (2):433-449.
Similar books and articles
Françoise Point (2000). On Decidable Extensions of Presburger Arithmetic: From A. Bertrand Numeration Systems to Pisot Numbers. Journal of Symbolic Logic 65 (3):1347-1374.
M. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
Stephen Read (1997). Completeness and Categoricity: Frege, Gödel and Model Theory. History and Philosophy of Logic 18 (2):79-93.
Joseph Y. Halpern (1991). Presburger Arithmetic with Unary Predicates is Π11 Complete. Journal of Symbolic Logic 56 (2):637 - 642.
Dick Jongh, Marc Jumelet & Franco Montagna (1991). On the Proof of Solovay's Theorem. Studia Logica 50 (1):51 - 69.
Sergei Artëmov & Franco Montagna (1994). On First-Order Theories with Provability Operator. Journal of Symbolic Logic 59 (4):1139-1153.
Camilla K. Gilmore, Shannon E. McCarthy & Elizabeth S. Spelke, Symbolic Arithmetic Knowledge Without Instruction.
D. C. McCarty (1996). Undecidability and Intuitionistic Incompleteness. Journal of Philosophical Logic 25 (5):559 - 565.
Added to index2010-08-10
Total downloads25 ( #159,094 of 1,911,312 )
Recent downloads (6 months)1 ( #457,064 of 1,911,312 )
How can I increase my downloads?