Customer Reviews

Computability and Logic

5 star:		(8)
4 star:		(4)
3 star:		(5)
2 star:		(2)
1 star:		(3)

 

 

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.

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.

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.

I can hardly imagine a better introduction to the topics covered than this book. It discusses virtually everything the intermediate logic student could want: diagonalization, Turing machines, undeciability, indefinability, incompleteness, forcing, and on and on. Although the first few chapters are a bit awkward, the style is generally crystal clear and the examples and metaphors vivid. It's far and away the best read of any text on logic I've yet encountered.

As a mathematician, I was concerned about the books' emphasis on logic rather than mathematics (the text is aimed at philosophy students, too). But the introduction to foundations flows so easily and naturally that I could never complain. Anyone interested in the topic, regardless of their background, could hardly do better (or cheaper) for an introduction.

P.S. - I wanted to give this five stars, but, as other reviewers have pointed out, there are simply too many typos. C'mon, get an editor.

Just about the only mathematical logic book readable by ordinary human beings, assuming only a background of first-order predicate logic, taught in almost any introductory logic class.

The first eight chapters introduce Turing machines and other formal models of computation, emphazing the evidence for Church's thesis. Chapters 9-13 prove important results concerning first-order logic, including soundness, completeness, compactness, and Lowenheim-Skolem. The rest of the book focuses on number theory, and proves results such as Goedel's incompleteness theorems, Loeb's theorem, the existence and structure of non-standard models of arithmetic, and the decidability of Presburger arithmetic.

Highly recommended as an introduction to mathematical logic.

I have used the old edition for a class in computability and logic where the students did not have much background in either. Having used the new edition this year, I find I greatly prefer the old one. The new one may be more rigorous, but it is much harder to read and understand for students without the background. The first part is not so bad, but the second half on logic gets too involved in the proofs and the students lose sight of the overall pupose and what these result really mean.

it should be noted that this book is not intended for the auto-didact. Like other good logic texts-Jeffrey's Formal Logic or Pollock's Technical Method's (out of print, but available in PDF on his website)-there is very little commentary in the brief chapters, so it is useful if you are already very familiar with the material or if you have a very worthy guide. An advantage of the short chapters is that material is broken down in finer increments; a disadvantage is that material is presented with spare guidance at times. I was also disappointed by the sparsity of examples. Like many logic and math students, I learn better from examining a few examples than I do from either lectures or text: give me three examples of something and I'll usually have it down. I would have liked to see more examples in this text. The exercises are ample and creative, which I appreciate, but often go so far beyond the text it's mind boggling. They often require extensive extrapolations from the text sometimes even proving theorems or lemmas not in the text just for use in the exercise. I should say that I'm a philosopher and not a mathematician (I suspect the other reviewers are primarily mathematicians), so my estimation of the difficulty will differ. I aced Symbolic Logic, Modal Logic, Deviant Logic, and Advanced Symbolic Logic and still had difficulty with some of this material, even though I had a prior acquaintance with Godel's proof. Note that the first reviewer, who thought it was a breeze, described himself this way "As a topologist who recently got interested in computational topology..." Good for him, but if you are not a professional mathematician this book will probably be quite challenging at times, even if you are otherwise good at mathematical logic. Note also that the second five-star review refers to the older edition-it has not necessarily improved with age. I firmly agree with the reviewer from Brooklyn that the proofs could have had more forecasting and with the reviewer from Raleigh that a solution set, say to the odds, would have been very useful, especially for the auto-didact, from whose perspective I am writing.

The main virtue of this book, and which sets it apart from most other modern textbooks I have seen, is that it provides clear and usually illuminating explanations of the philosophical importance of the topics covered. These explanations and clarifications are given in a clear and usually crisp prose and emphasise the philosophical importance of whatever metalogical method or result they concern. I regard it as a very suitable companion or reference-work for the philosophically interested student of logic. For rigorous and very detailed proofs and definitions I normally consult a book like Mendelson's Introduction to Mathematical Logic, but usually I read what Boolos, Burgess and Jeffrey say too. The fact that the book (in its fourth edition at least) is divided into many short chapters makes it all the more useful as a companion. The short 'abstracts' that introduce each chapter deserve special mention. An index is the best way of localising information about something one knows one needs. The abstracts often do the reverse; they help one realise what one needs.
As other reviewers have pointed out, the book has WAY TOO MANY typos. Burgess has a list of errata on his web-page, but it is not exhaustive and above all a professionally edited book should not have this many typos. The typos is in my mind the only thing that prevents it from earning five stars.

Except for the scores of typos. Previous reviewers have observed this already; one has added that Burgess maintains an errata file on his website at Princeton. In fact he has two (for 1st and 2nd printings). But note that the errata file, at least for the 1st edition, is far from complete. I've noticed at least a dozen (potentially very confusing) typos that he has not yet catalogued. It's very frustrating to have to check the errata file (over 40 pages!) everytime one gets confused.

Two more points (1) the proof of compactness could have been better organized, and thereby made less tedious. (2) In general, there could stand to be more meta-level discussion about what's going on in the book. I find it's mostly trees, very little forest. (I'm not asking for _Godel, Escher, Bach_ here; I mean: where is this proof headed? Where did these satisfacton properties come from? etc)

On the positive side, the book is comprehensive, with very little handwaving, and the chapters are usually short and sweet. I prefer this text to Mendelson's. Enderton's is not bad.

The textbook itself was pretty well written. The major problem I had with it was that the problem sets are RIDDLED with mistakes. The errata on their website help, but it doesn't catch everything. I sincerely hope the next edition has more proof reading before going to press.