# Book:H. Jerome Keisler/Mathematical Logic and Computability

## H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability

Published $\text {1996}$, McGraw-Hill

ISBN 0-07-114426-9

### Contents

Preface
1. Propositional Logic
1.1 Introduction
1.2 Syntax of Propositional Logic
1.3 Induction on Length of Wffs
1.4 Main Connective
1.5 Semantics of Propositional Logic
1.6 Truth Tables and Tautologies
1.7 Tableaus
1.8 Soundness
1.9 Finished Sets
1.10 Completeness
1.11 Compactness
1.12 Valid Arguments
1.13 Tableau Problems (TAB1)
1.14 Exercises
2. Pure Predicate Logic
2.1 Introduction
2.2 Syntax of Predicate Logic
2.3 Free and Bound Variables
2.4 Semantics of Predicate Logic
2.5 Graphs
2.6 Tableaus
2.7 Soundness
2.8 Finished sets
2.9 Completeness
2.10 Equivalence Relations
2.11 Order Relations
2.12 Set Theory
2.13 Tableaus and Mathematical Proofs
2.14 PREDCALC Problems (PRED2)
2.15 Tableau Problems (TAB3)
2.16 Exercises
3. Full Predicate Logic
3.1 Syntax
3.2 Semantics
3.3 Tableaus
3.4 Soundness
3.5 Completeness
3.6 Theory of Groups
3.7 Peano Arithmetic
3.8 Some Applications of Compactness
3.9 Tableau Problems (TAB4)
3.10 Exercises
4. Computable Functions
4.1 Introduction
4.2 Numerical Functions and Relations
4.3 The Unlimited Register Machine
4.4 RM computability
4.5 Examples of RM-computable Functions
4.6 Gödel Numbers, Extract, and Put
4.8 Closure Theorems
4.9 Universal RM Programs
4.10 Church's Thesis
4.11 The Halting Problem
4.12 Church's Theorem
4.13 Simple Gnumber Problems (GNUM5)
4.15 Exercises
5. The Incompleteness Theorems
5.1 Coding Tableaus
5.2 Definability and Representability
5.3 The Equivalence Theorem
5.4 Computable Implies Representable
5.5 First Incompleteness Theorem
5.6 Gödel's Original Incompleteness Proof
5.7 Gödel-Rosser Theorem
5.8 Provability and Modal Logic
5.9 Modal Systems and Tableaus
5.10 First Incompleteness Theorem Revisited
5.11 Second Incompleteness Theorem
5.12 Modal Tableau Problems (TAB7)
5.13 Exercises
A. Sets and Functions
A.1 Sets
A.2 Boolean Operations
A.3 Functions
A.4 Composition and Restriction
A.5 Identity, One-one, and Onto Functions
A.6 Cardinality
A.7 Inverses
A.8 Cartesian Product
A.9 Graphing Functions
A.10 Finite Sequences
A.11 Permutations
A.12 Induction
B. Listings
B.1 Simple GNUMBER Programs
B.3 Pseudocode for PARAM
B.4 PARAM.GN listing
B.5 Pseudocode for NXSTATE and UNIV
B.6 NXSTATE0.GN listing
B.7 UNIV.GN listing
C. The Logiclab Package
D. TABLEAU - Tableau Editor for DOS
D.1 Introduction
D.2 Getting Started
D.3 Title Screen
D.4 Hypothesis Mode
D.4.1 Commands in Hypothesis Mode
D.4.2 Propositional Logic
D.4.3 Predicate Logic
D.4.4 Moving Within a Formula
D.4.5 Size Limit for Formulas
D.5 Tableau Mode
D.5.1 Moving Within the Tableau
D.5.2 Mouse
D.5.3 Commands in Tableau Mode
D.5.4 Propositional Logic
D.5.5 Predicate Logic
D.5.6 Predicate Logic with Equality
D.5.7 Size Limit for Substitutions
D.6 Map Mode
D.7 The Modal Logic Option
D.8 Changing Directories
E. TABWIN - Tableau Editor for Windows (R)
E.1 Introduction
E.4 Entering Hypotheses
E.5 Viewing Tableaus
E.6 Building Tableaus
F COMPLETE - Tableau Completer for DOS
G COMPWIN - Tableau Completer for Windows (R)
G.1 Introduction
G.4 Building a Finished Tableau
G.5 Other Commands
H. PREDCALC - Predicate Calculator for DOS
H.1 Introduction
H.2 Getting Started
H.3 Title Screen
H.4 Display Modes
H.5 Goals
H.6.1 The Time Counter
H.6.2 Moving Within the Calculator Pad
H.6.3 The Help Window
H.6.4 Mouse
H.6.5 Using the Calculator Buttons
H.7 The Letter Commands
H.8 Changing Directories
I. PREDWIN - Predicate Calculator for Windows (R)
I.1 Introduction
I.2 Goals
J. GNUMBER - Gödel Numberer for DOS
J.1 Introduction
J.2 Getting Started
J.3 Title Screen
J.4 Execution Mode
J.4.1 Viewing More Instructions or Registers
J.4.2 Execution Mode Commands
J.5 Program Mode
J.5.1 Moving Within the Screen
J.5.2 Commands in the Program Mode
J.6 Instruction Editor
J.6.l Register Machine Instruction Letters
J.6.2 Entering Register Machine Instructions
J.6.3 Register Machine Program Files
J.7 Register Mode
J.7.l Moving Within the Registers
J.7.2 Entering a Number into a Register
J.7.3 Exploring a Register
J.7.4 Register Mode Commands
J.8 Changing Directories
K GNUMWIN - Gödel Numberer for Windows (R)
K.1 Introduction
K.2 Program Execution
K.3 Register Machine Instructions
Redoing Appendix $\text A$ from Next: lots of examples missed, and some fine detail ignored