A Beginner's Further Guide To Mathematical Logic

by Raymond M Smullyan

Overview

'A wealth of examples to which solutions are given permeate the text so the reader will certainly be active.'
The Mathematical GazetteThis is the final book written by the late great puzzle master and logician, Dr. Raymond Smullyan.This book is a sequel to my Beginner's Guide to Mathematical Logic.The previous volume deals with elements of propositional and first-order logic, contains a bit on formal systems and recursion, and concludes with chapters on Gödel's famous incompleteness theorem, along with related results.The present volume begins with a bit more on propositional and first-order logic, followed by what I would call a 'fein' chapter, which simultaneously generalizes some results from recursion theory, first-order arithmetic systems, and what I dub a 'decision machine.' Then come five chapters on formal systems, recursion theory and metamathematical applications in a general setting. The concluding five chapters are on the beautiful subject of combinatory logic, which is not only intriguing in its own right, but has important applications to computer science. Argonne National Laboratory is especially involved in these applications, and I am proud to say that its members have found use for some of my results in combinatory logic.This book does not cover such important subjects as set theory, model theory, proof theory, and modern developments in recursion theory, but the reader, after studying this volume, will be amply prepared for the study of these more advanced topics.

Product Details

ISBN-13:	9789814725729
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	01/13/2017
Pages:	288
Product dimensions:	5.90(w) x 8.90(h) x 0.60(d)

Table of Contents

Preface ix

Part I More on Propositional and First-Order Logic 1

Chapter 1 More on Propositional Logic 3

I Propositional Logic and the Boolean Algebra of Sets 3

II An Algebraic Approach 4

III Another Completeness Proof 7

IV Fidelity to Modus Ponens 13

Chapter 2 More on First-Order Logic 23

I Magic Sets 23

II Gentzen Sequents and Some Variants 29

III Craig's Lemma and an Application 43

IV A Unification 48

V A Henkin-Style Completeness Proof 54

Part II Recursion Theory and Metamathematics 67

Chapter 3 Some Special Topics 69

I A Decision Machine 69

II Variations on a Theme of Gödel 73

III R-Systems 76

IV A Synthesis 79

Chapter 4 Elementary Formal Systems and Recursive Enmnerability 89

I More on Elementary Formal Systems 89

II Recursive Enumerability 93

III A Universal System 99

Chapter 5 Some Recursion Theory 113

I Enumeration and Iteration Theorems 113

II Recursion Theorems 117

Chapter 6 Doubling Up 133

Chapter 7 Metamathematical Applications 149

I Simple Systems 149

II Standard Simple Systems 154

Part III Elements of Combinatory Logic 171

Chapter 8 Beginning Combinatory Logic 173

Chapter 9 Combinatorics Galore 185

I The B-Combinators 185

II The Permuting Combinators 187

III The Q-Family and the Goldfinch, G 190

IV Combinators Derivable from B, T, M and I (X-I Combinators) 192

Chapter 10 Sages, Oracles and Doublets 205

Chapter 11 Complete and Partial Systems 215

I The Complete System 215

II Partial Systems of Combinatory Logic 224

Chapter 12 Combinators, Recursion and the Undecidable 233

I Preparation for the Finale 236

II The Grand Problem 239

Afterword. Where to Go from Here 253

References 261

Index 265