Logical number theory - I : An introduction

Includes index

I. Arithmetic Encoding 1. Polynomials 2. Sums of Powers 3. The Cantor Pairing function 4. The Fueter-Pólya Theorem, I *5. The Fueter-Pólya Theorem, II 6. The Chinese Remainder Theorem 7. The ?-Function and Other Encoding Schemes 8. Primitive Recursion *9. Ackermann Functions 10. Arithmetic Relations 11. Computability 12. Elementary Recursion Theory 13. The Arithmetic Hierarchy 14. Reading List II. Diophantine Encoding 1. Diophantine Equations; Some Background 2. Initial Results; The Davis-Putnam-Robinson Theorem 3. The Pell Equation, I 4. The Pell Equation, II 5. The Diophantine Nature of R.E. Relations 6. Applications 7. Forms *8. Binomial Coëfficients *9. A Direct Proof of the Davis-Putnam-Robinson Theorem *10. The 3-Variable Exponential Diophantine Result 11. Reading List III. Weak Formal Theories of Arithmetic 1. Ignorabimus? 2. Formal Language and Logic 3. The Completeness Theorem 4. Presburger-Skolem Arithmetic; The Theory of Addition *5. Skolem Arithmetic; The Theory of Multiplication 6. Theories with + and ?; Incompleteness and Undecidability 7. Semi-Repiesentability of Functions 8. Further Undecidability Results 9. Reading List.

This first volume can stand on its own as a somewhat unorthodox introduction to mathematical logic for undergraduates, dealing with the usual introductory material: recursion theory, first-order logic, completeness, incompleteness, and undecidability.