Patrick Lutz (UC Berkeley)

September 1, 2020 @ 10:00 am – 11:00 am

Title: Part 1 of Martin’s Conjecture for Order Preserving Functions
by Patrick Lutz (UC Berkeley) as part of Computability theory and applications

Martin’s conjecture is an attempt to make precise the idea that the only natural functions on the Turing degrees are the constant functions, the identity, and transfinite iterates of the Turing jump. The conjecture is typically divided into two parts. Very roughly, the first part states that every natural function on the Turing degrees is either eventually constant or eventually increasing and the second part states that the natural functions which are increasing form a well-order under eventual domination, where the successor operation in this well-order is the Turing jump.

In the 1980′s, Slaman and Steel proved that the second part of Martin’s conjecture holds for order-preserving Borel functions. In joint work with Benny Siskind, we prove the complementary result that (assuming analytic determinacy) the first part of the conjecture also holds for order-preserving Borel functions (and under AD, for all order-preserving functions). Our methods also yield several other new results, including an equivalence between the first part of Martin’s conjecture and a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees.

In my talk, I will give an overview of Martin’s conjecture and then describe our new results.