Oliver Club

Matthew Harrison-TrainorUniversity of Michigan
Measuring complexity with computability and topology

Tuesday, November 1, 2022 - 4:00pm
Malott 532 (Lounge)

Abstract: All mathematicians know informally that some mathematical objects, constructions, and classifications are more complicated than others. Methods of mathematical logic allow us to measure this complexity formally, for example proving that a given characterization is as good as possible. To do this, we must deal with presentations: copies of objects whose domain is some fixed countable set, such as the natural numbers. From a computability-theoretic perspective, a presentation is an encoding of the object in an infinite string which can be fed into a computer program as input, and we measure complexity using computational hierarchies. From a topological (descriptive-set-theoretic) perspective, a presentation is a point in a Polish space, and we measure complexity using hierarchies such as the Borel hierarchy. These two perspectives are highly intertwined. In this talk, I will describe the general program with some examples, followed by highlighting particular ways in which each of the two perspectives informs the other.

Refreshments will be served at 3:30 PM