An Introduction to Proof Theory: Normalization, Cut-Elimination, and Consistency Proofs

by Paolo Mancosu, Sergio Galvan, Richard Zach

An Introduction to Proof Theory provides an accessible introduction to the theory of proofs, with details of proofs worked out and examples and exercises to aid the reader's understanding. It also serves as a companion to reading the original pathbreaking articles by Gerhard Gentzen. The first half covers topics in structural proof theory, including the Gödel-Gentzen translation of classical into intuitionistic logic (and arithmetic), natural deduction and the normalization theorems (for both NJ and NK), the sequent calculus, including cut-elimination and mid-sequent theorems, and various applications of these results. The second half examines ordinal proof theory, specifically Gentzen's consistency proof for first-order Peano Arithmetic. The theory of ordinal notations and other elements of ordinal theory are developed from scratch, and no knowledge of set theory is presumed. The proof methods needed to establish proof-theoretic results, especially proof by induction, are introduced in stages throughout the text. Mancosu, Galvan, and Zach's introduction will provide a solid foundation for those looking to understand this central area of mathematical logic and the philosophy
of mathematics.

Genres: Mathematics, Philosophy, Logic

432 pages, Paperback

Published October 17, 2021

About the author

Paolo Mancosu, Ph.D., Stanford University, is Professor of Philosophy. His interests lie in the philosophy of mathematics and its history, in philosophy of logic, and in mathematical logic. His written work is currently focused upon neologicism and the philosophy of mathematical practice.

Reviews

[Mohan Morusupalli · Rating 5 out of 5]

Before I begin the review, it is important to understand the sheer breadth of what the authors attempt to accomplish in this text. Creating a foundational understanding of proof theory is a difficult task, especially from only understanding basic first-order logic.

I was lucky enough to be able to take the class with Professor Mancosu at the University of California, Berkeley, where chapter by chapter, we built our knowledge in the field. I remember flipping to the end of the book and being overwhelmed by how much I needed to learn, but by the time I reached the end, I felt as if it was within my reach. This isn't to say about my understanding, but rather to be a testament to the ability of the text to guide the readers through difficult concepts.

However, no book is without its limitations. The first edition does have a few errors and gaps in explanation that I think do harm the reader's understanding. The most apparent of this is in the natural deduction section. The authors make far too many assumptions about the reader's level of understanding, and without doing your reading, it will be very difficult to understand. The same is true for the problems in the book. Though they are meant to test your understanding, they often fail to add to it. In many cases, the problems ask you to complete elements of the proof explained; however, I argue that when teaching an introduction to proof theory, it is important to show the whole proof and all cases. Problems that ask the reader to consider the implications of changing certain premises or asking readers to repeat algorithms for different cases were more effective in engraining the actual concepts.

Ultimately, this book should be celebrated for its amazing strides in teaching proof theory. Though many aspects can be improved, the book does not fall short in communicating a basic knowledge of the field.