Logic, Sets and Recursion, Second Edition

• Teaches students how to construct and write informal, yet rigorous mathematical proofs using basic set theory, recursive definitions, and mathematical induction.
• Set exercises, which were formerly a supplement, have been moved into the body of the book enhancing the text's pedagogy.
• Introduces formalized sentential and predicate logic.

Table of Contents

Introduction

1.  Sentential Calculus
  1.1  Syntax of the Sentential Calculus
  1.2  Correspondence to Natural Languages
  1.3  Semantics of the Sentential Calculus
  1.4  Some Metatheoretical Concepts
  1.5  Principles for Sentential Calculus Derivations
  1.6  Adequacy and Use of Sentential Calculus Derivation Rules
        1.6 1  Soundness and Completeness
        1.6 2  Strategies for Constructing Proofs
        1.6 3  Sentential Calculus Derivation Examples
  1.7  Conjunctive Normal Form and Resolution Proofs

2.  Basic Set Theory
  2.1  Sets
        2.1 1  Extensionality, Predicates, and Abstraction
        2.1 2  Some Special Sets and Set Operations
  2.2  Relations
        2.2 1  General Features
        2.2 2  Special Kinds of Relations
  2.3  Functions
        2.3 1  Basic Ideas
        2.3 2  Compositions and Inverses
  2.4  Relational Systems

3.  Recursion and mathematical Induction
  3.1  The Natural Number System
         3.1 1  Introduction
         3.1 2  Peano's Axioms and the Induction Principle
         3.1 3  Definition by Recursion
  3.2  Basic Arithmetic
         3.2 1  Some Simple Functions
         3.2 2  Additional Arithmetical Definitions
  3.3  Extensions of Recursive Definition and Induction
         3.3 1  Some Additional Applications of the Recursion Theorem
         3.3 2  The Well-Ordering of the Natural Numbers
         3.3 3  Course of Values Induction
         3.3 4  Two Arithmetical Algorithms
         3.3 5  Pitfalls of Recursion
  3.4  Non-Numerical Data
         3.4 1  Strings
         3.4 2  A Simple Treatment of Lists
         3.4 3  Sentential Calculus Expressions
         3.4 4  Stacks and Queues

4.  Predicate Calculus
  4.1  Syntax of the Predicate Calculus
  4.2  Semantical Aspects of the Predicate Calculus
         4.2 1  Interpretations and Truth
         4.2 2  Tautologous Sentences in Predicate Calculus
         4.2 3  Tautological Consequences in Predicate Calculus
  4.3  Predicate Calculus Derivations
         4.3 1  Derivation Rules
         4.3 2  Proof Strategies and Examples
         4.3 3  Adequacy of the Predicate Calculus Rules
  4.4  Application Example
  4.5  Identity and Function Symbols
        4.5 1  Extension of the Syntax
        4.5 2  Semantics of Predicate Calculus with Identity and Function Symbols
        4.5 3  Derivation Rules for Predicate Calculus with Identity and Function Symbols
        4.5 4  Use of Identity in Representing Information
  4.6  Formalized Theories

References
Answers to Selected Exercises
The Greek Alphabet
Glossary of Symbols
Index 

This book is an introduction to mathematical logic and related topics for undergraduates.  It is primarily intended for students of computer science, mathematics, and philosophy.

• Math Logic 
• Discrete Math 
• Set Theory