Logic Seminar

Please note that the time is PST

The Solecki dichotomy in descriptive set theory, roughly stated, says that every Borel function on the real numbers is either a countable union of partial continuous functions or at least as complicated as the Turing jump. The Posner-Robinson theorem in computability theory, again roughly stated, says that every non-computable real looks like 0' relative to some oracle. Superficially, these theorems look similar: both roughly say that some object is either simple or as complicated as the jump. However, it is not immediately apparent whether this similarity is more than superficial. If nothing else, the Solecki dichotomy is about third order objects—functions on the real numbers—while the Posner-Robinson theorem is about second order objects—individual real numbers. We will show that there is a genuine mathematical connection between the two theorems by showing that the Posner-Robinson theorem plus determinacy can be used to give a short proof of a slightly weakened version of the Solecki dichotomy. We will explain the idea of this proof and then discuss its connections to some questions about well-foundedness of various reducibility notions on functions.