Denis Hirschfeldt, University of Chicago
"Computable Mathematics and Reverse Mathematics"
Every mathematician knows that if 2+2=5 then Bertrand Russell is the pope. Russell is credited with having given a proof of that fact in a lecture, though from the point of view of classical logic, no such proof is needed, since a false statement implies every statement. Contrapositively, every statement implies a given true statement. But we are often interested in questions of implication and nonimplication between true statements. We have all heard and said things like ”Theorems A and B are equivalent,” or ”Theorem C does not just follow from Theorem D.” There is also a wellestablished practice of showing that a given theorem can be proved without using certain methods. These are often crucial things to understand about an area of mathematics, and can also help us make connections between different areas.
Computability theory and proof theory can both be used to analyze, and hence compare, the strength of theorems and constructions. For example, when we have a principle such as ”Every infinite binary tree has an infinite path”, we can ask how difficult it is to compute such a path from a given tree. We can also ask how much axiomatic power is necessary to prove that this principle holds. The first kind of question leads to the program of Computable Mathematics. One version of the second kind of question leads to the program of Reverse Mathematics. I will give an introduction to these research programs, and discuss how close connection between computability and definability yields a fruitful interplay between them.
Please note room - MC 4060.
Refreshments will be served in MC 5158B at 3:30pm.
All are welcome!