Computability and Logic

Description

This is a classic and an absolute must for anyone required (or wanting) to gain insight into intermediate logic. A more accessible (and yet more comprehensive) introduction is simply not available. The first part introduces basic concepts of computation, the second goes through the standard stock of important first-order result (culminating, of course, in the incompleteness theorems) whereas the third part goes through various further topics, including the Interpolation theorem (obviously), nonstandard models and provability (especially Loeb's theorem).And the style? The philosophical lexicon contains the following entry: [boo, n. The length of a mathematical or logical proof; hence, booloss, n., the process of shortening such a proof. "Only after significant booloss could the compactness theorem be explained in fifteen minutes."]. That one is pretty apt. With the Berry paradox, Boolos is able to prove the first incompleteness theorem in approximately half a page (a more standard approach is of course included as well). He has elsewhere explained the second incompleteness theorem using only one-syllable words. Point is: these authors (and, one suspects, Boolos in particular) has (had) an almost scary ability to make difficult things simple and easily comprehensible. That said, I do have a few misgivings. The typos have of course been mentioned (a list of errata is available on http://www.princeton.edu/~jburgess/addenda.htm), but most have been corrected in the second printing (so if you buy the book new, you'll probably get this one) - there are a few left, however. I am also not sure about some of the changes to the fourth edition. In particular, the structure of the proofs of the completeness, compactness and Löwenheim-Skolem theorems is somewhat surprising, proceeding from two lemmas concerning "satisfaction properties" and "closure properties". It is an interesting move, but will (partially because of the presentation, admittedly) surely be somewhat confusing to anyone coming to these for the first time not already being aware of how they fit together. That said, there is no way I can give this book less than five stars. There is simply no relevant competition comparable in accessibility and comprehensiveness. Urgently recommended.