Mathematical Logic
Published on 1. March 2011
294 pages
978-1-118-03069-1 (ISBN)
Description
A comprehensive and user-friendly guide to the use of logic inmathematical reasoning
Mathematical Logic presents a comprehensive introductionto formal methods of logic and their use as a reliable tool fordeductive reasoning. With its user-friendly approach, this booksuccessfully equips readers with the key concepts and methods forformulating valid mathematical arguments that can be used touncover truths across diverse areas of study such as mathematics,computer science, and philosophy.
The book develops the logical tools for writing proofs byguiding readers through both the established "Hilbert" style ofproof writing, as well as the "equational" style that is emergingin computer science and engineering applications. Chapters havebeen organized into the two topical areas of Boolean logic andpredicate logic. Techniques situated outside formal logic areapplied to illustrate and demonstrate significant facts regardingthe power and limitations of logic, such as:
* Logic can certify truths and only truths.
* Logic can certify all absolute truths (completeness theorems ofPost and Gödel).
* Logic cannot certify all "conditional" truths, such as thosethat are specific to the Peano arithmetic. Therefore, logic hassome serious limitations, as shown through Gödel'sincompleteness theorem.
Numerous examples and problem sets are provided throughout thetext, further facilitating readers' understanding of thecapabilities of logic to discover mathematical truths. In addition,an extensive appendix introduces Tarski semantics and proceeds withdetailed proofs of completeness and first incompleteness theorems,while also providing a self-contained introduction to the theory ofcomputability.
With its thorough scope of coverage and accessible style,Mathematical Logic is an ideal book for courses inmathematics, computer science, and philosophy at theupper-undergraduate and graduate levels. It is also a valuablereference for researchers and practitioners who wish to learn howto use logic in their everyday work.
Reviews / Votes
"Overall, he presents the material as if he were holding adialogue with the reader. An advanced independent reader with avery strong background in mathematics would find the book helpfulin learning this area of mathematics. Summing Up:Recommended." (Choice, April 2009) "The book would be ideas as an introduction to classical logicfor students of mathematics, computer science or philosophy. Due to the author's clear and approachable style, it can berecommended to a large circle of readers interested in mathematicallogic as well." (Mathematical Review, Issue 2009e) "I give this outstanding book my highest recommendation, whilstbeing grateful that excellence in the logic-book 'business' is thevery opposite of a zero-sum game: there's plenty of room at thetop." (Computing Reviews, November 5, 2008)More details
Other editions
Additional editions
Person
GEORGE TOURLAKIS, PhD, is University Professor of Computer Science and Engineering at York University, Canada. Dr. Tourlakis has authored or coauthored numerous articles in his areas of research interest, which include calculational logic, modal logic, computability, complexity theory, and arithmetical forcing.
Content
Preface.
Acknowledgments.
PART I: BOOLEAN LOGIC.
1. The Beginning.
1.1 Boolean Formulae.
1.2 Induction on the Complexity of WFF: Some Easy Properties ofWFF.
1.3 Inductive definitions on formulae.
1.4 Proofs and Theorems.
1.5 Additional Exercises.
2. Theorems and Metatheorems.
2.1 More Hilbertstyle Proofs.
2.2 Equational-style Proofs.
2.3 Equational Proof Layout.
2.4 More Proofs: Enriching our Toolbox.
2.5 Using Special Axioms in Equational Proofs.
2.6 The Deduction Theorem.
2.7 Additional Exercises.
3. The Interplay between Syntax and Semantics.
3.1 Soundness.
3.2 Post's Theorem.
3.3 Full Circle.
3.4 Single-Formula Leibniz.
3.5 Appendix: Resolution in Boolean Logic.
3.6 Additional Exercises.
PART II: PREDICATE LOGIC.
4. Extending Boolean Logic.
4.1 The First Order Language of Predicate Logic.
4.2 Axioms and Rules of First Order Logic.
4.3 Additional Exercises.
5. Two Equivalent Logics.
6. Generalization and Additional Leibniz Rules.
6.1 Inserting and Removing "(& #8704;x)".
6.2 Leibniz Rules that Affect Quantifier Scopes.
6.3 The Leibniz Rules "8.12".
6.4 More Useful Tools.
6.5 Inserting and Removing "(& #8707;x)".
6.6 Additional Exercises.
7. Properties of Equality.
8. First Order Semantics -- Very Naïvely.
8.1 Interpretations.
8.2 Soundness in Predicate Logic.
8.3 Additional Exercises.
Appendix A: Gödel's Theorems and Computability.
A.1 Revisiting Tarski Semantics.
A.2 Completeness.
A.3 A Brief Theory of Computability.
A.3.1 A Programming Framework for Computable Functions.
A.3.2 Primitive Recursive Functions.
A.3.3 URM Computations.
A.3.4 Semi-Computable Relations; Unsolvability.
A.4 Godel's First Incompleteness Theorem.
A.4.1 Supplement: & #248;x(x) " is first order definable inN.
References.
Index.
