Modern Mathematical Logic (Cambridge Mathematical Textbooks)

✍ Scribed by Joseph Mileti

• Publisher: Cambridge University Press
• Year: 2022
• Tongue: English
• Leaves: 518
• Edition: New
• Category: Library

✦ Synopsis

This textbook gives a complete and modern introduction to mathematical logic. The author uses contemporary notation, conventions, and perspectives throughout, and emphasizes interactions with the rest of mathematics. In addition to covering the basic concepts of mathematical logic and the fundamental material on completeness, compactness, and incompleteness, it devotes significant space to thorough introductions to the pillars of the modern subject: model theory, set theory, and computability. Requiring only a modest background of undergraduate mathematics, the text can be readily adapted for a variety of one- or two-semester courses at the upper-undergraduate or beginning-graduate level. Numerous examples reinforce the key ideas and illustrate their applications, and a wealth of classroom-tested exercises serve to consolidate readers' understanding. Comprehensive and engaging, this book offers a fresh approach to this enduringly fascinating and important subject.

✦ Table of Contents

Cover
Endorsement
Half-Title page
Series page
Title page
Copyright page
Contents
Preface
Acknowledgments
1 Introduction
1.1 The Nature of Mathematical Logic
1.2 The Language of Mathematics
1.3 Syntax and Semantics
1.4 The Point of It All
1.5 Terminology and Notation
2 Induction and Recursion
2.1 Induction and Recursion on N
2.2 Generation
2.3 Step Induction
2.4 Freeness and Step Recursion
2.5 An Illustrative Example
Exercises
3 Propositional Logic
3.1 The Syntax of Propositional Logic
3.2 Truth Assignments and Semantic Equivalence
3.3 Boolean Functions and Connectives
3.4 Semantic Implication and Satisfiability
3.5 Syntactic Implication and Consistency
3.6 Soundness and Completeness
3.7 Compactness and Applications
3.8 Further Reading
Exercises
4 First-Order Logic: Languages and Structures
4.1 Terms and Formulas
4.2 Structures
4.3 Introduction to Definability
4.4 Substitution
4.5 Semantic Equivalence
Exercises
5 Relationships between Structures
5.1 Elementary Classes
5.2 Substructures and Homomorphisms
5.3 Definability Revisited
5.4 Counting the Number of Models
5.5 Elementary Substructures and Elementary Embeddings
Exercises
6 Implication and Compactness
6.1 Semantic Implication and Satisfiability
6.2 Syntactic Implication and Consistency
6.3 Soundness and Completeness
6.4 Compactness and Applications
6.5 Theories
6.6 Random Graphs
Exercises
7 Model Theory
7.1 Diagrams and Embeddings
7.2 Nonstandard Models of Arithmetic and Analysis
7.3 Theories and Universal Sentences
7.4 Quantifier Elimination
7.5 Algebraically Closed Fields
Exercises
8 Axiomatic Set Theory
8.1 Motivating the Axioms
8.2 First-Order Axiomatic Set Theory
8.3 Fundamental Set Constructions
8.4 The Natural Numbers and Induction
8.5 Finite Sets, Finite Powers, and Recursion
8.6 Countable and Uncountable Sets
8.7 Models, Sets, and Classes
Exercises
9 Ordinals, Cardinals, and Choice
9.1 Well-Orderings
9.2 Ordinals
9.3 Ordinal Arithmetic
9.4 Cardinals
9.5 The Axiom of Choice
9.6 Further Reading
Exercises
10 Set-Theoretic Methods in Model Theory
10.1 The Size of Models
10.2 Ultraproducts and Compactness
10.3 Further Reading
Exercises
11 Computable Sets and Functions
11.1 Primitive Recursive Functions
11.2 Coding Sequences and Primitive Recursive Functions
11.3 Partial Recursive Functions
11.4 A Machine Model of Computation
11.5 Computability and the Church–Turing Thesis
11.6 Computably Enumerable Sets
11.7 Further Reading
Exercises
12 Logic, Computation, and Incompleteness
12.1 Coding Formulas and Deductions
12.2 Definability in Arithmetic
12.3 Incompleteness and Undecidability, Part 1
12.4 Representable Relations and Robinson Arithmetic
12.5 Incompleteness and Undecidability, Part 2
12.6 Further Reading
Exercises
Appendix: Mathematical Background
A.1 Countable Sets
A.2 Partial and Linear Orderings
A.3 Algebraic Structures
A.4 Ordered Algebraic Structures
Bibliography
List of Notation
Index