Logic Seminar

The goal of this talk is to introduce a notion of hyperfiniteness for Borel partial orders, which was recently defined by Matthew Harrison-Trainor and myself as part of ongoing work. We were motivated to formulate this definition by a question about Turing reducibility. In particular, it turned out that this question is essentially equivalent to asking whether strict Turing reducibility is hyperfinite. I will introduce our notion of hyperfiniteness, discuss some of its basic properties, and then explain a general criterion which implies that a Borel partial order is not hyperfinite. Along the way, I will explain the answer to the question about Turing reducibility that was our original motivation for this work. I will also mention some open questions about hyperfinite Borel partial orders.