Computability Learning Seminar

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

"Borel Reducibility and Linear Orderings"

We define Borel reducibility introduced by Friedman and Stanley between classes of countable structures. We will define what it means for a class of structures to be complete with respect to Borel reducibility and then we will go through their proof of the fact that the class of countable linear orderings is complete with respect to Borel reducibility.

MC 5413