Mathematics TEXTBOOKS in MATHEMATICS TEXTBOOKS in MATHEMATICS I N T R O D U C T I O N T O I N T R O D U C T I O N T O MATHEMATICAL LOGIC MATHEMATICAL LOGIC MI SIXTH EDITION N A TT The new edition of this classic textbook, Introduction to Mathemati- HR cal Logic, Sixth Edition explores the principal topics of mathematical E O logic. It covers propositional logic, first-order logic, first-order number M D theory, axiomatic set theory, and the theory of computability. The text A U also discusses the major results of Gödel, Church, Kleene, Rosser, T C I and Turing. C SIXTH EDITION T A The sixth edition incorporates recent work on Gödel’s second incom- I L pleteness theorem as well as restoring an appendix on consistency O L proofs for first-order arithmetic. This appendix last appeared in the N O first edition. It is offered in the new edition for historical considerations. G The text also offers historical perspectives and many new exercises T I of varying difficulty, which motivate and lead students to an in-depth, CO practical understanding of the material. SIXTH EDITION Elliott Mendelson Mendelson K23184 www.crcpress.com I N T R O D U C T I O N T O MATHEMATICAL LOGIC SIXTH EDITION TEXTBOOKS in MATHEMATICS Series Editors: Al Boggess and Ken Rosen PUBLISHED TITLES ABSTRACT ALGEBRA: AN INQUIRY-BASED APPROACH Jonathan K. Hodge, Steven Schlicker, and Ted Sundstrom ABSTRACT ALGEBRA: AN INTERACTIVE APPROACH William Paulsen ADVANCED CALCULUS: THEORY AND PRACTICE John Srdjan Petrovic ADVANCED LINEAR ALGEBRA Nicholas Loehr ANALYSIS WITH ULTRASMALL NUMBERS Karel Hrbacek, Olivier Lessmann, and Richard O’Donovan APPLIED DIFFERENTIAL EQUATIONS: THE PRIMARY COURSE Vladimir Dobrushkin APPLYING ANALYTICS: A PRACTICAL APPROACH Evan S. Levine COMPUTATIONS OF IMPROPER REIMANN INTEGRALS Ioannis Roussos CONVEX ANALYSIS Steven G. Krantz COUNTEREXAMPLES: FROM ELEMENTARY CALCULUS TO THE BEGINNINGS OF ANALYSIS Andrei Bourchtein and Ludmila Bourchtein DIFFERENTIAL EQUATIONS: THEORY, TECHNIQUE, AND PRACTICE, SECOND EDITION Steven G. Krantz DIFFERENTIAL EQUATIONS WITH MATLAB®: EXPLORATION, APPLICATIONS, AND THEORY Mark A. McKibben and Micah D. Webster ELEMENTARY NUMBER THEORY James S. Kraft and Lawrence C. Washington ELEMENTS OF ADVANCED MATHEMATICS, THIRD EDITION Steven G. Krantz PUBLISHED TITLES CONTINUED EXPLORING LINEAR ALGEBRA: LABS AND PROJECTS WITH MATHEMATICA® Crista Arangala AN INTRODUCTION TO NUMBER THEORY WITH CRYPTOGRAPHY James Kraft and Larry Washington AN INTRODUCTION TO PARTIAL DIFFERENTIAL EQUATIONS WITH MATLAB®, SECOND EDITION Mathew Coleman INTRODUCTION TO THE CALCULUS OF VARIATIONS AND CONTROL WITH MODERN APPLICATIONS John T. Burns INTRODUCTION TO MATHEMATICAL LOGIC, SIXTH EDITION Elliott Mendelson INTRODUCTION TO MATHEMATICAL PROOFS: A TRANSITION TO ADVANCED MATHEMATICS, SECOND EDITION Charles E. Roberts, Jr. LINEAR ALGEBRA, GEOMETRY AND TRANSFORMATION Bruce Solomon THE MATHEMATICS OF GAMES: AN INTRODUCTION TO PROBABILITY David G. Taylor QUADRACTIC IRRATIONALS: AN INTRODUCTION TO CLASSICAL NUMBER THEORY Franz Holter-Koch REAL ANALYSIS AND FOUNDATIONS, THIRD EDITION Steven G. Krantz RISK ANALYSIS IN ENGINEERING AND ECONOMICS, SECOND EDITION Bilal M. Ayyub RISK MANAGEMENT AND SIMULATION Aparna Gupta TRANSFORMATIONAL PLANE GEOMETRY Ronald N. Umble and Zhigang Han TEXTBOOKS in MATHEMATICS I N T R O D U C T I O N T O MATHEMATICAL LOGIC SIXTH EDITION Elliott Mendelson Queens College Flushing, New York, USA CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2015 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20150205 International Standard Book Number-13: 978-1-4822-3778-8 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com To Arlene Contents Preface....................................................................................................................xiii Introduction............................................................................................................xv 1. The Propositional Calculus...........................................................................1 1.1. Propositional.Connectives:.Truth.Tables............................................1 1.2. Tautologies..............................................................................................6 1.3. Adequate.Sets.of.Connectives............................................................19 1.4. An.Axiom.System.for.the.Propositional.Calculus..........................27 1.5. Independence:.Many-Valued.Logics.................................................36 1.6. Other.Axiomatizations........................................................................39 2. First-Order Logic and Model Theory........................................................45 2.1. Quantifiers............................................................................................45 2.1.1. Parentheses..............................................................................48 2.2. First-Order.Languages.and.Their.Interpretations:. Satisfiability.and.Truth:.Models.........................................................53 2.3. First-Order.Theories............................................................................66 2.3.1. Logical.Axioms.......................................................................66 2.3.2. Proper.Axioms........................................................................67 2.3.3. Rules.of.Inference...................................................................67 2.4. Properties.of.First-Order.Theories....................................................69 2.5. Additional.Metatheorems.and.Derived.Rules.................................73 2.5.1. Particularization.Rule.A4......................................................74 2.5.2. Existential.Rule.E4..................................................................74 2.6. Rule.C.....................................................................................................78 2.7. Completeness.Theorems.....................................................................82 2.8. First-Order.Theories.with.Equality...................................................93 2.9. Definitions.of.New.Function.Letters.and.Individual. Constants.........................................................................................102 2.10. Prenex.Normal.Forms.......................................................................105 2.11. Isomorphism.of.Interpretations:.Categoricity.of.Theories..........111 2.12. Generalized.First-Order.Theories:.Completeness.and. Decidability.........................................................................................113 2.12.1. Mathematical.Applications.................................................117 2.13. Elementary.Equivalence:.Elementary.Extensions.........................123 2.14. Ultrapowers:.Nonstandard.Analysis..............................................128 2.14.1. Reduced.Direct.Products.....................................................131 2.14.2. Nonstandard.Analysis.........................................................136 ix