Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science) [Paperback]

A. S. Troelstra (Author), H. Schwichtenberg (Author)

Book Description

Publication Date: July 31, 2000 | ISBN-10: 0521779111 | ISBN-13: 978-0521779111 | Edition: 2

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of first-order logic formalization. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic, logic programming theory, category theory, modal logic, linear logic, first-order arithmetic and second-order logic. In each case the authors illustrate the methods in relatively simple situations and then apply them elsewhere in much more complex settings. For the new edition, they have rewritten many sections to improve clarity, added new sections on cut elimination, and included solutions to selected exercises. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence.

Editorial Reviews

Review

'This is a fine book. Any computer scientist with some logical background will benefit from studying it. It is written by two of the experts in the field and comes up to their usual standards of precision and care.' Ray Turner, Computer Journal

Book Description

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included.

Product Details

• Paperback: 432 pages
• Publisher: Cambridge University Press; 2 edition (July 31, 2000)
• Language: English
• ISBN-10: 0521779111
• ISBN-13: 978-0521779111
• Product Dimensions: 8.8 x 6.1 x 1.3 inches
• Shipping Weight: 1.5 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #980,872 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

30 of 32 people found the following review helpful:

4.0 out of 5 stars Useful but a bit mis-pitched, March 18, 2005

By 

William Stirton - See all my reviews
(REAL NAME)   

This review is from: Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science) (Paperback)

This is a very bread-and-butter introduction to proof theory. Apart from digressions, it is not until we are five-sixths of the way through the book that we begin to meet formal systems in which any actual mathematics can be formalized (chapter 10). The first nine chapters are devoted to studying, in great detail, a plethora of purely logical systems. Anyone who thought, under the influence of Hilbert, perhaps, that proof theory was about proving the consistency of classical mathematics will probably be seriously disappointed with this book.

This is the main flaw in the book. Computer scientists (of whom I am not one) might like it; but beginners looking for an explanation of the relevance of proof theory to either mathematics or philosophy will probably not find what they are looking for, at least through the first five-sixths of the book.

Why is proof theory interesting? I could be missing something, but I just do not see that the authors have anything much to say about this question - rather a serious fault in an introductory textbook, surely? The book is very clear and the style is pleasant; but a great many hairs are split and a beginner cannot be expected to see that there is anything much to be gained from doing so.

Despite these faults, for readers who *already* possess a moderately advanced knowledge of proof theory and want a really thorough, in-depth treatment of the very basics of the subject, this book is very useful. A thing I particularly liked is the emphasis given to considerations about the lengths of proofs (sections 5.1 and 6.7). Some textbooks on proof theory either do not treat pure logic at all (Pohlers) or do treat it but without giving any information about what cut-elimination in pure logic does to the length of a proof (Schuette). The latter strategy is perverse. Considerations about lengths of proofs are undeniably important when the proofs in question are infinitely long; yet students of the subject should be allowed to see that the considerations that apply here are just generalizations of the same considerations as they apply to finitely long proofs. You will understand the advanced stuff better if you know the basics as well.

People doing research in proof theory might also welcome the fact that the authors discuss quite a wide variety of logical systems, thus giving the reader a chance to weigh up the merits and disadvantages of each.

Anyone wanting a first introduction to proof theory will probably find the one by Pohlers a lot more exciting than this one. Of the older books, the one by Girard is the one that bears the closest resemblance to this book: in fact, this book covers much of the same ground as the earlier chapters of Girard's, but is easier to follow. On the other hand, because Girard goes much further into the subject, he allows you better to see the relevance of the basics to the more advanced material.