Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T09:26:53.019Z Has data issue: false hasContentIssue false

RANDOMNESS NOTIONS AND REVERSE MATHEMATICS

Published online by Cambridge University Press:  09 September 2019

ANDRÉ NIES
Affiliation:
SCHOOL OF COMPUTER SCIENCE UNIVERSITY OF AUCKLAND PRIVATE BAG92019AUCKLAND, NEW ZEALAND E-mail: andre@cs.auckland.ac.nzURL: https://www.cs.auckland.ac.nz/~nies/
PAUL SHAFER
Affiliation:
SCHOOL OF MATHEMATICS UNIVERSITY OF LEEDS LEEDS, LS2 9JT, UK E-mail: p.e.shafer@leeds.ac.ukURL: http://www1.maths.leeds.ac.uk/~matpsh/
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2019