Speaker:  Lorenzo Carlucci

evento esterno  
Quando:  12/11/2007  14:00


Dove:  Dipartimento Informatica  Via Salaria 113  third floor  Seminari Lecture Room


Abstract
Since Goedel's famous discovery of the existence of an undecidable sentence in (firstorder) Peano Arithmetic in 1931, the relevance of the incompleteness phenomena for socalled "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 settheory. 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 