Paul Shafer (University of Leeds)

November 10, 2020 @ 11:00 am – 12:00 pm

Title: Randomness notions and reverse mathematics
by Paul Shafer (University of Leeds) as part of Computability theory and applications

There are many notions of algorithmic randomness in addition to classic Martin-Löf randomness, such as 2-randomness, weak 2-randomness, computable randomness, and Schnorr randomness. For each notion of randomness, we consider the statement “For every set Z, there is a set X that is random relative to Z” as a set-existence principle in second-order arithmetic, and we compare the strengths of these principles. We also show that a well-known characterization of 2-randomness in terms of incompressibility can be proved in RCA_0, which is non-trivial because it requires avoiding the use of $Sigma^0_2$ bounding.