Lectures in Proof Theory and Complexity

Overview & Synopsis

The book is based on lecture notes from the course ‘Formal Systems’, taught by the author for the Master’s Degree in ‘Applied Mathematics’ at the University of Siena. It was created for educational purposes, specifically for second-level (graduate) courses. The work is mainly oriented towards applications of Proof Theory — one of the macro-areas into which Mathematical Logic is divided — to Computability Theory and Computational Complexity Theory, albeit with entanglements with Model Theory and with Category Theory. The book begins with some classical results concerning formal arithmetic, dating back to the 1930s, and then compares them with more recent developments, emphasising the acceleration imparted to logical study by the development of computer science.