(panoramic photo of Moscow from moscow.photobase.ru)
Eighth International Conference on Computability, Complexity and Randomness (CCR 2013)
September 23–27, 2013, Moscow, Russia
Classifying principles by the no randomized algorithm property
A principle P studied in reverse mathematics has the no randomized algorithm
(NRA) property if when picking a sequence of X_i at random, and considering the
omega-model M consisting of the reals which are computable from some nite join of the
X_i, then the probability that M is a model of P is zero.
We provide a classication of every principle of the current reverse mathematics
zoo in terms of the NRA property by providing proofs of NRA property for very
weak principles in the zoo. This provides easy separation results like rainbow Ramsey
theorem for pairs (RRT22)) implies neither the stable version of thin set for pairs (STS(2))
nor the stable version of Erd}os Moser theorem (SEM).