A Concise Introduction to Mathematical Logic

by Wolfgang Rautenberg

Overview

Traditional logic as a part of philosophy is one of the oldest scientific disciplines and can be traced back to the Stoics and to Aristotle. Mathematical logic, however, is a relatively young discipline and arose from the endeavors of Peano, Frege, and others to create a logistic foundation for mathematics. It steadily developed during the twentieth century into a broad discipline with several sub-areas and numerous applications in mathematics, informatics, linguistics and philosophy.

This book treats the most important material in a concise and streamlined fashion. The third edition is a thorough and expanded revision of the former. Although the book is intended for use as a graduate text, the first three chapters can easily be read by undergraduates interested in mathematical logic. These initial chapters cover the material for an introductory course on mathematical logic, combined with applications of formalization techniques to set theory. Chapter 3 is partly of descriptive nature, providing a view towards algorithmic decision problems, automated theorem proving, non-standard models including non-standard analysis, and related topics.

The remaining chapters contain basic material on logic programming for logicians and computer scientists, model theory, recursion theory, Gödel’s Incompleteness Theorems, and applications of mathematical logic. Philosophical and foundational problems of mathematics are discussed throughout the text. Each section of the seven chapters ends with exercises some of which of importance for the text itself. There are hints to most of the exercises in a separate file Solution Hints to the Exercises which is not part of the book but is available from the author’s website.

Product Details

ISBN-13:	9781441912206
Publisher:	Springer New York
Publication date:	12/17/2009
Series:	Universitext
Edition description:	3rd ed. 2010
Pages:	320
Product dimensions:	6.60(w) x 9.40(h) x 0.90(d)

Table of Contents

Introduction xv

Notation xix

1 Propositions Logic 1

1.1 Boolean Functions and Formulas 2

1.2 Semantic Equivalence and Normal Forms 11

1.3 Tautologies and Logical Consequence 17

1.4 A Calculus of Natural Deduction 22

1.5 Applications of the Compactness Theorem 30

1.6 Hilbert Calculi 35

2 First-Order Logic 41

2.1 Mathematical Structures 42

2.2 Syntax of First-Order Languages 53

2.3 Semantics of First-Order Languages 61

2.4 General Validity and Logical Equivalence 73

2.5 Logical Consequence and Theories 78

2.6 Explicit Definitions—Language Expansions 85

3 Complete Logical Calculi 91

3.1 A Calculus of Natural Deduction 92

3.2 The Completeness Proof 97

3.3 First Applications: Nonstandard Models 103

3.4 ZFC and Skolem's Paradox 111

3.5 Enumerability and Decidability 117

3.6 Complete Hilbert Calculi 121

3.7 First-Order Fragments 126

3.8 Extensions of First-Order Languages 129

4 Foundations of Logic Programming 135

4.1 Term Models and Herbrand's Theorem 136

4.2 Horn Formulas 140

4.3 Prepositional Resolution 143

4.4 Horn Resolution 149

4.5 Unification 152

4.6 Logic Programming 156

4.7 A Proof of the Main Theorem 66

5 Elements of Model Theory 169

5.1 Elementary Extensions 170

5.2 Complete and k-Categorical Theories 176

5.3 The Ehrenfeucht Game 183

5.4 Embedding and Characterization Theorems 186

5.5 Model Completeness 194

5.6 Quantifier Elimination 202

5.7 Reduced Products and Ultraproducts 209

6 Incompleteness and Undecidability 215

6.1 Recursive and Primitive Recursive Functions 217

6.2 Arithmetization 226

6.3 RepresentabiUty of Arithmetical Predicates 234

6.4 The Representability Theorem 243

6.5 The Theorems of Gödel, Tarski, Church 250

6.6 Transfer by Interpretation 258

6.7 The Arithmetical Hierarchy 264

7 On the Theory of Self-Reference 269

7.1 The Derivability Conditions 270

7.2 The Provable σ1-Completeness 277

7.3 The Theorems of Gödel and Löb 279

7.4 The Provability Logic G 284

7.5 The Modal Treatment of Self-Reference 287

7.6 A Bimodal Provability Logic for PA 291

7.7 Modal Operators in ZFC 294

Bibliography 299

Index of Terms and Names 307

Index of Symbols 317

Editorial Reviews

From the reviews of the third edition:

“Wolfgang Rautenberg’s A Concise Introduction to Mathematical Logic is a pretty ambitious undertaking, seeing that at the indicated introductory level it covers ‘classical material … and Godel’s incompleteness theorems, as well as some topics motivated by applications, such as chapter on logic programming’ (from the Foreword by Lev Beklemishev). … The third edition … is a fine piece of scholarship and will more than repay the efforts of the committed student who chooses this means as an entry into modern mathematical logic.” (Michael Berg, The Mathematical Association of America, June, 2010)

“This is essentially the English translation of the third edition of the German version [Einführung in die mathematische Logik. Ein Lehrbuch. Wiesbaden: Vieweg+Teubner (2008; Zb1 1152.03-002)] of this well-written textbook … . The book remains one of the most recommendable introductions into mathematical logic for mathematicians, and well-suited for computer scientists too.” (Siegfried J. Gottwald, Zentralblatt MATH, Vol. 1185, 2010)

From the Publisher