## An Introduction to Proof Theory: Normalization, Cut-Elimination, and Consistency ProofsAn 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 Introduction | 1 |

2 Axiomatic calculi | 13 |

3 Natural deduction | 65 |

4 Normal deductions | 101 |

5 The sequent calculus | 168 |

6 The cutelimination theorem | 202 |

7 The consistency of arithmetic | 269 |

8 Ordinal notations and induction | 312 |

B Settheoretic notation | 381 |

C Axioms rules and theorems of axiomatic calculi | 383 |

D Exercises on axiomatic derivations | 386 |

E Natural deduction | 394 |

F Sequent calculus | 399 |

G Outline of the cutelimination theorem | 401 |

405 | |

412 | |

### Other editions - View all

### Common terms and phrases

𝐴 allow already antecedent apply arithmetic assume atomic axiom 𝐵 basis calculus called cj inference classical clause complex conclusion condition consider consistency construction contains corresponding cut segment deduction defined Definition derivation discharged eigenvariable elements elimination empty end-formula end-part end-sequent ending example fact formula free variables Gentzen give given height holds inductive hypothesis instance introduced intuitionistic intuitionistic logic labelled least Lemma length logic lower major premise mathematics maximal means minor natural normal deduction Note obtain occur open assumptions operational ordinal notation ordinal notation assigned original path Problem proof proof theory Proposition prove quantifier rank reasoning reducible removed replace result right premise rule sequent simple step sub-deduction sub-formula sub-proof Suppose term theorem thread transformed true Vx B(x weakening well-ordering