A comprehensive and user-friendly guide to the use of logic in mathematical reasoningMathematical Logic presents a comprehensive introduction to formal methods of logic and their use as a reliable tool for deductive reasoning. With its user-friendly approach, this book successfully equips readers with the key concepts and methods for formulating valid mathematical arguments that can be used to uncover truths across diverse areas of study such as mathematics, computer science, and philosophy.The book develops the logical tools for writing proofs by guiding readers through both the established "Hilbert" style of proof writing, as well as the "equational" style that is emerging in computer science and engineering applications. Chapters have been organized into the two topical areas of Boolean logic and predicate logic. Techniques situated outside formal logic are applied to illustrate and demonstrate significant facts regarding the power and limitations of logic, such as:Logic can certify truths and only truths.Logic can certify all absolute truths (completeness theorems of Post and G?del).Logic cannot certify all "conditional" truths, such as those that are specific to the Peano arithmetic. Therefore, logic has some serious limitations, as shown through G?del's incompleteness theorem.Numerous examples and problem sets are provided throughout the text, further facilitating readers' understanding of the capabilities of logic to discover mathematical truths. In addition, an extensive appendix introduces Tarski semantics and proceeds with detailed proofs of completeness and first incompleteness theorems, while also providing a self-contained introduction to the theory of computability.With its thorough scope of coverage and accessible style, Mathematical Logic is an ideal book for courses in mathematics, computer science, and philosophy at the upper-undergraduate and graduate levels. It is also a valuable reference for researchers and practitioners who wish to learn how to use logic in their everyday work.
Author(s): George Tourlakis
Edition: 1
Publisher: Wiley
Year: 2008
Language: English
Pages: 293
Tags: Математика;Математическая логика;
Mathematical Logic......Page 6
Contents......Page 10
Preface......Page 14
Acknowledgments......Page 20
PART I BOOLEAN LOGIC......Page 22
1 The Beginning......Page 24
1.1 Boolean Formulae......Page 29
1.2 Induction on the Complexity of WFF: Some Easy Properties of WFF......Page 38
1.3 Inductive Definitions on Formulae......Page 43
1.4 Proofs and Theorems......Page 58
1.5 Additional Exercises......Page 69
2.1 More Hilbert-Style Proofs......Page 72
2.2 Equational-Style Proofs......Page 81
2.3 Equational Proof Layout......Page 84
2.4 More Proofs: Enriching Our Toolbox......Page 87
2.5 Using Special Axioms in Equational Proofs......Page 97
2.6 The Deduction Theorem......Page 102
2.7 Additional Exercises......Page 107
3 The Interplay between Syntax and Semantics......Page 110
3.1 Soundness......Page 111
3.2 Post's Theorem......Page 114
3.3 Full Circle......Page 120
3.4 Single-Formula Leibniz......Page 121
3.5 Appendix: Resolution in Boolean Logic......Page 125
3.6 Additional Exercises......Page 128
PART II PREDICATE LOGIC......Page 132
4 Extending Boolean Logic......Page 134
4.1 The First-Order Language of Predicate Logic......Page 136
4.2 Axioms and Rules of First-Order Logic......Page 159
4.3 Additional Exercises......Page 169
5 Two Equivalent Logics......Page 172
6.1 Inserting and Removing "(forallx)"......Page 176
6.2 Leibniz Rules that Affect Quantifier Scopes......Page 186
6.3 The Leibniz Rules "8.12"......Page 189
6.4 Additional Useful Tools......Page 191
6.5 Inserting and Removing "(existsx)"......Page 199
6.6 Additional Exercises......Page 208
7 Properties of Equality......Page 212
8 First-Order Semantics—Very Naïvely......Page 216
8.1 Interpretations......Page 217
8.2 Soundness in Predicate Logic......Page 222
8.3 Additional Exercises......Page 229
Appendix A: Gödel's Theorems and Computability......Page 232
A.1 Revisiting Tarski Semantics......Page 233
A.2 Completeness......Page 244
A.3 A Brief Theory of Computability......Page 253
A.3.1 A Programming Framework for Computable Functions......Page 254
A.3.2 Primitive Recursive Functions......Page 264
A.3.3 URM Computations......Page 275
A.3.4 Semi-computable Relations; Unsolvability......Page 280
A.4 Gödel's First Incompleteness Theorem......Page 284
A.4.1 Supplement: smallphix(x) aero Is First-Order Definable in smalleta......Page 296
References......Page 302
Index......Page 306
