I MERCOLEDì DEL DIMI

SEMINARIO

How can one sort mathematical theorems

Vasco Brattka

Universitat der Bundeswehr di Monaco

Abstract
It is common mathematical practice to say that one theorem implies another one. For instance, it is mathematical folklore that the Baire Category Theorem implies the Closed Graph Theorem and Banach's Inverse Mapping Theorem. However, after a bit of reflection it becomes clear that this notion of implication cannot be the usual logical implication that we teach to our undergraduate students, since all true theorems are logically equivalent to each other. What is actually meant by implication in this informal sense is rather something such as "one theorem is easily derivable from another one". However, what does "easily derivable" mean exactly? We present a survey on a recent computational approach to metamathematics that provides a formal definition of what "easily derivable" could mean. This approach borrows ideas from theoretical computer science, in particular the notion of a reducibility. The basic idea is that Theorem A is easily derivable from Theorem B if A is reducible to B in the sense that the input and output data of these theorems can be transferred into each other. In this case the task of Theorem A can be reduced to the task of Theorem B. Such reductions should at least be continuous and they are typically considered to be computable, which means that they can be performed algorithmically.The resulting structure is a lattice that allows one to sort mathematical theorems according to their computational content and phenomenologically, the emerging picture is very much in line with how mathematicians actually use the notion of implication in their daily practice.