Randomness notions and reverse mathematics

Journal of Symbolic Logic 85 (1):271-299 (2020)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 93,745

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Schnorr randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Luzin’s (n) and randomness reflection.Arno Pauly, Linda Westrick & Liang Yu - 2022 - Journal of Symbolic Logic 87 (2):802-828.
Shift-complex sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.


Added to PP

23 (#160,613)

6 months
9 (#1,260,759)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.

View all 11 references / Add more references