Recursion Theory for Metamathematics

Synopsis

This work is a sequel to the author's G¿del's Incompleteness Theorems, though it can be read independently by anyone familiar with G¿del's incompleteness theorem for Peano arithmetic. The book deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability, and related topics. It is both an introduction to the theory and a presentation of new results in the field.

Excerpt

This volume, though a sequel to our book G.I.T. (Gödel's Incompleteness Theorems), can be read independently by those who have seen at least one proof of Gödel's incompleteness theorem for Peano Arithmetic (or at least know that the system is recursively axiomatizable). Our introductory chapter (Ch. 0) reviews all the background of G.I.T. (notations, definitions, key theorems and proofs) necessary for this volume.

Our study deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability and related topics. It is both an introduction to the theory and a presentation of new results in the field.

The Gödel and Rosser incompleteness theorems were forerunners of many results of recursion theory--indeed, they were significantly responsible for opening up many portions of the field. But also, subsequent developments in pure recursion theory have shed further light on the phenomenon of incompleteness (and uniform incompleteness, as defined in our closing chapter). It is our purpose here to explore these fascinating interrelationships more deeply. Some related work of John Shepherdson (studied in G.I.T. and thoroughly reviewed here) plays a fundamental rôle in this study (particularly in Chapters 7 and 12).

Although we want this book to be thoroughly comprehensible to the reader with no prior knowledge of recursive function theory, we have written it just as much for the expert, who will find Chapters 4- 12 (and particularly 6-12) to be the more mathematically original ones. A good deal of the latter portion of our Theory of Formal Systems [1961] is given an upgraded presentation here; we supply more motivation and make the results more easily accessible to the general reader, and several of the results and techniques are improved.

And now, for the reader familiar with the field, here is a very brief summary of what we do. Chapters 1-3 consist mainly of standard introductory material (basic closure properties of r.e. relations, the enumeration and iteration theorems, etc.) with Chapter 2 beginning . . .

Search by...
Show...

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.