Logic Seminar

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.