AVVISO SEMINARIO DIP. INFORMATICA - SAPIENZA

Date: Monday, November 12, 2007
Time: 3:00pm
Duration: about 60 min.
Venue: DI, Via Salaria 113, third floor, Seminari Lecture Room
Speaker: Lorenzo Carlucci
Title: Unprovability after Goedel

ABSTRACT
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.

BIOGRAPHICAL SKETCH
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.
http://www.cis.udel.edu/~carlucci/