Mathematical Logic (eBook)

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.

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.

"Overall, he presents the material as if he were holding a
dialogue with the reader. An advanced independent reader with a
very strong background in mathematics would find the book helpful
in learning this area of mathematics. Summing Up:
Recommended." (Choice, April 2009)

"The book would be ideas as an introduction to classical logic
for students of mathematics, computer science or philosophy.
Due to the author's clear and approachable style, it can be
recommended to a large circle of readers interested in mathematical
logic as well." (Mathematical Review, Issue 2009e)

"I give this outstanding book my highest recommendation, whilst
being grateful that excellence in the logic-book 'business' is the
very opposite of a zero-sum game: there's plenty of room at the
top." (Computing Reviews, November 5, 2008)