George Tourlakis 
Mathematical Logic 

A comprehensive and user-friendly guide to the use of logic in
mathematical reasoning

Mathematical 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.

Table des matières

Preface.

Acknowledgments.

PART I: BOOLEAN LOGIC.

1. The Beginning.

1.1 Boolean Formulae.

1.2 Induction on the Complexity of WFF: Some Easy Properties of
WFF.

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 in
N.

References.

Index.

A propos de l’auteur

GEORGE TOURLAKIS, Ph D, 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.