Cover image for Recursion theory for metamathematics
Recursion theory for metamathematics
Smullyan, Raymond M.
Personal Author:
Publication Information:
New York : Oxford University Press, 1993.
Physical Description:
xiv, 163 pages ; 25 cm.
Reading Level:
1350 Lexile.
Format :


Call Number
Material Type
Home Location
Item Holds
QA9.6 .S68 1993 Adult Non-Fiction Non-Fiction Area

On Order



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

Author Notes

Raymond Merrill Smullyan was born in Far Rockaway, Queens, New York on May 25, 1919. He received a bachelor's degree in mathematics from the University of Chicago and a Ph.D. from Princeton University. He taught at Princeton, Yeshiva University, Lehman College of the City University of New York, and Indiana University. He also performed magic under the stage name Five-Ace Merrill at nightclubs like the Pump Room in Chicago.

He was a puzzle-creating logician who wrote many books including The Chess Mysteries of the Arabian Knights, The Lady or the Tiger?: And Other Logic Puzzles, Alice in Puzzle-Land: A Carrollian Tale for Children, and The Magic Garden of George B and Other Logic Puzzles. He died on February 6, 2017 at the age of 97.

(Bowker Author Biography)

Reviews 1

Choice Review

Roughly speaking, from G"odel we know the existence, relative to any fixed consistent finite set of axioms for number theory, of number theoretical propositions that are independent and consistent, which is neither provable nor refutable; from Turing we know the existence of certain families of well-posed mathematical questions that are undecidable by any single algorithm. The elaboration of G"odel's ideas gives rise to much of modern mathematical logic; the refinement of Turing's ideas constitute recursion theory. Distinct phenomena, independence, and undecidability are nevertheless intimately related. This sequel to Smullyan's recent G"odel Incompleteness Theorem (CH, Sep'93) sets forth recursion theory in a form that brings out its logical content, with an eye toward consequences for independence phenomena. A self-contained exposition, it presumes neither a reading of the previous volume (whose relevant results are summarized, with proof, in the first few pages) nor a prior knowledge of recursion theory. Nevertheless, recursion theory neophytes may find more intuition in expositions that explicitly feature some model of computation (such as the Turing machine). The reader with some familiarity with both recursion theory and logic should find this an excellent source for the interconnections between them. Undergraduate. D. V. Feldman; University of New Hampshire

Table of Contents

1 Recursive Enumerability and Recursivity
2 Undecidability and Recursive Inseparability
3 Indexing
4 Generative Sets and Creative Systems
5 Double Generativity and Complete Effective Inseparability
6 Universal and Doubly Universal Systems
7 Shepherdson Revisited
8 Recursion Theorems
9 Symmetric and Double Recursion Theorems
10 Productivity and Double Productivity
11 Three Special Topics
12 Uniform Godelization