Proof Theory and Logical Complexity

Introduction: Elementary Proof Theory. The Fall of Hilbert's Program. Hilbert's Program. Recursive Functions. The First Incompleteness Theorem. The Second Incompleteness Theorem. Exercises. Annex: Intuitionism. Part I: Sigma 0 1 Proof Theory. The Calculus of Sequents. Definitions. Completeness of the Sequent Calculus. The Cut-Elimination Theorem. The Subformula Property. Intuitionistic Sequent Calculus. Herbrand's Theorem. Generalization. Annex: Natural Deduction. The Church-Rosser Property. Strong Normalization. The Semantics of Sequent Calculus. Completeness of the Cut-Free Rules. Three-Valued Models. Three-Valued Logic. Annex: Takeuti's Conjecture. Limitations of Takeuti's Conjecture. Three-Valued Equivalence. Cut-Free Analysis. Three-Valued Semantics and Generalized Logics. Applications of the ``Hauptsatz''. The Interpolation Lemma. The Reflection Schema of PA. Elementary Consistency Proofs. 1-Consistency. Annex: The Hauptsatz in a Concrete Case. Normalization in HA. Normalization for NL 2 J. Part II: Pi 1 1 Proof Theory. Pi 1 1 Formulas and Well-Foundedness. The Projective Hierarchy. Well-Founded Trees. Well-Orders. Equivalents of (Sigma 0 1 -CA * ). Recursive Well-Orders. Hyperarithmetical Sets. Annex: Kleene's 0. Hierarchies Indexed by 0. Paths Through 0. The Classification Problem. The omega-Rule. omega-Logic. The Cut-Elimination Theorem. Bounds for Cut-Elimination. Equivalents for (Sigma 0 1 -CA * ). Annex: The Calculus Lomega 1 omega. Cut-Elimination in Lomega 1 omega. The Ordinal epsilon o and Arithmetic. Ordinal Analysis of PA. Extensions to other Systems. Ordinals and Theories. Annex: Godel's System T. Functional Interpretation. Spector's Interpretation. No Conterexample Interpretation. An Application. Bibliography. Analytical Index.