Paul Shafer (University of Leeds)

When:
November 10, 2020 @ 11:00 am – 12:00 pm
2020-11-10T11:00:00-10:00
2020-11-10T12:00:00-10:00

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

Abstract
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.