SUNY Community

A Friendly Introduction to Mathematical Logic

Author(s): and

At the intersection of mathematics, computer science, and philosophy, mathematical logic examines the power and limitations of formal mathematical thinking. In this expansion of Leary’s user-friendly 1st edition, readers with no previous study in the field are introduced to the basics of model theory, proof theory, and computability theory. The text is designed to be used either in an upper division undergraduate classroom, or for self study. Updating the 1st Edition’s treatment of languages, structures, and deductions, leading to rigorous proofs of Gödel’s First and Second Incompleteness Theorems, the expanded 2nd Edition includes a new introduction to incompleteness through computability as well as solutions to selected exercises. Available on Lulu.comIndiBound.com, and Amazon.com, as well as wholesale through Ingram Content Group.

Facebooktwittergoogle_plusredditlinkedintumblrmail


Preface

1 Structures and Languages

1.1 Naïvely

1.2 Languages

1.2.1 Exercises

1.3 Terms and Formulas

1.3.1 Exercises

1.4 Induction

1.4.1 Exercises

1.5 Sentences

1.5.1 Exercises

1.6 Structures

1.6.1 Exercises

1.7 Truth in a Structure

1.7.1 Exercises

1.8 Substitutions and Substitutability

1.8.1 Exercises

1.9 Logical Implication

1.9.1 Exercises

1.10 Summing Up, Looking Ahead

2 Deductions

2.1 Naïvely

2.2 Deductions

2.2.1 Exercises

2.3 The Logical Axioms

2.3.1 Equality Axioms

2.3.2 Quanti er Axioms

2.3.3 Recap

2.4 Rules of Inference

2.4.1 Propositional Consequence

2.4.2 Quanti er Rules

2.4.3 Exercises

2.5 Soundness

2.5.1 Exercises

2.6 Two Technical Lemmas

2.7 Properties of Our Deductive System

2.7.1 Exercises

2.8 Nonlogical Axioms

2.8.1 Exercises

2.9 Summing Up, Looking Ahead

3 Completeness and Compactness

3.1 Naïvely

3.2 Completeness

3.2.1 Exercises

3.3 Compactness

3.3.1 Exercises

3.4 Substructures and the Löwenheim-Skolem Theorems

3.4.1 Exercises

3.5 Summing Up, Looking Ahead

4 Incompleteness from Two Points of View

4.1 Introduction

4.2 Complexity of Formulas

4.2.1 Exercises

4.3 The Roadmap to Incompleteness

4.4 An Alternate Route

4.5 How to Code a Sequence of Numbers

4.5.1 Exercises

4.6 An Old Friend

4.7 Summing Up, Looking Ahead

5 Syntactic Incompleteness—Groundwork

5.1 Introduction

5.2 The Language, the Structure, and the Axioms of N

5.2.1 Exercises

5.3 Representable Sets and Functions

5.3.1 Exercises

5.4 Representable Functions and Computer Programs

5.4.1 Exercises

5.5 Coding—Naïvely

5.5.1 Exercises

5.6 Coding Is Representable

5.6.1 Exercise

5.7 Godel Numbering

5.7.1 Exercises

5.8 Godel Numbers and N

5.8.1 Exercises

5.9 Num and Sub Are Representable

5.9.1 Exercises

5.10 Defi nitions by Recursion Are Representable

5.10.1 Exercises

5.11 The Collection of Axioms Is Representable

5.11.1 Exercise

5.12 Coding Deductions

5.12.1 Exercises

5.13 Summing Up, Looking Ahead

6 The Incompleteness Theorems

6.1 Introduction

6.2 The Self-Reference Lemma

6.2.1 Exercises

6.3 The First Incompleteness Theorem

6.3.1 Exercises

6.4 Extensions and Re nements of Incompleteness

6.4.1 Exercises

6.5 Another Proof of Incompleteness

6.5.1 Exercises

6.6 Peano Arithmetic and the Second Incompleteness Theorem

6.6.1 Exercises

6.7 Summing Up, Looking Ahead

7 Computability Theory

7.1 The Origin of Computability Theory

7.2 The Basics

7.3 Primitive Recursion

7.3.1 Exercises

7.4 Computable Functions and Computable Indices

7.4.1 Exercises

7.5 The Proof of Kleene’s Normal Form Theorem

7.5.1 Exercises

7.6 Semi-Computable and Computably Enumerable Sets

7.6.1 Exercises

7.7 Applications to First-Order Logic

7.7.1 The Entscheidungsproblem

7.7.2 Gödel’s First Incompleteness Theorem

7.7.3 Exercises

7.8 More on Undecidability

7.8.1 Exercises

8 Summing Up, Looking Ahead

8.1 Once More, With Feeling

8.2 The Language LBT and the Structure B

8.3 Nonstandard LBT-structures

8.4 The Axioms of B

8.5 B extended with an induction scheme

8.6 Incompleteness

8.7 O ff You Go

Appendix: Just Enough Set Theory to Be Dangerous

Solutions to Selected Exercises

Bibliography



Christopher Leary

Chris Leary, from Homewood, Illinois, was educated at Oberlin College and the University of Michigan, where he wrote his dissertation under the direction of Andreas Blass in 1985. He has held teaching positions at Oberlin, Stetson University, and at SUNY Geneseo, where he has been since 1992. A recipient of the SUNY Chancellor’s Award for Excellence in Teaching and the MAA Seaway Section’s Clarence F. Stephens Distinguished Teaching Award, he has published work in set theory and in mathematical biology.

Lars Kristiansen

Lars Kristiansen was born in Fredrikstad, Norway. He received his Ph.D. from the University of Oslo in 1996, where he has taught since 2005. Kristiansen’s research areas are computability theory and complexity theory.