Skip to content

Computability and Logic

ISBN-10: 0521877520

ISBN-13: 9780521877527

Edition: 5th 2007 (Revised)

Authors: George S. Boolos, Richard C. Jeffrey, John P. Burgess

List price: $124.00
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
Buy eBooks
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel??'s incompleteness theorems, but also a large number of optional topics, from Turing??'s theory of computability to Ramsey??'s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.
Customers also bought

Book details

List price: $124.00
Edition: 5th
Copyright year: 2007
Publisher: Cambridge University Press
Publication date: 9/17/2007
Binding: Hardcover
Pages: 366
Size: 7.25" wide x 10.25" long x 1.00" tall
Weight: 1.738
Language: English

George Boolos was Professor of Philosophy, Massachusetts Institute of Technology.

Preface to the Fifth Edition
Computability Theory
Enumerable Sets
Turing Computability
The Halting Problem
The Productivity Function
Abacus Computability
Abacus Machines
Simulating Abacus Machines by Turing Machines
The Scope of Abacus Computability
Recursive Functions
Primitive Recursive Functions
Recursive Sets and Relations
Recursive Relations
Semirecursive Relations
Further Examples
Equivalent Definitions of Computability
Coding Turing Computations
Universal Turing Machines
Recursively Enumerable Sets
Basic Metalogic
A Precis of First-Order Logic: Syntax
First-Order Logic
A Precis of First-Order Logic: Semantics
Metalogical Notions
The Undecidability of First-Order Logic
Logic and Turing Machines
Logic and Primitive Recursive Functions
The Size and Number of Models
Equivalence Relations
The Lowenheim-Skolem and Compactness Theorems
The Existence of Models
Outline of the Proof
The First Stage of the Proof
The Second Stage of the Proof
The Third Stage of the Proof
Nonenumerable Languages
Proofs and Completeness
Sequent Calculus
Soundness and Completeness
Other Proof Procedures and Hilbert's Thesis
Arithmetization of Syntax
Godel Numbers
More Godel Numbers
Representability of Recursive Functions
Arithmetical Definability
Minimal Arithmetic and Representability
Mathematical Induction
Robinson Arithmetic
Indefinability, Undecidability, Incompleteness
The Diagonal Lemma and the Limitative Theorems
Undecidable Sentences
Undecidable Sentences without the Diagonal Lemma
The Unprovability of Consistency
Further Topics
Normal Forms
Disjunctive and Prenex Normal Forms
Skolem Normal Form
Herbrand's Theorem
Eliminating Function Symbols and Identity
The Craig Interpolation Theorem
Craig's Theorem and Its Proof
Robinson's Joint Consistency Theorem
Beth's Definability Theorem
Monadic and Dyadic Logic
Solvable and Unsolvable Decision Problems
Monadic Logic
Dyadic Logic
Second-Order Logic
Arithmetical Definability
Arithmetical Definability and Truth
Arithmetical Definability and Forcing
Decidability of Arithmetic without Multiplication
Nonstandard Models
Order in Nonstandard Models
Operations in Nonstandard Models
Nonstandard Models of Analysis
Ramsey's Theorem
Ramsey's Theorem: Finitary and Infinitary
Konig's Lemma
Modal Logic and Provability
Modal Logic
The Logic of Provability
The Fixed Point and Normal Form Theorems
Annotated Bibliography