Author(s): Christopher Leary and Lars Kristiansen
At the intersection of mathematics, computer science, and philosophy, mathematical logic examines the power and limitations of formal mathematical thinking. In this expansion of Leary’s user-friendly 1st edition, readers with no previous study in the field are introduced to the basics of model theory, proof theory, and computability theory. The text is designed to be used either in an upper division undergraduate classroom, or for self study. Updating the 1st Edition’s treatment of languages, structures, and deductions, leading to rigorous proofs of Gödel’s First and Second Incompleteness Theorems, the expanded 2nd Edition includes a new introduction to incompleteness through computability as well as solutions to selected exercises. Available on Lulu.com, IndiBound.com, and Amazon.com, as well as wholesale through Ingram Content Group.
A Friendly Introduction to Mathematical Logic
PDF 2MB
Preface
1 Structures and Languages
1.1 Naïvely
1.2 Languages
1.2.1 Exercises
1.3 Terms and Formulas
1.3.1 Exercises
1.4 Induction
1.4.1 Exercises
1.5 Sentences
1.5.1 Exercises
1.6 Structures
1.6.1 Exercises
1.7 Truth in a Structure
1.7.1 Exercises
1.8 Substitutions and Substitutability
1.8.1 Exercises
1.9 Logical Implication
1.9.1 Exercises
1.10 Summing Up, Looking Ahead
2 Deductions
2.1 Naïvely
2.2 Deductions
2.2.1 Exercises
2.3 The Logical Axioms
2.3.1 Equality Axioms
2.3.2 Quanti er Axioms
2.3.3 Recap
2.4 Rules of Inference
2.4.1 Propositional Consequence
2.4.2 Quanti er Rules
2.4.3 Exercises
2.5 Soundness
2.5.1 Exercises
2.6 Two Technical Lemmas
2.7 Properties of Our Deductive System
2.7.1 Exercises
2.8 Nonlogical Axioms
2.8.1 Exercises
2.9 Summing Up, Looking Ahead
3 Completeness and Compactness
3.1 Naïvely
3.2 Completeness
3.2.1 Exercises
3.3 Compactness
3.3.1 Exercises
3.4 Substructures and the Löwenheim-Skolem Theorems
3.4.1 Exercises
3.5 Summing Up, Looking Ahead
4 Incompleteness from Two Points of View
4.1 Introduction
4.2 Complexity of Formulas
4.2.1 Exercises
4.3 The Roadmap to Incompleteness
4.4 An Alternate Route
4.5 How to Code a Sequence of Numbers
4.5.1 Exercises
4.6 An Old Friend
4.7 Summing Up, Looking Ahead
5 Syntactic Incompleteness—Groundwork
5.1 Introduction
5.2 The Language, the Structure, and the Axioms of N
5.2.1 Exercises
5.3 Representable Sets and Functions
5.3.1 Exercises
5.4 Representable Functions and Computer Programs
5.4.1 Exercises
5.5 Coding—Naïvely
5.5.1 Exercises
5.6 Coding Is Representable
5.6.1 Exercise
5.7 Godel Numbering
5.7.1 Exercises
5.8 Godel Numbers and N
5.8.1 Exercises
5.9 Num and Sub Are Representable
5.9.1 Exercises
5.10 Defi nitions by Recursion Are Representable
5.10.1 Exercises
5.11 The Collection of Axioms Is Representable
5.11.1 Exercise
5.12 Coding Deductions
5.12.1 Exercises
5.13 Summing Up, Looking Ahead
6 The Incompleteness Theorems
6.1 Introduction
6.2 The Self-Reference Lemma
6.2.1 Exercises
6.3 The First Incompleteness Theorem
6.3.1 Exercises
6.4 Extensions and Re nements of Incompleteness
6.4.1 Exercises
6.5 Another Proof of Incompleteness
6.5.1 Exercises
6.6 Peano Arithmetic and the Second Incompleteness Theorem
6.6.1 Exercises
6.7 Summing Up, Looking Ahead
7 Computability Theory
7.1 The Origin of Computability Theory
7.2 The Basics
7.3 Primitive Recursion
7.3.1 Exercises
7.4 Computable Functions and Computable Indices
7.4.1 Exercises
7.5 The Proof of Kleene’s Normal Form Theorem
7.5.1 Exercises
7.6 Semi-Computable and Computably Enumerable Sets
7.6.1 Exercises
7.7 Applications to First-Order Logic
7.7.1 The Entscheidungsproblem
7.7.2 Gödel’s First Incompleteness Theorem
7.7.3 Exercises
7.8 More on Undecidability
7.8.1 Exercises
8 Summing Up, Looking Ahead
8.1 Once More, With Feeling
8.2 The Language LBT and the Structure B
8.3 Nonstandard LBT-structures
8.4 The Axioms of B
8.5 B extended with an induction scheme
8.6 Incompleteness
8.7 O ff You Go
Appendix: Just Enough Set Theory to Be Dangerous
Solutions to Selected Exercises
Bibliography
License: