Unprovability after Goedel

Lorenzo Carlucci
evento esterno
12/11/2007 - 14:00
Dipartimento Informatica - Via Salaria 113 - third floor - Seminari Lecture Room

Since Goedel's famous discovery of the existence of an undecidable sentence in (first-order) Peano Arithmetic in 1931, the relevance of the incompleteness phenomena for so-called "mainstream" mathematics has been intensively debated. The question roughly was: since Goedel's undecidable propositions are mathematically meaningless, does the incompleteness phenomenon matter for "normal mathematics" at all?

A breakthrough occured in the late Seventies, with the discovery by Paris and Harrington that a seemingly innocent variant of the finite Ramsey Theorem is unprovable in Peano Arithmetic (while the finite Ramsey Theorem is provable in a much weaker system).

From then on, a large number of other (more or less) "natural" combinatorial statements have been found to be unprovable in stronger and stronger systems of arithmetic, analysis and even set-theory. Among the high points of this research is Harvery Friedman's proof that Robertson and Seymour's "Graph Minor Theorem" is unprovable from a strong (impredicative) system.

In other terms, many combinatorial theorems have been proved to be provable *only* under the assumption of some unexpectedly strong axiom of infinity.

We will give an overview of past and present research in the study of (arithmetic) unprovability. Research in this area features an interplay between proof theory, recursion theory, model theory, combinatorics, number theory etc. The basic concepts and proof techniques will be illustrated, as well as the current directions of research.

Lorenzo Carlucci is currently affiliated with the Computer Science Department of the University of Rome "La Sapienza", as a Research Associate. He is also a Research Fellow of the "Scuola Normale Superiore di Pisa". He got his Ph.D. in Theoretical Computer Science at the "Computer and Information Sciences Department" of the University of Delaware, USA. He got his Ph.D. in Mathematics (spec. Mathematical Logic and Theoretical Computer Science) at the Mathematics Department of the University of Siena. His research interests include Mathematical independence results, proof theory, ordinal analysis and Recursion-theoretic learning theory.