Lectures in Proof Theory and Complexity

Monograph

Lectures in Proof Theory and Complexity

Duccio Pianigiani,

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.

Keywords:
Proof Theory,
Category Theory,
Lambda Calculus,
Computational complexity,
mathematical Logic,

+ Show more

DOI: 10.36253/979-12-215-0778-2
Series: UNIverSI. Ricerca e Didattica all’Università di Siena
Scientific Board:
Language: English
Subjects: Mathematics

Download PDF
© 2025 Author(s)
CC BY-SA 4.0

Duccio Pianigiani

University of Siena, Italy - ORCID: 0000-0001-9441-7226

Duccio Pianigiani graduated in Philosophy of Science at the University of Siena. He obtained a diploma from the Postgraduate School of Logic at the local Department of Mathematics, and later a PhD in the same field from the Department of Philosophy at the University of Florence. He is currently a researcher at the Department of Information Engineering and Mathematics, University of Siena. He is currently a researcher at the Department of Information Engineering and Mathematics, University of Siena.

More About the Authors Close

Table of contents

Introduction

PART I - FORMAL SYSTEMS

Duccio Pianigiani

From decidability to feasibility

CC BY-SA 4.0

|

© Author(s)

PDF

pp.7-32

Duccio Pianigiani

Abstract views of incompleteness

CC BY-SA 4.0

|

© Author(s)

PDF

pp.33-60

Duccio Pianigiani

Church’s formal system of lambda-calculus

CC BY-SA 4.0

|

© Author(s)

PDF

pp.61-96

PART II - THE INCOMPLETENESS THEOREMS

Duccio Pianigiani

First and second Gödel’s theorems and related results

CC BY-SA 4.0

|

© Author(s)

PDF

pp.99-120

Duccio Pianigiani

Second incompleteness theorem: research developments and consequences

CC BY-SA 4.0

|

© Author(s)

PDF

pp.121-152

PART III - PROOF THEORY, MATHEMATICS AND COMPLEXITY

Duccio Pianigiani

Independent sentences of mathematical character

CC BY-SA 4.0

|

© Author(s)

PDF

pp.155-172

Duccio Pianigiani

Sequent calculus and complexity theory

CC BY-SA 4.0

|

© Author(s)

PDF

pp.173-204

Duccio Pianigiani

Random sequences, incompleteness and information

CC BY-SA 4.0

|

© Author(s)

PDF

pp.205-224

Bibliography

CC BY-SA 4.0

|

© Author(s)

PDF

pp.225-244

Key concepts

PDF

Publication Year: 2025
Pages: 252

eISBN: 979-12-215-0778-2
Content License: CC BY-SA 4.0
© 2025 Author(s)

Download PDF

XML

Publication Year: 2025

eISBN: 979-12-215-0779-9
Content License: CC BY-SA 4.0

Download XML

Bibliographic Information

Book Title

Lectures in Proof Theory and Complexity

Authors

Duccio Pianigiani

Peer Reviewed

Publication Year

2025

Copyright Information

Content License

CC BY-SA 4.0

Metadata License

CC0 1.0

Publisher Name

Firenze University Press, USiena Press

DOI

10.36253/979-12-215-0778-2

eISBN (pdf)

979-12-215-0778-2

eISBN (xml)

979-12-215-0779-9

Series Title

UNIverSI. Ricerca e Didattica all’Università di Siena

Series ISSN

3035-5915

Series E-ISSN

3035-5931

0