# 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).