Caltech Logo

Logic Seminar

Wednesday, November 3, 2021
12:00pm to 1:00pm
Add to Cal
Online Event
Embedding Borel quasi-orders into the Turing degrees
Patrick Lutz, Department of Mathematics, UCLA,

Which Borel quasi-orders are Borel reducible to Turing reducibility? In any such quasi-order, every element must have at most countably many predecessors (in which case we say the quasi-order is locally countable), but are there any other restrictions? It turns out that there are. It follows from recent work by Siskind and me that not every locally countable Borel quasi-order is Borel reducible to Turing reducibility. A more careful analysis shows that even fairly simple quasi-orders are not always reducible to Turing reducibility. I will discuss a few such examples as well as the broader context for this question. This talk contains joint work with Benjamin Siskind and Kojiro Higuchi.

For more information, please email A. Kechris at kechris@caltech.edu.