Lectures in Proof Theory and Complexity

Monografia

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.

Parole chiave:
Proof Theory,
Category Theory,
Lambda Calculus,
Computational complexity,
mathematical Logic,

+ Show more

DOI: 10.36253/979-12-215-0778-2
Collana: UNIverSI. Ricerca e Didattica all’Università di Siena
Comitato scientifico:
Lingua: Inglese
Argomento: Matematica

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.

Info autori Chiudi

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

Anno di pubblicazione: 2025
Pagine: 252

eISBN: 979-12-215-0778-2
Licenza d'uso: CC BY-SA 4.0
© 2025 Author(s)

Download PDF

XML

Anno di pubblicazione: 2025

eISBN: 979-12-215-0779-9
Licenza d'uso: CC BY-SA 4.0

Download XML

Informazioni bibliografiche

Titolo del libro

Lectures in Proof Theory and Complexity

Autori

Duccio Pianigiani

Opera sottoposta a peer review

Anno di pubblicazione

2025

Copyright

Licenza d'uso

CC BY-SA 4.0

Licenza dei metadati

CC0 1.0

Editore

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

Collana

UNIverSI. Ricerca e Didattica all’Università di Siena

ISSN della collana

3035-5915

e-ISSN della collana

3035-5931

0