Computability, Reverse Mathematics and Combinatorics (08w5019)
Organizers
Peter Cholak (University of Notre Dame)
Barbara Csima (University of Waterloo)
Steffen Lempp (University of Wisconsin - Madison)
Manuel Lerman (University of Connecticut-Storrs)
Richard Shore (Cornell University)
Theodore Slaman (University of California, Berkeley)
Description
Reverse Mathematics or How Much Coffee?
What does it take to prove a mathematical theorem? The itinerant and eccentric
mathematician Paul Erdos, famous as both a solver and poser of problems,
used to say that a mathematician is a machine for turning coffee into
theorems. The task of this workshop is to figure out how much coffee do we
really need. How hard is it to prove specific mathematical theorems? Hard, not
actually in the sense of the numbers of hours of effort or the amount of
caffeine consumed, but in the mathematical sense of what assumptions (axioms)
are needed. The familiar paradigm from high school geometry is to start with a
list of axioms and prove theorems. We textquotedblleft
reversetextquotedblright the process. If we can omit some of the axioms and
assume instead the textquotedblleft theoremtextquotedblright and then prove
the axioms left out then they were really needed.
Perhaps surprisingly, this measure of axiomatic strength is not only of
philosophical and methodological interest but is also intimately related to
the computational complexity of the problem at hand. If the existence of some
function is textquotedblleft hard to provetextquotedblright then the function is
textquotedblleft hard to compute" and vice versa. Thus our work at times
shows that problems cannot be solved by computer algorithms even with various
additional information. They also at times point to the additional information
needed to solve the problem. In the other direction, we are at times driven to
produce proofs that use weaker axioms than had previously been used. These
proofs generally give sharper computational information as well.
The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).
