Colloqiuim- Computable Mathematics and Reverse Mathematics

Title: Computable Mathematics and Reverse Mathematics

https://math.uchicago.edu/~drh/

Date and Time: Friday November 9, 2:00-3:00pm
Place: Rome 206

Abstract : Every mathematician knows that if 2+2=5 then Bertrand Russell is the pope. Russell is credited with having given a proof of 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 well-established 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 the close connection between computability and definability yields a fruitful interplay between them.

Short Bio: Denis Hirschfeldt is a Professor of Mathematics at the University of Chicago. His research is in computability theory, especially computable  mathematics, reverse mathematics, and algorithmic randomness. Among other works, he is the author of two books, Algorithmic Randomness and Complexity (with Rod Downey) and Slicing the Truth. His 1999 PhD dissertation, written at Cornell under the supervision of Richard Shore, received the Sacks Prize of the Association for Symbolic Logic for most outstanding doctoral dissertation in mathematical logic. He is also a two-time winner of the ASL's Shoenfield Prize for outstanding expository writing in the field of logic.