Retaining all the key features of the previous editions, Introduction to Mathematical Logic, Fifth Edition explores the principal topics of mathematical logic. It covers propositional logic, first-order logic, first-order number theory, axiomatic set theory, and the theory of computability. The text also discusses the major results of Gödel, Church, Kleene, Rosser, and Turing.
New to the Fifth Edition
- A new section covering basic ideas and results about nonstandard models of number theory
- A second appendix that introduces modal propositional logic
- An expanded bibliography
- Additional exercises and selected answers
This long-established text continues to expose students to natural proofs and set-theoretic methods. Only requiring some experience in abstract mathematical thinking, it offers enough material for either a one- or two-semester course on mathematical logic.
Author(s): Mendelson, Elliott
Series: Discrete Mathematics and Its Applications
Edition: 5
Publisher: Chapman and Hall/CRC
Year: 2010
Language: English
Pages: 469
Tags: Математика;Математическая логика;
Front Cover......Page 1
Title Page......Page 6
Contents......Page 10
Preface......Page 14
Introduction......Page 16
1.1 Propositional Connectives. Truth Tables......Page 26
1.2 Tautologies......Page 30
1.3 Adequate Sets of Connectives......Page 43
1.4 An Axiom System for the Propositional Calculus......Page 49
1.5 Independence. Many-Valued Logics......Page 59
1.6 Other Axiomatizations......Page 62
2.1 Quantifiers......Page 66
2.2 First-Order Languages and Their Interpretations. Satisfiability and Truth. Models......Page 73
2.3 First-Order Theories......Page 86
2.4 Properties of First-Order Theories......Page 89
2.5 Additional Metatheorems and Derived Rules......Page 94
2.6 Rule C......Page 98
2.7 Completeness Theorems......Page 102
2.8 First-Order Theories with Equality......Page 113
2.9 Definitions of New Function Letters and Individual Constants......Page 122
2.10 Prenex Normal Forms......Page 125
2.11 Isomorphism of Interpretations. Categoricity of Theories......Page 130
2.12 Generalized First-Order Theories. Completeness and Decidability......Page 132
2.13 Elementary Equivalence. Elementary Extensions......Page 142
2.14 Ultrapowers. Nonstandard Analysis......Page 148
2.15 Semantic Trees......Page 160
2.16 Quantification Theory Allowing Empty Domains......Page 166
3.1 An Axiom System......Page 174
3.2 Number-Theoretic Functions and Relations......Page 191
3.3 Primitive Recursive and Recursive Functions......Page 196
3.4 Arithmetization. Gödel Numbers......Page 213
3.5 The Fixed-Point Theorem. Gödel’s Incompleteness Theorem......Page 227
3.6 Recursive Undecidability. Church’s Theorem......Page 239
3.7 Nonstandard Models......Page 249
4.1 An Axiom System......Page 252
4.2 Ordinal Numbers......Page 267
4.3 Equinumerosity. Finite and Denumerable Sets......Page 281
4.4 Hartogs’ Theorem. Initial Ordinals. Ordinal Arithmetic......Page 291
4.5 The Axiom of Choice. The Axiom of Regularity......Page 304
4.6 Other Axiomatizations of Set Theory......Page 315
5.1 Algorithms. Turing Machines......Page 334
5.2 Diagrams......Page 340
5.3 Partial Recursive Functions. Unsolvable Problems......Page 347
5.4 The Kleene–Mostowski Hierarchy. Recursively Enumerable Sets......Page 363
5.5 Other Notions of Computability......Page 375
5.6 Decision Problems......Page 393
Appendix A: Second-Order Logic......Page 400
Appendix B: First Steps in Modal Propositional Logic......Page 416
Answers to Selected Exercises......Page 428
Bibliography......Page 458
Notation......Page 472
Index......Page 478
Back cover......Page 496
