A Course on Mathematical Logic

S. M. Srivastava
Publisher:
Springer
Publication Date:
2008
Number of Pages:
140
Format:
Paperback
Series:
Universitext
Price:
49.95
ISBN:
9780387762753
Category:
Textbook
[Reviewed by
Allen Stenger
, on
07/6/2008
]
This is an introductory textbook on modern mathematical logic, aimed at upper-level undergraduates. It has no explicit mathematical prerequisites, although most of the examples are based on abstract algebra and it uses Tychonoff's theorem at one spot. It has some coverage of most areas of mathematical logic, but its focus is on Gödel's Completeness and Incompleteness Theorems.

The book suffers an absence of overview material. For example, Gödel's arithmetization of theories is obviously a key topic in this subject. There must be dozens of popular math books that explain the idea of turning statements into numbers and give a few contrived examples, but there's none of that in this book — arithmetization is just another definition (and one that's not even listed in the index).

We deal with many kinds of logical structures and it's hard for the beginners who are the audience for this book to understand their differences and their importance. The text follows a traditional Definition-Theorem-Proof style, and it's often hard to see what path we are following, The first two chapters deal with syntax and semantics of first-order logic, although we don't make much progress beyond definitions. Then we switch to propositional logic, which would more normally come before first-order logic. Then we go back to first-order logic for a while and actually prove some theorems. Finally we get to the main purpose of the book: Gödel's results.

The book is well-equipped with examples in the beginning, but these get sparser as we go on. There are lots of known examples of complete and incomplete systems and of undecidable statements, and it would have been nice to survey those here even if we can't go into their proofs.

The book also suffers from an inadequate index. Mathematical logic has a tremendous amount of specialized terminology and symbology, and much of what is defined here does not appear in the index. When you forget what a symbol or term means, your only recourse is leaf through the past pages looking for it. I'm not a logician, but I didn't have much trouble following the book on a "local" level. The trouble came when we referred back to something that had happened 20 pages ago and I had forgotten what a term meant, and couldn't find it in the index.

Allen Stenger is a math hobbyist, library propagandist, and retired computer programmer. He volunteers in his spare time at MathNerds.com, a math help site that fosters inquiry learning. His mathematical interests are number theory and classical analysis.

Preface

1 Syntax of First-Order Logic
1.1 First-Order Languages
1.2 Terms of a Language
1.3 Formulas of a Language
1.4 First-Order Theories

2 Semantics of First-Order Languages
2.1 Structures of First-Order Languages
2.2 Truth in a Structure
2.3 Model of a Theory
2.4 Embeddings and Isomorphisms

3 Propositional Logic
3.1 Syntax of Propositional Logic
3.2 Semantics of Propositional Logic
3.3 Compactness Theorem for Propositional Logic
3.4 Proof in Propositional Logic
3.5 Metatheorems in Propositional Logic
3.6 Post Tautology Theorem

4 Proof and Metatheorems in First-Order Logic
4.1 Proof in First-Order Logic
4.2 Metatheorems in First-Order Logic
4.3 Some Metatheorems in Arithmetic
4.4 Consistency and Completeness

5 Completeness Theorem and Model Theory
5.1 Completeness Theorem
5.2 Interpretations in a Theory
5.3 Extension by Definitions
5.4 Compactness Theorem and Applications
5.5 Complete Theories
5.6 Applications in Algebra

6 Recursive Functions and Arithmetization of Theories
6.1 Recursive Functions and Recursive Predicates
6.2 Semirecursive Predicates
6.3 Arithmetization of Theories
6.4 Decidable Theories

7 Incompleteness Theorems and Recursion Theory
7.1 Representability
7.2 First Incompleteness Theorem
7.3 Arithmetical Sets
7.4 Recursive Extensions of Peano Arithmetic
7.5 Second Incompleteness Theorem

References

Index

Tags: