The Solecki dichotomy and the Posner Robinson theorem

Abstract: 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, and vice-versa.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic