tailieunhanh - A Problem Course in Mathematical Logic Version 1.6 Stefan Bilaniuk

Copyright c 1994-2003 Stefan Bilaniuk. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled “GNU Free Documentation License”. | A Problem Course in Mathematical Logic Version Stefan Bilaniuk Department of Mathematics Trent UNivERSiTy Peterborough Ontario Canada K9J 7B8 E-mail address sbilaniuk@ 1991 Mathematics Subject Classification. 03 Key words and phrases. logic computability incompleteness Abstract. This is a text for a problem-oriented course on mathematical logic and computability. Copyright 1994-2003 Stefan Bilaniuk. Permission is granted to copy distribute and or modify this document under the terms of the GNU Free Documentation License Version or any later version published by the Free Software Foundation with no Invariant Sections no Front-Cover Texts and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License . This work was typeset with lATpX using the Ạ S-IATpX and Ạ. óToiits packages of the American Mathematical Society. Contents Preface v Introduction ix Part I. Propositional Logic 1 Chapter 1. Language 3 Chapter 2. Truth Assignments 7 Chapter 3. Deductions 11 Chapter 4. Soundness and Completeness 15 Hints for Chapters 1-4 17 Part II. First-Order Logic 21 Chapter 5. Languages 23 Chapter 6. Structures and Models 33 Chapter 7. Deductions 41 Chapter 8. Soundness and Completeness 47 Chapter 9. Applications of Compactness 53 Hints for Chapters 5-9 59 Part III. Computability 65 Chapter 10. Turing Machines 67 Chapter 11. Variations and Simulations 75 Chapter 12. Computable and Non-Computable Functions 81 Chapter 13. Recursive Functions 87 Chapter 14. Characterizing Computability 95 .