6th Edition

Introduction to Mathematical Logic

By Elliott Mendelson Copyright 2015
    514 Pages 28 B/W Illustrations
    by Chapman & Hall

    The new edition of this classic textbook, Introduction to Mathematical Logic, Sixth 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.

    The sixth edition incorporates recent work on Gödel’s second incompleteness theorem as well as restoring an appendix on consistency proofs for first-order arithmetic. This appendix last appeared in the first edition. It is offered in the new edition for historical considerations. The text also offers historical perspectives and many new exercises of varying difficulty, which motivate and lead students to an in-depth, practical understanding of the material.

    Preface

    Introduction

    The Propositional Calculus
    Propositional Connectives: Truth Tables
    Tautologies
    Adequate Sets of Connectives
    An Axiom System for the Propositional Calculus
    Independence: Many-Valued Logics
    Other Axiomatizations

    First-Order Logic and Model Theory

    Quantifiers
    First-Order Languages and Their Interpretations: Satisfiability and Truth Models
    First-Order Theories
    Properties of First-Order Theories
    Additional Metatheorems and Derived Rules
    Rule C
    Completeness Theorems
    First-Order Theories with Equality
    Definitions of New Function Letters and Individual Constants
    Prenex Normal Forms
    Isomorphism of Interpretations: Categoricity of Theories
    Generalized First-Order Theories: Completeness and Decidability
    Elementary Equivalence: Elementary Extensions
    Ultrapowers: Nonstandard Analysis
    Semantic Trees
    Quantification Theory Allowing Empty Domains

    Formal Number Theory
    An Axiom System
    Number-Theoretic Functions and Relations
    Primitive Recursive and Recursive Functions
    Arithmetization: Gödel Numbers
    The Fixed-Point Theorem: Gödel’s Incompleteness Theorem
    Recursive Undecidability: Church’s Theorem
    Nonstandard Models

    Axiomatic Set Theory

    An Axiom System
    Ordinal Numbers
    Equinumerosity: Finite and Denumerable Sets
    Hartogs’ Theorem: Initial Ordinals—Ordinal Arithmetic
    The Axiom of Choice: The Axiom of Regularity
    Other Axiomatizations of Set Theory

    Computability

    Algorithms: Turing Machines
    Diagrams
    Partial Recursive Functions: Unsolvable Problems
    The Kleene–Mostowski Hierarchy: Recursively Enumerable Sets
    Other Notions of Computability
    Decision Problems

    Appendix A: Second-Order Logic

    Appendix B: First Steps in Modal Propositional Logic

    Appendix C: A Consistency Proof for Formal Number Theory

    Answers to Selected Exercises

    Bibliography

    Notations

    Index

    Biography

    Elliott Mendelson is professor emeritus at Queens College in Flushing, New York, USA. Dr. Mendelson obtained his bachelor's degree at Columbia University and his master's and doctoral degrees at Cornell University, and was elected afterward to the Harvard Society of Fellows. In addition to his other writings, he is the author of another CRC Press book Introducing Game Theory and Its Applications. 

    Praise for the Fifth Edition
    "Since it first appeared in 1964, Mendelson’s book has been recognized as an excellent textbook in the field. It is one of the most frequently mentioned texts in references and recommended reading lists … This book rightfully belongs in the small, elite set of superb books that every computer science graduate, graduate student, scientist, and teacher should be familiar with."
    Computing Reviews, May 2010

    "The following are the significant changes in this edition: A new section (3.7) on the order type of a countable nonstandard model of arithmetic; a second appendix, Appendix B, on basic modal logic, in particular on the normal modal logics K, T, S4, and S5 and the relevant Kripke semantics for each; an expanded bibliography and additions to both the exercises and to the Answers to Selected Exercises, including corrections to the previous version of the latter."
    —J.M. Plotkin, Zentralblatt MATH 1173

    "Since its first edition, this fine book has been a text of choice for a beginner’s course on mathematical logic. … There are many fine books on mathematical logic, but Mendelson’s textbook remains a sure choice for a first course for its clear explanations and organization: definitions, examples and results fit together in a harmonic way, making the book a pleasure to read. The book is especially suitable for self-study, with a wealth of exercises to test the reader’s understanding."
    MAA Reviews, December 2009