Lectures in Proof Theory and Complexity

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 entan- glements with Model Theory and with Category Theory. The book begins with some classical results concerning formal arithmetic, dating back to the 1930s, and then com- pares them with more recent developments, emphasising the acceleration imparted to logical study by the deve- lopment of computer science.