Monday, October 14, 2013, 16.30
Seminar room 0.011, Mathematical Institute, University of Bonn
Speaker: Andre Nies (University of Auckland)
Title: Algorithmic randomness connects to set theory
Abstract: We discuss two connections between algorithmic randomness and set theory. The first direction replaces algorithmic tools such as test definitions by tools from effective descriptive set theory in order to obtain “higher” randomness notions. This goes back to Martin-Loef (1970) and was recently developed by Hjorth and Nies (2007), Chitat Chong and Yu Liang, and Greenberg and Monin. Their recent result is that the Borel complexity of the largest Pi-1-1 null set (first described by Kechris 1975) is exactly (boldface) Pi-0-3. The second direction finds analogs of cardinal invariants of the continuum in the realm of highness properties that indicate strength of a Turing oracle A. For instance, the bounding number corresponds to A computing a function that dominates all computable functions. This was first observed by N. Rupprecht (2010). Recent work of Brendle, Brooke-Taylor, Ng and Nies studied the full analog of the so-called Cichon diagram of cardinal invariants.