Computability and Logic [Paperback]

George S. Boolos (Author), Richard C. Jeffrey (Author)

Book Description

Publication Date: September 29, 1989 | ISBN-10: 0521389232 | ISBN-13: 978-0521389235 | Edition: 3

A text for a second course in logic for graduate and advanced undergraduate students. This third edition has been corrected and contains thoroughly revised versions of the chapters on Ramsey and provability, with new exercises provided for three other chapters. There are also two new chapters dealing with undecidable sentences and on the non-existence of non-standard recursive models of Z.

Editorial Reviews

Review

'Intended for a second course in logic it gives excellent coverage of the fundamental theoretical results about logic involving computability, undecidability, axiomatization, definability, incompleteness, etc.' American Math Monthly

'... particularly appropriate for graduate and advanced undergraduate students in philosophy ... The book is written in a clear and pleasing style and avoids pedantry ... It should be an excellent text for its intended audience.' Mathematical Reviews

Book Description

Now in its fourth edition, this book has become a classic because of its accessibility to tudents 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. John Burgess has now enhanced the book by adding a selection of problems at the end of each chapter, and by reorganising and rewriting chapters to make them more independent of each other. --This text refers to an out of print or unavailable edition of this title.

Product Details

• Paperback: 320 pages
• Publisher: Cambridge University Press; 3 edition (September 29, 1989)
• Language: English
• ISBN-10: 0521389232
• ISBN-13: 978-0521389235
• Product Dimensions: 7.8 x 5.1 x 1 inches
• Shipping Weight: 1 pounds
• Average Customer Review: 3.5 out of 5 stars  See all reviews (22 customer reviews)
• Amazon Best Sellers Rank: #68,846 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

21 of 21 people found the following review helpful:

4.0 out of 5 stars For typo-tolerant readers only., September 19, 2002

By A Customer

This review is from: Computability and Logic (Paperback)

I think George Boolos is a wonderful writer. (I'm midway through his _Logic, Logic, and Logic_ right now.) I think Cambridge University Press is a wonderful company. (I own 25 of their titles.) I think the subject matter of this book is fascinating, and I'd probably agree with 95% of the nice things reviewers say about this book. But it is aggravating to spend good money on a book with as many typos as this one has. The reader of a math book should be expected to have a pencil handy to work out details, not to correct errors.

This fourth edition is a major revision of the third edition, which is the edition that pre-2002 reviews (including those excerpted on the fourth edition's back cover) are talking about. Boolos is now deceased and had no part in the revisions, and I think the fourth edition has suffered as a result.

As a sampling of the typos, consider what we find starting halfway through Chapter 7 and proceeding through Chapter 9: In the proof of Corollary 7.6, the word "smallest" is omitted in the 4th sentence, and in 9 different places the argument x has been dropped from the function c (p. 78). Example 7.10 has the erroneous condition x<x (p. 79). The definition of "semirecursive" refers to an n-place recursive relation R but shows an (n+1)-place relation (p. 81). In the proof of part (d) of Corollary 7.15, R_2y is written in place of R_2x (p.82). In the proof of Proposition 7.17, the v in the definition of g should be a w (p. 83). In Section 8.1, newleft_1 is claimed to be id^2_1 even though it has 3 inputs, r^* is claimed to be equal to 2r^*+1 rather than 2r+1 (p. 90), an undefined variable l is written in place of p, the word "be" is omitted before "subsumed", and the formula for valu(r) has a superfluous "+1" (p. 91). In 2 places the entry function is written as "entry" instead of "ent" (p. 92). The definition of "universal" function talks about a one-place function f but shows an n-place function, the 3-place function stdh is show with only 2 arguments, and a nonexistent Theorem 5.5 is referenced (p. 95). The proof of Corollary 8.8 says A is a set of F rather than a set of x (p. 97). The abstract of Chapter 9 talks about "notions pertaining formulas" (p. 101). Quantified variables in Table 9-1 are erroneously shown as subscripts (p. 102). The identity symbol is said not to be "treated like other the nonlogical predicates" (p. 104). There are superfluous copies of the words "also", "with" (p. 106), "zero" (p. 107), "every" (p. 109), and "that" (p. 111) inserted in the text, while a copy of "notation" is missing (p. 108). And then there's the Karl Malonesque sentence: "Where function symbol are present, they also are supposed to be written in front of the terms to which it applies." (p. 108) Tired of all this? Well, so am I.

One expects these sorts of mistakes in a first draft, but not in a book that has passed through several intermediate drafts that were vetted by (Princeton!) students (p. xi). One would hope, at least, that an errata sheet would be posted on the Web, but I can find none.

22 of 24 people found the following review helpful:

5.0 out of 5 stars Very lucid explanations, June 30, 2002

By 

Chan-Ho Suh (California) - See all my reviews
(REAL NAME)   

This review is from: Computability and Logic (Paperback)

This book is regarded as a 'classic' and rightly so. It assumes a minimal background, some familiarity with the propositional calculus. Even this can be dispensed with, if the reader is sufficiently motivated, as there is a well-written review of the first-order logic that one typically learns in an introductory formal logic course.

The book is highly readable. Each chapter begins with a short paragraph outlining the topics in the chapter, how they relate to each other, and how they connect with the topics in later and earlier chapters. These intros by themselves are valuable. The explanations though are what stand out. The authors are somehow able to take the reader's hand and guide him/her leisurely along with plentiful examples, but without getting bogged down in excessive prose. And they are somehow able to cover a substantive amount of material in a short space without seeming rushed or making the text too dense. It's nothing short of miraculous.

What made the book especially appealing to me is that it starts right out with Turing Machines. As a topologist who recently got interested in computational topology, I needed a book that would quickly impart a good, intuitive grasp of the basic notions of computability. I have more "mathematical maturity" than is needed to read an introductory book on computability, so I feel confident in saying that most of the standard texts on computability revel in excessive detail, like defining Turing Machines as a 6-tuple -- something that serves no purpose other than pedantry. This book is different. I particularly liked how the authors stress the intuitive notions underlying the definitions. For example, they lay special emphasis on the Church-Turing thesis, always asking the reader to consider how arguments can be simplified if it were true.

One should note that the emphasis of this book is more towards logic. While it starts with issues of computability, it moves into issues of provability, consistency, etc. The book covers the standards such as Goedel's famous incompleteness theorems in addition to some less standard topics at the end of the book. A small set of instructive exercises follows each chapter.

10 of 11 people found the following review helpful:

1.0 out of 5 stars Absolutely rediculous, February 15, 2005

By 

steve - See all my reviews

This review is from: Computability and Logic (Paperback)

WAY TOO MANY TYPOS!!!!!! There were so many typos, it made it extremely difficult to follow this book at times. As a first time student to mathematical logic, I found this to be just too much. People who are veterans with logic and logicians may easily spot typos, but for a first time student of the subject, I was confused as hell at some parts simply because there was a typo. I wasted hours trying to figure out some parts (such as the factorial function in chapter 6) when I finally found out that the reason why I couldn't figure it out was because of a typo. The Errata sheet on the internet IS 35 PAGES LONG!!!! I didn't pay money to correct a horde of typos! God that pisses me off.