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

Subject Matter

• Formal Languages
• Symbolic Logic
• Mathematical Logic

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.7 The Advanced RM

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.14 Advanced Gnumber Problems (GNUM6)

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.2 Advanced RM 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.2 File Menu

E.3 View Menu

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.2 File Menu

G.3 View Menu

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 The Calculator Pad

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

I.3 The Help Menu

I.4 The Calculator Pad

I.5 The File Menu

I.6 The View Menu

I.7 The Options Menu

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.6.4 Advanced Instruction Letters

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.7.5 Advanced 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

K.4 File Menu

K.5 Program Menu

K.6 The Registers Menu

K.7 Windows Menu

K.8 Options Menu

K.9 Step Command and Go Menu

Bibliography

Index

Next

Source work progress

• 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): $\S 2.1$: Introduction

Redo from start

Redoing Appendix $\text A$ from Next: lots of examples missed, and some fine detail ignored

• 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text A$: Sets and Functions: $\text{A}.2$: Boolean Operations