Midwest Computability Seminar

Part ii

The Midwest Computability Seminar is meeting remotely in the fall of 2020. The recurring Zoom link is:


Meeting ID: 997 5433 2165

Passcode: midwest

Slides    YouTube video    Panopto video

This session will be held jointly with the Computability Theory and Applications Online Seminar.

: Tuesday, September 1st, 2020

TIME: 3:00 - 4:00 PM CDT

SPEAKER: Patrick Lutz - University of California, Berkeley

Part 1 of Martin's Conjecture for Order Preserving Functions

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.

Past and Future Sessions

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.