Proof theory. The first step into impredicativity (Q930618)

This book could be considered a kind of a sequel, but not second edition, of the author's ``Proof Theory'' published twenty years ago [\textit{W. Pohlers}, Proof theory. An introduction. Lecture Notes in Mathematics 1407. Berlin etc.: Springer-Verlag (1989; Zbl 0695.03024)], due to the fact that it presents an essential extension of the previous one. After giving a historical background and basic primitive recursive functions and relations, the author develops the theory of ordinals on the basis of a not fully axiomatized naive set theory in Chapter 3. More emphasis is placed on the development of recursion theory in Chapters 5 and 6. A recapitulation of fundamental facts in general logic is given in Chapters 2 and 4. Chapter 7 is devoted to Gentzen's original results on ordinal analysis for arithmetic. The autonomous ordinals and the boundaries of predicativity are treated in Chapter 8. In Chapter 9, Buchholz's technique of operator-controlled derivation is applied in order to obtain an upper bound for the ordinal \(\kappa^{\text{ID}_1}\) coinciding with the proof-theoretical ordinal of \(\text{ID}_1\). In Chapter 10 an adaption of Weiermann's theory on subrecursive functions to a study of the provably recursive functions of arithmetic is presented and discussed. Chapter 11 deals with the Kripke-Platek axiomatic set theory with infinity, the axiom system \((\Pi_2\)-REF) and the computation of their proof-theoretical ordinals. The book ends with two chapters considering the revising predicativity and the theory of nonmonotone inductive definitions. Each statement is followed by its proof, and each chapter contains a lot of relevant and useful remarks and exercises. The book is addressed primarily to students of mathematical logic interested in the basics of proof theory, and it can be used both for introductory and advanced courses in proof theory. Due to the author's intent to `write a book on proof theory that needs no previous knowledge of proof theory' and to his approachable style, this book may be recommended to a larger circle of readers interested in proof theory.