A Friendly Introduction to Mathematical Logic

Author(s): Christopher Leary and Lars Kristiansen

Publication Date: August 10, 2015

ISBN: 978-1942341079

OCLC: 922892917

Affiliation: SUNY Geneseo

About the book

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.com, IndieBound.com, and Amazon.com, as well as wholesale through Ingram Content Group.

Table of Contents

• Preface
• 1 Structures and Languages
  • 1.1 Naïvely
  • 1.2 Languages
  • 1.3 Terms and Formulas
  • 1.4 Induction
  • 1.5 Sentences
  • 1.6 Structures
  • 1.7 Truth in a Structure
  • 1.8 Substitutions and Substitutability
  • 1.9 Logical Implication
  • 1.10 Summing Up, Looking Ahead
• 2 Deductions
  • 2.1 Naïvely
  • 2.2 Deductions
  • 2.3 The Logical Axioms
    • 2.3.1 Equality Axioms
    • 2.3.2 Quantifier Axioms
    • 2.3.3 Recap
  • 2.4 Rules of Inference
    • 2.4.1 Propositional Consequence
    • 2.4.2 Quantifier Rules
  • 2.5 Soundness
  • 2.6 Two Technical Lemmas
  • 2.7 Properties of Our Deductive System
  • 2.8 Nonlogical Axioms
  • 2.9 Summing Up, Looking Ahead
• 3 Completeness and Compactness
  • 3.1 Naïvely
  • 3.2 Completeness
  • 3.3 Compactness
  • 3.4 Substructures and the Löwenheim-Skolem Theorems
  • 3.5 Summing Up, Looking Ahead
• 4 Incompleteness from Two Points of View
  • 4.1 Introduction
  • 4.2 Complexity of Formulas
  • 4.3 The Roadmap to Incompleteness
  • 4.4 An Alternate Route
  • 4.5 How to Code a Sequence of Numbers
  • 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.3 Representable Sets and Functions
  • 5.4 Representable Functions and Computer Programs
  • 5.5 Coding—Naïvely
  • 5.6 Coding Is Representable
  • 5.7 Godel Numbering
  • 5.8 Godel Numbers and N
  • 5.9 Num and Sub Are Representable
  • 5.10 Definitions by Recursion Are Representable
  • 5.11 The Collection of Axioms Is Representable
  • 5.12 Coding Deductions
  • 5.13 Summing Up, Looking Ahead
• 6 The Incompleteness Theorems
  • 6.1 Introduction
  • 6.2 The Self-Reference Lemma
  • 6.3 The First Incompleteness Theorem
  • 6.4 Extensions and Refinements of Incompleteness
  • 6.5 Another Proof of Incompleteness
  • 6.6 Peano Arithmetic and the Second Incompleteness Theorem
  • 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.4 Computable Functions and Computable Indices
  • 7.5 The Proof of Kleene’s Normal Form Theorem
  • 7.6 Semi-Computable and Computably Enumerable Sets
  • 7.7 Applications to First-Order Logic
    • 7.7.1 The Entscheidungsproblem
    • 7.7.2 Gödel’s First Incompleteness Theorem
  • 7.8 More on Undecidability
• 8 Summing Up, Looking Ahead
  • 8.1 Once More, With Feeling
  • 8.2 The Language L_BT and the Structure B
  • 8.3 Nonstandard L_BT-structures
  • 8.4 The Axioms of B
  • 8.5 B extended with an induction scheme
  • 8.6 Incompleteness
  • 8.7 Off You Go
• Appendix: Just Enough Set Theory to Be Dangerous
• Solutions to Selected Exercises
• Bibliography

---

Available Now, Math, Mathematics | Subjects/Keywords: Available in print, logic, mathematics